如何针对紧密的OOBB群快速测试光线交叉点？

Question

我在3d空间中有成千上万个OOBB(面向对象的边界框),它包含简单的细长3d网格.他们紧紧地挤在一起.

我想拍摄光线并找出哪些OOBB被击中.由于我需要执行的光线交叉测试的数量(数百万),对所有OOBB的暴力方法是不够的.

最初我认为使用某种空间分区系统来快速缩小潜在结果会很容易,但像BVH或KDTrees这样的系统依赖于AABB(轴对齐边界框)来加速查询,在我的情况下,那些效率非常低(因为我所包含的网格的对角线性质使得我的紧密堆积的OOBB具有大致相同的AABB).

我在RAPID库中读到了OBBTrees,但看起来它们是从上到下构建的(从多边形汤开始并细分为逐渐变小的OOBB组以形成树),而不是自下而上(从大量OOBB开始)并从他们建立一个树).

有没有其他数据结构可以用来加速交叉口测试？

这是我的OOBB图片.正如你所看到的,它们是紧密的,如果你可以想象它们的AABB会是什么样子,你会发现它们重叠到基于AABB的树不会真正提高性能的程度(因为几乎所有这些都是会被群体中心的射线击中.

值得注意的是,我需要查询所有被光线击中的OOBB,而不仅仅是第一个/最近的一个.

Answer 1

也许最好的方法是使用 3d 轴对齐的网格结构。网格中的每个单元格保存与该单元格相交的所有 oobb（向量、数组等）。8 个空单元格可以折叠成一个更大的空单元格，以加快空旷空间的遍历速度。对于网格的大小，您必须进行一些测试才能找到最佳大小。

遍历该网格很简单，您必须从距离射线原点最近的单元格开始，测试那里的所有对象，然后沿着射线移动到下一个单元格。遍历单元格基本上是 3d 保守线光栅化，其复杂性非常轻。更多相关内容请点击这里

此外，如果数据非常重叠，您可能需要一个大网格（其中单元格非常小）。在这种情况下，我建议您研究空间填充曲线来存储网格数据。（z 顺序曲线出奇地简单）