6

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

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

最初我认为使用某种空间分区系统来快速缩小潜在结果很容易，但是像 BVHs 或 KDTrees 这样的系统依赖于 AABBs（轴对齐的边界框）来加速查询，在我的情况下，这些将非常低效（因为我的许多紧密包装的 OOBB 具有大致相同的 AABB，因为它们包含的网格的对角线性质）。

我在 RAPID 库中阅读了有关 OBBTrees 的信息，但它们似乎是自上而下构建的（从多边形汤开始并细分为逐渐更小的 OOBB 组以形成树），而不是自下而上（从大量 OOBB 开始并用它们建造一棵树）。

是否有任何其他数据结构可以用来加速我的交叉测试？

这是我的 OOBB 的照片。如您所见，它们非常紧凑，如果您可以想象它们的 AABB 会是什么样子，您会发现它们会重叠到基于 AABB 的树不会真正提高性能的程度（因为几乎所有会被穿过人群中心的射线击中）。

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

OOBB

4

1 回答 1

1

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

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

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

于 2017-05-03T19:16:54.043 回答