c++ - 如何针对一组紧密的 OOBB 快速测试射线相交？

Question

我在 3d 空间中有数千个 OOBB(面向对象的边界框)，其中包含简单的细长 3d 网格。它们紧紧地挤在一起。

我想向它们发射光线并找出哪些 OOBB 被击中。由于我需要执行的射线相交测试的数量(数百万)，针对所有 OOBB 的强力方法是不够的。

最初我认为使用某种空间分区系统可以很容易地快速缩小潜在结果的范围，但像 BVH 或 KDTrees 这样的系统依赖 AABB(轴对齐边界框)来加速查询，在我的例子中，它们会效率非常低(因为我的许多紧密包装的 OOBB 由于它们包含的网格的对角线性质而具有大致相同的 AABB)。

我在 RAPID 库中读到了有关 OBBTrees 的信息，但它们似乎是自上而下构建的(从多边形汤开始并 segmentation 为逐渐变小的 OOBB 组以形成树)，而不是自下而上(从许多 OOBB，并从中构建一棵树)。

我可以使用任何其他数据结构来加速我的相交测试吗？

这是我的 OOBB 的照片。如您所见，它们紧密排列，如果您能想象它们的 AABB 会是什么样子，您会发现它们会重叠到基于 AABB 的树不会真正提高性能的程度(因为几乎所有它们会被穿过组中心的射线击中)。

值得注意的是，我需要查询一条射线击中的所有 OOBB，而不仅仅是第一个/最近的一个。

Answer 1

最好的方法可能是使用对齐的 3d 轴 grid structure .网格中的每个单元格都包含与该单元格相交的所有 oobb( vector 、数组等)。 8 个空单元格可以折叠成一个更大的空单元格，以加快空白空间的遍历。对于网格的大小，您必须进行一些测试才能找到最佳大小。

遍历该网格很简单，您必须从距离射线原点最近的单元格开始，测试那里的所有对象，然后沿着射线移动到下一个单元格。遍历cell基本上就是3d保守线栅格化，复杂度很低。更多关于 here

---

此外，如果数据非常重叠，您可能需要一个大网格(其中单元格非常小)。在这种情况下，我建议您查看 space filling curves存储网格数据。 (z-order curve 非常简单)