dynamic - 物体间高效碰撞检测的最佳算法

Question

我很困惑。好吧，不要感到困惑，就像不想做 6 个测试程序来看看哪种算法是最好的一样。所以我想我应该请教我在 SO 的专家 friend ，让我从他们的经验中获益。

该场景是一个 3D 场景，与其中对象的大小相比，其区域可能相当大。场景中可能有数千个对象。物体的大小从十分之一到大约十个单位不等，但没有更大(或更小)。这些对象往往聚集在一起，但这些群集可能会出现在场景中的任何位置。所有物体都是动态的、移动的。星团往往会一起移动，但当它们一起移动时，它们的速度可能并不总是相同。还需要考虑静态几何形状。尽管动态对象数量较多，但场景中也存在一些静态对象(静态对象往往比动态对象大一两个数量级)。

现在，我想要的是一个空间数据结构，可以有效地对场景中的所有项目执行碰撞检测。如果该算法也支持渲染管道的可见性查询，那就太好了。为了简单起见，假设这里的碰撞检测是宽相的(即所有动态物体都是完美的球体)。

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

(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/ 。看起来是一个很好的妥协。

最终编辑:决定不重新发明轮子。子弹物理库可能会为我完成所有这些(它有 AABB 树，可能也优化得很好)。

Answer 1

很好的问题。

您基本上需要在以下方面进行复杂的权衡:

1. 完整碰撞检测阶段的速度
2. 对象移动时更新/维护数据结构的开销

坏消息是，因此没有“完美”的答案 - 这实际上取决于您的情况所特有的许多不同因素。例如，当 BSP 使用大量静态平面几何体进行预先计算时，其速度非常快，这解释了为什么它们在早期 FPS 游戏中如此流行。

我个人的猜测是，每个底层边界框中包含合理数量的对象(5-10？)的松散 AABB(轴对齐边界框)树可能最适合您的情况。原因:

• 您有一个相当大/稀疏的空间，其中有一些对象簇。 AABB 树往往对此很有用，因为您可以删除许多原本需要的级别。
• 您假设的是完美的球体。球体到球体的碰撞测试非常便宜，因此您可以轻松地为每个底层节点进行 10-45 次测试。基本上 N^2 对于较小的 N 值来说是没问题的:-)
• 轴对齐使更新树变得更加简单，并且相交测试比大多数替代方法便宜得多。由于您假设大致为球形物体，因此我认为您不会从定向边界框中获得太多 yield (只有当您在有趣的角度有大量长/细形状时，这才真正给您带来优势)。
• 通过允许边界框宽松并包含合理数量的对象，可以减少任何单个对象的运动将其带出 AABB 边界的可能性。除非发生这种情况，否则您不需要更新树。这将为您节省大量树更新时间。当这种情况发生时，请稍微扩展边界，这样您就不必立即重新扩展下一帧 - 请记住，大多数运动往往会在同一方向上持续几帧!

抱歉，我的回答有点模糊，但我希望这能给您一些有用的想法/需要考虑的事情!