如何快速测试射线是否与一组紧密的OOBBs相交？

Question

我在3D空间中有成千上万个OOBBs（面向对象的边界框），它们包含简单的细长的3D网格，紧密地挤在一起。我想将光线射入其中，并确定哪些OOBBs被击中。由于我需要执行大量的光线交叉测试（数百万次），对所有OOBBs进行暴力搜索是不够的。最初，我认为可以使用某种空间划分系统来快速缩小潜在结果的范围，但是像BVHs或KDTrees这样的系统依赖于AABBs（轴对齐边界框）以加快查询速度，在我的情况下，这些方法非常低效（因为我紧密打包的OOBBs由于所包含的网格的对角线特性而具有大致相同的AABB）。我了解了RAPID库中的OBBTrees，但似乎它们是自上而下构建的（从多边形soup开始，逐渐将OOBBs分成越来越小的组以形成树），而不是自下而上构建的（从大量OOBBs开始并从中构建树）。是否有其他数据结构可用于加速我的交叉测试？

这是我OOBBs的一张图片。如您所见，它们紧密地排列在一起，如果您可以想象出它们的AABB会是什么样子，您会发现它们会重叠到一个基于AABB的树不会真正提高性能的程度（因为几乎所有的OOBB都会被射穿整个组的光线击中）。

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

- Tyson

---

尝试将光线旋转到某个空间中，使大多数bbs接近aabbs，并在该新空间中使用某种空间分割算法。另一个解决方案是，如果对象从光线到光线不改变，除了线性变换：您还可以生成一个3D数组，其中每个单元格都有一个列表，列出哪些三角形/ oobbs与其相交，并沿着该3D数组沿光线步进。 - programmerjake

@programmerjake 很遗憾，第一个建议行不通，因为OOBBs不会总是像我的示例图像那样对齐。第二个选项可能更接近一些东西，但内存占用和预处理要求可能会成为问题...我需要解决方案在非常大的3D环境中工作，在那里使用3D数组是不可行的（需要数十亿个单元格才能包括所有内容，同时保持合理的粒度）。但还是谢谢你的建议。 - Tyson

@Angew 在OOBBs改变之前，我将投射几百万条光线。它们可能会在每个模拟步骤中发生相当大的变化（它们包含沿任意轨迹移动的三角形）。 - Tyson

@Tyson，使用3D网格怎么样？对于每个拥有太多三角形的单元格，您可以将其细分为较小的网格。 - programmerjake

@programmerjake 我猜那应该类似于八叉树之类的东西吧？ - Tyson

Answer 1

最好的方法可能是使用一个三维轴对齐的网格结构。网格中的每个单元格都包含与该单元格相交的所有oobb的向量、数组等。将8个空单元格合并成一个更大的空单元格，以加快遍历空间的速度。对于网格的大小，您需要进行一些测试以找到最佳大小。

遍历该网格很简单，您必须从射线起点最近的单元格开始，测试所有在那里的对象，然后沿着射线移动到下一个单元格。遍历单元格基本上是一种三维保守直线光栅化，复杂度非常轻。更多信息在这里

---

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

- Raxvan