我在3d空间中有数千个OOBB(面向对象的边界框)，其中包含简单的细长3d网格。它们紧密地包装在一起。
我想向其中发射光线，并找出哪些OOBB受到了打击。由于我需要执行的射线相交测试数量(以百万计)，针对所有OOBB的蛮力方法不足。
最初，我认为使用某种空间分区系统来快速缩小潜在结果的范围很容易，但是BVH或KDTree之类的系统依靠AABB(轴对齐的边界框)来加快查询的速度，而在我的情况下，这些效率非常低下(由于封闭的网格物体的对角线性质，我的许多紧密包装的OOBB的AABB大致相同)。
我在RAPID库中读到有关OBBTree的信息，但似乎它们是从上至下(从多边形汤开始，再 segmentation 为越来越小的OOBB组以形成树)，而不是从下至上(从许多OOBB开始)并用它们 build 一棵树)。
我还有其他数据结构可以用来加快路口测试吗？
这是我的OOBB的图片。如您所见，它们紧密地包装在一起，如果您可以设想它们的AABB外观，您会发现它们重叠到基于AABB的树并不能真正提高性能的程度(因为几乎所有树都如此)会被穿过该组中心的射线击中)。
值得注意的是，我需要查询所有被射线击中的OOBB，而不仅仅是第一个/最近的一个。
最佳答案
最好的方法是使用3d轴对齐的grid structure。网格中的每个单元格都包含( vector ，数组等)与该单元格相交的所有oobb。可以将8个空单元折叠成一个较大的空单元，以加快空空间的遍历。对于网格的大小，您将必须进行一些测试才能找到最佳大小。
遍历该网格是微不足道的，您将必须从最接近射线源的单元开始，测试那里的所有对象，然后沿着射线移动到下一个单元。遍历像元基本上是3d保守线栅格化，复杂度非常低。有关here的更多信息
此外，如果数据非常重叠，则可能需要一个较大的网格(单元格很小)。在这种情况下，我建议您调查space filling curves以存储网格数据。 (z-order curve非常简单)