Самый эффективный алгоритм на уровне сетки, оптимальный выбор окклюзии?
Я новичок в отбраковке. На первый взгляд кажется, что большинство алгоритмов отбора окклюзии являются объектными, а не рассматривают отдельные сетки, что было бы полезно для рендеринга игр.
То, что я ищу, - это алгоритм, который отбирает все сетки внутри одного объекта, которые закрыты для данной точки зрения, с высокой точностью. Это должно быть по крайней мере O (n log n), наивное сравнение по сеткам (O (n ^ 2)) слишком медленное.
Я заметил, что графический интерфейс Blender идентифицирует закрытые сетки для вас в режиме реального времени, даже если вы работаете с большими объектами с более чем 10000 сетками. Какой алгоритм там используется, скажите, пожалуйста?
5 ответов
Blender выполняет выборку усеченного вида и выборку окклюзии, основываясь на динамических структурах ускорения дерева AABB из библиотеки физики Bullet. Окклюдеры и объекты представлены их ограничивающим объемом (ограничивающий прямоугольник, выровненный по оси).
Отбор вида усеченного конуса просто пересекает дерево AABB, учитывая усеченную камеру.
Отбор окклюзии основан на буфере окклюзии, типе буфера глубины, который инициализируется с помощью очень простого программного средства визуализации: базового трассировщика лучей, использующего динамические структуры ускорения дерева AABB. Вы можете выбрать разрешение буфера окклюзии, чтобы торговать точность и эффективность.
См. Также документацию http://wiki.blender.org/index.php/Dev:Ref/Release_Notes/2.49/Game_Engine
Реализация Blender из исходного дерева Blender: метод blender\source\gameengine\Physics\Bullet\CcdPhysicsEnvironment.cpp bool CcdPhysicsEnvironment::cullingTest(обратный вызов PHY_CullingCallback, плоскости void* userData, PHY__Vector4 *, плоскости int, плоскости)
и в Bullet Physics SDK есть некоторый пример кода C++ в Bullet/Extras/CDTestFramework.
Причина, по которой выбраковка не выполняется на уровне меша, заключается в том, что меш является очень тупым объектом уровня визуализатора, в то время как игровой объект находится на уровне сцены, где происходит все выбраковка. Решение по выбору уровня сетки не принимается, это просто способ пакетирования примитивов с похожими состояниями шейдеров, если их объекты необходимо визуализировать.
Если вам действительно нужно отбраковать на уровне меша, то вы можете создать один объект на сетку, а затем создать групповой объект, содержащий меш-объекты. Имейте в виду, что вы можете фактически потерять производительность, поскольку отбраковка на уровне меша обычно не стоит того; это может нарушить поток передачи данных на оборудование.
Обычно первое, что вы делаете, это проверяете, нет ли у мешей шансов перекрыть друг друга. Часто с простым ограничивающим примитивом (ограничивающие рамки или ограничивающие сферы). Если я правильно помню, Octrees поможет с этим.
Я попробовал наивный подход, который был достаточно быстрым для моего приложения.
Для каждого треугольника в сетке проверьте, не перекрыт ли какой-либо другой треугольник в сетке, таким образом, O (n2). (Я получил результаты высокой точности только после проверки, была ли закрыта центральная точка в каждом треугольнике или нет, хотя вы должны по крайней мере также проверить угловые вершины треугольника, если точность важна).
На компьютере с процессором Pentium 4 (C++) двоичный объект STL из ~10000 треугольников занял около 1 минуты.
Алгоритм может быть оптимизирован до ~40 процентов, сначала отсортировав треугольники, например, по размеру области или расстоянию от точки обзора (более вероятно, что он будет перекрыт, поэтому вы можете пропустить больше проверок).
Следующим шагом оптимизации будет размещение треугольников в октрее, что должно значительно сократить количество проверок окклюзии.