Когда использовать Binary Space Partitioning, Quadtree, Octree?

Недавно я узнал о деревьях разбиения двоичного пространства и их применении к трехмерной графике и обнаружению столкновений. Я также кратко ознакомился с материалами, касающимися квадр и октре. Когда бы вы использовали дерево на деревьях BSP, или наоборот? Они взаимозаменяемы? Я был бы удовлетворен, если бы у меня было достаточно информации, чтобы заполнить такую ​​таблицу:

            | BSP | Quadtree | Octree
------------+----------------+-------
Situation A |  X  |          |
Situation B |     |     X    |
Situation C |     |          |   X

Что такое А, В и С?

7 ответов

Решение

Нет четкого ответа на ваш вопрос. Это полностью зависит от того, как организованы ваши данные.

Что-то иметь в виду:

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

Octrees и BVH (иерархии ограничивающего объема) выигрывают, если данные являются трехмерными. Это также работает очень хорошо, если ваши геометрические объекты сгруппированы в трехмерном пространстве. (см. Октри против BVH)

Преимущество Oc- и Quadtrees заключается в том, что вы можете прекратить генерировать деревья в любое время. Если вы хотите визуализировать графику с помощью графического ускорителя, это позволяет вам просто генерировать деревья на уровне объектов и отправлять каждый объект в одном вызове отрисовки в графический API. Это работает намного лучше, чем отправка отдельных треугольников (что нужно делать, если вы используете BSP-Trees в полной мере).

BSP-Trees - это особый случай. Они очень хорошо работают в 2D и 3D, но создание хороших BSP-деревьев само по себе является искусством. У BSP-деревьев есть недостаток, заключающийся в том, что вам может потребоваться разбить вашу геометрию на более мелкие части. Это может увеличить общее количество полигонов вашего набора данных. Они хороши для рендеринга, но они намного лучше для обнаружения столкновений и трассировки лучей.

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

Это, кстати, причина, почему они были так популярны 10 лет назад. Quake использовал их, потому что позволил графическому движку / программному растеризатору не использовать дорогостоящий z-буфер.

Все упомянутые деревья просто семейства деревьев. Есть свободные октреи, гибридные деревья kd-деревьев и множество других связанных структур.

Самое большое практическое различие между BSP-деревьями и другими видами 3d-деревьев заключается в том, что BSP-деревья могут быть более оптимальными, но работать только со статической геометрией. Это связано с тем, что BSP-деревья обычно строятся очень медленно, и для типичного статического городского уровня игры требуются часы или дни.

Две основные причины, по которым деревья BSP строятся дольше: (а) они используют нерасщепленные плоскости расщепления, для оптимального поиска которых требуется больше времени, и (б) они разделяют геометрию на границах осей, гарантируя, что объекты не пересекают плоскости расщепления.

Другие типы 3d-деревьев (Octrees, Quadtrees, kd-tree, Bounding-Volume-Hierarchy) используют ограничивающие объемы по оси, и объемы (опционально) могут перекрываться, поэтому содержащиеся объекты не нужно обрезать по объему границы. Они оба делают деревья менее оптимальными, чем BSP-деревья, но быстрее строятся и легче изменяются для динамических объектов.

Экстраполируя эти факторы в ситуации...

Наружные области обычно используют наземные представления, основанные на полях высоты, либо простые карты высот, либо более сложные методы гео-mip-картографирования, такие как ROAM. Сама земля не участвует в разделении трехмерного пространства, только объекты, размещенные на земле.

Миры с множеством экземпляров более простой и похожей геометрии (дома, деревья, астероиды и т. Д.) Часто будут использовать не BSP-дерево (такое как BVH), потому что помещение геометрии в BSP-дерево будет означать дублирование и разбиение детальная геометрия для каждого экземпляра.

И наоборот, большая настраиваемая статическая сетка без экземпляров, такая как городская сцена или сложная внутренняя среда, обычно будет использовать BSP-дерево для улучшения производительности во время выполнения. Тот факт, что дерево BSP разделяет геометрию на границах узлов, помогает повысить производительность рендеринга, поскольку узлы BSP могут использоваться в качестве предварительно организованных пакетов рендеринга треугольников. Дерево BSP также может быть оптимизировано для окклюзии, избегая необходимости рисовать части дерева BSP, которые, как известно, находятся за другой геометрией.

См. Также: Octree vs BVH, Учебное пособие по иерархии ограничивающих томов, Учебное пособие по BSP.

BSP лучше всего подходит для городской среды.

Quadtree лучше всего подходит, когда вы используете карту высот для местности и т. Д.

Octree лучше всего подходит для случаев, когда у вас есть геометрия в трехмерном пространстве, например, в солнечной системе.

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

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

Если вы не знаете, что делаете, всегда выбирайте октодеревья, чтобы перестать сосредотачиваться на чрезмерной оптимизации и начать работать над более серьезными функциями. Серьезно, узкие места всегда будут где-то еще, или вы разрабатываете свой код вокруг оптимизированной системы, которая в конечном итоге предотвращает определенные типы изменений позже.

У меня нет большого опыта работы с BSP, но я могу сказать, что вы должны использовать октре по сравнению с квадродеревами, когда сцена, которую вы рендерите, высока. То есть высота составляет более половины ширины и глубины - мало практического правила. Как правило, октреи не принесут огромных затрат по сравнению с квадродеревами, и у них есть потенциал, чтобы немного ускорить процесс. YMMV.

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

BSP лучше для меньшего, более простого пространства, с которым вы только хотите сделать окклюзию. Если вы хотите, чтобы все пересечения для данного луча, вам нужно обновить до квад / октре.

Что касается квадри против октри - сколько измерений вас волнует? Два измерения означают квадри, четыре октре. Как уже говорилось, квадродерево может работать в трех пространствах, но если вы хотите, чтобы каждому измерению было уделено должное внимание, то октябрь - это путь.

Другие вопросы по тегам