宽相位碰撞检测方法？

Question

我正在构建一个2D物理引擎，我想添加一个宽相位碰撞检测，尽管我只知道2到3种类型：

• 检查所有其他事物(O(n^2)复杂性)
• 扫描和Prune (排序和扫描)
• 有关二进制空间分区的内容(不确定如何实现)

但肯定还有更多的选择对吧？他们是什么?是否可以提供每个描述的基本描述，或者链接到描述？

我已经看过这了，但我想要的是可用算法的列表，而不是满足我需求的最佳算法。

在这种情况下，“宽相位碰撞检测”是一种物理引擎使用的方法，以确定在其模拟中哪些物体足够接近，需要进一步的研究和可能的碰撞分辨率。

Answer 1

最好的方法取决于具体的用途，但底线是你要细分你的世界空间，以便：(a)每一个物体都在一个细分中，(b)每一个细分都足够大，一个物体在同一细分或相邻的细分中只能与物体碰撞，和(c)某一细分中的物体数目尽可能小。

如何做到这一点取决于您有多少身体，它们如何移动，您的性能要求是什么，以及您想花多少时间在您的引擎上。如果你说的是在很大程度上开放的空间中移动的物体，最简单的方法是把世界划分成一个网格，每个细胞都比你最大的物体大，并跟踪每个细胞中的物体列表。如果您正在构建一个经典的街机游戏的规模，这个解决方案很可能就足够了。

如果你处理的是在一个更大的开放世界中移动的物体，一个简单的网格很快就会变得势不可挡，你可能会像Arriu所建议的那样，想要一种基于树的结构，比如四叉树。

如果你说的是在有限制的空间内移动物体，而不是开放的空间，那么你可以考虑一个BSP树；树将世界划分为“你可以行走的空间”和“墙壁”，然后把一个物体插进树中，这决定了它是否处于合法的地位。根据世界几何学的不同，你也可以使用BSP来探测世界上物体之间的碰撞。

在有界空间中移动的物体的另一种选择是门户引擎；如果您的世界可以由凸多边形区域组成，其中多边形的每一侧都是一个实体墙，或者是另一个凹空间的“门户”，那么您可以很容易地确定一个物体是否在一个区域内，并进行点多边形测试，并通过只查看同一区域或连接区域的物体来简化碰撞检测。

Answer 2

QuadTrees或BSPTrees的另一种选择是SphereTrees ( 2D中的CircleTrees，实现方式大致相同)。SphereTrees的优点是它们能够很好地处理大量动态对象。如果您的对象一直在移动，那么BSPTrees和QuadTrees的更新要比Sphere/圆圈树慢得多。

如果您很好地混合了静态和动态对象，那么一个比较好的解决方案是使用四叉树/BSPTree作为静态对象，使用Sphere/Cicle来处理动态对象。请记住，对于任何给定的对象，您都需要对照(两个树)检查它。

Answer 3

我建议使用四叉树分区。这很简单，而且效果很好。这里是一个闪存演示的蛮力碰撞检测与四叉树碰撞检测.(您可以告诉它显示四叉树结构。)你注意到在这个演示中，四叉树碰撞检测只有3%的蛮力吗？

另外，如果你对你的引擎是认真的，那么我强烈建议你选择实时碰撞检测。这本书并不贵，而且是一本很棒的书，涵盖了你想知道的一切。(包括基于GPU的碰撞检测。)