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