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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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