视频游戏物理教程 - 第二部分：固体物体的碰撞检测

这是我们关于视频游戏物理的三部分系列的第二部分。 对于本系列的其余部分，请参阅：

第一部分：刚体动力学简介
第三部分：约束刚体模拟

在本系列的第一部分中，我们探索了刚体及其运动。 然而，在那次讨论中，对象并没有相互影响。 如果没有一些额外的工作，模拟的刚体可以直接穿过彼此，或者“相互穿透”，这在大多数情况下是不可取的。

为了更真实地模拟固体物体的行为，我们必须检查它们是否在每次移动时相互碰撞，如果它们发生碰撞，我们必须对此做一些事情，例如施加改变它们速度的力，所以他们会朝相反的方向移动。 这就是理解碰撞物理对游戏开发者来说特别重要的地方。

在第二部分中，我们将介绍碰撞检测步骤，该步骤包括在散布在 2D 或 3D 世界中的可能大量物体之间寻找碰撞的物体对。 在下一期也是最后一期中，我们将更多地讨论“解决”这些碰撞以消除相互渗透。

对于本文中提到的线性代数概念的复习，您可以参考第 I 部分的线性代数速成课程。

电子游戏中的碰撞物理

在刚体模拟的上下文中，当两个刚体的形状相交时，或者当这些形状之间的距离低于一个小的公差时，就会发生碰撞。

如果我们的模拟中有n 个物体，那么通过成对测试检测碰撞的计算复杂度是O ( n 2 ) ，这个数字让计算机科学家畏缩不前。 成对测试的数量随着物体的数量呈二次方增加，并且确定任意位置和方向的两个形状是否发生碰撞已经不便宜了。 为了优化碰撞检测过程，我们一般将其分为两个阶段：宽阶段和窄阶段。

广义阶段负责从模拟中的整组刚体中找到可能发生碰撞的刚体对，并排除肯定不会发生碰撞的刚体对。 这一步必须能够很好地随着刚体的数量而扩展，以确保我们保持在O ( n 2 )时间复杂度之下。 为了实现这一点，这个阶段通常使用空间分区以及为碰撞建立上限的边界体积。

窄相作用于宽相发现的可能发生碰撞的刚体对。 这是一个细化步骤，我们确定碰撞是否实际发生，并且对于发现的每个碰撞，我们计算将用于稍后解决碰撞的接触点。

在接下来的部分中，我们将讨论一些可用于广义阶段和狭义阶段的算法。

宽相

在电子游戏碰撞物理的广泛阶段，我们需要确定哪些刚体对可能发生碰撞。 这些物体可能有复杂的形状，比如多边形和多面体，我们可以做的是用更简单的形状来包围物体。 如果这些包围体不相交，那么实际形状也不会相交。 如果它们相交，那么实际的形状可能会相交。

一些流行的包围体类型是定向包围盒 (OBB)、2D 中的圆和 3D 中的球体。 让我们看一下最简单的包围盒之一：轴对齐包围盒 (AABB) 。

AABB 深受物理程序员的喜爱，因为它们简单且提供良好的权衡。 一个二维的 AABB 可以用 C 语言中这样的结构来表示：

 typedef struct { float x; float y; } Vector2; typedef struct { Vector2 min; Vector2 max; } AABB;

min字段表示框左下角的位置， max字段表示右上角。

要测试两个 AABB 是否相交，我们只需确定它们的投影是否在所有坐标轴上相交：

 BOOL TestAABBOverlap(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; }

此代码与 Box2D 引擎（版本 2.3.0）中的b2TestOverlap函数具有相同的逻辑。 它以两个顺序计算两个轴上两个 AABB 的min和max之间的差异。 如果这些值中的任何一个大于零，则 AABB 不会相交。

尽管 AABB 重叠测试很便宜，但如果我们仍然对每个可能的对进行成对测试，它也无济于事，因为我们仍然有不合需要的O ( n 2 )时间复杂度。 为了最大限度地减少 AABB 重叠测试的数量，我们可以使用某种空间分区，它的工作原理与加快查询的数据库索引相同。 （地理数据库，如 PostGIS，实际上对其空间索引使用类似的数据结构和算法。）但是，在这种情况下，AABB 将不断移动，因此通常我们必须在模拟的每一步之后重新创建索引。

有很多空间划分算法和数据结构可以用于此，例如统一网格、2D 中的四叉树、3D 中的八叉树和空间散列。 让我们仔细看看两种流行的空间分区算法：排序和扫描，以及包围体层次结构 (BVH)。

排序和扫描算法

排序和扫描方法（也称为扫描和修剪）是物理程序员在刚体模拟中最喜欢的选择之一。 例如，Bullet Physics 引擎在btAxisSweep3类中实现了此方法。

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

在排序和扫描算法中，我们将所有b和e值插入到一个列表中，并按它们的标量值升序排序。 然后我们扫描或遍历列表。 每当遇到b值时，其对应的区间就会存储在单独的活动区间列表中，而每当遇到e值时，其对应的区间就会从活动区间列表中删除。 在任何时候，所有活动区间都相交。 （查看 David Baraff 的博士论文，第 52 页了解详细信息。我建议使用此在线工具查看 postscript 文件。）间隔列表可以在模拟的每个步骤中重复使用，我们可以有效地重新排序这个列表使用插入排序，它擅长对几乎排序的列表进行排序。

在二维和三维中，如上所述，在单个坐标轴上运行排序和扫描将减少必须执行的直接 AABB 相交测试的数量，但在一个坐标轴上的回报可能比在另一个坐标轴上更好。 因此，实现了排序和扫描算法的更复杂的变体。 在他的书Real-Time Collision Detection （第 336 页）中，Christer Ericson 提出了一种有效的变体，他将所有 AABB 存储在一个数组中，并且对于每次运行的排序和扫描，选择一个坐标轴，数组按以下方式排序使用快速排序，所选轴中 AABB 的min 。 然后，遍历数组并执行 AABB 重叠测试。 为了确定应该用于排序的下一个轴，计算 AABB 中心的方差，并选择方差较大的轴进行下一步。

动态包围体树

另一种有用的空间划分方法是动态边界体积树，也称为Dbvt 。 这是一种包围体层次结构。

Dbvt 是一棵二叉树，其中每个节点都有一个 AABB，它限制了其子节点的所有 AABB。 刚体本身的 AABB 位于叶节点中。 通常，通过给出我们想要检测交叉点的 AABB 来“查询” Dbvt。 此操作是有效的，因为不与查询的 AABB 相交的节点的子节点不需要进行重叠测试。 因此，AABB 冲突查询从根开始，并且仅针对与查询的 AABB 相交的 AABB 节点递归地继续遍历树。 树可以通过树旋转来平衡，就像在 AVL 树中一样。

Box2D 在b2DynamicTree类中有一个复杂的 Dbvt 实现。 b2BroadPhase类负责执行广泛阶段，它使用b2DynamicTree的一个实例来执行 AABB 查询。

窄相

在视频游戏碰撞物理的广泛阶段之后，我们有一组可能发生碰撞的刚体对。 因此，对于每一对，给定两个物体的形状、位置和方向，我们需要确定它们是否真的发生了碰撞； 如果它们相交或者它们的距离是否低于一个小的公差值。 我们还需要知道碰撞体之间的接触点，因为这是稍后解决碰撞所需要的。

凸面和凹面形状

作为视频游戏物理学的一般规则，确定两个任意形状是否相交或计算它们之间的距离并非易事。 然而，在确定它的硬度方面至关重要的一个属性是形状的凸度。 形状可以是凸形或凹形，而凹形更难处理，因此我们需要一些策略来处理它们。

在凸形中，形状内任意两点之间的线段始终完全落在形状内。 然而，对于凹形（或“非凸形”）形状，对于连接该形状中的点的所有可能线段，情况并非如此。 如果你能找到至少一个完全不在形状之外的线段，那么这个形状就是凹的。

在计算上，希望所有形状在模拟中都是凸的，因为我们有很多强大的距离和相交测试算法可以处理凸形状。 但并非所有对象都是凸的，通常我们以两种方式解决它们：凸包和凸分解。

形状的凸包是完全包含它的最小凸形状。 对于二维的凹多边形，这就像在每个顶点上敲钉子并在所有钉子周围缠绕橡皮筋。 要计算多边形或多面体的凸包，或者更一般地，计算一组点，一个好的算法是quickhull算法，它的平均时间复杂度为O ( n log n ) 。

显然，如果我们用凸包来表示一个凹物体，它就会失去它的凹属性。 诸如“鬼”碰撞之类的不良行为可能会变得明显，因为对象仍将具有凹形图形表示。 例如，汽车通常是凹形的，如果我们用凸包来物理表示它，然后在上面放一个盒子，这个盒子可能看起来像是漂浮在上面的空间中。

通常，凸包通常足以表示凹对象，因为不切实际的碰撞不是很明显，或者它们的凹属性对于所模拟的任何内容都不是必需的。 但是，在某些情况下，我们可能希望让凹形物体在物理上表现得像一个凹形。 例如，如果我们使用凸包来物理表示一个碗，我们将无法在其中放入任何东西。 物体只会漂浮在它上面。 在这种情况下，我们可以使用凹形的凸分解。

凸分解算法接收一个凹形并返回一组凸形，其并集与原始凹形相同。 一些凹形只能用大量的凸形来表示，而这些凸形的计算和使用成本可能会变得过高。 但是，近似值通常足够好，因此，诸如V-HACD 之类的算法会从凹多面体中生成一小组凸多面体。

然而，在许多 collisons 物理案例中，凸分解可以由艺术家手工制作。 这消除了使用分解算法对性能征税的需要。 由于性能是实时模拟中最重要的方面之一，因此为复杂的图形对象创建非常简单的物理表示通常是一个好主意。 下图显示了使用九个凸形对 2D 汽车进行的一种可能的凸分解。

测试交叉点 - 分离轴定理

分离轴定理(SAT) 指出两个凸形不相交当且仅当存在至少一个轴，该轴上的形状的正交投影不相交。

但是，通常在 2D 中找到一条线或在 3D 中找到一条分隔两个形状的平面在视觉上更直观，这实际上是相同的原理。 与 2D 中的线正交的向量，或 3D 中平面的法线向量，可以用作“分离轴”。

游戏物理引擎有许多不同类别的形状，例如圆形（3D 中的球体）、边（单线段）和凸多边形（3D 中的多面体）。 对于每一对形状类型，它们都有特定的碰撞检测算法。 其中最简单的可能是圆环算法：

 typedef struct { float centerX; float centerY; float radius; } Circle; bool CollideCircles(Circle *cA, Circle *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 适用于圆，但检查它们的中心之间的距离是否小于它们的半径之和要简单得多。 出于这个原因，SAT 用于特定形状类对的碰撞检测算法，例如凸多边形与凸多边形（或 3D 中的多面体）。

对于任何一对形状，我们可以测试无数个轴的分离度。 因此，确定首先测试哪个轴对于高效的 SAT 实施至关重要。 幸运的是，当测试一对凸多边形是否碰撞时，我们可以使用边缘法线作为潜在的分离轴。 边的法线向量n垂直于边向量，并且指向多边形之外。 对于每个多边形的每条边，我们只需要找出另一个多边形的所有顶点是否都在边的前面。

如果任何测试通过——也就是说，对于任何边，如果另一个多边形的所有顶点都在它前面——那么多边形不会相交。 线性代数为这个测试提供了一个简单的公式：给定第一个形状的边，顶点a和b ，另一个形状的顶点v ，如果( v - a ) · n大于零，则顶点在前面的边缘。

对于多面体，我们可以使用面法线以及每个形状的所有边组合的叉积。 这听起来需要测试很多东西。 但是，为了加快速度，我们可以缓存我们使用的最后一个分离轴，并在接下来的模拟步骤中再次尝试使用它。 如果缓存的分离轴不再分离形状，我们可以从与前一个面或边相邻的面或边开始搜索新轴。 这是有效的，因为身体在步骤之间通常不会移动或旋转太多。

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

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

在许多碰撞物理案例中，我们想要考虑的对象不仅是它们实际上相交，而且它们彼此非常接近，这需要我们知道它们之间的距离。 Gilbert-Johnson-Keerthi (GJK) 算法计算两个凸形之间的距离以及它们最近的点。 这是一种优雅的算法，通过支持函数、Minkowski 和和单纯形来隐式表示凸形状，如下所述。

支持功能

支持函数s A ( d )返回形状A边界上的一个点，该点在向量d上具有最高投影。 在数学上，它与d的点积最高。 这称为支持点，此操作也称为支持映射。 在几何上，该点是形状上沿d方向的最远点。

在多边形上找到支撑点相对容易。 对于向量d的支持点，您只需遍历其顶点并找到与d具有最高点积的那个，如下所示：

 Vector2 GetSupport(Vector2 *vertices, int count, Vector2 d) { float highest = -FLT_MAX; Vector2 support = (Vector2){0, 0}; for (int i = 0; i < count; ++i) { Vector2 v = vertices[i]; float dot = vx * dx + vy * dy; if (dot > highest) { highest = dot; support = v; } } return support; }

然而，支持函数的真正威力在于它可以轻松处理圆锥、圆柱和椭圆等形状。 直接计算这些形状之间的距离是相当困难的，如果没有像 GJK 这样的算法，您通常必须将它们离散化为多边形或多面体以使事情变得更简单。 但是，这可能会导致进一步的问题，因为多面体的表面不如球体的表面那么光滑，除非多面体非常详细，这可能导致碰撞检测期间的性能不佳。 其他不良副作用也可能出现； 例如，“多面体”球体可能滚动不顺畅。

要获得以原点为中心的球体的支持点，我们只需对d进行归一化（即计算d / || d || ，它是长度为 1（单位长度）的向量，仍然指向同一方向d ) 然后我们将它乘以球体半径。

查看 Gino van den Bergen 的论文以找到更多关于圆柱体和圆锥体以及其他形状的支撑函数示例。

当然，我们的对象会在模拟空间中从原点发生位移和旋转，因此我们需要能够计算变换形状的支撑点。 我们使用仿射变换T ( x ) = R x + c来位移和旋转我们的对象，其中c是位移向量， R是旋转矩阵。 这种变换首先围绕原点旋转对象，然后平移它。 变换后的形状A的支持函数为：

闵可夫斯基和

两个形状A和B的Minkowski 和定义为：

这意味着我们计算A和B中包含的所有点的总和。 结果就像用B膨胀A 。

同样，我们将Minkowski 差定义为：

我们也可以将其写为A与-B的 Minkowski 和：

对于凸A和B ， A⊕B也是凸的。

Minkowski 差异的一个有用特性是，如果它包含空间的原点，则形状相交，如上图所示。 这是为什么？ 因为如果两个形状相交，它们至少有一个共同点，它们在空间中的同一位置，它们的区别是零向量，实际上就是原点。

Minkowski 差异的另一个很好的特点是，如果它不包含原点，则原点和 Minkowski 差异之间的最小距离就是形状之间的距离。

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

换句话说， A和B之间的距离是从A到B的最短向量的长度。 该向量包含在A⊖B中，它是长度最小的向量，因此也是最接近原点的向量。

明确地构建两个形状的 Minkowski 和通常并不简单。 幸运的是，我们也可以在这里使用支持映射，因为：

单纯形

GJK 算法迭代地搜索最接近原点的 Minkowski 差上的点。 它通过在每次迭代中构建一系列更接近原点的单纯形来实现这一点。 单纯形（或更具体地说，整数k的k-单纯形）是 k 维空间中k + 1 个仿射独立点的凸包。 也就是说，如果两点不能重合，三点也不能在同一直线上，如果有四点，它们也不能在同一平面上。 因此，0-单纯形是点，1-单纯形是线段，2-单纯形是三角形，3-单纯形是四面体。 如果我们从单纯形中删除一个点，我们将其维度减一，如果我们将一个点添加到一个单纯形，我们将其维度增加一。

GJK 在行动

让我们把这些放在一起，看看 GJK 是如何工作的。 为了确定两个形状A和B之间的距离，我们首先取它们的 Minkowski 差A⊖B 。 我们正在搜索结果形状上离原点最近的点，因为到该点的距离是原始两个形状之间的距离。 我们在A⊖B中选择一些点v ，这将是我们的距离近似值。 我们还定义了一个空点集W ，它将包含当前测试单纯形中的点。

然后我们进入一个循环。 我们首先得到支持点w = s A⊖B (- v ) ，即A⊖B上投影到v上的点最接近原点。

如果|| w || 和||没有太大区别v || 并且它们之间的角度没有太大变化（根据一些预定义的公差），这意味着算法已经收敛，我们可以返回|| v || 作为距离。

否则，我们将w添加到W 。 如果W的凸包（即单纯形）包含原点，则形状相交，这也意味着我们完成了。 否则，我们在单纯形中找到最接近原点的点，然后我们将v重置为这个新的最接近的近似值。 最后，我们删除了W中任何对最近点计算没有贡献的点。 （例如，如果我们有一个三角形，并且离原点最近的点位于它的一条边上，我们可以从W中删除不是该边的顶点的点。）然后我们重复这些相同的步骤，直到算法收敛。

下图显示了 GJK 算法四次迭代的示例。 蓝色对象表示 Minkowski 差A⊖B ，绿色向量是v 。 你可以在这里看到v如何在离原点最近的点上磨练。

有关 GJK 算法的详细和深入解释，请查看 Gino van den Bergen 的论文A Fast and Robust GJK Implementation for Collision Detection of Convex Objects 。 dyn4j 物理引擎的博客也有一篇关于 GJK 的精彩文章。

Box2D 在 b2Distance.cpp 中的b2Distance函数中实现了 GJK 算法。 它仅在影响计算期间使用 GJK 在其算法中进行连续碰撞检测（我们将进一步讨论这个主题）。

Chimpunk 物理引擎使用 GJK 进行所有碰撞检测，其实现在 cpCollision.c 中的GJK函数中。 如果 GJK 算法报告相交，它仍然需要知道接触点是什么，以及穿透深度。 为此，它使用了扩展多面体算法，我们将在接下来进行探索。

确定穿透深度 - 扩展多面体算法

如上所述，如果形状A和B相交，GJK 将在 Minkowski 差A⊖B内生成包含原点的单纯形W。 在这个阶段，我们只知道形状相交，但是在许多碰撞检测系统的设计中，希望能够计算出我们有多少相交，以及我们可以将哪些点用作接触点，这样我们以现实的方式处理碰撞。 扩展多面体算法(EPA) 允许我们从 GJK 停止的地方开始获取该信息：使用包含原点的单纯形。

穿透深度是最小平移向量(MTV) 的长度，这是我们可以平移相交形状以将其与其他形状分开的最小向量。

当两个形状相交时，它们的闵可夫斯基差包含原点，而闵可夫斯基差边界上离原点最近的点就是MTV。 EPA 算法通过将 GJK 给我们的单纯形扩展为多边形来找到该点； 用新的顶点连续细分它的边缘。

首先，我们找到最接近原点的单纯形的边，并在垂直于边的方向（即垂直于边并指向多边形外部）计算 Minkowski 差中的支持点。 然后我们通过添加这个支持点来分割这条边。 我们重复这些步骤，直到向量的长度和方向没有太大变化。 一旦算法收敛，我们就有了 MTV 和穿透深度。

将 GJK 与 EPA 结合使用，我们可以获得碰撞的详细描述，无论对象是否已经相交，或者只是足够接近以被视为碰撞。

EPA 算法在同样由 Gino van den Bergen 撰写的论文Proximity Queries and Penetration Depth Computation on 3D Game Objects中进行了描述。 dyn4j 博客也有一篇关于 EPA 的文章。

连续碰撞检测

迄今为止介绍的视频游戏物理技术对模拟的静态快照执行碰撞检测。 这称为离散碰撞检测，它忽略了先前步骤和当前步骤之间发生的情况。 因此，可能无法检测到某些碰撞，尤其是对于快速移动的物体。 这个问题被称为隧道。

连续碰撞检测技术试图找出两个物体何时在模拟的前一个步骤和当前步骤之间发生碰撞。 他们计算碰撞时间，因此我们可以及时返回并处理该点的碰撞。

撞击时间（或接触时间） t c是两个物体之间的距离为零的时刻。 如果我们可以写一个函数来计算两个物体之间的时间距离，我们想要找到的是这个函数的最小根。 因此，影响计算的时间是一个寻根问题。

对于影响计算的时间，我们考虑上一步在时间t i -1和当前步骤在时间t i的身体状态（位置和方向）。 为了使事情更简单，我们假设步骤之间的线性运动。

让我们假设形状是圆形来简化问题。 对于半径为r 1和r 2的两个圆C 1和C 2 ，其中它们的质心x 1和x 2与它们的质心重合（即它们自然地围绕它们的质心旋转），我们可以写出距离函数作为：

考虑步骤之间的线性运动，我们可以为C 1从t i -1到t i的位置编写以下函数

它是从x 1 ( t i -1 )到x 1 ( t i )的线性插值。 x 2也可以这样做。 对于这个区间，我们可以写另一个距离函数：

将此表达式设置为零，您将得到一个关于t的二次方程。 根可以直接使用二次公式找到。 如果圆不相交，则二次公式将无解。 如果他们这样做，它可能会导致一两个根。 如果它只有一个根，则该值就是影响时间。 如果它有两个根，最小的一个是撞击时间，另一个是圆分开的时间。 注意这里的影响时间是一个从0到1的数字。它不是以秒为单位的时间； 它只是一个数字，我们可以用来将物体的状态插入到发生碰撞的精确位置。

非圆的连续碰撞检测

为其他类型的形状编写距离函数很困难，主要是因为它们的距离取决于它们的方向。 出于这个原因，我们通常使用迭代算法，在每次迭代中将对象移动得越来越近，直到它们接近到足以被认为发生碰撞。

保守的推进算法迭代地向前移动物体（并旋转它们）。 在每次迭代中，它都会计算位移的上限。 原始算法在 Brian Mirtich 的博士论文（第 2.3.2 节）中提出，它考虑了物体的弹道运动。 Erwin Coumans（子弹物理引擎的作者）的这篇论文提出了一个更简单的版本，它使用恒定的线速度和角速度。

该算法计算形状A和B之间的最近点，从一个点到另一个点绘制一个向量，并将速度投影到该向量上以计算运动的上限。 它保证身体上的任何点都不会超出这个投影。 然后它将物体向前推进这个量并重复，直到距离低于一个小的公差值。

在某些情况下，可能需要太多次迭代才能收敛，例如，当其中一个物体的角速度太高时。

解决碰撞

一旦检测到碰撞，就需要以逼真的方式改变碰撞对象的运动，例如使它们相互反弹。 在本理论的下一部分也是最后一部分中，我们将讨论一些解决视频游戏中碰撞的流行方法。

参考

如果您有兴趣更深入地了解碰撞物理，例如碰撞检测算法和技术，那么 Christer Ericson 的Real-Time Collision Detection一书是必备之物。

由于碰撞检测严重依赖几何，Toptal 的文章Computational Geometry in Python: From Theory to Application是对该主题的出色介绍。