Войти
ПрограммированиеФорумГрафика

Проблема с усечением Frustum области другим Frustumом (6 стр)

Страницы: 13 4 5 6 7 8 Следующая »
#75
(Правка: 8:11) 8:10, 6 фев. 2021

Aslan
> Вычислять пересечение секторов же просто
Не совсем понял о чем ты.
Вообще, объединение стен порталов которые смотрят в одинаковый сектор в один фрустум это необходимая мера и после объединения фрустум становится не выпуклым и с большим количеством стен. Если стены не объединять,  тогда алгоритм зависает когда через один фрустум видно второй от того же сектора...и оба фрустума как видимые друг другу начинают добавлять друг друга в очередь обработки. Может быть попозже я попробую разобраться в этой проблеме


#76
(Правка: 19:39) 19:35, 6 фев. 2021

m210
Да,я неточно выразился. Фрустум в 2.5D - это сектор бесконечной окружности, а не сектор карты (область с постоянной высотой)

Портал же задается двумя точками: левый и правый край, так?
Фрустум - сектор бесконечной окружности с вершиной в игроке и крайними лучами, проходящими через края портала. Что же тт сложного построить пересечение?

#77
(Правка: 18:35) 18:33, 7 фев. 2021

Aslan
> Портал же задается двумя точками: левый и правый край, так?
Левый, правый, верхний, нижний - 4 плоскости дают фрустум.

Если бы я решал задачу в 2D, я бы и не создал эту тему.
>Что же тт сложного построить пересечение?
Ничего, в конце концов то, что ты спрашиваешь, все я описал в самом первом посте.

#78
14:25, 9 фев. 2021

Раскрываю секрет фирмы, как делаются порталы.

Входные данные:
1) Портал определенный 3-мя или более точками.
2) Плоскости отсечения, извлеченные из PerspectiveView матрицы
3) Точка расположения камеры

Шаги:
1) Сортируем точки так, чтобы в массиве точки шли по порядку и соответствовали порядку граней
2) Боковыми плоскостями делаем отсечение граней портала. И на пересечении грани и боковой плоскости рождаем новые точки. В движке Q3 это делает функция ClipWindingEpsilon например. В результате получаем набор точек, а вместе с ним и новый набор усеченных граней портала.
3) Из граней полученных на пред. шаге делаем и точки камеры - делаем новые боковые плоскости отсечения (точка камеры + 2 точки грани = 3 точки, что есть достаточно для создания вектора плоскости)
4) Плоскость портала становится новой передней плоскостью отсечения, заднюю плоскость оставляем без изменений
5) Плоскостями из пунктов 3 и 4 отсекам объекты за порталом. При нахождении нового портала переходим к пункту 1

#79
15:31, 9 фев. 2021

m210
>> Портал же задается двумя точками: левый и правый край, так?
> Левый, правый, верхний, нижний - 4 плоскости дают фрустум
Если две вертикальные и две горизонтальные плоскости, то опять сводится к 2D: брать min/max из dy/dx. Если же произвольные плоскости, то брать max left/ min right для каждой сканлинии, как в Лабиринтах Хулиона

#80
18:56, 9 фев. 2021

Aslan
Я так до сих пор и не понимаю, как ты в 2D собрался отсекать точки, нахоядиещся выше или ниже камеры?

И видимо зря я скрываю картинки под спойлеры, их никто не видит :(

Вот типичное место с ограничением по видимости:
2 | Проблема с усечением Frustum области другим Frustumом
Вот так оно выглядит без текстур, где видно, какие сектора рисуются (за пределами видимости)
1 | Проблема с усечением Frustum области другим Frustumом
Вот таже самая картина в 2D, где четко видно, в в случае 2D в массив видимости попадет куча всего лишнего (и там могло быть еще пол-карты за кадром)
3 | Проблема с усечением Frustum области другим Frustumом

На втором скриншоте я выделил зеленым цветом предполагаемый AABB, который строится через первый портал, построенный портал выглядит как то так:
4 | Проблема с усечением Frustum области другим Frustumом

Ну и вид со стороны, где четко видно, куда направлены верхняя и нижняя граница фрустума
5 | Проблема с усечением Frustum области другим Frustumом

А вот тут тот же самый портал с другого ракурса, где видно проблему - в такой фрустум попадает слишком много лишнего, но тут уже ничего не поделаешь....хотя идеи все  еще появляются, обычно упираюсь либо в дыры, либо в зависание алгоритма-обходчика стен.
6 | Проблема с усечением Frustum области другим Frustumом

#81
19:04, 9 фев. 2021

Deamon
Спасибо за ответ, поизучаю немного, но я это все уже проделал, за исключением ближней и дальной плоскости - бесполезные абсолютно :)

Проблема то не в том, чтобы построить портал, а в том, чтобы соединить все стены смотрящие в один и тот же сектор в один фрустум (ну или несколько маленьких, если стены не имеют общей точки соединения)

Вот например как тут:
Камера смотрит в пол, находится в одном секторе, а все 4 стены, которые окружают сектор - смотрят в другой сектор

7 | Проблема с усечением Frustum области другим Frustumом

Вот так это выглядит сверху:

8 | Проблема с усечением Frustum области другим Frustumом

В этом случае - в 2D получается угол обзора 360 градусов, верхнюю и нижнюю плоскость тут невозможно построить впринципе...но если сделать из этих 4х стен AABB, после проверки все AABB соединяться в один большой AABB который будет имееть координаты 0,0,screenwidth, screenheight, и построенный через эти точки фрустум будет совпадать с фрустумом камеры...и генеально и просто :)
Т.е. во всем универсальный алгоритм, который имеет конскую погрешность в случаях, если смотреть на стены под углом

#82
19:32, 10 фев. 2021

m210
Пирамида, с вершиной в камере и онованием в портале в проеции на горизонтальную и вертикальную плоскость - два луча, последнем случае брать min/max от к-та наклона луча dz/dx чтобы посчитать пересечение двух порталов или портала и камеры, камера тоже с вертикальной Oy и ограниченным наклоном, можно задать фрустум как портал
У меня же идея как рендерить рэйкастом

#83
6:13, 11 фев. 2021

Aslan
> в проеции на горизонтальную и вертикальную плоскость - два луча, последнем
> случае брать min/max от к-та наклона луча dz/dx
Это надо обдумать, но опять же, в 3D нет вертикальной плоскости, там их как минимум две, и поэтому я и написал в самом первом посте - пока смотришь на такой фрустум на стену, которая идет вдоль оси X, то все нормально, а когда разворачиваешь камеру на стену вдоль Y, то все становится плохо. Можно попробовать брать вертикальную плоскость вдоль направлении камеры, но не знаю... Мне кажется, получится тоже самое, что и во всех 100 других попытках сделать правильно :)
Aslan
> меня же идея как рендерить рэйкастом
Это в 10 раз медленнее, проверено. Для более менее быстрого алгоритма, нужно сортировать точки стен по углу, т. е вызывать atan2, который писец какой медленный... Ну или без сортировки запускать 1000 лучей и получать явные дыры, потому что 1000 лучей не хватает тэи даже при этом количестве все тормозит))

#84
7:47, 11 фев. 2021

m210
> Для более менее быстрого алгоритма, нужно сортировать точки стен по углу, т. е вызывать atan2, который писец какой медленный...
Для того, чтобы сортировать точки по углу, atan2 не нужен.
Даже без деления, в принципе, можно обойтись (правда, не факт, что будет быстрее).

#85
9:41, 11 фев. 2021

}:+()___ [Smile]
> Даже без деления, в принципе, можно обойтись (правда, не факт, что будет
> быстрее).
Расскажи как, я проверю, быстрее или нет :)

Вот кусок кода рейкаста

Segment segment = segments.get(i);
      segment.p1.angle = (float) Math.atan2((segment.p1.y - globalposy), (segment.p1.x - globalposx));
      segment.p2.angle = (float) Math.atan2((segment.p2.y - globalposy), (segment.p2.x - globalposx));

      double dAngle = (segment.p2.angle - segment.p1.angle);

      if ((dAngle <= -(Math.PI)))
        dAngle += (2 * Math.PI);

      if ((dAngle > Math.PI))
        dAngle -= (2 * Math.PI);

      segment.p1.begin = (dAngle > 0.0);
      segment.p2.begin = !(segment.p1.begin);

Смысл такой, что по отсортированным точкам можно определить, какой сегмент перекрывает стоящий рядом при прохождении луча от 0 до 360 гр.

#86
11:25, 11 фев. 2021

m210
> Расскажи как, я проверю, быстрее или нет :)
Сортировать \(x_i\in[0..1]\) — это то же самое, что сортировать \(\sqrt x_i\), \(x_i^2\), \(x_i‎^{3.21}\), \(\sin x_i\) и т. п.
Соответственно, atan2 можно заменить вычислительно более простой функцией, сортировка по которой которой даст тот же результат (хинт: отношение двух координат с подходящим знаком + номер квадранта). Более того, чтобы сравнить два угла, совершенно не обязательно эти углы находить, достаточно посмотреть знаки векторных произведений (избавляемся от делений ценой усложнения функции сравнения).

> if ((dAngle <= -(Math.PI))) dAngle += (2 * Math.PI);
Для операций с углами идеально подходит wrap-around арифметика целых чисел (uint32 и т. п.), не в курсе, есть ли в этом языке их поддержка.

#87
(Правка: 16:27) 13:24, 11 фев. 2021

m210
> Это в 10 раз медленнее, проверено. Для более менее быстрого алгоритма, нужно сортировать точки стен по углу, т. е вызывать atan2, который писец какой медленный...
это твоя реализация писец, вектора сравниваются псевдовекторным произведением
Чтобы утверждать что чтото в 10 раз медленнее, надо уметь нормально реализовать

> Расскажи как, я проверю, быстрее или нет :)

// Знак числа: 
// <0: -1
// 0: 0
//>0: 1
int sgn(float x) { return ((x>0)-(x<0)); }

// нетранзитивное сравнение, не годится для сортировки
// Пример: три точки в вершинах равностороннего треугольника с центром в нач коорд
// каждый вектор левее соседа справа так по кругу
int cmp1(const vec2& v1,const vec2& v2) { return sgn(v1.x*v2.y-v1.y*v2.x); }

// транзитивное сравнение, годится для сортировки, возвращает знак, -1 - меньше,0-равно,1-больше
// выбираем некоторый вектор v0, считаем те что слева от него < тех что справа
// которые с одной стороны сравниваем по cmp1
int cmp2(const vec2& v1,const vec2& v2) { 
  int l1=cmp1(v1,v0),l2=cmp1(v2,v0);
  if(l1!=l2) return sgn(l1-l2);
  return cmp1(v1,v2);
 }

UPD. Это для общего случая произвольных векторов,
НО тебе нужны лишь вершины, попадающие во фрустум, т.е. лежащие в секторе окружности с углом<180 с центром в камере, для них cmp1 транзитивно, всего 2 умножения на сравнение

> в 3D нет вертикальной плоскости, там их как минимум две
В Duke ограниченный наклон с искажением, скошенный фрустум, передняя грань и боковины остаются вертикальными

#88
(Правка: 8:00) 7:57, 12 фев. 2021

Aslan
> это твоя реализация писец, вектора сравниваются псевдовекторным произведением
> Чтобы утверждать что чтото в 10 раз медленнее, надо уметь нормально реализовать
Когда твой код будет выполняться за 0.1мс на Селероне, тогда и поговорим :)

Да и не знал, что топографическая сортировка может быть быстрее, чем пара операций cross и dot продуктов)))) Еще раз повторюсь, рейкаст не очень то подходит для определения видимости, есть более быстрые решения...в данном случае даже мое, которое умеет обрабатывать 10000 порталов за намного короткое время. И именно поэтому я использую рейкаст постобработкой, когда порталов становится 50-100, тогда рейкаст уже не несет такой ощутимой нагрузки.

Aslan
>В Duke ограниченный наклон с искажением, скошенный фрустум, передняя грань и боковины остаются вертикальными

Спасибо, я в курсе...но вот проблема - я пишу новый 3D рендер с freelookом, он 3D, у меня 3 плоскости а не 2 (наверно уже в 4й раз пишу) и мне абсолютно не важно, что там было реализовано в 90е....сейчас 2021год.

Но спасибо за методы, оставлю их на потом.

#89
(Правка: 17:42) 17:39, 12 фев. 2021

m210
> Когда твой код будет выполняться за 0.1мс на Селероне, тогда и поговорим :)
Рендер или что? 1000 fps крутовато даже для простой заливки экрана
У тебя портал - любая открытая линия между секторами?
Есть демка погонять?

> я пишу новый 3D рендер с freelookом
Честная проекция нарушает вертикальность порталов, но не влияет на их перекрытие, в результате пересечения двух проекций прямогольников - опять проекция прямоугольника, надо только разобраться с геометрией

Страницы: 13 4 5 6 7 8 Следующая »
ПрограммированиеФорумГрафика