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

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

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

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

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

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

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

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

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

Ответы на вопрос(2)

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

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

Решение Вопроса

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

Хорошая ссылка на эту темуТезис Инго Уолдав частности, глава 7.3, «Качественная конструкция BSP», в которой SAH объясняется лучше, чем я.

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

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

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

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

 celion14 мая 2014 г., 23:30
Да, это похоже на тот.
 vedantk14 мая 2014 г., 21:24
Упомянутая вами «сшитая» бумага SAH может быть «Быстрая конструкция kd-дерева с адаптивной эвристикой, ограниченной по ошибкам» Ханта, Марка и Столла. Основная идея этой статьи - использовать кусочно-квадратичные приближения к истинной функции SAH путем интеллектуальной выборки. По моему опыту, это быстрый и эффективный алгоритм.

Ваш ответ на вопрос