У меня есть тысячи OOBBs (объектно-ориентированных ограничивающих рамок) в трехмерном пространстве, которые охватывают простые вытянутые трехмерные сетки. Они плотно упакованы вместе.
Я хотел бы стрелять в них лучами и выяснить, какие OOBB-ы получили удар. Из-за количества испытаний на пересечение лучей, которые мне нужно выполнить (миллионы), подхода грубой силы против всех OOBB недостаточно.
Первоначально я думал, что было бы легко использовать какую-то систему пространственного разделения для быстрого сужения потенциальных результатов, но такие системы, как BVH или KDTrees, полагаются на AABB (ограничивающие прямоугольники по оси) для ускорения запросов, и в моем случае это было бы очень неэффективно. (потому что многие из моих плотно упакованных OOBB имеют примерно одинаковый AABB из-за диагональной природы меша, который они охватывают).
Я читал о OBBTree в библиотеке RAPID, но кажется, что они построены сверху вниз (начнем с многоугольного супа и разделим на постепенно меньшие группы OOBB для формирования дерева), а не снизу вверх (начнем с большого количества OOBB и построить из них дерево).
Существуют ли какие-либо другие структуры данных, которые я могу использовать для ускорения испытаний на пересечение?
Вот фотография моих OOBB. Как вы можете видеть, они плотно упакованы, и если вы сможете представить, как будет выглядеть их AABB, вы увидите, что они будут перекрываться до такой степени, что дерево на основе AABB не будет реально повышать производительность (потому что практически все они будет поражен лучом, стреляющим через центр группы).
Стоит отметить, что мне нужно запрашивать все OOBB, пораженные лучом, а не только первый / ближайший.
Вероятно, лучше всего использовать выровненную ось 3d структура сетки. Каждая ячейка в сетке содержит (вектор, массив и т. Д.) Всех oobb, которые пересекают эту ячейку. 8 пустых ячеек могут быть свернуты в большую пустую ячейку для ускорения обхода пустого пространства. Для размера сетки вам придется провести некоторое тестирование, чтобы найти оптимальный размер.
Обход этой сетки тривиален, вам придется начать с ближайшей ячейки до источника луча, проверить все объекты там, а затем перейти к следующей ячейке вдоль луча. Обход ячейки — это в основном растеризация трехмерной линии, которая очень легка по сложности. Подробнее об этом Вот
Кроме того, если данные сильно перекрываются, вы можете захотеть иметь большую сетку (где ячейки очень маленькие). В этом случае я бы посоветовал вам посмотреть на кривые заполнения пространства хранить данные сетки. (кривая z-порядка удивительно просто)
Других решений пока нет …