电子游戏物理教程-第二部分：实体物体的碰撞检测

本文概述

• 电子游戏中的碰撞物理
• 宽相
• 窄相
• 连续碰撞检测
• 解决冲突
• 参考文献

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

第一部分：刚体动力学简介

第三部分：约束刚体模拟

在本系列的第一部分中, 我们探讨了刚体及其运动。但是, 在该讨论中, 对象之间没有相互作用。如果不做额外的工作, 模拟的刚体可以相互穿过或”穿透”, 这在大多数情况下是不希望的。

为了更真实地模拟实体对象的行为, 我们必须检查它们每次移动时是否相互碰撞, 如果确实发生碰撞, 则必须对此进行一些处理, 例如施加改变其速度的力, 因此他们将朝相反的方向移动。在这里, 了解碰撞物理对游戏开发人员尤为重要。

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

要回顾本文中提到的线性代数概念, 你可以参考第一部分中的线性代数速成课程。

电子游戏中的碰撞物理

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

如果我们在仿真中有n个物体, 则使用成对测试检测碰撞的计算复杂度为O(n2), 这个数字使计算机科学家畏缩。成对测试的数量与主体的数量成二次方增加, 并且确定两个形状(在任意位置和方向上)是否发生碰撞已经不便宜了。为了优化碰撞检测过程, 我们通常将其分为两个阶段：宽相和窄相。

广义阶段负责从模拟中的整个实体集中查找可能碰撞的刚体对, 并排除肯定不会碰撞的刚体对。该步骤必须能够根据刚体的数量进行缩放, 以确保我们在O(n2)时间复杂度下保持良好状态。为此, 此阶段通常使用空间分区以及为碰撞建立上限的边界体积。

窄相在宽相发现的可能碰撞的成对刚体上运行。这是一个优化步骤, 其中我们确定碰撞是否确实发生了, 对于发现的每个碰撞, 我们都将计算将用于以后解决碰撞的接触点。

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

宽相

在电子游戏碰撞物理学的广泛阶段, 我们需要确定哪些刚体可能发生碰撞。这些物体可能具有复杂的形状, 例如多边形和多面体, 而我们可以做的就是使用更简单的形状来包围对象。如果这些边界体积不相交, 则实际形状也将不相交。如果它们相交, 则实际形状可能相交。

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

AABB很简单, 并提供了良好的折衷, 因此受到了物理程序员的极大欢迎。二维AABB可以用C语言这样的结构表示：

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

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

最小值字段表示框左下角的位置, 最大值字段表示右上角。

要测试两个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的最小值和最大值之差。如果这些值中的任何一个大于零, 则AABB不会相交。

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

有很多可用于此目的的空间分区算法和数据结构, 例如统一网格, 2D中的四叉树, 3D中的八叉树和空间哈希。让我们仔细看看两种流行的空间分区算法：排序和清除以及边界体积层次结构(BVH)。

排序和扫描算法

排序和扫掠方法(也称为扫掠和修剪)是物理程序员在刚体模拟中最喜欢的选择之一。例如, Bullet Physics引擎在btAxisSweep3类中具有此方法的实现。

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

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

在二维和三维中, 如上所述, 在单个坐标轴上运行排序和扫掠将减少必须执行的直接AABB相交测试的数量, 但在一个坐标轴上的收益可能要好于另一个坐标轴。因此, 实现了排序和清除算法的更复杂的变体。 Christer Ericson在他的书《实时碰撞检测》(第336页)中提出了一种有效的变体, 他将所有AABB存储在一个阵列中, 并且对于每一次的排序和扫描, 都选择了一个坐标轴, 并根据使用快速排序, 选定轴上AABB的最小值。然后, 遍历该数组并执行AABB重叠测试。为了确定应该用于排序的下一个轴, 需要计算AABB中心的方差, 并为下一步选择方差更大的轴。

动态边界体积树

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

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

Box2D在b2DynamicTree类中具有Dbvt的复杂实现。 b2BroadPhase类负责执行广义阶段, 它使用b2DynamicTree的实例执行AABB查询。

窄相

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

凹凸形状

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

在凸形中, 形状内任意两点之间的线段始终完全落入形状内。但是, 对于凹形(或”非凸形”)形状, 并非所有连接该形状中点的可能线段都适用。如果你发现至少一个线段根本不在形状之外, 则该形状是凹形的。

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

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

显然, 如果我们使用凸包来表示凹对象, 则它将失去其凹属性。由于对象仍将具有凹入的图形表示, 因此可能会出现不良行为, 例如”鬼影”碰撞。例如, 汽车通常具有凹形形状, 如果我们使用凸形船体对其进行物理表示, 然后在其上放置一个框, 则该框可能似乎漂浮在上方的空间中。

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

凸分解算法接收凹形并返回一组凸形, 它们的并集与原始凹形相同。有些凹形只能用大量的凸形表示, 而这些凸形的计算和使用可能会变得非常昂贵。但是, 近似值通常已经足够好, 因此, 诸如V-HACD之类的算法会从凹面多面体中生成一小部分凸面多面体。

但是, 在许多科里森大学的物理案例中, 凸分解可以由艺术家手工完成。这样就无需使用分解算法来提高性能。由于性能是实时仿真中最重要的方面之一, 因此为复杂的图形对象创建非常简单的物理表示形式通常是一个好主意。下图显示了使用9个凸形状的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使用SAT来测试b2CollidePolygon.cpp中的两个凸多边形在其多边形-多边形碰撞检测算法中是否相交。

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

在许多碰撞物理情况下, 我们不仅要考虑物体实际相交的情况, 还要考虑彼此之间的距离, 这要求我们知道它们之间的距离。 Gilbert-Johnson-Keerthi(GJK)算法计算两个凸形之间的距离以及它们的最接近点。这是一种优雅的算法, 可通过支持函数, Minkowski和和单形来隐式表示凸形, 如下所述。

支持功能

支持函数sA(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 = v.x * d.x + v.y * d.y;

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

    return support;
}

但是, 支持功能的真正强大之处在于可以轻松处理圆锥, 圆柱和椭圆等形状。直接计算这些形状之间的距离相当困难, 并且如果没有GJK之类的算法, 通常必须将它们离散化为多边形或多面体, 以简化处理。但是, 这可能会导致进一步的问题, 因为除非多面体非常详细, 否则多面体的表面不像球体的表面那么光滑, 否则会导致碰撞检测期间的性能下降。其他不良副作用也可能出现。例如, “多面体”球体可能无法平稳滚动。

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

查看Gino van den Bergen的论文, 以找到有关圆柱, 圆锥和其他形状的支撑功能的更多示例。

当然, 我们的对象将从模拟空间中的原点开始位移和旋转, 因此我们需要能够计算变形形状的支撑点。我们使用仿射变换T(x)= Rx + c来位移和旋转我们的对象, 其中c是位移矢量, R是旋转矩阵。此转换首先使对象绕原点旋转, 然后对其进行平移。变形形状A的支持函数为：

明可夫斯基(Minkowski Sums)

两个形状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 =sA⊖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的论文《快速和鲁棒的GJK实现凸物体的碰撞检测》。 dyn4j物理引擎的博客也有关于GJK的精彩文章。

Box2D在b2Distance函数中的b2Distance.cpp中具有GJK算法的实现。它仅在影响算法计算期间的连续碰撞检测算法中使用GJK(我们将在后面进一步讨论的主题)。

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

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

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

穿透深度是最小平移矢量(MTV)的长度, 它是最小的矢量, 我们可以沿着该最小平移矢量平移相交的形状以将其与其他形状分开。

当两个形状相交时, 它们的Minkowski差包含原点, 并且Minkowski差的边界上最接近原点的点是MTV。 EPA算法通过将GJK给我们的单纯形扩展为多边形来找到这一点。依次用新的顶点细分边缘。

首先, 我们找到最接近原点的单纯形的边, 并在与边垂直的方向(即垂直于边并指向多边形外部)的方向上计算Minkowski差中的支撑点。然后, 通过向其添加支撑点来拆分该边缘。我们重复这些步骤, 直到向量的长度和方向没有太大变化。一旦算法收敛, 我们便有了MTV和穿透深度。

将GJK与EPA结合使用, 我们将对碰撞进行详细的描述, 无论物体是否已经相交, 或者距离物体足够近以至于被视为碰撞。

EPA算法已在Gino van den Bergen撰写的论文《 3D游戏对象上的邻近度查询和穿透深度计算》中进行了描述。 dyn4j博客上也有关于EPA的帖子。

连续碰撞检测

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

连续碰撞检测技术试图找出两个物体何时在模拟的上一步与当前步骤之间发生碰撞。他们计算了碰撞的时间, 因此我们可以回到过去并在那一点处理碰撞。

碰撞时间(或接触时间)tc是两个物体之间的距离为零时的时刻。如果我们可以为两个物体之间的距离编写一个函数, 那么我们要查找的是该函数的最小根。因此, 影响计算的时间是一个根本的问题。

对于影响计算的时间, 我们在时间ti-1的上一步中考虑身体的状态(位置和方向), 在时间ti时考虑当前步骤中的身体状态。为简化起见, 我们假设步骤之间存在线性运动。

通过假设形状为圆形来简化问题。对于半径为r1和r2的两个圆C1和C2, 它们的质心x1和x2与质心重合(即它们自然围绕质心旋转), 我们可以将距离函数写为：

考虑到步骤之间的线性运动, 我们可以编写以下函数来计算C1从ti-1到ti的位置

它是从x1(ti-1)到x1(ti)的线性插值。对于x2也可以这样做。对于这个间隔, 我们可以编写另一个距离函数：

将此表达式设置为零, 你将在t上得到一个二次方程。可以使用二次公式直接找到根。如果圆不相交, 则二次方程式将没有解。如果这样做, 可能会导致一两个根。如果只有一个根, 那么该值就是影响的时间。如果有两个根, 则最小的是碰撞的时间, 另一个是圆分开的时间。请注意, 此处的影响时间是从0到1的数字。这只是一个数字, 我们可以用来将物体的状态插值到发生碰撞的确切位置。

非圆的连续碰撞检测

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

保守推进算法迭代地移动身体(并使它们旋转)。在每次迭代中, 它都会计算位移的上限。最初的算法在Brian Mirtich的博士学位论文(第2.3.2节)中进行了介绍, 该论文考虑了物体的弹道运动。 Erwin Coumans(Bullet Physics Engine的作者)的这篇论文提出了一种使用恒定线性和角速度的简单版本。

该算法计算形状A和B之间的最接近点, 从一个点到另一个点绘制一个向量, 并在该向量上投影速度以计算运动的上限。它保证身体上的任何点都不会超出该投影。然后, 它将物体向前移动此量, 并重复进行直到该距离降到较小的公差值以下为止。

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

解决冲突

一旦检测到碰撞, 就必须以逼真的方式更改碰撞对象的运动, 例如使它们彼此反弹。在本理论的下篇也是最后一部分中, 我们将讨论一些解决视频游戏中冲突的流行方法。

参考文献

如果你想对碰撞物理学有更深入的了解, 例如碰撞检测算法和技术, 那么Christer Ericson的《实时碰撞检测》一书是必不可少的。

由于碰撞检测在很大程度上依赖于几何, 因此srcmini的文章《 Python中的计算几何：从理论到应用》是对该主题的出色介绍。

相关：机器人编程入门教程