KDTree Расщепление

Question

В настоящее время я пишу KDTree для физического движка (проект Hobby).

KDTree не содержит точек.Вместо этого он содержит ограничивающие прямоугольники с выравниванием по оси, которые ограничивают различные объекты в среде.

Моя проблема заключается в том, чтобы решить, как разделить узлы KDTree, когда они заполнятся.Я пробую 2 метода:

Метод 1: Всегда делить узел ровно пополам по самой большой оси.

• Преимущество этого состоит в том, что дерево довольно равномерно расположено.
• Большой недостаток: если объекты сосредоточены в небольшой области узла, будут созданы избыточные подразделения.Это потому, что все тома разделены ровно пополам.

Метод 2: Найти область узла, в которой находятся объекты.Разделите узел на плоскости, которая разделяет эту область пополам по его наибольшей оси.Пример. Если все объекты сосредоточены в нижней части узла, то он делится по длине, тем самым разделяя дно на две части.

• Это решает проблему описанным выше методом
• Когдаиндексируя что-то, что существует в той же плоскости (например, ландшафт), оно создает длинные и узкие узлы.Если позже я добавлю некоторые другие объекты, которые не находятся на одной плоскости, эти удлиненные узлы обеспечивают очень плохую индексацию.

Так что то, что я ищу здесь, - лучший способ разделить мой KD-Деревянный узел.Учитывая, что это будет физический движок, решение должно быть достаточно простым, чтобы принимать его в режиме реального времени.

Answer 1

«Эвристика площади поверхности» (SAH) считается лучшим методом расщепления для построения kd-деревьев, по крайней мере, в сообществе трассировщиков лучей.Идея состоит в том, чтобы добавить плоскость так, чтобы площади поверхности двух дочерних пространств, взвешенные по количеству объектов в каждом дочернем элементе, были равны.

Хорошая ссылка на предмет: Диссертация Инго Уолда, в частности главу 7.3, «Высококачественная конструкция BSP», которая объясняет SAH лучше, чем я.

В данный момент я не могу найти хорошую ссылку, но вам следует поискать документына «binned» SAH, который является приближением к истинному SAH, но гораздо быстрее.

Все это говорит о том, что иерархии ограничивающего объема (BVH), также известные как деревья AABB, кажутся гораздо более популярными, чем kd-деревьяЭти дни.Опять же, Страница публикации Инго Уолда является хорошей отправной точкой, вероятно, с документацией «О быстром построении иерархий ограничивающих объемов на основе SAH», хотя я давно ее прочитал.

Форумы OMPF также являются хорошим местом для обсуждения подобных вещей.

Надеюсь, что это поможет.Удачи!

Answer 2

Конечно, для физического движка, в котором много движущейся геометрии, вероятно, лучшим выбором будет bvh, он движется не так быстро, но его сборка происходит намного быстрее, и его гораздо проще переоборудовать / реструктурировать кадр за кадром, и offen не нуждается в полной перестройке каждого кадра (то, что можно сделать параллельно через серию кадров, в то время как достаточно переопределенного bvh, опять же, обратитесь к wald).

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