最佳算法用于对象之间的高效碰撞检测

Question

最佳算法用于对象之间的高效碰撞检测

47

我有些困惑，不是真正的困惑，只是不想做6个测试程序来看哪个算法最好。因此，我想向SO上的专家朋友们请教一下他们的经验。

场景是一个三维场景，与其中的对象相比可能有相当大的面积。场景中可能有成千上万个对象。对象的大小从十分之一单位到大约10个单位不等，但没有更大（或更小）的对象。对象往往会聚集在一起，但这些集群可能出现在场景的任何地方。所有对象都是动态的并且在移动。集群往往会一起移动，但当它们移动时，它们的速度可能并不总是相同的。还需要考虑静态几何。虽然场景中有大量的动态对象，但也有一些静态对象（静态对象往往比动态对象大一到两个数量级）。

现在，我想要一个空间数据结构，以便有效地执行场景中所有项目的碰撞检测。如果该算法还支持可视性查询，则效果将非常好，用于渲染管道。为简单起见，假设这里的碰撞检测是广义的（即所有动态对象都是完美的球体）。

因此，在我的研究中，我可以使用以下之一：

(1) 八叉树 (2) 宽松八叉树 (3) 线性八叉树+宽松八叉树 (4) KD树 (5) BSP树 (6) 哈希

到目前为止，我只尝试过（6）。如果场景中的对象平均分布，则速度非常快（在我的系统上检查8192个项目的碰撞时间不到1毫秒）。如果所有对象被限制在一个较小的区域内，那么它并不是一个好算法，这可能是可能的。

有没有人对使用哪个技术有什么见解，或者有哪些技巧可以加快速度？我想无论发生什么情况，我都可以为静态几何体使用单独的BSP树。我想最让我担心的是动态“球体”。请注意：没有CUDA，这只是CPU :p.

谢谢

编辑：好的，感谢Floris，我找到了更多关于AABB树的信息。在GameDev上有一个旧的讨论：http://www.gamedev.net/topic/308665-aabb-tree---wheres-the-poly-o_o/。看起来是个不错的折衷方案。

最终编辑：决定不重复造轮子了。可能Bullet物理库会为我完成所有这些工作（它在其中有AABB树，可能也被很好地优化了）。

- Robinson

1

你在处理动态场景时可以跳过KD树。KD树适用于静态数据集，每当单个元素移动时，您都需要重建整个（子）树。 - SingleNegationElimination

是的，看起来在动态场景中使用它太过密集。 - Robinson

2个回答

7

许多物理引擎使用AABB树（轴对齐包围盒树），它将一个对象细分为越来越小的部分。通过使用这个算法，您可以获得非常好的碰撞检测效果。这棵树看起来有点像八叉树。

OOBB树（定向包围盒）是其更好的对应部分。

- Floris

当然。那是一个边界体层次结构，对于细粒度的交叉测试可能更好。我正在寻找广相位（即单个移动球体/粒子）检测的想法。- 我犯了错误...我会再仔细研究一下。我在网上找到的第一个示例看起来像是在进行细粒度碰撞，但我还要看看其他的。 - Robinson

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mikera · Accepted Answer

很好的问题。

基本上，您需要在以下两个方面进行权衡：

完成碰撞检测阶段的速度
随着对象的移动更新/维护数据结构所需的开销

不幸的是，由于这一点，没有“完美”的答案-它确实取决于许多不同因素，这些因素对您的情况独特。

例如，当BSP与大量静态平面几何体预计算时，它们可以极快地运行，这解释了为什么它们在早期FPS游戏中如此流行。

我个人的猜测是，一个包含每个底层边界框中有合理数量物体（5-10？）的宽松AABB（轴对齐边界框）树可能会在您的情况下效果最好。原因：

您拥有相当大/稀疏的空间和物体聚类。 AABB树往往在此方面表现良好，因为您可以切掉许多其他情况下需要的层级。
您假设是完美球形。球与球之间的碰撞测试非常便宜，因此您可以轻松承受每个底层节点的10-45次测试。基本上，对于小值N，N²是可以接受的 :-)
轴对齐使得更新树变得更简单，交集测试比大多数替代方案更便宜。由于您假设物体大致是球形的，我认为您不会从定向边界框中获得太多好处（这仅在您有很多长/细形状以及奇怪角度时才真正给您带来优势）。
通过允许边界框是宽松的并包含合理数量的对象，您降低了任何单个对象的运动将其带出AABB范围的可能性。除非发生这种情况，否则您不需要更新树。这将为您节省大量更新树的时间。当它确实发生时，请使用一点余量扩展边界框，以便您不必立即在下一帧重新扩展-请记住，大多数运动倾向于连续几帧朝着同一个方向进行！

对于略微模糊的答案感到抱歉，但我希望这为您提供了一些有用的想法/需要考虑的事项！