При использовании двоичного разбиения, дерева квадрантов, восьмеричного дерева набора?
недавно я узнал о бинарных пространственных деревьях разбиения и их применении к 3d-графике и обнаружению столкновений. Я также кратко просматривал материалы, касающиеся деревья квадрантов и octrees. Когда бы вы использовали квадроциклы над деревьями bsp или наоборот? Они взаимозаменяемы? Я был бы доволен если бы у меня было достаточно информации, чтобы заполнить таблицу такой:
| BSP | Quadtree | Octree
------------+----------------+-------
Situation A | X | |
Situation B | | X |
Situation C | | | X
что такое A, B и C?
7 ответов:
нет четкого ответа на ваш вопрос. Это полностью зависит от того, как организованы ваши данные.
Что-то, чтобы иметь в виду:
Quadtrees лучше всего работают для данных, которые в основном являются двумерными, как отображение карт в навигационных системах. В этом случае он быстрее, чем octrees, потому что он лучше адаптируется к геометрии и сохраняет узловые структуры небольшими.
Octrees и BVHs (ограничивающие иерархии томов) выигрывают, если данные трехмерны. Это также работает очень хорошо, если ваши геометрические объекты сгруппированы в трехмерном пространстве. (см. Octree vs BVH)
преимущество Oc-и Quadtrees заключается в том, что вы можете прекратить генерировать деревья в любое время. Если вы хотите визуализировать графику с помощью графического ускорителя, он позволяет вам просто генерировать деревья на уровне объекта и отправлять каждый объект в одном вызове draw в графический API. Это выполняет много лучше, чем отправка отдельных треугольников (то, что вы должны сделать, если вы используете BSP-деревья в полной мере).
BSP-деревья-это действительно особый случай. Они очень хорошо работают в 2D и 3D, но создание хороших BSP-деревьев-это форма искусства сама по себе. BSP-деревья имеют тот недостаток, что вам, возможно, придется разделить вашу геометрию на более мелкие части. Это может увеличить общее количество полигонов вашего набора данных. Они хороши для рендеринга, но они намного лучше для обнаружения столкновений и трассировки лучей.
хорошим свойством BSP-деревьев является то, что они разлагают полигональный суп в структуру, которая может быть идеально отображена назад к фронту (и наоборот) из любой позиции камеры без выполнения фактической сортировки. Порядок с каждой точки зрения является частью структуры данных и выполняется во время компиляции BSP-дерева.
вот, кстати, почему они были так популярны 10 лет назад. Quake использовал их, потому что это позволило графическому движку / программному растеризатору не использовать дорогостоящий z-буфер.
все упомянутые деревья это просто семьи деревьев. Есть свободные octrees, KD-деревья гибридные деревья и много других связанных структур, а также.
самая большая практическая разница между BSP-деревьями и другими видами 3d-деревьев заключается в том, что BSP-деревья могут быть более оптимальными, но работать только на static геометрия. Это связано с тем, что BSP-деревья, как правило, очень медленно строятся, часто занимая часы или дни для типичного статического городского уровня игры.
две основные причины, по которым BSP-деревья занимают больше времени для построения,-это (а) они используют неосевые плоскости расщепления, которые занимают больше времени для оптимального поиска, и (б) они подразделяют геометрию на границы оси, гарантируя, что никакие объекты не пересекают плоскости разделения.
другие типы 3d-деревьев (Октреи, квадратики, KD-дерево, ограничивающая иерархия объема) используют выровненные по оси ограничивающие объемы, и объемы (необязательно) могут перекрываться, поэтому содержащиеся объекты не нужно вырезать на границах объема. Они оба делают деревья менее оптимальными, чем BSP-деревья, но быстрее строить и легче изменять для динамических объектов.
экстраполяция этих факторов в положения...
на открытых площадках обычно используются наземные представления на основе высоты, либо простые карты высоты, либо более сложные методы гео-МИП-картографирования, такие как ROAM. Сама земля не участвует в трехмерном разделении пространства, только объекты, размещенные на земле.
миры с большим количеством экземпляров более простой и похожей геометрии (дома, деревья, астероиды и т. д.) Часто будут использовать не-BSP-дерево (например, BVH), потому что помещение геометрии в BSP-дерево будет означать дублирование и разделение геометрии детали для каждого экземпляра.
и наоборот, большая пользовательская статическая сетка без инстанцирования, такая как Городская сцена или сложная внутренняя среда, обычно использует BSP-дерево для повышения производительности во время выполнения. Тот факт, что BSP-дерево разбивает геометрию на узловые границы, полезен для производительности рендеринга, поскольку узлы BSP могут использоваться в качестве предварительно организованных пакетов рендеринга треугольников. BSP-дерево также может быть оптимизировано для окклюзии, избегая необходимости рисовать части BSP-дерева, которые, как известно, находятся за другой геометрией.
Читайте также: Octree vs BVH,Учебник По Ограничению Иерархии Томов, BSP Tutorial.
BSP лучше всего подходит для городской среды.
Quadtree лучше всего подходит для использования карты высоты для местности и т. д.
Octree лучше всего подходит для того, когда у вас есть сгустки геометрии в 3d-пространстве, такие как Солнечная система.
BSPs являются хорошим вариантом для ускорения обнаружения столкновений, в зависимости от того, какой вкус вы используете. Они особенно быстры в точечных и линейных или лучевых тестах, несколько менее быстры и немного сложнее для вещей с объемом.
Что касается их использования в графике, BSP в значительной степени устарели. Octrees хорошо работают для таких вещей, как грубая видимость выбраковки, как и деревья AABB.
У меня нет большого опыта работы с BSPs, но я могу сказать, что вы должны идти с октрами над квадратиками, когда сцена, которую вы рендерите, высока. То есть высота больше половины ширины и глубины-небольшое эмпирическое правило. Как правило, octrees не принесет огромных затрат за деревья квадрантов и у них есть потенциал, чтобы ускорить приличное. МММ.
обычно такие вещи не имеют четкого ответа. Я бы предположил,что A, B и C являются результатом функции размера вашего пространства и количества вещей, которые вы дифференцируете.
BSP лучше для меньшего, более простого пространства, с которым вы только хотите сделать окклюзию. Если вы хотите, чтобы все пересечения для данного луча, вам нужно перейти на quad/octree.
Что касается quadtree против octree - сколько измерений вы заботитесь много? Двух измерениях означает дерева квадрантов, четыре восьмеричного дерева набора. Как уже говорилось, поскольку quadtree может работать в трех пространствах, но если вы хотите, чтобы каждому измерению была дана надлежащая обработка, octree-это путь.
Comments