Где найти внятный пример binary space partitioning tree (bspt)?
Очень хочется найти внятный пример (а еще лучше, статью о практической реализации) bspt. Язык реализации не принципиален - я в этом смысле полиглот. Во всяком случае, прочитать и понять код способен.
Сама суть алгоритма мне ясна и понятна. А вот что совсем не понятно, так это выбор плоскости для сечения пространства. Во всех материалах, которые мне удалось найти принцип выбора плоскости опускается, как будто это что-то очевидное или не очень важное. Вместе с тем, лично для меня, выбор оптимальной плоскости для сечения пространства явился "тупиком".
Все реализации, которые мне удалось найти, работают с уже выбранной плоскостью/плоскостями. Помогите, господа знатоки. И за ранее спасибо.
> как будто это что-то очевидное
0.5 ширины, потом 0.5 высоты, потом 0.5 глубины. И так для каждой партиции. Например.
Точки разбиения зависят от того, что именно разбиваете. Можно ровно по середине партиции, можно привязываться к каким-то особенностям геометрии, например к дверным проёмам... Хоть как разбивать можно.
Если хочется живого примера, скачай движок какого-нибудь первого quake, там bsp деревья используются, но будет весьма непонятно.
Роман Сохарев: Коллизии будут всегда на любой более-менее не квадратной геометрии. С этим приходится жить и это не страшно.
Если есть какие-то особенности в топологии, то можно привязываться к ним, чтобы оптимизировать разбиение. В принципе, плоскости могут даже не быть ортогональными и выровненными по глобальным осям, но это уже сложнее равномерно разбить.
Если нет никаких "особенностей", то можно резать ровно пополам и быть уверенным, что всё делаете правильно.
Спасибо за ответ. Но я не думаю, что это простые диагональные плоскости являются оптимальными.
Во-первых, они не учитывают возможности избежать коллизий с полигонами, и таким образом снизить количество "нарезаемых" на трапеции полигонов. Разрезаемый плоскостью полигон породит еще два полигона (трапецию).
Во-вторых, не позволяют избежать слишком раннего вырождения дерева.
Роман Сохарев: В зависимости от применения, разрезать треугольник на три других может не быть нужным. Вместо этого один и тот же треугольник можно внести в две партиции. Опять же, в зависимости от вариантов использования, оверхед от дублирования треугольников может быть гораздо меньше времени дробления треугольников. Сколько-нибудь сложную геометрию в принципе невозможно разрезать пополам, не разрезая(дублируя) треугольников.
Простой
