GJK算法实战：从原理到Unity/Unreal碰撞检测实现

1. 项目概述：为什么GJK算法是碰撞检测的“硬核”选择？

在Unity或Unreal Engine里做游戏，碰撞检测是绕不开的基础。Unity自带的Collider组件和Unreal的Collision组件用起来很方便，点几下鼠标，两个物体就能“砰”地一声撞在一起。但当你需要处理自定义形状、高速运动的物体，或者想实现更精确的物理反馈时，内置的近似检测（比如用包围盒）就可能不够用了。你会发现，两个形状明明没有相交，系统却报告了碰撞；或者高速子弹“穿”过了薄墙。这时候，你就需要深入到几何层面，自己来实现一套精确的、支持凸多面体的碰撞检测算法。而GJK（Gilbert–Johnson–Keerthi）算法，就是解决这个问题的“行业标准”答案。

GJK算法听起来很高深，但它的核心思想却异常巧妙：它不直接计算两个形状是否相交，而是通过一种叫做“闵可夫斯基差”的几何操作，将“两个形状是否相交”的问题，转化为了“一个点是否在另一个形状内部”的问题，更具体地说，是判断原点是否在闵可夫斯基差集内部。这个转换是理解GJK的关键。算法本身则通过一种迭代寻找“支撑点”的方式，在闵可夫斯基差集内部构建一个不断逼近原点的单纯形（在2D中是三角形，3D中是四面体），从而高效地判断出分离或相交。它的优势在于，对于凸体，其计算复杂度与顶点数无关，只与迭代次数有关，因此非常高效，被广泛应用于从物理引擎到机器人学的各个领域。

如果你正在开发一款需要自定义碰撞体（比如一个复杂的飞船模型）、实现布娃娃物理的精确关节碰撞，或者优化AR/VR中虚拟物体的交互，理解并实现GJK算法将让你从“引擎使用者”变为“系统构建者”。本文将从零开始，拆解GJK算法的每一步，并提供可直接在Unity（C#）和Unreal Engine（C++）中运行、调试的实战代码。我会分享我在实现过程中踩过的坑，比如单纯形退化、数值精度问题，以及如何与EPA（Expanding Polytope Algorithm）算法结合获取碰撞深度和法线，让你不仅能检测到“是否碰撞”，还能知道“撞得多深、从哪个方向撞的”。

2. GJK算法核心原理深度拆解

要理解GJK，我们不能只停留在调用API的层面，必须深入其几何原理。这就像学开车，不仅要会踩油门和刹车，还得知道发动机和变速箱是怎么工作的，这样车坏了你才知道怎么修。

2.1 从问题转换开始：闵可夫斯基差（Minkowski Difference）

这是GJK算法的基石。给定两个凸集（形状）A和B，它们的闵可夫斯基差集定义为：A ⊖ B = { a - b | a ∈ A, b ∈ B }。通俗地讲，对于形状A中的每一个点a，减去形状B中的每一个点b，得到的所有可能结果构成的集合，就是闵可夫斯基差集。

这个操作的魔力在于一个关键性质：如果两个凸集A和B相交，那么它们的闵可夫斯基差集必然包含原点（0, 0, 0）。反过来，如果原点在差集内部，那么A和B一定相交。如果原点不在差集内部，那么A和B就是分离的，并且从原点到差集最近点的向量，就是它们的分离轴（的负方向）。

注意：这里说的“内部”包括边界。也就是说，如果两个形状刚好相切，原点就在差集的边界上。

通过这个转换，我们就把一个“两个形状的关系”问题，变成了一个“点和单个形状的关系”问题。而判断一个点（原点）是否在一个凸集中，GJK提供了一种极其高效的迭代方法。

2.2 算法的引擎：支撑函数（Support Function）

支撑函数是GJK迭代的“燃料”。对于一个凸形状C和一个给定的方向向量d，支撑函数Support(C, d)返回的是形状C在方向d上最远的点。数学表达是：Support(C, d) = argmax_{v ∈ C} (v · d)，即点积最大的那个点。

为什么需要它？因为我们要在闵可夫斯基差集（我们称之为M）中寻找点。根据定义，M = A ⊖ B。那么，M在方向d上的支撑点Support(M, d)，可以通过分别计算A和B的支撑点来高效获得：Support(M, d) = Support(A, d) - Support(B, -d)。这个性质太重要了！它意味着我们不需要显式地、耗费巨大资源去计算和存储整个闵可夫斯基差集（那可能是一个无限点集），我们只需要知道原始形状A和B的支撑函数，就能动态地得到M在任意方向上的边界点。

在实现中，为你的碰撞体实现一个高效的支撑函数是第一步。对于多边形/多面体，就是遍历所有顶点找点积最大的。对于球体、胶囊体等，则有解析解，速度更快。

2.3 迭代与终止：单纯形（Simplex）和包含判断

GJK算法通过迭代构建一个“单纯形”来逼近原点。单纯形是所在空间中最简单的几何体：在2D中是线段、三角形；在3D中是线段、三角形、四面体。

算法流程可以概括为以下步骤，我结合一个2D例子来说明，这样更直观：

1. 初始化：选择一个初始搜索方向d（通常可以取两个形状中心点的向量差，即d = centerB - centerA）。构建初始单纯形，它是一个包含单个点的集合，这个点就是Support(M, d)。
2. 迭代循环： a.获取新点：根据当前搜索方向d，通过支撑函数得到一个新点p = Support(M, d)，并将其加入单纯形。 b.判断方向：计算点p到原点的向量点积p · d。如果p · d< 0，说明在当前搜索方向d上，我们找到的支撑点p都无法让单纯形包含原点（因为原点在d的相反侧），那么可以立即断定原点不在M内，即A和B分离。算法结束，返回“无碰撞”。 c.更新单纯形：将新点p加入当前单纯形。现在单纯形可能包含2、3（2D）或4（3D）个点。我们需要判断原点是否被这个新的单纯形所“包围”。 d.检查包含：这是GJK的核心子程序。我们需要判断原点是否在当前单纯形内部（或边界上）。在2D中，如果单纯形是三角形，我们就检查原点是否在这个三角形内。同时，更重要的是，如果原点不在单纯形内，我们需要找到单纯形中离原点最近的那个部分（点、边或面），并丢弃单纯形中远离原点的点，从而得到一个更小的、更靠近原点的单纯形（例如从三角形退化成包含原点的边）。然后，基于这个新的、更小的单纯形，计算出一个新的搜索方向d，这个方向是从这个最近的部分指向原点。 e.循环条件：如果通过检查发现原点已经在当前单纯形内部（对于2D三角形或3D四面体），那么算法成功，返回“碰撞”。否则，用新的搜索方向d继续下一次迭代。

这个迭代过程就像是用一个不断收缩的“网”去兜原点。每次迭代都朝着原点的方向优化这个网，直到网住原点（碰撞）或者确定网不住（分离）。

实操心得：迭代次数需要设置一个上限（比如32次），防止在极端情况下（如两个几乎平行且非常接近的面）陷入无限循环。同时，由于浮点数精度问题，判断“原点是否在单纯形内”时需要引入一个很小的容差（epsilon，如1e-6）。

3. 实战代码解析：从理论到可运行的C#/C++

理解了原理，我们来看代码。我会分别给出Unity (C#) 和 Unreal Engine (C++) 的核心实现框架。为了聚焦于GJK本身，我们假设碰撞体都是凸多边形（2D）或凸多面体（3D），并用顶点列表表示。

3.1 C#实现（Unity版本）

在Unity中，我们通常将GJK实现为一个静态工具类。首先，我们需要定义支撑函数和向量运算。

using UnityEngine; using System.Collections.Generic; public static class GJKAlgorithm { // 容差，用于处理浮点数精度 public const float EPSILON = 1e-6f; // 支撑函数：对于给定方向dir，返回凸体vertices中点积最大的顶点 public static Vector3 Support(List<Vector3> vertices, Vector3 dir) { float maxDot = Mathf.NegativeInfinity; Vector3 supportPoint = Vector3.zero; foreach (var vertex in vertices) { float dot = Vector3.Dot(vertex, dir); if (dot > maxDot) { maxDot = dot; supportPoint = vertex; } } return supportPoint; } // 闵可夫斯基差支撑点 public static Vector3 MinkowskiSupport(List<Vector3> verticesA, List<Vector3> verticesB, Vector3 dir) { Vector3 pointA = Support(verticesA, dir); Vector3 pointB = Support(verticesB, -dir); // 注意方向取反 return pointA - pointB; // A - B } // 核心GJK碰撞检测函数 public static bool CheckCollision(List<Vector3> verticesA, List<Vector3> verticesB) { // 1. 初始化方向（取中心差，简单有效） Vector3 centerA = CalculateCenter(verticesA); Vector3 centerB = CalculateCenter(verticesB); Vector3 d = centerB - centerA; if (d.sqrMagnitude < EPSILON) d = Vector3.right; // 如果中心重合，给一个默认方向 // 2. 初始化单纯形（列表） List<Vector3> simplex = new List<Vector3>(); Vector3 a = MinkowskiSupport(verticesA, verticesB, d); simplex.Add(a); // 搜索方向取反，指向原点 d = -a; // 3. 开始迭代 int maxIterations = 32; for (int i = 0; i < maxIterations; i++) { Vector3 p = MinkowskiSupport(verticesA, verticesB, d); // 如果新支撑点在d方向上的投影小于0，则原点不可能在M内 if (Vector3.Dot(p, d) < EPSILON) { return false; // 分离 } simplex.Add(p); // 调用子函数处理单纯形，并更新搜索方向d if (HandleSimplex(ref simplex, ref d)) { return true; // 碰撞 } } // 达到最大迭代次数，通常视为未碰撞（或需要更复杂的处理） Debug.LogWarning("GJK reached max iterations."); return false; } // 处理单纯形（这里是2D版本的核心，3D版本更复杂） // 返回true表示原点在单纯形内（碰撞），否则更新simplex和d private static bool HandleSimplex(ref List<Vector3> simplex, ref Vector3 d) { // 此函数需要根据单纯形点数（1,2,3）分别处理 // 由于篇幅，这里给出2D情况下的逻辑示意，3D需要实现包含四面体的判断 // 实际应用中，建议使用成熟的几何库或参考标准实现（如Bullet Physics中的GJK） // 此处代码为示意，完整实现需补充： // 1. 当simplex有2个点（线段）时，找到线段上离原点最近的点，更新d为原点指向该最近点的方向。 // 2. 如果最近点是线段端点，则丢弃另一个点，simplex保留该端点。 // 3. 当simplex有3个点（三角形）时，检查原点是否在三角形内（通过重心坐标或边法线）。 // 4. 如果在三角形内，返回true（碰撞）。 // 5. 如果不在，找到离原点最近的边，丢弃对面的顶点，simplex退化为该边，并更新d。 // 伪代码逻辑： if (simplex.Count == 2) { /* 处理线段 */ } else if (simplex.Count == 3) { /* 处理三角形 */ } return false; // 默认返回未包含 } private static Vector3 CalculateCenter(List<Vector3> vertices) { Vector3 sum = Vector3.zero; foreach (var v in vertices) sum += v; return sum / vertices.Count; } }

上面的HandleSimplex函数是GJK的精华也是难点。一个健壮的实现需要正确处理各种退化情况（比如单纯形共线）。在3D中，情况更复杂，需要判断原点相对于线段、三角形、四面体的位置。网上有许多开源实现（如Bullet, Box2D）的GJK::Evaluate函数可供深入研究。

3.2 C++实现（Unreal Engine版本）

在Unreal Engine中，我们利用FVector等内置类型。逻辑与C#版完全一致，只是语法和API不同。

// GJK.h #pragma once #include "CoreMinimal.h" #include "GameFramework/Actor.h" #include "GJK.generated.h" UCLASS() class MYPROJECT_API UGJKFunctionLibrary : public UBlueprintFunctionLibrary { GENERATED_BODY() public: // 判断两个凸体（顶点数组）是否碰撞 UFUNCTION(BlueprintCallable, Category = "Collision|GJK") static bool GJKCheckCollision(const TArray<FVector>& VerticesA, const TArray<FVector>& VerticesB); private: static FVector Support(const TArray<FVector>& Vertices, const FVector& Direction); static FVector MinkowskiSupport(const TArray<FVector>& VerticesA, const TArray<FVector>& VerticesB, const FVector& Direction); static bool HandleSimplex(TArray<FVector>& Simplex, FVector& Direction); static FVector CalculateCenter(const TArray<FVector>& Vertices); }; // GJK.cpp #include "GJK.h" #include <limits> const float EPSILON = 1e-6f; FVector UGJKFunctionLibrary::Support(const TArray<FVector>& Vertices, const FVector& Direction) { float MaxDot = -std::numeric_limits<float>::max(); FVector SupportPoint = FVector::ZeroVector; for (const FVector& Vertex : Vertices) { float Dot = FVector::DotProduct(Vertex, Direction); if (Dot > MaxDot) { MaxDot = Dot; SupportPoint = Vertex; } } return SupportPoint; } FVector UGJKFunctionLibrary::MinkowskiSupport(const TArray<FVector>& VerticesA, const TArray<FVector>& VerticesB, const FVector& Direction) { FVector PointA = Support(VerticesA, Direction); FVector PointB = Support(VerticesB, -Direction); return PointA - PointB; } bool UGJKFunctionLibrary::GJKCheckCollision(const TArray<FVector>& VerticesA, const TArray<FVector>& VerticesB) { // 初始化方向 FVector CenterA = CalculateCenter(VerticesA); FVector CenterB = CalculateCenter(VerticesB); FVector D = CenterB - CenterA; if (D.SizeSquared() < EPSILON) D = FVector::ForwardVector; // 初始化单纯形 TArray<FVector> Simplex; FVector A = MinkowskiSupport(VerticesA, VerticesB, D); Simplex.Add(A); D = -A; const int32 MaxIterations = 32; for (int32 i = 0; i < MaxIterations; ++i) { FVector P = MinkowskiSupport(VerticesA, VerticesB, D); if (FVector::DotProduct(P, D) < EPSILON) { return false; // 分离 } Simplex.Add(P); if (HandleSimplex(Simplex, D)) { return true; // 碰撞 } } UE_LOG(LogTemp, Warning, TEXT("GJK reached max iterations.")); return false; } // HandleSimplex 的实现是GJK的核心，此处省略详细代码，需参考标准几何算法实现。 // 其职责与C#版本描述一致：根据单纯形点数，判断原点包含性，并更新单纯形和搜索方向。 bool UGJKFunctionLibrary::HandleSimplex(TArray<FVector>& Simplex, FVector& Direction) { // 实现原点对线段、三角形、四面体的最近点计算和包含性判断。 // 这是一个需要细致编码的部分，建议参考《Real-Time Collision Detection》或开源物理引擎。 return false; } FVector UGJKFunctionLibrary::CalculateCenter(const TArray<FVector>& Vertices) { FVector Sum = FVector::ZeroVector; for (const FVector& V : Vertices) Sum += V; return Vertices.Num() > 0 ? Sum / Vertices.Num() : Sum; }

在Unreal中，你可以将这个函数库暴露给蓝图，方便地在任何地方调用，检测两个自定义形状的碰撞。

4. 超越布尔检测：用EPA算法获取碰撞信息

GJK算法高效地给出了“是否碰撞”的布尔答案。但对于物理引擎来说，这远远不够。我们需要知道碰撞的深度（穿透距离）和法线（碰撞方向），以便计算碰撞响应，让物体被“推开”。这时就需要EPA（Expanding Polytope Algorithm）算法作为GJK的搭档。

EPA算法的思路很直观：当GJK确认碰撞（即原点在闵可夫斯基差集M内部）后，EPA以GJK终止时得到的那个包含原点的单纯形（一个位于M边界上的多面体）为起点。因为这个单纯形在M内部，但原点在它内部，所以我们需要扩展这个多面体，使其不断膨胀，直到它的各个面紧贴M的边界。最终，离原点最近的那个面，其外法线方向就是碰撞法线，原点到该面的距离就是穿透深度。

EPA的步骤简述如下：

1. 初始化：将GJK最后得到的单纯形（一个四面体）作为初始多面体（Polytope）。
2. 寻找最近面：计算多面体每个面（三角形）到原点的距离（点乘法线），找到距离最近的那个面。
3. 获取支撑点：以这个最近面的外法线方向为d，调用支撑函数Support(M, d)，得到M边界上的一个新点。
4. 判断收敛：计算这个新点到该最近面的距离。如果这个距离与当前最近面距离的差值小于某个容差，说明我们已经足够接近M的边界，算法收敛。此时，该最近面的法线和距离就是我们要的碰撞信息。
5. 扩展多面体：如果未收敛，则将新点插入多面体。这需要像增量构造凸包一样，删除所有从新点看过去“可见”的旧面（即新点在该面法线指向的正半空间），然后用新点与这些被删除面的边界边组成新的三角形面，添加到多面体中。
6. 循环：回到步骤2，继续寻找新的最近面。

EPA的实现比GJK更复杂，因为它涉及到凸包的面管理、拓扑结构的变化。同样，数值稳定性是关键，需要小心处理共面、共线的情况。

注意事项：EPA在物体刚好接触（穿透深度为0）或穿透很浅时可能不稳定。在实际物理引擎中，通常会结合GJK/EPA用于深度穿透，而对于浅穿透或接触，则采用其他方法（如分离轴定理SAT的变种）来获取更稳定的接触信息。

5. 性能优化与工程化实践

将GJK/EPA集成到游戏引擎中，不能只考虑算法正确性，还必须考虑性能、易用性和健壮性。

5.1 支撑函数的优化

支撑函数的性能至关重要，因为GJK/EPA的每次迭代都要调用它多次。

• 对于多边形/多面体：如果顶点数很多，每次遍历所有顶点是O(n)。可以采用以下优化：
  • 缓存和增量更新：如果物体在旋转，可以缓存物体局部空间的支撑点，然后通过变换矩阵快速计算世界空间的支撑点。对于凸体，在给定方向上最远的顶点往往是固定的几个“极值点”。
  • 使用GJK/EPA专用的数据结构：如“凸包”对象，它预计算并存储了顶点、边、面信息，支撑函数可以利用凸包的法线锥或预计算的极值方向来加速。
• 对于基本图元（球、盒、胶囊）：必须使用解析解，绝对不要用顶点列表模拟。
  • 球体：Support(sphere, d) = center + radius * normalize(d)。
  • AABB（轴对齐包围盒）：根据d的每个分量的正负，选择min或max顶点。
  • OBB（定向包围盒）：将方向d变换到OBB的局部空间，然后在局部空间使用AABB的支撑函数，再将结果变换回世界空间。
  • 胶囊体：支撑点在两个半球中心连线的线段上，加上半球半径的偏移。

5.2 数值鲁棒性处理

浮点数精度是几何算法的天敌。

• 容差（Epsilon）：所有相等性判断（如点积是否为0、距离是否小于某值）都必须使用容差。容差值不能太小（否则失去作用），也不能太大（否则影响精度）。通常取1e-6到1e-4之间，根据你的世界尺度调整。
• 退化单纯形：在GJK迭代中，可能会产生共线或共面的点（例如，三个点几乎在一条直线上）。你的HandleSimplex函数必须能检测并正确处理这种情况，否则会导致搜索方向错误甚至除零错误。一种常见策略是当检测到退化时，主动给搜索方向一个微小的随机扰动。
• EPA的收敛性：EPA可能在某些病理情况下收敛很慢或失败（例如物体穿透极深且形状复杂）。必须设置最大迭代次数（如50-100次），并在达到上限时采用备选方案，比如返回一个基于当前最近面的近似结果，或者直接使用GJK最后的方向作为一个近似的碰撞法线。

5.3 与引擎集成：碰撞查询与响应

在Unity/Unreal中，你通常不会完全替换内置的碰撞系统，而是将其用于特定场合。

• 自定义Collider组件：在Unity中，你可以创建一个CustomGJKCollider组件，它挂载在GameObject上，定义其凸体形状（顶点列表或基本图元参数）。在FixedUpdate中，你可以遍历其他同类组件，执行GJK检测。
• 作为Broad Phase的补充：GJK/EPA是精确的Narrow Phase算法。在大规模场景中，你仍然需要Broad Phase（如动态AABB树、空间网格）来快速筛选出可能碰撞的对象对，只对它们执行昂贵的GJK/EPA计算。
• 获取碰撞信息后：一旦EPA返回了穿透深度和法线，你就可以计算碰撞响应了。最简单的响应是“投影修正”：将发生穿透的物体沿着碰撞法线方向，移动穿透深度的距离。更复杂的物理响应则涉及动量、摩擦力的计算，这需要结合物体的质量、速度等属性。

6. 常见问题与调试技巧实录

自己实现GJK/EPA，调试是最大的挑战。问题往往不是“不工作”，而是“在某些奇怪的角度不工作”。

6.1 问题排查清单

6.2 可视化调试：你的最佳伙伴

在3D空间中调试几何算法，光靠打印日志是远远不够的。必须将中间过程画出来。

• 绘制支撑点：在每次调用MinkowskiSupport后，用不同颜色在世界空间中画出点A、点B以及它们的差（点P）。这能帮你确认支撑函数是否正确，以及搜索方向是否合理。
• 绘制单纯形：在GJK的每次迭代后，绘制当前的单纯形（2D为线段/三角形，3D为线段/三角形/四面体）。用明显的颜色（如红色）标出单纯形，观察它如何向原点收缩。
• 绘制搜索方向：从原点画一条射线，方向为当前的搜索方向d，长度适中。这能直观显示算法正在朝哪个方向“寻找”边界。
• 绘制EPA多面体：用线框模式绘制EPA迭代过程中的多面体。你可以看到它如何从一个四面体开始，像吹气球一样膨胀，直到贴合碰撞边界。

在Unity中，使用Debug.DrawLine,Debug.DrawRay，在OnDrawGizmos或Update中绘制。在Unreal中，使用DrawDebugLine,DrawDebugPoint等函数，通常在Tick或特定调试函数中调用。这些可视化工具能让你瞬间定位问题所在，效率远超盲目修改代码。

6.3 一个实用的调试技巧：从2D开始

如果你对3D GJK/EPA的实现感到头疼，一个极其有效的策略是：先在2D平面上实现并调试通过。2D的GJK（判断原点是否在三角形内）和EPA（扩展多边形）在概念上与3D完全一致，但几何处理简单得多，可视化也更容易（你可以在XY平面上画图）。将2D版本彻底调通，理解每一个细节后，再扩展到3D，你会发现自己面对的不是一个全新的问题，而只是一个增加了维度的问题，很多逻辑可以类比迁移。这是学习复杂几何算法的一条捷径。

实现一个健壮的GJK/EPA碰撞检测系统是一项有挑战但回报丰厚的工作。它不仅能解决你项目中特定的碰撞问题，更能让你对计算机图形学、计算几何和物理引擎的核心机制有深刻的理解。当你看到自己编写的代码让两个复杂的自定义形状产生精确的碰撞反应时，那种成就感是使用现成组件无法比拟的。希望这篇结合了原理、代码和实战经验的指南，能为你铺平这条路。