Разделение дерева KD

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

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

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

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

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

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

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

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


algorithm physics game-physics kdtree
person shaleve    schedule 08.01.2011    source источник

Ответы (2)


arrow_upward
23
arrow_downward

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

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

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

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

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

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

person celion    schedule 08.01.2011
comment
Упомянутая вами статья SAH в корзине может быть построена быстро kd-деревом с адаптивной эвристикой, ограниченной ошибками Ханта, Марка и Столла. Основная идея этой статьи состоит в том, чтобы использовать кусочно-квадратичные приближения к истинной функции SAH путем разумной выборки. По моему опыту, это быстрый и эффективный алгоритм. - person vedantk; 14.05.2014
comment
Да, похоже на тот. - person celion; 15.05.2014

arrow_upward
4
arrow_downward

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

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

person chrisjhebert1973    schedule 07.10.2013