粗检测阶段（一）：Sweep and Prune 算法

phenomLi commented 5 years ago

什么是粗检测

上一篇我们介绍了 AABB 的概念，我们可以使用 AABB 快速筛去根本不可能发生碰撞的物体，然而即使 AABB 相交检测很快，我们也不能为对每一个 AABB 进行两两相交检测，因为假如我们有 100 个物体，就需要 100 * 100 次的两两 AABB 相交检测，即使我们使用某种优化手段跳过已经检测过的 AABB 对，也需要至少 5000 多次的检测。在性能要求如此高的物理模拟中，这显然是不能接受的。我们必须在进行精确的碰撞检测前，找到一种方法来快速筛选可能相交的 AABB 对，降低检测 AABB 的规模，这个阶段就叫做粗检测阶段。

比如说，我们现在场景下有 6 个 AABB：

从这个图我们可以看出，由于 AABB 都是散落在空间的不同位置，即 AABB 间有着不同的空间距离，因此我们根本不需对其进行两两检测，比如说图中的 AABB1 和 AABB6 由于相隔太远，不可能发生接触。

粗检测算法有许多种，而这些算法基本都利用了这种思想。

Sweep and Prune

Sweep and Prune 算法又称扫描剪枝算法，是一种碰撞检测系统的粗检测阶段算法。该算法的核心思想是：如果两个 AABB 重叠，那么这两个 AABB 在 x，y 轴上的投影必定也是重叠的。怎么理解这句话呢？看下面的图。

一个 AABB 投影在一个轴上就变成了一条直线，那么假如两个 AABB 相交，那么其在 x，y 上的投影出的两条直线必定会重叠。如果不相交，那么起码有一个轴上，两投影直线不重叠，因此，我们只需检测某条轴上投影相交的 AABB 对即可。Sweep and Prune 算法利用这个特性，将二维的 AABB 问题降到一维的直线问题。

选取用作投影的轴，x，y 都可，通常使用的是x轴。然后将所有AABB包围盒投影到投影轴上。我们需要用 s（start）和 e（end）表示投影线段的区间端点，为此我们还需要一个活动队列 L 来保存当前未闭合的区间。

算法主要流程如下：

将所有 AABB 投影至特定轴上
对轴上所有区间端点进行升序排序
从小到大扫描投影轴
遇到一个开始端点 s(i) ，将 s(i) 所属的 AABB(i) 与 L 中的所有 s 所属的 AABB 进行相交检测, 并将 S(i) 加入至 L
遇到一个结束端点 e(i) ，将与同属 e(i) 同属一个AABB 的 s(i) 从 L 中移除

我本人推荐使用插入排序对区间端点进行排序。

我们取文章开头的情境为例子，我们将 6 个 AABB 投影到 x 轴上，得到：

之后，我们从左往右扫描，检测区间端点。下图一步步展示了算法的运行细节：

可以看到，Sweep and Prune 在 6 个 AABB 的情况下，只进行了 4 次相交检测。假如场景中 AABB 均匀分布，Sweep and Prune 往往会有不错的效率。

然而，在某些情况下，投影轴的选取会影响 Sweep and Prune 的性能，甚至退回到两两检测的最坏情况，比如说：

假如在这种情况下选择 x 轴作为投影轴，那么 Sweep and Prune 的优势就会大打折扣，这时理想的投影轴应该是y轴。

为什么是插入排序？

上面在对区间端点进行排序时，我提到了插入排序，为什么？

在物理模拟中，我们绝大多数的情境都是低速情境，也就是物体在两帧之间不会有太大变化。同样，对于位置改变，同一物体在两帧之间可能只有微小的移动。

这种现象叫帧相干性（frame coherence）。利用这个特性，可以对物理引擎做各种的优化。因为两帧之间 AABB 的前后位置变化不大，因此在进行了第一次排序后，之后的任意一次排序都可认为是近乎有序情况下的排序。在近乎有序情况下，插入排序算法的复杂度为 O(n*k) 的线性复杂度，因此获得了性能优化。当然，堆排序也是可行的，只是插入排序比较简单易于实现。