这是我们关于电子游戏物理的三部分系列的第二部分. 有关本系列的其余部分，请参见:

第一部分:刚体动力学介绍
第三部分:约束刚体仿真

---

在本系列的第一部分中，我们探讨了刚体及其运动. 然而，在那个讨论中，对象之间不相互作用. 没有额外的功，模拟的刚体可以直接穿过彼此, or “interpenetrate”, 在大多数情况下，哪种情况是不可取的.

为了更真实地模拟实体物体的行为, 我们必须检查它们每次移动时是否会相互碰撞, and if they do, 我们必须做点什么, 比如施加改变它们速度的力, 这样它们就会朝相反的方向运动. 这就是理解碰撞物理特别重要的地方 game developers.

In Part II, 我们将介绍碰撞检测步骤, 它包括在可能分散在2D或3D世界中的大量物体中寻找成对碰撞的物体. In the next, and final, installment, 我们将更多地讨论如何“解决”这些碰撞以消除互穿.

对于本文中提到的线性代数概念的回顾，您可以参考 线性代数速成班第一部分.

电子游戏中的碰撞物理

在刚体模拟的背景下, 当两个刚体的形状相交时，就会发生碰撞, 或者当这些形状之间的距离小于一个小公差时.

If we have n bodies in our simulation, 用两两检验检测碰撞的计算复杂度为 O(n2)这个数字让计算机科学家们感到畏缩. 成对试验的次数随物体的数量呈二次增长, 确定两个形状, 在任意位置和方向, 是不是碰撞已经不便宜了. 为了优化碰撞检测过程，我们一般将其分为两个阶段: broad phase and narrow phase.

宽相负责寻找刚体对 potentially colliding, 排除那些没有碰撞的对, 从模拟的所有身体中选出. 这个步骤必须能够很好地与刚体的数量相匹配以确保我们保持在 O(n2) time complexity. 为了达到这个目的，这个阶段通常使用 space partitioning coupled with bounding volumes 建立了碰撞的上界.

窄相作用于宽相发现的可能发生碰撞的刚体对. 这是一个改进的步骤，我们确定碰撞是否真的发生了, 对于每一次发现的碰撞, 我们计算稍后将用于解决碰撞的接触点.

在接下来的章节中，我们将讨论一些可以用于宽相位和窄相位的算法.

Broad Phase

在电子游戏碰撞物理的广泛阶段，我们需要确定哪些刚体对 might be colliding. 这些物体可能有复杂的形状，比如多边形和多面体, 为了加速，我们可以用一个更简单的形状来包裹这个物体. If these bounding volumes 不相交，那么实际的形状也不相交吗. 如果它们相交，那么实际的形状 might intersect.

一些流行的边界体类型是定向边界盒(OBB)。, circles in 2D, and spheres in 3D. 让我们来看一个最简单的边界体积: 轴向边界框(AABB).

aabb从物理程序员那里得到了很多的喜爱，因为它们很简单，并且提供了很好的权衡. 在C语言中，二维AABB可以用这样的结构体表示:

typedef struct {
    float x;
    float y;
} Vector2;

typedef struct {
    Vector2 min;
    Vector2 max;
} AABB;

The min 字段表示框的左下角的位置 max 字段表示右上角.

测试两个aabb是否相交, 我们只需要找出它们的投影是否在所有坐标轴上相交:

BOOL testabboverlap (AABB* a, AABB* b)
{
    float d1x = b->min.x - a->max.x;
    float d1y = b->min.y - a->max.y;
    float d2x = a->min.x - b->max.x;
    float d2y = a->min.y - b->max.y;

    if (d1x > 0.0f || d1y > 0.0f)
        return FALSE;

    if (d2x > 0.0f || d2y > 0.0f)
        return FALSE;

    return TRUE;
}

的逻辑相同 b2TestOverlap function from the Box2D engine (version 2.3.0). 它计算两者之间的差 min and max 在两个轴上，在两个顺序上. 如果这些值中的任何一个大于零，则aabb不相交.

尽管AABB重叠测试很便宜, 如果我们仍然对每一对可能的配对进行两两测试，这不会有多大帮助，因为我们仍然有不希望看到的结果 O(n2) time complexity. 为了最小化AABB重叠测试的数量，我们可以使用某种 space partitioning，它的工作原理与 database indices that speed up queries. (地理数据库，如 PostGIS，实际上它们的空间索引使用类似的数据结构和算法.) In this case, though, aabb会不停地移动, so generally, 我们必须在模拟的每一步之后重新创建索引.

有很多空间划分算法和数据结构可用于此, such as uniform grids, quadtrees in 2D, octrees in 3D, and spatial hashing. 让我们仔细看看两种流行的空间划分算法:排序和扫描, 和边界卷层次结构(BVH).

排序和扫描算法

The sort and sweep 方法(或称为 sweep and prune)是物理程序员最喜欢的选择之一，用于刚体模拟. The Bullet Physics 引擎中有此方法的实现 btAxisSweep3 class.

一个AABB在一个坐标轴上的投影本质上是一个区间 [b, e] (即开始和结束). 在我们的模拟中，我们有很多刚体，因此，有很多aabb，这意味着很多间隔. 我们想找出哪些区间是相交的.

在排序和扫描算法中，我们插入所有 b and e 单个列表中的值，并按其标量值升序排序. Then we sweep or traverse the list. Whenever a b 值时，其对应的间隔存储在一个单独的列表中 active intervals, and whenever an e 值，则从活动间隔列表中删除其对应的间隔. 在任何时刻，所有的活动区间都是相交的. (Check out David Baraff’s Ph. D Thesis, p. 52 for details. I suggest using this online tool 查看postscript文件.)间隔列表可以在模拟的每个步骤上重复使用, 在哪里我们可以有效地重新排序这个列表 insertion sort，它擅长对几乎排序的列表进行排序.

在二维和三维空间, 运行排序和扫描, as described above, 将减少必须执行的直接AABB交叉测试的次数, 但在一个坐标轴上的收益可能比另一个坐标轴上的收益更好. 因此，实现了更复杂的排序和扫描算法的变体. In his book 实时碰撞检测 (page 336), Christer Ericson提出了一种有效的变体，他将所有aabb存储在单个数组中, 对于每一次这样的跑和扫, 选择一个坐标轴，并按 min 所选轴中aabb的值，使用 quicksort. 然后，遍历数组并执行AABB重叠测试. 要确定应用于排序的下一个轴，请使用 variance 计算了aabb的中心位置, 然后选择方差较大的轴进行下一步.

动态边界体树

另一种有用的空间划分方法是 动态边界卷树, also known as Dbvt. This is a type of 边界体层次结构.

Dbvt是一个二叉树，其中每个节点都有一个AABB，该AABB约束了其子节点的所有AABB. 刚体本身的aabb位于叶节点中. 通常，通过给出我们想要检测交集的AABB来“查询”Dbvt. 该操作是高效的，因为不与所查询的AABB相交的节点的子节点不需要测试重叠. As such, AABB冲突查询从根开始, 并且只在与查询的AABB相交的AABB节点上继续递归地遍历树. 这棵树可以保持平衡 tree rotations, as in an AVL tree.

中的Dbvt有一个复杂的实现 b2DynamicTree class. The b2BroadPhase class 负责执行广泛阶段，并且它使用的实例 b2DynamicTree to perform AABB queries.

Narrow Phase

在电子游戏碰撞物理的广泛阶段之后, 我们有一组刚体 potentially colliding. Thus, for each pair, given the shape, 两个物体的位置和方向, 我们得弄清楚他们是不是, in fact, colliding; if they are intersecting or if their distance falls under a small tolerance value. 我们还需要知道碰撞物体之间的接触点是什么, 因为这是以后解决冲突所需要的.

Convex and Concave Shapes

作为电子游戏物理的一般规则, 确定两个任意形状是否相交并不容易, 或者计算它们之间的距离. 然而，有一个属性对决定它的难度至关重要，那就是 convexity of the shape. Shapes can be either convex or concave 凹形更难处理，所以我们需要一些策略来处理它们.

In a convex shape, 形状内任意两点之间的线段总是完全落在形状内. 但是对于凹(或“非凸”)形状, 对于形状中连接点的所有可能线段，情况并非如此. 如果你能找到至少一条线段落在形状之外, then the shape is concave.

Computationally, 在模拟中，所有的形状都是凸的是理想的, 因为我们有很多强大的距离和相交测试算法，可以处理凸形状. 但并不是所有的对象都是凸的, 通常我们用两种方法来解决它们:凸包和凸分解.

The convex hull 一个形状是完全包含它的最小的凸形状. 对于二维凹多边形, 这就像在每个顶点上钉一颗钉子，然后在所有钉子上缠上橡皮筋. 计算多边形或多面体的凸壳, or more generally, for a set of points, 一个很好的算法是 quickhull 算法，其平均时间复杂度为 O(n log n).

Obviously, 如果我们用一个凸壳来表示一个凹物体, 它会失去凹的特性. Undesirable behavior, 比如“幽灵”碰撞可能会变得明显, 因为对象仍然会有一个凹的图形表示. For example, 汽车通常呈凹形, 如果我们用一个凸包来表示它，然后在上面放一个盒子, 盒子可能看起来像是漂浮在上面的空间里.

In general, 凸壳通常足以表示凹物体, 要么是因为不现实的碰撞不是很明显, 或者它们的凹特性对于任何模拟都不是必需的. In some cases, though, 我们可能想让凹物体在物理上表现得像凹形状. For example, 如果我们用一个凸壳来代表一个碗, 我们不能在里面放任何东西. 物体会浮在上面. 在这种情况下，我们可以用a convex decomposition of the concave shape.

凸分解算法接收一个凹形状，并返回一组凸形状，这些凸形状的并集与原始凹形状相同. 有些凹形只能用大量的凸形来表示, 计算和使用这些可能会变得非常昂贵. 然而，一个近似通常是足够好的，因此，算法，如 V-HACD 由一个凹多面体产生一小组凸多面体.

然而，在许多碰撞物理情况下，凸分解可以由艺术家手工制作. 这消除了分解算法对性能的影响. 因为性能是实时仿真中最重要的方面之一, 为复杂的图形对象创建非常简单的物理表示通常是个好主意. 下图显示了使用9个凸形状的2D汽车的一种可能的凸分解.

交叉点的测试-分离轴定理

The separating axis theorem (SAT)指出，当且仅当存在至少一个轴，在该轴上的形状的正交投影不相交时，两个凸形状不相交.

在2D中找到一条线或在3D中找到一个分离这两个形状的平面通常在视觉上更直观, though, 这实际上是相同的原则吗. 一个与二维直线正交的向量, 或者三维平面的法向量, 可作为“分离轴”.

Game physics engines 有许多不同种类的形状, 比如圆(3D中的球体), 边缘(单线段), 和凸多边形(3D中的多面体). 对于每一对形状类型，它们都有特定的碰撞检测算法. 其中最简单的可能是圆-圆算法:

typedef struct {
    float centerX;
    float centerY;
    float radius;
} Circle;

bool CollideCircles(圆圈*cA，圆圈*cB) {
    float x = cA->centerX - cB->centerX;
    float y = cA->centerY - cB->centerY;
    float centerDistanceSq = x * x + y * y; // squared distance
    float radius = cA->radius + cB->radius;
    float radiusSq = radius * radius;
    return centerDistanceSq <= radiusSq;
}

尽管SAT适用于圆圈, 检查它们中心之间的距离是否小于它们半径的和要简单得多. For that reason, 在碰撞检测算法中对特定的形状类对使用SAT, 例如凸多边形对凸多边形(或3D中的多面体).

对于任何一对形状，都有无限多的轴可以测试分离. 因此，确定首先测试哪个轴对于有效的SAT实现至关重要. Fortunately, 当测试一对凸多边形是否碰撞时, 我们可以使用边缘法线作为潜在的分离轴. The normal vector n 一条边垂直于边向量，并点在多边形外. 对于每个多边形的每条边，我们只需要找出其他多边形的所有顶点是否都是 in front of the edge.

如果任何测试通过-也就是说，如果，对于任何边，其他多边形的所有顶点都是 in front 那么多边形就不会相交. 线性代数为这个测试提供了一个简单的公式:在第一个带有顶点的形状上给定一条边 a and b and a vertex v on the other shape, if (v - a) · n 大于0，那么顶点在边的前面.

For polyhedrons, 我们可以使用面法线，也可以使用每个形状的所有边缘组合的叉乘. That sounds like a lot of things to test; however, to speed things up, 我们可以缓存我们使用的最后一个分离轴，并在接下来的模拟步骤中再次尝试使用它. 如果缓存的分隔轴不再分隔形状, 我们可以从与前一个面或边相邻的面或边开始搜索新的轴. 这是有效的，因为身体通常不会在步骤之间移动或旋转太多.

Box2D在其多边形-多边形碰撞检测算法中使用SAT检测两个凸多边形是否相交 b2CollidePolygon.cpp.

计算距离- Gilbert-Johnson-Keerthi算法

在很多碰撞物理情况下, 我们想要考虑物体的碰撞，而不仅仅是当它们相交的时候, 但如果它们彼此非常接近, 这要求我们知道它们之间的距离. The Gilbert-Johnson-Keerthi (GJK)算法计算两个凸形状之间的距离以及它们最近的点. 它是一种优雅的算法，通过支持函数对凸形状进行隐式表示, Minkowski sums, and simplexes, as explained below.

Support Functions

A support function sA(d) 返回形状边界上的一个点 A 它在向量上的投影最大 d. 数学上，它的点积是最高的 d. This is called a support point，这种操作也被称为 support mapping. 在几何上，这一点是形状上在方向上最远的点 d.

在多边形上找到支撑点相对容易. 对于向量的支撑点 d你只需要遍历它的顶点，找到与它点积最大的那个点 d, like this:

Vector2 GetSupport(Vector2 *顶点，int count, Vector2 d) {
    float highest = -FLT_MAX;
    Vector2支持= (Vector2){0,0};

    for (int i = 0; i < count; ++i) {
        Vector2 v = vertices[i];
        float dot = v.x * d.x + v.y * d.y;

        if (dot > highest) {
            highest = dot;
            support = v;
        }
    }

    return support;
}

However, 支持函数的真正强大之处在于，它可以很容易地处理诸如锥体之类的形状, cylinders, and ellipses, among others. 直接计算这些形状之间的距离是相当困难的, 如果没有像GJK这样的算法，你通常不得不将它们离散成一个多边形或多面体来简化事情. However, 这可能会导致进一步的问题，因为多面体的表面不像表面那么光滑, say, a sphere, 除非多面体非常详细, 在碰撞检测期间，哪些会导致性能不佳. Other undesirable side effects might show up as well; for example, 一个“多面体”球体可能不会平滑地滚动.

为了得到一个以原点为中心的球体的支撑点，我们只需要规范化 d (that is, compute d / ||d||，它是一个长度为1(单位长度)的向量，仍然指向相同的方向 d)，然后乘以球半径.

Check Gino van den Bergen的论文 查找柱体和锥体以及其他形状的支持函数的更多示例.

Our objects will, of course, 在模拟空间中从原点被移动和旋转, 因此，我们需要能够计算一个变换形状的支撑点. We use an affine transformation T(x) = Rx + c 移动和旋转我们的对象，其中 c 位移向量是和吗 R is the rotation matrix. 这个变换首先围绕原点旋转对象，然后对其进行平移. 变换形状的支持函数 A is:

Minkowski Sums

The Minkowski sum of two shapes A and B is defined as:

这意味着我们计算包含的所有点的和 A and B. The result is like inflating A with B.

Similarly, we define the Minkowski difference as:

我们也可以把它写成闵可夫斯基和 A with -B:

For convex A and B, A⊕B is also convex.

闵可夫斯基差分的一个有用的性质是如果它包含空间的原点, the shapes intersect, 如上图所示. Why is that? 因为如果两个形状相交, 他们至少有一个共同点, 它们在空间的同一位置, 它们的差就是0向量, 哪个才是真正的原点.

闵可夫斯基差异的另一个很好的特征是如果它不包含原点, 原点与闵可夫斯基差之间的最小距离是形状之间的距离.

两个形状之间的距离定义为:

也就是说，两者之间的距离 A and B 最短向量的长度是多少 A to B. 这个向量包含在 A⊖B 它的长度是最小的，也就是离原点最近的.

明确地建立两个形状的闵可夫斯基和通常并不简单. 幸运的是，我们也可以在这里使用支持映射，因为:

Simplexes

GJK算法迭代地搜索Minkowski差上最接近原点的点. 它通过建立一系列 simplexes 在每次迭代中更接近原点. 一个简单的，或者更具体地说，一个 k-simplex for an integer k – is the convex hull of k + 1 affinely independent k维空间中的点. That is, if for two points, they must not coincide, 另外，对于三个点，它们不能位于同一条线上, 如果有四个点它们也不能在同一平面上. Hence, the 0-simplex is a point, 单形是一条线段, 2-单纯形是一个三角形，3-单纯形是一个四面体. 如果我们从单纯形中移除一个点，我们将其维数减少1, 如果我们把一个点加到单纯形上我们把它的维数增加1.

GJK in Action

让我们把这些放在一起看看GJK是如何工作的. 确定两个形状之间的距离 A and B，我们从它们的闵可夫斯基差开始 A⊖B. 我们正在搜索结果形状上离原点最近的点, 因为到这一点的距离就是原来两个形状之间的距离. We choose some point v in A⊖B，这就是距离近似值. 我们还定义了一个空点集 W，它将包含当前测试单纯形中的点.

Then we enter a loop. 我们从支撑点开始 w = sA⊖B(-v), the point on A⊖B whose projection onto v is closest to the origin.

If ||w|| 没有太大的不同 ||v|| 它们之间的夹角变化不大(根据一些预定义的公差), 这意味着算法已经收敛，我们可以返回 ||v|| as the distance.

Otherwise, we add w to W. If the convex hull of W (即单纯形)包含原点，形状相交，这也意味着我们完成了. 否则，我们在单纯形中找到离原点最近的点，然后重置 v 得到这个新的最接近的近似. 最后，我们移除所有的点 W 对最近点计算没有贡献. (For example, if we have a triangle, 离原点最近的点在它的一条边上, 我们可以把这个点从 W 它不是这条边的顶点.)然后我们重复这些相同的步骤，直到算法收敛.

下一个图像显示了GJK算法的四次迭代的示例. 蓝色的物体代表闵可夫斯基差 A⊖B and the green vector is v. You can see here how v 瞄准离原点最近的点.

有关GJK算法的详细而深入的解释，请查看该论文 凸物体碰撞检测的快速鲁棒GJK实现, by Gino van den Bergen. The blog for the dyn4j 物理引擎也有一个 great post on GJK.

Box2D中有GJK算法的实现 b2Distance.cpp, in the b2Distance function. 它只在连续碰撞检测算法的碰撞计算期间使用GJK(我们将在后面讨论这个主题)。.

Chimpunk物理引擎使用GJK进行所有的碰撞检测，它的实现已经完成 cpCollision.c, in the GJK function. 如果GJK算法报告交集, 它仍然需要知道接触点是什么, 以及穿透深度. 要做到这一点，它使用扩展多边形算法，我们将在接下来探索.

确定穿透深度-扩展多边形算法

如上所述，如果形状 A and B 相交，GJK会生成单纯形吗 W 在闵可夫斯基差中包含原点 A⊖B. At this stage, 我们只知道这些形状相交, 但在许多碰撞检测系统的设计中, 我们希望能够计算出有多少个交点, 哪些点可以作为接触点, 这样我们就能以一种真实的方式处理碰撞. The 扩展多边形算法 (EPA)允许我们获得这些信息, 从GJK停止的地方开始:使用包含原点的单纯形.

The penetration depth is the length of the 最小平移矢量 (MTV), 哪一个向量是最小的，我们可以沿着它平移一个相交的形状，把它和另一个形状分开.

当两个形状相交时, 它们的闵可夫斯基差包含了原点, 闵可夫斯基差边界上最接近原点的点是MTV. The EPA algorithm finds that point by expanding the simplex that GJK gave us into a polygon; successively subdividing it’s edges with new vertices.

First, 我们找到最接近原点的单纯形的边, 在与边缘垂直的方向上计算闵可夫斯基差中的支撑点.e. 垂直于它并指向多边形外). 然后我们通过添加支撑点来分割这条边. 我们重复这些步骤，直到向量的长度和方向变化不大. 一旦算法收敛，我们就有了MTV和渗透深度.

GJK与EPA联合使用, 我们得到了碰撞的详细描述, 不管物体是否已经相交, 或者接近到足以被认为是碰撞.

本文介绍了EPA算法 三维游戏对象的接近查询和穿透深度计算，也是吉诺·范登·卑尔根写的. The dyn4j blog also has a post about EPA.

连续碰撞检测

到目前为止，视频游戏物理技术为模拟的静态快照执行碰撞检测. This is called 离散碰撞检测，它忽略了之前和当前步骤之间发生的事情. 由于这个原因，某些碰撞可能无法检测到，特别是对于快速移动的物体. This issue is known as tunneling.

连续碰撞检测技术试图找到 when 两个物体在模拟的前一个步骤和当前步骤之间碰撞. They compute the time of impact，这样我们就可以回到过去，处理那个点的碰撞.

撞击时间(或接触时间) tc 两个物体之间的距离是零的瞬间吗. 如果我们能写出两个物体之间的距离随时间的函数, 我们要找的是最小的 root of this function. 因此，冲击计算时间为a root-finding problem.

用于冲击计算的时间, 我们考虑身体在前一步中的状态(位置和方向) ti-1，在当前步骤中 ti. 为了简单起见，我们假设步骤之间是线性运动.

我们把问题简化一下，假设这些形状是圆. For two circles C1 and C2, with radius r1 and r2，它们的质心在这里 x1 and x2 与质心重合(i.e.，它们自然地围绕质心旋转)，我们可以把距离函数写成:

考虑步间的线性运动，我们可以写出如下的函数来表示的位置 C1 from ti-1 to ti

它是一个线性插值 x1(ti-1) to x1(ti). The same can be done for x2. 对于这个区间，我们可以写出另一个距离函数:

令这个表达式等于0，就得到a quadratic equation on t. 根可以直接使用 quadratic formula. 如果两个圆不相交，二次方程就没有解. 如果他们这样做，它可能会导致一个或两个根. 如果只有一个根，则该值为影响时间. If it has two roots, 最小的一个是撞击时间，另一个是圆分离的时间. 注意，这里的撞击时间是一个从0到1的数字. It is not a time in seconds; it is just a number we can use to interpolate the state of the bodies to the precise location where the collision happened.

非圆的连续碰撞检测

写出其他形状的距离函数是很困难的, 主要是因为它们的距离取决于它们的方向. For this reason, 我们通常使用迭代算法，在每次迭代中将对象移动得越来越近，直到它们 close enough 被认为是碰撞的.

The conservative advancement 算法迭代地向前移动物体(并旋转它们). 在每次迭代中，它计算位移的上界. 原始算法在 布莱恩·米尔蒂奇的博士论文 (section 2.3.2)，考虑物体的弹道运动. This paper 由Erwin Coumans(子弹物理引擎的作者)提出了一个更简单的版本，它使用恒定的线速度和角速度.

该算法计算形状之间最接近的点 A and B, 绘制从一个点到另一个点的矢量, 然后把速度投影到这个矢量上来计算运动的上限. 它保证身体上的任何点都不会移动到这个投影之外. 然后将物体向前推进这个量并重复，直到距离落在一个小的容差值之下.

在某些情况下，可能需要太多的迭代才能收敛, for example, 当其中一个物体的角速度太高时.

Resolving Collisions

一旦检测到碰撞, 以一种真实的方式改变碰撞物体的运动是必要的, 比如让它们相互反弹. 在这个理论的下一部分，也是最后一部分, 我们将讨论解决电子游戏中碰撞的一些流行方法.

References

如果你有兴趣深入了解碰撞物理，如碰撞检测算法和技术, the book 实时碰撞检测克里斯特·埃里克森(Christer Ericson)的这本书是必备品.

由于碰撞检测在很大程度上依赖于几何，Toptal的文章 Python中的计算几何:从理论到应用 是一个很好的主题介绍.