Когда использовать двоичное пространственное разделение, Quadtree, Octree?

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

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

Что такое A, B и C?

Ответ 1

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

Что нужно иметь в виду:

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

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

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

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

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

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

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

Ответ 2

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

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

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

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

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

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

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

См. также: Octree vs BVH (заархивировано из ~~оригинала~~), Учебное пособие по иерархии объединенных томов, Учебное пособие по BSP.

Ответ 3

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

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

Octree лучше всего, когда у вас есть глыбы геометрии в 3d-пространстве, например, солнечная система.

Ответ 4

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

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

Ответ 5

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

Ответ 6

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

Ответ 7

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

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

Ответ 8

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