Broad Phase 算法简介

Broad Phase 算法简介

物理引擎通常将碰撞检测分为两(三)个阶段，Broad Phase & Narrow Phase (& Mid Phase)，其中，Broad Phase 通常使用某种Bounding Volume (Sphere,AABB,OBB,Convex Hull等)来作为物体的碰撞体来简化计算。而Narrow Phase则使用物体真实的碰撞体，进行物体是否碰撞与碰撞点的求解，将数据发送给后续的Resolve Phase。

一般地，使用的Bounding Volume 越精确，False Positive 就越少。在上述列举的几种包围体中，精确度大概是凸包>OBB>AABB约等于球。

本文介绍Broad Phase几种常见的算法与数据结构。重点介绍其中的SAP(Sweep And Prune)算法

Space Partioning Data Structures & Bounding Volume Hierarchy

考虑这样一个情形：假设我们要对全世界所有的人进行碰撞检测，那么我们显然没有必要检测一个在北京的人与另一个在深圳的人的碰撞：这两个人离得太远了，根本不可能发生碰撞。

尝试将这种思想应用进物理引擎中，就诞生了两类数据结构：空间划分树/BVH(Bounding Volume Hierarchy)树。

空间划分树将空间递归地划分为若干部分，常见的空间划分数据结构有四叉树/八叉树/kDTree等。

BVH与空间划分树不同，它将若干包围体组成一个层次结构(Hierarchy)而非对空间进行划分。

这两类数据结构实际实现起来有很多很多的细节可以讲，例如四叉树/八叉树为了适应频繁移动物体需要一些trick，BVH的构建方法等，但它们不是本文的重点。

Uniform Grid(均匀网格)也是一种空间划分数据结构，它将在接下来的Multi-SAP,MBP等算法出现😀

SAP Algorithm & Variants

终于来到本文的重点:SAP算法。

SAP使用最简单的包围盒之一AABB (Axis-Align Bounding Box)作为碰撞检测的对象。注意到两个AABB相交当且仅当它们在x,y,z轴上的投影都相交。因此我们可以把$n$个AABB两两相交问题转化为一轴上$n$条线段的两两相交问题。

容易发现，如果直接对$n$个AABB两两碰撞检测，时间复杂度为$O(n^2)$。

Sweeping Plane Algorithm(Brute Force SAP)

我们先从最简单的情况考虑。假设$n$个AABB已经被投影到某一轴上，如何判断两两相交情况？

考虑ACM/OI中的差分算法：从左到右扫描，维护还未结束的线段列表。这就是Brute Force SAP的思路。

算法主要流程如下：

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

Brute Force SAP的时间复杂度即为投影+扫描+排序+输出的复杂度，即在平均情况下(最劣情况很少出现，因此本文仅考虑平均情况下的时间/空间复杂度)为$O(n\log n)$。

为了方便理解，这里举一个例子来说明Brute Force SAP的运行过程。

BFSAP

(source:https://github.com/phenomLi/Blog/issues/22)

TODO

SAP Description　

Brute Force SAP能较好地处理很多情况下的碰撞检测。但它在一些情况下还是很慢。它有几个很显著的缺点：

每一帧都要独立地做一次碰撞检测，没有利用好之前的信息，使得算法复杂度不优秀。
投影轴的选取影响性能，如下图，如果使用x轴作为投影轴，和完全的暴力算法没有明显区别。

BFD

那么，如何改进呢？

考虑实际物体的物理过程，一般地，由于物体的速度相对不大，物体的位置在两帧之间不会有太大变化。

我们把这种特性叫做帧相关性(frame coherence)

由于帧相关性，实际排序的时候物体的位置变化不大，因此我们需要一种在序列接近有序的时候复杂度较小的排序算法，我们知道，插入排序（Insertion Sort）在序列接近有序时的复杂度为$O(n)$，因此，我们可以选择插入排序作为我们的排序算法。

insertionsort

由于插入排序有不同的实现方式，在本文中，插入排序特指在双重循环中，每次比较相邻两个数，如果前者较大就交换并继续比较，否则结束本层循环的算法实现。

接下来，考虑Brute Force SAP的三个阶段：投影 -> 排序 -> 扫描相交。我们能否设计一种算法能够利用好帧相关性，在上一帧存储一些信息共下一帧使用，而非帧帧独立计算，来简化这三个步骤呢？我们注意到，我们没有必要每帧都进行扫描，线段是否相交只与它们的相对位置关系有关，如果排序没有改变线段端点的相对位置，我们自然没有必要更新碰撞对的列表。我们只需要在插入排序发生交换时更新碰撞对。

如下图所示：[]中的数字表示线段编号，*表示线段端点，其旁边的数字表示端点编号。u

0*——[0]—*2 3*——[1]—*5

1*——-[2]——-*4

假设 2 号线段在移动

若它的1号端点(左端点)越过了 0 号线段的右端点，则 0与2停止相交
若它的1号端点(左端点)越过了 1 号线段的左端点，则无事发生
若它的3号端点(右端点)越过了 1 号线段的左端点，则 1与2开始相交
若它的3号端点(右端点)越过了 1 号线段的左端点，则无事发生

由于运动的相对性，这四种情况能够概括所有情况。

这种在排序发生交换时更新碰撞的增量式算法，就是SAP(Sweep And Prune)算法。由D. Baraff于1992年的博士论文中提出(D. Baraff. Dynamic Simulation of Non-Penetrating Rigid Bodies. PhD thesis, Cornell University, 1992)。

From 1D to 3D

在Brute force SAP 中，我们只使用了一个轴作为扫描轴，并没有使用其他的轴上的信息。但在SAP中不同，我们必须更新三个轴上的信息，由于缓存友好性，通常使用再做一次单独的AABB碰撞检测的方法。（因为我们可以直接比较AABB表上的数组index，这样根本不用访问区间端点坐标，不会污染缓存）。

SAP Data Structures & Implementation Details

我们讨论用何种数据结构实现SAP以及实现中的一些细节。

我们使用多个数组/链表存贮AABB编号，区间信息。一般情况下，我们使用数组，因为数组形式更缓存友好(cache-friendly)。其中，每个AABB存储x,y,z坐标的引用(在x,y,z轴区间坐标的index)。对于每个区间端点，我们存储它的坐标以及是左端点还是右端点。phsyx等现代物理引擎通常使用坐标分出1bit来存贮这个信息。

当向场景添加一个AABB时，我们需要做三件事：1、分配空间 2、使线段端点插入到正确位置 3、更新碰撞对集合。一个小trick是将新添加的AABB放在充分远处(即区间数组的末尾)，再更改其坐标使之移动到正确位置。

当在场景中删除一个AABB时，与更新类似，我们可以先将AABB移到充分远处，再删除之。

当我们一次性在场景中添加多个物体时，我们可以考虑以下技巧(Batch Insertion)：相比于一个一个添加，我们可以先将插入物体的端点列表排好序，这样一次插入$m$个物体的时间复杂度为$O(n)$,其中$n$为现有物体数量，而非一个一个插入的$O(mn)$。

SAP Complexity Analysis

在D. Baraff的原论文中，他给出了O(n+s)的复杂度时间，其中，n为AABB的数量，s为在一次排序中交换的次数。我们尝试进一步详细分析SAP的时间复杂度。

考虑SAP的更新过程，我们可以分析出，SAP的时间复杂度为O(u+s+e+mn+o) 其中，u为移动AABB的数量，e为需更新AABB对的数量，s为一次排序中交换的次数，m为插入删除AABB数量，o为碰撞AABB对的总数(输出所需时间)。在物体均匀分布时可以给出$s$与$n$的关系，$s=n^{1-\frac1k}$,$k$为维度，$k=2$即2D时，时间复杂度为$O(n^{1.5})$，3D时复杂度约为$O(n^{1.66})$。

FAQ

（其实是我自己看论文时的一些疑问，经过思考之后想明白的）

-Ｑ：既然我们比较一个轴上的信息之后，直接进行一次完整的AABB检测，为什么还有维护3个轴的信息？直接维护一个轴不就行了？

-A：如果只保存一个轴的信息，不妨设为x轴，由于SAP是增量式算法，当物体在x轴上的投影不动，但在y轴，z轴上移动时，我们就不知道了。

Multi-SAP & Multi Box Pruning

Design Issues and Drawbacks of SAP

SAP算法也有一些缺点：

(a)如图所示，红色物体在y轴上移动，两个在x轴上与红色物体离得很远，静止不动，显然红色物体与蓝色物体不可能发生碰撞，但由于它们的投影在y轴上相交，当红色物体在y轴上运动时，它们的相对位置发生频繁改变，使得SAP算法频繁触发碰撞检测。这使得SAP本身的优势荡然无存。

(b) SAP插入一次物体所需的时间为O(n),即使使用批量插入方法，在AABB的数量较大时，SAP的性能仍然不优秀。

SAPD

一个很自然的想法是：将SAP与空间划分数据结构结合，在每个小区域内部使用SAP，

这就是Multi-SAP算法。

MSAP

如上图所示：我们使用均匀网格作为空间划分数据结构。我们将空间划分为4份，在每份中单独使用SAP算法。对于那些落在边线上的点，我们将它们在出现过的区域都复制一份。

Multi-SAP可以分为三步：分配到网格中 -> 独立执行SAP -> 合并结果。如果空间划分数据结构过于复杂，会造成分配和收集的困难，得不偿失。

Multi Box Pruning

Multi-SAP的加速思路对Box Pruning 算法也适用。(Box Pruning 即为非增量式，只有一个投影轴的SAP)，这就是Multi Box Pruning算法。它与Multi-SAP的区别仅在于每个小空间中使用的是SAP还是Box Pruning。

MBP算法有优点也有缺点：

优点：

每个小空间中物体数量很少，这使得Box Pruning执行的速度很快。
第二部独立执行Box Pruning的步骤可以很方便地并行化。

缺点：

需要给定世界边界以及网格划分的参数。而额外的参数增加了调优难度。如果参数设置不好，一般效果不如SAP。
对于大型物体，它可能被分配到很多网格之中，这使得检测时间增加。通常，对于大型的静止物体，物理引擎会单独处理它与其它物体的碰撞，不用SAP/MBP而是使用BVH等

Broad Phase Algorithms in Physx & Unity

doc

如上图所示，Unity使用了Physx作为自己的底层物理引擎。而Physx有三种Broad Phase Algorithm，除了我们前面提到过的SAP和MBP之外，还有一种ABP(Automatic Box Pruning)。ABP在MBP的基础上，可以自动的设置世界边界以及网格参数。实践中，ABP表现相当优秀。

另外，Physx的API中，对于MBP可以自己增加任意区域，但在Unity中的MBP只能设置世界边界以及世界x轴和z轴上均匀网格的数量。这就更加不推荐在Unity中使用MBP Broad Phase了。

Reference

1、Real-Time Collision Detection——Christer Ericson

2、http://www.codercorner.com/SAP.pdf

3、Efficient Large-Scale Sweep and Prune Methods with AABB Insertion and Removal Daniel J. Tracy et. al.

除另有声明外，本博客文章均采用知识共享(Creative Commons) 署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行许可。

Broad Phase算法简介