Самый эффективный алгоритм на уровне сетки, оптимальный выбор окклюзии

Question

Я новичок в отбраковке. На первый взгляд кажется, что большинство алгоритмов отбраковки окклюзии являются объектными, а не проверяют отдельные сетки, что было бы полезно для рендеринга игры.

То, что я ищу, - это алгоритм, который отбирает все сетки в пределах одного объекта, которые закрыты для данной точки обзора, с высокой точностью. Оно должно быть не менее O (n log n) , наивное сравнение по сеткам ( O (n ^ 2) ) слишком медленное.

Я заметил, что графический интерфейс Blender идентифицирует закрытые сетки для вас в режиме реального времени, даже если вы работаете с большими объектами с более чем 10000 сетками. Какой алгоритм там используется, скажите, пожалуйста?

Answer 1

Blender выполняет выборку усеченного вида и выборку окклюзии на основе динамических структур ускорения дерева AABB из библиотеки физики Bullet. Окклюдеры и объекты представлены их ограничивающим объемом (ограничивающим прямоугольником, выровненным по оси).

Просмотр отбраковки усеченного прохода по дереву AABB с учетом усеченности камеры.

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

См. Также документацию http://wiki.blender.org/index.php/Dev:Ref/Release_Notes/2.49/Game_Engine#Performance

Реализация Blender из исходного дерева Blender: метод blender \ source \ gameengine \ Physics \ Bullet \ CcdPhysicsEnvironment.cpp bool CcdPhysicsEnvironment :: cullingTest (обратный вызов PHY_CullingCallback, void * userData, PHY__Vector4 * плоскости, int nplanes, int occlusionRes)

и Bullet Physics SDK содержит пример кода C ++ в Bullet / Extras / CDTestFramework.

Answer 2

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

Если вам действительно нужно отбраковать на уровне меша, то вы можете создать один объект на сетку, а затем создать групповой объект, содержащий меш-объекты. Имейте в виду, что вы можете фактически потерять производительность, поскольку отбраковка на уровне меша обычно не стоит того; это может нарушить поток передачи данных на оборудование.

Answer 3

Вы смотрели на такие вещи, как Октри ?

Answer 4

Я попробовал наивный подход , который был достаточно быстрым для моего приложения.

Для каждого треугольника в сетке проверьте, не перекрыт ли какой-либо другой треугольник в сетке, таким образом O (n2) . (Я получил результаты с высокой точностью только из-за проверки, была ли закрыта центральная точка каждого треугольника или нет, хотя вам следует хотя бы проверить вершины углов треугольника, если точность важна).

На компьютере с процессором Pentium 4 (c ++) двоичный объект STL из ~ 10000 треугольников занял около 1 минуты, чтобы завершить .

Алгоритм можно оптимизировать до ~ 40 процентов, сначала отсортировав треугольники, например, по размеру области или расстоянию от точки обзора (с большей вероятностью, чтобы перекрыть, поэтому вы можете пропустить больше проверок).

Следующим шагом оптимизации будет размещение треугольников в октрое, что должно значительно сократить количество проверок окклюзии.

Answer 5

Обычно первое, что вы делаете, это проверяете, нет ли у мешей шансов перекрыть друг друга. Часто с простым ограничивающим примитивом (ограничивающие рамки или ограничивающие сферы). Если я правильно помню, Octrees поможет с этим.