GJK和EPA

在窄相碰撞检测的武器库中，GJK (Gilbert-Johnson-Keerthi) 算法和 EPA (Expanding Polytope Algorithm) 算法无疑是最耀眼的双子星。GJK 负责高效地回答“是否碰撞？”这个问题，而 EPA 则在 GJK 确认碰撞后，接力计算出“碰撞得有多深？”以及“碰撞的方向是什么？”。这两个算法的组合，为现代物理引擎（如 Bullet, PhysX, Box2D）提供了一个极其强大、通用且高效的框架，用以处理任意凸体之间的碰撞检测和接触信息生成。

GJK：高效的碰撞探测器

GJK 的核心任务是检测两个凸体 A 和 B 是否相交。它通过一个巧妙的转化，将这个问题变成了判断原点 O 是否位于闵可夫斯基差集 C = A - B 之中。

1. 核心组件

闵可夫斯基差集 (Minkowski Difference): $C = {a - b ∣ a \in A, b \in B}$ 。如果 $A \cap B \neq = \emptyset$ ，则 $O \in C$ 。
支撑函数 (Support Function): $S_{C} (d)$ 返回差集 C 在方向 $d$ 上最远的点。 $S_{C} (d) = S_{A} (d) - S_{B} (- d)$ 。
单纯形 (Simplex): 算法在迭代过程中维护的一个点集，这些点都位于差集 C 中。在3D空间中，单纯形可以是点（0-simplex）、线段（1-simplex）、三角形（2-simplex）或四面体（3-simplex）。我们的目标是构建一个包含原点的单纯形。

2. GJK 算法流程

GJK 是一个迭代算法，它不断地构建一个越来越“接近”原点的单纯形。

初始化:
- 创建一个空的单纯形 simplex。
- 随机选择一个初始方向 d (例如, (1, 0, 0))。
- 计算第一个支撑点 a = support(d)，并将其加入 simplex。
- 更新方向 d 为指向原点的方向，即 d = -a。
主循环: a. 计算新方向上的支撑点 a = support(d)。 b. 终止条件1 (不碰撞): 如果 a 沿 d 方向没有越过原点（即 a.dot(d) < 0），说明原点不可能被 C 包围。A 和 B 没有碰撞，算法结束。 c. 将 a 加入 simplex。 d. 核心步骤 doSimplex: 根据 simplex 的类型（线段、三角形、四面体），判断原点是否被包含，并更新单纯形和新方向 d。 - 如果 doSimplex 返回 true，说明单纯形包含了原点。A 和 B 发生碰撞，算法结束，并将最终的单纯形传递给 EPA。 - 如果 doSimplex 返回 false，它会更新 simplex（移除不需要的点）和 d（指向原点的最近方向），然后继续下一次循环。

doSimplex 的几何直觉:

线段情况 (2个点): 检查原点是否在线段所在的 Voronoi 区域内。更新方向 d 为垂直于线段且指向原点的方向。
三角形情况 (3个点): 检查原点是在三角形内部，还是在某条边的外部，或某个顶点的外部。更新方向 d 为垂直于三角形平面或某条边且指向原点的方向。
四面体情况 (4个点): 检查原点是否在四面体内部。如果是，则碰撞！如果不是，找到离原点最近的面，更新方向 d 为该面的法线方向，并用这个面（三角形）作为新的单纯形。

代码示例 (GJK 主循环伪代码):

bool gjk(const Shape& A, const Shape& B, Simplex& out_simplex) {
    Vector3 d = Vector3(1, 0, 0); // Initial direction
    Simplex simplex;
    simplex.add(support(A, B, d));
    d = -simplex.getLastPoint();

    while (true) {
        Vector3 a = support(A, B, d);
        if (a.dot(d) < 0) {
            return false; // No collision
        }
        simplex.add(a);
        if (doSimplex(simplex, d)) {
            out_simplex = simplex;
            return true; // Collision
        }
    }
}

EPA：精确的穿透计算器

GJK 算法在返回 true 时，只告诉我们发生了碰撞，并提供了一个包含原点的四面体。它没有告诉我们穿透的深度和方向。这时，EPA 算法接管工作。

1. 核心思想

EPA 的出发点是 GJK 结束时得到的包含原点的单纯形（一个凸多面体）。既然原点在内部，那么这个多面体到原点的最小距离，就对应了两个原始物体之间的最小穿透深度。

EPA 是一个迭代算法，它从初始的单纯形（通常是四面体）开始，不断地“扩展”这个多面体，直到找到距离原点最近的那个面。

2. EPA 算法流程

初始化:
- 从 GJK 提供的包含原点的单纯形（四面体）开始，构建一个初始的凸多面体（polytope）。这个多面体由面（三角形）、边和顶点组成。
主循环: a. 找到最近的面: 在当前多面体的所有面中，找到距离原点最近的那个面。记录该面的法线 n 和到原点的距离 dist。 b. 扩展多面体: 在该最近面的法线方向 n 上，计算一个新的支撑点 p = support(n)。 c. 终止条件: 计算 p 在 n 方向上的投影距离 p.dot(n)。如果这个距离与 dist 的差值非常小（p.dot(n) - dist < tolerance），说明我们无法在 n 方向上进一步扩展多面体了。我们已经找到了最接近原点的面。算法结束，返回 dist 作为穿透深度，n 作为接触法线。 d. 重建多面体: 如果没有终止，说明 p 是一个新的、更远的点。我们需要将 p 加入多面体，并重建它。这通常涉及到删除所有 p 点可见的面，然后用 p 和被删除面的轮廓边构建新的三角面。

代码示例 (EPA 主循环伪代码):

PenetrationInfo epa(const Shape& A, const Shape& B, Simplex& initial_simplex) {
    Polytope polytope(initial_simplex);

    while (true) {
        // 1. 找到距离原点最近的面
        Face closestFace = polytope.findClosestFaceToOrigin();
        Vector3 normal = closestFace.normal;
        float distance = closestFace.distance;

        // 2. 在法线方向上获取新的支撑点
        Vector3 p = support(A, B, normal);

        // 3. 检查是否可以继续扩展
        if (p.dot(normal) - distance < 0.0001f) {
            // 无法扩展，找到最小穿透向量
            return {normal, distance};
        }

        // 4. 扩展多面体（最复杂的部分）
        polytope.expand(p);
    }
}

总结

GJK 和 EPA 是一对天作之合。GJK 像一个快速的侦察兵，利用闵可夫斯基差集的巧妙思想，高效地判断两个凸体是否可能接触。一旦发现接触，它立即将“战场”（一个包含原点的初始单纯形）交给 EPA。EPA 则像一个精密的工兵，从这个初始阵地出发，通过迭代扩展，精确地测量出穿透的深度和方向，为后续的碰撞响应提供至关重要的接触信息。

这个组合的强大之处在于其通用性和效率。通过 support 函数的抽象，它们可以统一处理任何凸体，而无需为每种形状组合编写特定的代码。虽然它们的实现细节，特别是 doSimplex 和 polytope.expand，充满了复杂的几何逻辑和对数值稳定性的考量，但理解并掌握这对算法，是通往高级物理引擎开发和几何算法设计的必经之路。

Keyboard shortcuts

Game Physics & Development Notes