宽相检测

原理说明

宽相碰撞检测目标是生成一个可能发生碰撞的“碰撞对列表”。所有宽相算法都基于一个简单的思想：用一个简单的、计算开销小的几何体（称为包围体）来包裹复杂的物体。如果两个物体的包围体没有重叠，那么这两个物体本身也一定没有重叠。

最常用的包围体是轴对齐包围盒 (Axis-Aligned Bounding Box, AABB)。一个 AABB 可以由两个点（最小值点 min 和最大值点 max）来定义。检查两个 AABB 是否重叠非常快速，只需要在三个轴上分别检查它们的区间是否重叠即可。

常见宽相算法

常见的宽相算法有下面几种：

• 直接遍历 直接两两检查所有物体的包围体是否重叠。复杂度为$O(n^2)$。当物体数量增多时，性能很差。所以，仅适合小规模场景或者教学示例。

• 网格法 将整个世界空间划分为一系列均匀大小的单元格。每个单元格存储其中包含的物体列表。对于一个物体，只需检查它所在的单元格及其相邻单元格中的物体。如果物体分布不均匀，大量单元格是空的，浪费内存。一个物体可能跨越多个单元格，需要额外处理。单元格的大小对性能影响很大，过大和过小都不行。在工程上，会用Dynamic Spatial Hashing来实现存储和管理。

• 四叉树和八叉树 递归地将空间划分为更小的子空间。四叉树用于 2D 空间，八叉树用于3D空间。当一个子空间中的物体数量超过阈值时，该子空间会被进一步细分,可以自定义一个叶子节点上最多几个物体。重叠测试流程：通过遍历树结构，检查那些与查询物体包围盒重叠的节点的物体。通过这种方法，可以很好的适应物体分布不均匀的场景，进行快速查询。如果一个物体跨越多个节点时，需要特殊处理，比如放在父节点或者子节点（需要去重）。

• Sweep and Prune (SAP / Sort and Sweep)

SAP 全称 Sweep and Prune（扫描与剪枝），也称 Sort and Sweep (SAS)。SAS 是算法思想，SAP 是其高效实现与优化版本。SAP 的核心思想是：

1. 每个物体用 AABB 包围，并在每个轴上有最小值（start）和最大值（end）；
2. 选择一个主轴（通常是 X 轴），将物体在该轴的端点排序；
3. 按排序顺序扫描端点，维护活动列表（Active List），生成在主轴上重叠的候选碰撞对；
4. 对候选对在其他轴（Y、Z）上做重叠检查（剪枝），只有在所有轴都重叠的情况下才将其保留为潜在碰撞对；
5. 候选对送到窄相检测阶段进行精确碰撞检测。

核心原则：排序轴做大规模剪枝，其他轴做精细剪枝。这种方式可以大幅减少不必要的碰撞测试，同时保持增量更新高效。

• Dynamic Bounding Volume Tree 动态包围体树，简称DBVT。DBVT是一种二叉树结构，树的每个节点都存储一个AABB。树的叶子节点存储实际物体的AABB。父节点的AABB是两个叶子节点的包围盒。如果查询的AABB与某个节点AABB不重叠，就可以快速剪枝，跳过整个子树。树支持动态的更新，允许物体的移动、插入和删除。DBVT可以很好处理动态场景，又能处理稀疏和密集的物体分布。

主流物理引擎的宽相实践

Box2D: 使用的DBVT算法.

Bullet3: 提供了多种宽相检测算法。

• Dynamic Spatial Hashing