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

Quadtree mesh и корректный frustum culling (2 стр)

Страницы: 1 2 3 4 5 6 7 Следующая »
#15
(Правка: 4:02) 4:00, 16 сен 2022

единственно правильный тест — это https://en.wikipedia.org/wiki/Hyperplane_separation_theorem

то есть любой правильный код, который перебирает что-то проверками для случая AABB vs frustum должен содержать 5 проверок на плоскости фрастума, 3 проверки на плоскости AABB, и 6*3=18 проверок на разделяющие плоскости, образованные рёбрами. количество проверок можно уменьшить, если использовать более продвинутые непереборные алгоритмы по типу GJK, но если алгоритм просто перебирает все условия, то условий для точного теста должно быть именно 26.

однако, для практических соображений часто оказывается быстрее сделать меньше проверок, так как это дешевле, даже если придётся порендерить чуть больше объектов чем нужно.

#16
7:00, 16 сен 2022

Suslik
Конкретно случай фрустума+бокса можно решить методом линейного программирования.
Дано: множество ограничивающих плоскостей \(a_i x + b_i y + c_i z \geqslant d_i\).
Оптимизируем \(\min \Delta\),
при ограничениях \(a_i x + b_i y + c_i z + \Delta \geqslant d_i\).
Например, симплекс-методом.
\(\min \Delta > 0\) тогда и только тогда, когда изначальное множество плоскостей образует непустое невырожденное пересечение.
Бесполезный бонус - если \((a_i,b_i,c_i)\) будут нормализованными, то симплекс-метод на этой проблеме сразу заодно даст и \((x,y,z)\) точки, наиболее удалённой от всех плоскостей; а \(\min \Delta\) - глубину, на которой эта точка лежит.

#17
(Правка: 7:43) 7:41, 16 сен 2022

Имбирная Ведьмочка
> Например, симплекс-методом.
симплекс-метод в collision detection'е называется hill climbing и я его включил в класс методов, которые оптимизируют SAT. к сожалению, для суммы минковского он реализуется не так-то просто, потому что никто не будет считать в явном виде грани получившегося многогранника (это медленно), приходится это делать неявно и это не особо просто. "не просто" здесь следует читать как "эффективнее будет частично перебрать и смириться с false positive случаями".

#18
(Правка: 8:48) 8:43, 16 сен 2022

Suslik
> симплекс-метод в collision detection'е называется hill climbing и я его включил
> в класс методов, которые оптимизируют SAT.
Мне кажется, мы говорим о разных методах.
То, о чём говорю я - это именно линейная оптимизация. https://en.wikipedia.org/wiki/Simplex_algorithm
Задача алгоритма, в общем виде - найти вектор-аргумент x, минимизирующий линейную форму \(\mathbf{c}^T \mathbf{x}\), и при этом не нарушающий линейную систему неравенств \(\mathbf{A} \mathbf{x} \leqslant \mathbf{b}\). Это чисто алгебраический метод, работающий с векторами и матрицами произвольной размерности.
Мы можем геометрическую задачу (модифицированную с дельтой) представить в виде вот такой алгебраической, и пустить её на обобщённый алгебраический солвер - и он выдаст оптимум.

Особенности:
- Этот метод сработает только для выпуклых полигональных коллайдеров - боксы и фрустумы пойдут без проблем, а вот для всяких шариков и капсул метод уже неприменим - ибо их невозможно представить в виде линейных неравенств.
- Он не использует разность Минковского. В частности, полученная точка оптимума - это именно геометрическая точка в глобальных координатах.
- Он не строит никаких промежуточных осей или плоскостей, во всяком случае, не в явном виде и не в оригинальном 3-мерном геометрическом пространстве.

Если и визуализировать его работу геометрически, то она будет выглядеть примерно так.
Каждое неравенство в условиях - это гипер-плоскость в пространстве \((x,y,z,\Delta)\). Пересечение положительных сторон этих плоскостей - это выпуклый многогранник.
Симплекс-алгоритм, который оптимизирует - берёт точку внутри этого многогранника и итеративно двигает её в сторону улучшения целевой функции.
Начальная точка обязательно должна быть внутри допустимой области (в частном случае для решения коллизий - такую точку найти несложно).
На первой итерации - алгоритм спускает её прямо в сторону градиента целевой функции, пока не упрётся в границу многогранника. На следующей - поедет вдоль грани, в сторону проекции градиента на эту грань, пока не упрётся в следующую грань. Если прогресс возможен только вдоль ребра - поедет вдоль ребра.
И так он и будет переходить по рёбрам и граням гипер-многогранника, пока на упрётся в самый минимум - локальный оптимум, а в силу выпуклости многогранника (по построению), он же будет и глобальным оптимумом - ответом на задачу оптимизации.

#19
(Правка: 11:21) 11:20, 16 сен 2022

Имбирная Ведьмочка
> Задача алгоритма, в общем виде - найти вектор-аргумент x, минимизирующий линейную форму cTx, и при этом не нарушающий линейную систему неравенств Ax⩽b. Это чисто алгебраический метод, работающий с векторами и матрицами
да, просто симплекс-метод, решающий эту задачу, гуляет по рёбрам образованного симплекса, потому что можно доказать, что решением будет одна из его вершин. поэтому он типа градиентным спуском идёт по рёбрам, пока не найдёт экстремальную вершину.

так вот hill climbing в CD делает то же самое — гуляет по рёбрам разницы минковского до тех пор, пока не найдёт самую близкую к началу координат вершину. вершина должна быть самая близкая к точке (началу координат) это не совсем эквивалентная линейному программированию задача, но решается примерно одинаково.

#20
(Правка: 12:38) 12:31, 16 сен 2022

Можно ещё просто тупо проверять по расстоянию от камеры минус радиус и если оно больше дальности видимости, отбраковывать.

#21
12:47, 16 сен 2022

Kripto289
Вот тебе идея на миллион - представь свой фрустум в виде нескольких шариков(можно эллипсойдов, колбасок - вообщем по вкусу) и кулль относительно них.

#22
13:39, 16 сен 2022

Battle Angel Alita
> Вот тебе идея на миллион - представь свой фрустум в виде нескольких
> шариков(можно эллипсойдов, колбасок - вообщем по вкусу) и кулль относительно
> них.
Я пробовал вместо фрустума использовать конус и пересекать его с боксом. Но максимум нашёл формулу пересечения конуса и сферы. И в целом это вроде работало, но корявенько :)

Ivashka
> Можно ещё просто тупо проверять по расстоянию от камеры минус радиус и если оно
> больше дальности видимости, отбраковывать.
Не помню упоминал или нет, но я использую quad tree для генерации меша океана, то есть начальные уровни почти всегда будут пересекать камеру, но нужно отсекать уже средние уровни, где как раз расстояние от камеры будет меньше дальности видимости, но во фрустум может не попасть.

Но да, про оптимизацию сферами я видел много упоминаний. Буду использовать эту идею для других мешей (например рек/озёр).

#23
14:15, 16 сен 2022

Kripto289
> то есть начальные уровни почти всегда будут пересекать камеру
Большие уровни же рисуются когда далеко от камеры, а если квад разбит на маленькие (в случае если близко к камере) то большие квады вообще не рисовать (проверка если квад разбит, то переходим к потомкам и уже их проверяем).

#24
15:14, 16 сен 2022

Ivashka
> Большие уровни же рисуются когда далеко от камеры, а если квад разбит на
> маленькие (в случае если близко к камере) то большие квады вообще не рисовать
> (проверка если квад разбит, то переходим к потомкам и уже их проверяем).
Я пока ещё не приступил к стадии "как правильно строить бесконечный quadtree для океана", но вроде он должен быть отцентрирован относительно камеры, как-то так?

+ Показать
#25
(Правка: 15:36) 15:35, 16 сен 2022

Kripto289
> но вроде он должен быть отцентрирован относительно камеры, как-то так?
если у тебя вода тупо плоскость, то сделай квад с нужной частотой трианглов (каждая пара - пиксель на экране или больше если не нужна сильная детализация) и проецируй его из screen_space в world_space, тогда и отсекать ничего не нужно будет.

#26
(Правка: 15:37) 15:36, 16 сен 2022

Kripto289
> Я пока ещё не приступил к стадии "как правильно строить бесконечный quadtree
> для океана", но вроде он должен быть отцентрирован относительно камеры, как-то
> так?
А океану точно нужен quad tree? Для конкретного случая нет более оптимального представления данных?
ну там держать константное количество вершин и двигать их через WorldPositionOffset образуя меш у которого
расстояние между вершинами зависит от удаленности от камеры, fov и угла к плоскости океана?
Aroch
> если у тебя вода тупо плоскость
У него не тупо плоскость. У него есть и волны и реки/озера на других высотах. Инфа 100.

#27
(Правка: 15:43) 15:42, 16 сен 2022

Aroch
> если у тебя вода тупо плоскость, то сделай квад с нужной частотой трианглов
> (каждая пара - пиксель на экране или больше если не нужна сильная детализация)
> и проецируй его из screen_space в world_space, тогда и отсекать ничего не нужно
> будет.
У этого метода сильный алиазинг. Там вроде ещё проблемы с сильными волнами, и надо растягивать меш, иначе дырки будут. В crysis 1 вроде пытались это юзать и плюнули.

Super_inoy
> ну там держать константное количество вершин и двигать их через
> WorldPositionOffset образуя меш у которого
> расстояние между вершинами зависит от удаленности от камеры, fov и угла к
> плоскости океана?
Почти так это щас и работает + тесселяция отсекает ненужные полигоны. Профитно.

Но я щас перешёл на стадию мобилок и тесселяция там дорогостоящая, дак ещё и из-за бага юнити не работает на вулкане. А на macos вообще тесселяцию не завезли и там софтварно тесселируют магией с compute shaders.

#28
(Правка: 15:42) 15:42, 16 сен 2022

Super_inoy
> У него не тупо плоскость. У него есть и волны и реки/озера на других высотах.
> Инфа 100.
на самом деле подойдет и для такого случая в том числе. Ты собственно про тоже самое ему говоришь

Вот https://rendermeapangolin.wordpress.com/2015/05/26/screen-space-grid/

#29
15:45, 16 сен 2022

Kripto289
> Но я щас перешёл на стадию мобилок и тесселяция там дорогостоящая, дак ещё и
> из-за бага юнити не работает на вулкане.
мне казалось что в первом кризисе, который 2007 года еще без тесселяции сделали тупо плоскость для океана с переменной плотностью(ближе к игроку плотнее),
в которой эта самая плотность никак не менялась(но двигалась с игроком) и у них прокатило. И был какой-то пейпер в котором они доказывали что так быстрее.
Ну да ладно, это оффтоп.

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