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

Question

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

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

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

Answer 1

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

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

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

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

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

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

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

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

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

Answer 2

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

Answer 3

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

Answer 4

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

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

Answer 5

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

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

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

Answer 6

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

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

Answer 7

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

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

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

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

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

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

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

См. Также: Octree vs BVH, Bounding Volume Hierarchy Tutorial, BSP Tutorial.