GJK算法实战：从原理到Unity/Unreal碰撞检测实现 1. 项目概述为什么GJK算法是碰撞检测的“硬核”选择在Unity或Unreal Engine里做游戏碰撞检测是绕不开的基础。Unity自带的Collider组件和Unreal的Collision组件用起来很方便点几下鼠标两个物体就能“砰”地一声撞在一起。但当你需要处理自定义形状、高速运动的物体或者想实现更精确的物理反馈时内置的近似检测比如用包围盒就可能不够用了。你会发现两个形状明明没有相交系统却报告了碰撞或者高速子弹“穿”过了薄墙。这时候你就需要深入到几何层面自己来实现一套精确的、支持凸多面体的碰撞检测算法。而GJKGilbert–Johnson–Keerthi算法就是解决这个问题的“行业标准”答案。GJK算法听起来很高深但它的核心思想却异常巧妙它不直接计算两个形状是否相交而是通过一种叫做“闵可夫斯基差”的几何操作将“两个形状是否相交”的问题转化为了“一个点是否在另一个形状内部”的问题更具体地说是判断原点是否在闵可夫斯基差集内部。这个转换是理解GJK的关键。算法本身则通过一种迭代寻找“支撑点”的方式在闵可夫斯基差集内部构建一个不断逼近原点的单纯形在2D中是三角形3D中是四面体从而高效地判断出分离或相交。它的优势在于对于凸体其计算复杂度与顶点数无关只与迭代次数有关因此非常高效被广泛应用于从物理引擎到机器人学的各个领域。如果你正在开发一款需要自定义碰撞体比如一个复杂的飞船模型、实现布娃娃物理的精确关节碰撞或者优化AR/VR中虚拟物体的交互理解并实现GJK算法将让你从“引擎使用者”变为“系统构建者”。本文将从零开始拆解GJK算法的每一步并提供可直接在UnityC#和Unreal EngineC中运行、调试的实战代码。我会分享我在实现过程中踩过的坑比如单纯形退化、数值精度问题以及如何与EPAExpanding 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例子来说明这样更直观初始化选择一个初始搜索方向d通常可以取两个形状中心点的向量差即d centerB - centerA。构建初始单纯形它是一个包含单个点的集合这个点就是Support(M, d)。迭代循环 a.获取新点根据当前搜索方向d通过支撑函数得到一个新点p Support(M, d)并将其加入单纯形。 b.判断方向计算点p到原点的向量点积p · d。如果p · d 0说明在当前搜索方向d上我们找到的支撑点p都无法让单纯形包含原点因为原点在d的相反侧那么可以立即断定原点不在M内即A和B分离。算法结束返回“无碰撞”。 c.更新单纯形将新点p加入当前单纯形。现在单纯形可能包含2、32D或43D个点。我们需要判断原点是否被这个新的单纯形所“包围”。 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(ListVector3 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(ListVector3 verticesA, ListVector3 verticesB, Vector3 dir) { Vector3 pointA Support(verticesA, dir); Vector3 pointB Support(verticesB, -dir); // 注意方向取反 return pointA - pointB; // A - B } // 核心GJK碰撞检测函数 public static bool CheckCollision(ListVector3 verticesA, ListVector3 verticesB) { // 1. 初始化方向取中心差简单有效 Vector3 centerA CalculateCenter(verticesA); Vector3 centerB CalculateCenter(verticesB); Vector3 d centerB - centerA; if (d.sqrMagnitude EPSILON) d Vector3.right; // 如果中心重合给一个默认方向 // 2. 初始化单纯形列表 ListVector3 simplex new ListVector3(); 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 ListVector3 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(ListVector3 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 TArrayFVector VerticesA, const TArrayFVector VerticesB); private: static FVector Support(const TArrayFVector Vertices, const FVector Direction); static FVector MinkowskiSupport(const TArrayFVector VerticesA, const TArrayFVector VerticesB, const FVector Direction); static bool HandleSimplex(TArrayFVector Simplex, FVector Direction); static FVector CalculateCenter(const TArrayFVector Vertices); }; // GJK.cpp #include GJK.h #include limits const float EPSILON 1e-6f; FVector UGJKFunctionLibrary::Support(const TArrayFVector Vertices, const FVector Direction) { float MaxDot -std::numeric_limitsfloat::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 TArrayFVector VerticesA, const TArrayFVector VerticesB, const FVector Direction) { FVector PointA Support(VerticesA, Direction); FVector PointB Support(VerticesB, -Direction); return PointA - PointB; } bool UGJKFunctionLibrary::GJKCheckCollision(const TArrayFVector VerticesA, const TArrayFVector VerticesB) { // 初始化方向 FVector CenterA CalculateCenter(VerticesA); FVector CenterB CalculateCenter(VerticesB); FVector D CenterB - CenterA; if (D.SizeSquared() EPSILON) D FVector::ForwardVector; // 初始化单纯形 TArrayFVector 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(TArrayFVector Simplex, FVector Direction) { // 实现原点对线段、三角形、四面体的最近点计算和包含性判断。 // 这是一个需要细致编码的部分建议参考《Real-Time Collision Detection》或开源物理引擎。 return false; } FVector UGJKFunctionLibrary::CalculateCenter(const TArrayFVector Vertices) { FVector Sum FVector::ZeroVector; for (const FVector V : Vertices) Sum V; return Vertices.Num() 0 ? Sum / Vertices.Num() : Sum; }在Unreal中你可以将这个函数库暴露给蓝图方便地在任何地方调用检测两个自定义形状的碰撞。4. 超越布尔检测用EPA算法获取碰撞信息GJK算法高效地给出了“是否碰撞”的布尔答案。但对于物理引擎来说这远远不够。我们需要知道碰撞的深度穿透距离和法线碰撞方向以便计算碰撞响应让物体被“推开”。这时就需要EPAExpanding Polytope Algorithm算法作为GJK的搭档。EPA算法的思路很直观当GJK确认碰撞即原点在闵可夫斯基差集M内部后EPA以GJK终止时得到的那个包含原点的单纯形一个位于M边界上的多面体为起点。因为这个单纯形在M内部但原点在它内部所以我们需要扩展这个多面体使其不断膨胀直到它的各个面紧贴M的边界。最终离原点最近的那个面其外法线方向就是碰撞法线原点到该面的距离就是穿透深度。EPA的步骤简述如下初始化将GJK最后得到的单纯形一个四面体作为初始多面体Polytope。寻找最近面计算多面体每个面三角形到原点的距离点乘法线找到距离最近的那个面。获取支撑点以这个最近面的外法线方向为d调用支撑函数Support(M, d)得到M边界上的一个新点。判断收敛计算这个新点到该最近面的距离。如果这个距离与当前最近面距离的差值小于某个容差说明我们已经足够接近M的边界算法收敛。此时该最近面的法线和距离就是我们要的碰撞信息。扩展多面体如果未收敛则将新点插入多面体。这需要像增量构造凸包一样删除所有从新点看过去“可见”的旧面即新点在该面法线指向的正半空间然后用新点与这些被删除面的边界边组成新的三角形面添加到多面体中。循环回到步骤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 问题排查清单现象可能原因排查步骤与解决方案算法总是返回“无碰撞”1. 初始方向错误或为零向量。2. 支撑函数实现错误返回的点不是最远点。3. 顶点数据坐标系不统一一个用局部坐标一个用世界坐标。1. 打印初始方向向量确保其不为零。可以尝试固定一个方向如(1,0,0)测试。2. 单独测试支撑函数给定一个简单形状如正方形和一个方向手动计算并验证返回值是否正确。3. 确保传入GJK的所有顶点都在同一个坐标系通常是世界坐标系下。在Unity/Unreal中需要将模型本地顶点通过Transform.TransformPoint转换到世界空间。算法有时返回碰撞有时不返回间歇性1. 浮点数精度问题容差设置不当。2.HandleSimplex函数中对退化情况处理不完善。3. 迭代次数不足复杂形状在达到最大迭代次数前未收敛。1. 适当增大EPSILON如从1e-6调到1e-4观察是否稳定。在判断点积p·d 0时使用容差。2. 在HandleSimplex中添加大量日志打印每次迭代后的单纯形顶点和搜索方向。观察在出错的那一步单纯形是否出现了异常如点非常接近。3. 增加最大迭代次数如64并记录达到迭代上限的情况。算法陷入无限循环1. 搜索方向d未能有效更新导致每次迭代都获得相同的支撑点。2. 在原点恰好位于闵可夫斯基差集边界时判断逻辑可能振荡。1. 强制设置循环上限如100并在达到上限时中断返回“未碰撞”或“错误”。这是必须做的安全措施。2. 检查HandleSimplex中当原点在边上或面上时的逻辑。确保在这种情况下能正确判断为“包含”并返回true。EPA返回的穿透深度为NaN或极大值1. 在计算三角形面积或四面体体积时出现除零错误共线/共面。2. EPA扩展时新加入的点未能有效扩展多面体导致最近面计算错误。1. 在计算法线、面积、体积前先检查边长、面积是否大于一个极小阈值如1e-10否则视为退化情况采用备用方向或直接返回上次有效结果。2. 可视化EPA的多面体。在每次迭代中将多面体的面绘制出来Unity用Debug.DrawLine, Unreal用DrawDebugLine观察其扩展过程是否合理。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碰撞检测系统是一项有挑战但回报丰厚的工作。它不仅能解决你项目中特定的碰撞问题更能让你对计算机图形学、计算几何和物理引擎的核心机制有深刻的理解。当你看到自己编写的代码让两个复杂的自定义形状产生精确的碰撞反应时那种成就感是使用现成组件无法比拟的。希望这篇结合了原理、代码和实战经验的指南能为你铺平这条路。