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

Question

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

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

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

Answer 1

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

Кое-что, что нужно иметь в виду:

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

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

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

На самом деле BSP-деревья - это особый случай.Они очень хорошо работают в 2D и 3D, но создание хороших BSP-деревьев само по себе является искусством.Недостаток 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-Tree разделяет геометрию по границам узлов, полезен для производительности рендеринга, поскольку узлы BSP могут использоваться как предварительно организованные пакеты рендеринга треугольников.BSP-дерево также может быть оптимизировано для окклюзии, избегая необходимости отрисовывать части BSP-дерева, которые, как известно, находятся за другой геометрией.

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

Answer 3

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

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

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

Answer 4

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

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

Answer 5

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

Answer 6

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

Answer 7

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

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