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

Question

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

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

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

Answer 1

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

Что следует иметь в виду:

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

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

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

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

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

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

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

Answer 2

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

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

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

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

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

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

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

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

Answer 3

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

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

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

Answer 4

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

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

Answer 5

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

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

Answer 6

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

Answer 7

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