algorithm - 宽相碰撞检测方法？

Question

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

• 检查所有内容与其他所有内容(O(n^2) 复杂度)
• Sweep and Prune(排序和清除)
• 关于二进制空间分区的一些事情(不确定如何做)

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

我看过 this但我要的是可用算法列表，而不是满足我需求的最佳算法。

在这种情况下，“广义相位碰撞检测”是物理引擎使用的一种方法，用于确定模拟中的哪些物体足够接近以保证进一步调查和可能的碰撞解决。

Answer 1

最佳方法取决于具体用途，但最重要的是，您要分割您的世界空间，以便 (a) 每个物体恰好在一个分割中，(b) 每个分割都足够大，以至于一个物体在特定分割只能与同一分割或相邻分割中的物体发生碰撞，并且 (c) 特定分割中的物体数量尽可能少。

如何做到这一点取决于您拥有多少物体、它们如何移动、您的性能要求是什么以及您希望在引擎上花费多少时间。如果您谈论的是在一个很大的开放空间中四处移动的物体，那么最简单的技术就是将世界划分为一个网格，其中每个单元格都大于您最大的物体，并跟踪每个单元格中的物体列表。如果您正在构建经典街机游戏的规模，此解决方案可能就足够了。

如果您要处理在更大的开放世界中移动的物体，一个简单的网格很快就会变得不堪重负，您可能需要某种基于树的结构，如四叉树，正如 Arriu 所建议的那样。

如果您谈论的是在有界空间而不是开放空间内移动物体，那么您可以考虑 BSP tree ;这棵树将世界划分为“你可以行走的空间”和“墙壁”，将一个 body 夹在树上决定它是否处于合法位置。根据世界几何形状，您还可以使用 BSP 对世界中物体之间的碰撞进行广相检测。

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