宽相碰撞检测方法？

Question

我正在构建一个2D物理引擎,我想添加宽相碰撞检测,但我只知道2或3种类型:

• 检查所有内容(O(n ^ 2)复杂度)
• 扫描和修剪(排序和扫描)
• 关于二进制空间分区的一些事情(不知道如何做到这一点)

但肯定还有更多选择吗？这些是什么？并且可以提供每个的基本描述或链接到描述吗？

我已经看到了这个,但我要求提供一系列可用的算法,而不是最符合我需求的算法.

在这种情况下,"广泛相位碰撞检测"是物理引擎用来确定模拟中哪些物体足够接近以保证进一步调查和可能的碰撞解决的方法.

Answer 1

最好的方法取决于具体用途,但最重要的是你想要细分你的世界空间,使得(a)每个身体只有一个细分,(b)每个细分都足够大,以至于特定细分中的身体只能与同一个细分或相邻细分中的实体发生碰撞,并且(c)特定细分中的实体数量尽可能小.

你如何做到这一点取决于你有多少身体,他们如何移动,你的性能要求是什么,以及你想在引擎上花多少时间.如果你在谈论在一个很大的开放空间中移动的物体,最简单的技术就是将世界划分为一个网格,每个单元格大于最大的对象,并跟踪每个单元格中的对象列表.如果你正在构建一个经典街机游戏的规模,这个解决方案可能就足够了.

如果你正在处理在一个更大的开放世界中移动的物体,一个简单的网格将很快变得势不可挡,你可能会想要某种基于树的结构,如四叉树,正如Arriu所说.

如果你在谈论在有界空间内移动物体而不是开放空间,那么你可以考虑一个BSP树 ; 树将世界划分为"你可以走进的空间"和"墙壁",并将树体剪入树中,以确定它是否处于合法位置.根据世界几何形状,您还可以使用BSP进行世界各体之间碰撞的广泛相位检测.

在有界空间中移动的物体的另一种选择是门户引擎; 如果你的世界可以由凸多边形区域组成,其中多边形的每一边都是实心墙或另一个凹空间的"门户",你可以很容易地确定一个体是否在一个带有多边形点测试的区域内.通过仅查看同一区域或连接区域中的实体来简化碰撞检测.

Answer 2

QuadTrees或BSPTrees的替代方案是SphereTrees(2D 中的CircleTrees,实现方式或多或少相同).SphereTrees的优势在于它们可以很好地处理大量动态对象.如果你的对象不断移动,BSPTrees和QuadTrees的更新速度要慢于Sphere/Circle Tree.

如果您有很好的静态和动态对象组合,一个相当不错的解决方案是使用QuadTree/BSPTree作为静态,使用Sphere/Cicle Tree作为动态对象.请记住,对于任何给定的对象,您需要针对两个树进行检查.

Answer 3

我建议使用四叉树分区.它非常简单,效果非常好.这是一个关于蛮力碰撞检测与四叉树碰撞检测的Flash 演示.(您可以告诉它显示四叉树结构.)您是否注意到四叉树碰撞检测在该演示中仅占蛮力的3%？

此外,如果您认真对待您的引擎,那么我强烈建议您选择实时碰撞检测.它并不昂贵,它是一本非常好的书,涵盖了你想知道的一切.(包括基于GPU的碰撞检测.)

Answer 4

所有加速算法都依赖于使用廉价的测试来快速排除对象（或对象组），从而减少必须执行的昂贵测试的数量。我按类别查看算法，每个类别都有许多变化。

1. 空间分区。划分空间并以低廉的成本排除来自不同地区的候选人。例如，BSP、网格、八叉树等。

2. 对象分区。与 #1 类似，但聚类更关注对象本身，而不是它们所在的空间。例如，包围体层次结构。

3. 排序和扫描方法。将物体按空间顺序排列，并排除不相邻物体之间的碰撞。

1 和 2 通常是分层的，根据需要递归到每个分区。使用 3，您可以选择沿不同维度进行迭代。

权衡在很大程度上取决于场景几何形状。物体是聚集的还是均匀分布还是稀疏分布？它们的尺寸都相同还是尺寸差异很大？场景是动态的吗？您能承担大量的预处理时间吗？

“便宜”的测试实际上是从非常便宜到有点昂贵的范围。选择最佳算法意味着最小化廉价测试的成本与昂贵测试数量减少的比率。除了算法问题之外，您还需要进行调整，例如担心缓存局部性。