1. 项目概述为什么我们要手写GJK碰撞检测在游戏开发中物理引擎是让虚拟世界“活”起来的关键。无论是角色跳跃、车辆碰撞还是物体被击飞背后都离不开一套精确且高效的碰撞检测系统。Unity和Cocos Creator等主流引擎都内置了强大的物理引擎如Box2D、Bullet或PhysX它们像黑盒一样为我们处理了所有复杂的物理计算。那么为什么我们还要“自讨苦吃”去手写一个听起来就很复杂的GJKGilbert–Johnson–Keerthi碰撞检测算法呢这恰恰是进阶与精通的分水岭。当你满足于调用Rigidbody和Collider组件却对“两个物体到底是如何被判定为碰撞的”感到好奇时当你的游戏需要处理大量、形状奇特的物体而通用物理引擎的性能或精度成为瓶颈时当你希望为自己的自定义物理系统或特效如精确的破碎、变形打下坚实基础时理解并实现GJK就成了一项极具价值的核心技能。GJK算法以其优雅的数学原理和高效的迭代特性成为处理凸体碰撞检测的黄金标准。它不直接计算复杂的几何交点而是通过一种称为“闵可夫斯基差”的数学工具将“两个物体是否相交”的问题巧妙地转化为“原点是否在一个凸包内”的问题从而极大地简化了计算。本文将带你从零开始在Unity或Cocos Creator的环境中用C#或TypeScript手写实现一个完整的GJK碰撞检测器。我们不仅会提供可直接运行的完整代码更会深入剖析算法每一步背后的几何直觉和数学原理分享我在实现过程中踩过的坑和优化技巧。无论你是希望深入理解物理引擎原理的开发者还是正在为特定项目寻找定制化碰撞解决方案的程序员这篇文章都将为你提供一条清晰的实践路径。2. GJK算法核心思想与数学基础拆解在动手写代码之前我们必须先吃透GJK算法的灵魂。如果直接跳进代码实现很容易迷失在循环和向量运算中。GJK的核心思想可以用一个生活中的比喻来理解想象你要判断两个房间凸多边形是否重叠你不需要测量每个墙角的位置关系。你可以派一个“盲人探路者”从某个点出发他每次只用手杖支撑函数去触摸离目标原点最近的那个房间墙壁的方向。通过不断向目标方向摸索并记录触摸点他最终能判断出自己是否站在了重叠区域原点在闵可夫斯基差内。2.1 闵可夫斯基差碰撞问题的空间转换GJK算法的基石是闵可夫斯基差Minkowski Difference。对于两个凸集物体A和B它们的闵可夫斯基差定义为M A - B {a - b | a ∈ A, b ∈ B}。这个集合的几何意义非常强大如果A和B相交那么原点O必定包含在M中。反之如果原点O在M中则A和B相交。这就把两个物体相对位置的问题转化为了一个点原点与一个形状M的关系问题。但M的形状可能非常复杂。GJK的聪明之处在于它并不需要显式地计算出整个M的形状而是通过迭代的方式去构建一个能包围原点的、M的凸包Simplex。2.2 支撑函数算法的“手杖”支撑函数Support Function是GJK算法的“手杖”。给定一个方向向量d形状C的支撑点S_C(d)是C中在方向d上投影最远的点。用公式表示就是S_C(d) argmax_{v ∈ C} (v · d)其中·表示点积。对于闵可夫斯基差M上的支撑点有一个关键性质S_{A-B}(d) S_A(d) - S_B(-d)。这意味着要得到M在方向d上的最远点我们只需要分别求出A在d方向上的最远点和B在反方向(-d)上的最远点然后相减即可。这让我们无需真正构造M就能获取其边界上的点。2.3 单纯形与迭代收敛GJK算法从一个初始方向通常是从A的中心指向B的中心开始通过支撑函数获得M上的一个点加入一个点集初始为单点集。然后它检查当前点集称为单纯形Simplex是否包含原点。如果不包含算法会计算一个新的搜索方向指向原点并获取该方向上的新支撑点将其加入点集。同时它会不断维护这个点集使其始终是当前已探索点中最接近原点的那个凸包对于2D是三角形3D是四面体。这个过程不断迭代直到单纯形包含原点碰撞或者新找到的支撑点无法让单纯形更靠近原点分离。关键理解为什么迭代会收敛因为每次找到的新支撑点都是在当前搜索方向下能到达的“最远点”这保证了新构建的单纯形比之前的更靠近原点或者至少不会更远。对于凸体这个过程是单调的最终要么包住原点要么证明原点不可达。3. 手把手实现2D版GJK算法核心代码解析理论足够扎实后我们开始动手实现。我们先从2D版本开始它更直观理解了2D扩展到3D就是顺理成章的事情。我们将创建一个名为GJKCollisionDetector的静态工具类。3.1 数据结构定义与支撑函数实现首先我们需要定义一些基础数据结构。在Unity中我们可以直接使用Vector2和Vector3在Cocos Creator中则使用Vec2和Vec3。为了通用性这里我们用伪代码风格描述你可以轻松替换为对应引擎的API。// Unity C# 示例结构 public struct Simplex { public ListVector2 points; // 当前单纯形的顶点列表 public int count; // 顶点数量 public Simplex(int capacity) { points new ListVector2(capacity); count 0; } public void Add(Vector2 point) { // 保持点集为凸包的前沿点移除不必要的内部点 // 具体逻辑在后续迭代中实现 points.Add(point); count; } public Vector2 this[int index] points[index]; } public static class GJKCollisionDetector { // 支撑函数计算形状在给定方向上的最远点 // 这里以多边形为例实际中可能是圆形、胶囊体等任何凸体 public static Vector2 GetSupport(ListVector2 vertices, Vector2 direction) { float maxDot float.MinValue; Vector2 supportPoint vertices[0]; foreach (var vertex in vertices) { float dot Vector2.Dot(vertex, direction); if (dot maxDot) { maxDot dot; supportPoint vertex; } } return supportPoint; } // 计算闵可夫斯基差上的支撑点 public static Vector2 Support(ListVector2 shapeA, ListVector2 shapeB, Vector2 direction) { Vector2 pointA GetSupport(shapeA, direction); Vector2 pointB GetSupport(shapeB, -direction); // B取反方向 return pointA - pointB; // 闵可夫斯基差 } }注意事项GetSupport函数的时间复杂度是O(n)n是顶点数。对于复杂形状这是性能瓶颈。在实际引擎中会对碰撞体如凸包进行预处理比如存储极值点或使用特殊数据结构加速。方向向量direction需要是归一化的吗在GJK中不需要。支撑函数只关心方向不关心长度。点积的大小比较与向量的模长成正比但最大值点不会因为归一化而改变。对于圆形、椭圆等有解析表达式的凸体可以直接计算支撑点无需遍历顶点效率极高。例如圆心的支撑点就是center radius * direction.normalized。3.2 GJK迭代过程与单纯形进化这是算法的核心循环。我们需要一个函数来判断两个形状是否相交并返回一个布尔值。public static bool GJKIntersect(ListVector2 shapeA, ListVector2 shapeB) { // 1. 初始化选择初始搜索方向通常从A中心指向B中心或任意方向如(1, 0) Vector2 centerA CalculateCenter(shapeA); Vector2 centerB CalculateCenter(shapeB); Vector2 direction centerB - centerA; // 如果两中心重合直接认为碰撞或需要特殊处理 if (direction.sqrMagnitude 1e-6) { direction Vector2.right; } // 2. 获取初始支撑点初始化单纯形一个点 Vector2 support Support(shapeA, shapeB, direction); Simplex simplex new Simplex(3); // 2D单纯形最多3个点 simplex.Add(support); // 3. 调整方向指向原点 direction -support; // 新的搜索方向是从支撑点指向原点 // 4. GJK主迭代循环最大迭代次数防止死循环 int maxIterations 20; for (int i 0; i maxIterations; i) { // 获取新方向上的支撑点 Vector2 newSupport Support(shapeA, shapeB, direction); // 判断终止条件如果新支撑点在方向上的投影小于0说明原点在此方向“后面”不可能相交 if (Vector2.Dot(newSupport, direction) 0) { return false; // 分离 } // 将新点加入单纯形 simplex.Add(newSupport); // 处理单纯形并更新下一次的搜索方向 // 这是GJK最精妙的部分根据单纯形是线段还是三角形判断是否包含原点并更新方向 if (HandleSimplex(ref simplex, ref direction)) { return true; // 单纯形包含原点碰撞发生 } // 否则用新的direction继续迭代 } // 理论上凸体迭代应收敛这里设置安全上限 return false; }3.3 单纯形处理算法的心脏HandleSimplex函数是GJK的灵魂它根据当前单纯形点集的状态判断是否包含原点并计算出下一个搜索方向。在2D中单纯形可以是1个点、2个点线段或3个点三角形。private static bool HandleSimplex(ref Simplex simplex, ref Vector2 direction) { switch (simplex.count) { case 2: // 单纯形是一条线段 (A, B) return HandleLineSegment(simplex[0], simplex[1], ref direction, ref simplex); case 3: // 单纯形是一个三角形 (A, B, C) return HandleTriangle(simplex[0], simplex[1], simplex[2], ref simplex); default: // 理论上不会进入这里因为初始点后第一次调用就是case 2 return false; } } private static bool HandleLineSegment(Vector2 a, Vector2 b, ref Vector2 direction, ref Simplex simplex) { Vector2 ab b - a; Vector2 ao -a; // 从a指向原点的向量 // 检查原点相对于线段AB的位置 // 使用向量叉积的符号在2D中叉积结果是一个标量表示有向面积 // 更通用的方法是使用向量投影和垂直分量 // 方法检查原点是否在AB的“前面”由A指向B的方向区域 // 计算AB的垂直向量法线指向原点一侧 Vector2 perp TripleProduct(ab, ao, ab); // 这是一个技巧得到垂直于AB且指向原点的向量 if (perp.sqrMagnitude 1e-6) { // 原点在线段AB上或非常接近 direction Vector2.zero; return true; // 实际上还需要进一步判断是否在线段内这里简化认为碰撞 } direction perp; // 更新单纯形保留离原点最近的点A或B移除另一个 // 通过点积判断如果AO在AB上的投影在AB之间保留AB如果超出B则方向指向B外侧保留B // 这里简化我们总是保留A和B因为下次迭代会由HandleSimplex重新处理 // 更精确的实现需要优化单纯形顶点 return false; } // 一个有用的向量运算a × (b × c) b(a·c) - c(a·b)在2D中可用于求垂直向量 private static Vector2 TripleProduct(Vector2 a, Vector2 b, Vector2 c) { float ac Vector2.Dot(a, c); float ab Vector2.Dot(a, b); return b * ac - c * ab; } private static bool HandleTriangle(Vector2 a, Vector2 b, Vector2 c, ref Simplex simplex) { // 检查原点是否在三角形ABC内 // 使用重心坐标法或连续边法Edge Test // 连续边法检查原点是否在每条边的“外侧” Vector2 ab b - a; Vector2 ac c - a; Vector2 ao -a; // 计算垂直于AB且指向三角形外侧的向量 Vector2 abPerp TripleProduct(ac, ab, ab); if (Vector2.Dot(abPerp, ao) 0) { // 原点在AB边的外侧 // 移除点C将单纯形退化为线段AB并设置搜索方向为abPerp simplex.points.RemoveAt(2); // 移除C simplex.count 2; direction abPerp; return false; } // 检查AC边 Vector2 acPerp TripleProduct(ab, ac, ac); if (Vector2.Dot(acPerp, ao) 0) { // 原点在AC边的外侧 // 移除点B将单纯形退化为线段AC simplex.points.RemoveAt(1); // 移除B (索引1是B因为A是0) simplex.count 2; direction acPerp; return false; } // 如果原点不在AB外侧也不在AC外侧那么它就在三角形ABC内部或非常接近 return true; // 碰撞 }实操心得TripleProduct技巧是2D GJK实现中的一个关键优化它避免了直接计算法向量和判断方向的复杂逻辑让代码更简洁。在HandleLineSegment中我们并没有真正优化单纯形移除多余点因为在下一次迭代中HandleSimplex会根据新的方向重新评估。一个更高效的实现会在每一步都保持单纯形是最小的即最接近原点的凸包子集。浮点数精度问题判断点积是否大于0时要使用一个很小的容差值如1e-6而不是直接与0比较以避免因浮点误差导致的误判或无限循环。4. 从GJK到EPA获取碰撞深度与法向量GJK算法只能告诉我们“是否碰撞”。但在游戏物理中我们通常还需要更多信息穿透深度Penetration Depth和碰撞法线Collision Normal以便于后续的碰撞响应如施加冲量、分离物体。这就需要EPAExpanding Polytope Algorithm算法登场了。EPA可以看作是GJK的延续当GJK判定为碰撞后EPA利用GJK最后得到的那个包含原点的单纯形一个三角形逐步扩展它使其逼近闵可夫斯基差M的边界从而找到原点到M边界的最短距离这个距离就是穿透深度方向就是碰撞法线。4.1 EPA算法原理简述输入GJK终止时得到的包含原点的单纯形2D为三角形3D为四面体。初始化多边形将这个单纯形作为初始的凸包多边形。迭代扩展 a. 在多边形的所有边2D或面3D中找到离原点最近的那条边面。 b. 沿着该边面的法线方向指向多边形外部调用支撑函数获得M边界上的一个新点。 c. 如果这个新点与旧边面的距离即原点到此边/面的距离在误差范围内则停止迭代。此时该最近边面的法线方向即为碰撞法线原点到该边面的距离即为穿透深度。 d. 否则将新点插入多边形分割最近的边面形成新的凸包重复此过程。输出穿透深度和碰撞法线。4.2 EPA核心代码实现2D版下面提供一个简化版的2D EPA实现用于演示原理。在实际应用中你需要处理更复杂的多边形插入和凸包维护逻辑。public static bool GJKEPAIntersect(ListVector2 shapeA, ListVector2 shapeB, out Vector2 normal, out float depth) { normal Vector2.zero; depth 0f; // 1. 先用GJK检测是否碰撞并获取最终的单纯形 Simplex simplex; if (!GJKIntersectWithSimplex(shapeA, shapeB, out simplex)) // 这是一个修改版的GJK返回最终单纯形 { return false; } // 2. EPA迭代 ListVector2 polytope new ListVector2(simplex.points); // 初始多边形就是GJK的最终单纯形 int maxEPAIterations 30; float tolerance 1e-4f; for (int i 0; i maxEPAIterations; i) { // 2a. 找到离原点最近的边 int edgeIndex; float minDistance; Vector2 closestNormal; FindClosestEdge(polytope, out edgeIndex, out minDistance, out closestNormal); // 2b. 沿着该边的法线方向获取支撑点 Vector2 support Support(shapeA, shapeB, closestNormal); // 2c. 计算支撑点到该边的距离实际上是原点到该边所在直线的有符号距离 float supportDistance Vector2.Dot(support, closestNormal); // 2d. 判断收敛如果新支撑点带来的“扩展”很小则认为已找到最近边界 if (supportDistance - minDistance tolerance) { normal closestNormal; depth supportDistance; // 或 minDistance根据实现略有不同 return true; } // 2e. 将新点插入多边形维护凸包 // 在最近边edgeIndex 和 edgeIndex1之间插入新点 polytope.Insert(edgeIndex 1, support); } // 迭代次数用尽返回近似结果或视为失败 // 通常这里会取最后一次迭代的结果 return false; } private static void FindClosestEdge(ListVector2 polytope, out int index, out float minDistance, out Vector2 normal) { index 0; minDistance float.MaxValue; normal Vector2.zero; for (int i 0; i polytope.Count; i) { int j (i 1) % polytope.Count; // 下一个顶点形成闭环 Vector2 a polytope[i]; Vector2 b polytope[j]; // 计算边AB的法线垂直于AB并指向多边形外部 Vector2 edge b - a; // 2D中获取垂直于边的向量(-edge.y, edge.x) 或 (edge.y, -edge.x)需要归一化并确保指向外部 Vector2 n new Vector2(-edge.y, edge.x).normalized; // 计算原点到边AB所在直线的距离有符号距离 float distance Vector2.Dot(n, a); // 因为a是边上的点n是单位法线点积即为距离 // 我们需要的是正距离原点在多边形外部在EPA中原点在内部距离应为正。 // 确保法线指向外部如果距离为负说明法线指向内部需要翻转 if (distance 0) { n -n; distance -distance; } if (distance minDistance) { minDistance distance; normal n; index i; // 记录边起始索引 } } }注意事项与常见问题凸包维护上述EPA实现中polytope.Insert非常简陋插入新点后可能破坏凸性。一个健壮的实现需要在插入后运行一次凸包算法如Andrews Monotone Chain来维护凸多边形或者更精细地处理边的替换。终止条件收敛条件supportDistance - minDistance tolerance是关键。supportDistance是新支撑点在法线方向上的投影理论上应等于原点到该边扩展后新边界的距离。当两者差值很小时说明扩展已微乎其微。法线方向碰撞法线normal的方向需要统一约定。通常约定为从物体A指向物体B或者指向需要施加冲量的方向即分离物体的方向。在计算响应时要注意方向的一致性。性能EPA的迭代次数通常很少10次但最坏情况下可能较多。设置最大迭代次数防止死循环并考虑使用更高效的数据结构如边列表来查找最近边。5. 在Unity与Cocos Creator中的集成与调试理论算法实现后我们需要将其集成到游戏引擎中并可视化调试确保它正确工作。5.1 Unity集成示例在Unity中我们可以创建一个MonoBehaviour脚本来驱动我们的GJK/EPA检测并使用Gizmos或新的Graphics.DrawMesh进行可视化。using UnityEngine; using System.Collections.Generic; public class GJKTest : MonoBehaviour { public Transform shapeA; public Transform shapeB; public Vector2[] verticesA; // 物体A的本地顶点坐标 public Vector2[] verticesB; // 物体B的本地顶点坐标 private ListVector2 worldVerticesA new ListVector2(); private ListVector2 worldVerticesB new ListVector2(); void Update() { // 将本地顶点转换到世界空间 UpdateWorldVertices(shapeA, verticesA, worldVerticesA); UpdateWorldVertices(shapeB, verticesB, worldVerticesB); // 执行碰撞检测 Vector2 collisionNormal; float penetrationDepth; bool isColliding GJKEPAIntersect(worldVerticesA, worldVerticesB, out collisionNormal, out penetrationDepth); // 在GUI或Log中显示结果 Debug.Log($碰撞: {isColliding}, 法线: {collisionNormal}, 深度: {penetrationDepth}); } void UpdateWorldVertices(Transform trans, Vector2[] localVerts, ListVector2 worldVerts) { worldVerts.Clear(); foreach (var localVert in localVerts) { Vector3 worldPos trans.TransformPoint(new Vector3(localVert.x, localVert.y, 0)); worldVerts.Add(new Vector2(worldPos.x, worldPos.y)); } } void OnDrawGizmos() { if (!Application.isPlaying) return; // 绘制形状A DrawPolygonGizmo(worldVerticesA, Color.blue); // 绘制形状B DrawPolygonGizmo(worldVerticesB, Color.green); // 如果碰撞绘制碰撞法线和深度 Vector2 normal; float depth; if (GJKEPAIntersect(worldVerticesA, worldVerticesB, out normal, out depth)) { // 计算一个参考点例如形状A的中心近似 Vector2 center GetCenter(worldVerticesA); Gizmos.color Color.red; Gizmos.DrawLine(center, center normal * depth); Gizmos.DrawSphere(center normal * depth, 0.05f); } } void DrawPolygonGizmo(ListVector2 vertices, Color color) { Gizmos.color color; for (int i 0; i vertices.Count; i) { int j (i 1) % vertices.Count; Gizmos.DrawLine(vertices[i], vertices[j]); } } Vector2 GetCenter(ListVector2 vertices) { Vector2 sum Vector2.zero; foreach (var v in vertices) sum v; return sum / vertices.Count; } }5.2 Cocos Creator (TypeScript) 集成示例在Cocos Creator中原理类似我们使用Graphics组件或DebugDraw来进行绘制。import { _decorator, Component, Vec2, Graphics, Color } from cc; const { ccclass, property } _decorator; ccclass(GJKTest) export class GJKTest extends Component { property({ type: Graphics }) graphics: Graphics | null null; property shapeAVertices: Vec2[] []; property shapeBVertices: Vec2[] []; private _worldVerticesA: Vec2[] []; private _worldVerticesB: Vec2[] []; update(deltaTime: number) { this.updateWorldVertices(this.node, this.shapeAVertices, this._worldVerticesA); // 假设shapeB是另一个节点 // this.updateWorldVertices(shapeBNode, this.shapeBVertices, this._worldVerticesB); let normal new Vec2(); let depth 0; let isColliding this.gjkepaIntersect(this._worldVerticesA, this._worldVerticesB, normal, depth); // 绘制逻辑可以放在这里或单独的渲染循环中 this.drawDebug(); } updateWorldVertices(node: Node, localVerts: Vec2[], outWorldVerts: Vec2[]) { outWorldVerts.length 0; let worldPos new Vec3(); for (let localVert of localVerts) { // 将本地坐标转换到世界坐标简化假设在2D平面 Vec3.set(worldPos, localVert.x, localVert.y, 0); node.getWorldPosition(worldPos); outWorldVerts.push(new Vec2(worldPos.x, worldPos.y)); } } drawDebug() { if (!this.graphics) return; this.graphics.clear(); // 绘制多边形A this.graphics.strokeColor Color.BLUE; this.graphics.moveTo(this._worldVerticesA[0].x, this._worldVerticesA[0].y); for (let i 1; i this._worldVerticesA.length; i) { this.graphics.lineTo(this._worldVerticesA[i].x, this._worldVerticesA[i].y); } this.graphics.close(); this.graphics.stroke(); // 绘制多边形B... // 绘制碰撞法线和深度... } // 将之前的C# GJK/EPA算法翻译成TypeScript here... gjkIntersect(shapeA: Vec2[], shapeB: Vec2[]): boolean { // ... 实现GJK算法 return false; } gjkepaIntersect(shapeA: Vec2[], shapeB: Vec2[], outNormal: Vec2, outDepth: number): boolean { // ... 实现GJKEPA算法 return false; } }调试技巧可视化单纯形在GJK迭代的每一步将当前的单纯形点、线、三角形绘制出来。观察它如何一步步逼近原点。这是理解算法动态过程的最佳方式。绘制搜索方向在每次迭代中绘制出当前的搜索方向向量。你会看到方向如何根据单纯形的状态而改变。EPA多边形可视化将EPA迭代过程中的扩展多边形绘制出来观察它如何从初始三角形“膨胀”并贴合闵可夫斯基差的边界。处理退化情况当两个物体刚好相切或者顶点共线时算法可能遇到数值不稳定。这时需要增加容错处理比如当单纯形面积接近零时视为分离或轻微穿透。6. 性能优化与高级话题一个基础的GJK/EPA实现已经能处理很多情况但在高性能游戏或处理大量物体时还需要进一步优化。6.1 缓存与增量计算对于运动中的物体其位置和旋转每帧变化。我们可以利用上一帧的碰撞信息来“预热”GJK算法缓存上一帧的单纯形如果两物体上一帧碰撞那么这一帧很可能仍然碰撞或非常接近。将上一帧GJK终止时的单纯形作为这一帧的初始单纯形可以极大减少迭代次数。缓存支撑点对于特定方向如果物体形状未变其支撑点可以缓存。但方向变化后缓存失效需权衡缓存开销与收益。6.2 形状特化支撑函数我们之前实现的GetSupport是通用的多边形遍历O(n)复杂度。对于特定形状可以O(1)计算圆形support center radius * direction.normalizedAABB轴对齐包围盒只需比较方向向量的正负号选择对应角落。OBB有向包围盒将方向向量变换到OBB的局部空间然后类似AABB处理。胶囊体计算线段两个端点的支撑点取点积更大的那个。 在引擎集成时你的碰撞检测系统应该根据碰撞体的类型分派到不同的支撑函数实现。6.3 扩展到3D将2D GJK扩展到3D核心思想完全一致但复杂度提升单纯形从点、线、三角形变为点、线、三角形、四面体。包含原点判断在3D中需要判断原点是否在四面体内。这可以通过计算四个面的有向体积标量三重积来判断所有面与原点同侧则在内部。搜索方向计算在HandleSimplex中情况更多。例如对于三角形单纯形需要判断原点在三角形的哪一侧利用法线并可能退化为边或保持为三角形。EPA从查找“最近边”变为查找“最近面”多边形扩展为多面体Polytope维护3D凸包更加复杂通常需要借助半边数据结构Half-Edge或现成的凸包库。6.4 与物理引擎的配合你手写的GJK/EPA通常不会完全替代引擎的物理引擎而是用于特定场景自定义碰撞过滤在引擎触发碰撞回调前用你的算法进行更精确或更定制化的预检测。特殊形状碰撞引擎不支持的复杂凸体或自定义复合形状。查询Raycast, OverlapGJK的思想可以用于其他空间查询如判断一个点是否在凸体内相当于与一个点形状进行GJK检测。性能对比与学习作为理解内置物理引擎的绝佳途径。7. 常见问题排查与实战心得在实际编码和调试中你几乎一定会遇到下面这些问题。7.1 算法陷入无限循环或提前退出症状两个明显相交的物体返回“未碰撞”或者程序卡死。排查浮点精度这是头号嫌犯。所有点积、距离的比较必须使用容差epsilon如1e-6f。例如if (dot 1e-6f)而不是if (dot 0)。方向向量零长在计算新的搜索方向direction后检查其长度。如果长度极小接近零说明单纯形可能已经包含原点或非常接近应直接返回碰撞。否则归一化或直接使用零向量可能导致除零错误或无效迭代。支撑函数错误确保你的支撑函数返回的是正确形状在给定方向上的最远点。用简单形状如两个正方形手动计算几个方向的支撑点进行验证。单纯形退化当三个点共线或四个点共面时单纯形退化体积为零无法判断原点在内还是在外。需要在代码中检测这种退化情况例如计算三角形面积或四面体体积并采取策略比如稍微扰动一个点或直接根据边缘情况判断。7.2 EPA结果不稳定或法线方向错误症状穿透深度时大时小碰撞法线方向跳动导致物理响应抖动。排查凸包维护EPA中插入新点后必须保证多边形/多面体始终是凸的。一个简单的插入可能产生凹点。实现一个快速的凸包维护例程或者使用更稳健的算法如“最近边插入后移除所有在新凸包内部的点”。法线方向一致性确保FindClosestEdge中计算的法线始终指向多边形外部对于内部的点距离为正。在3D中面的法线也要保持一致通常按顶点顺序右手定则。收敛条件过松或过紧容差值tolerance需要根据你的世界尺度调整。太小可能导致迭代次数过多太大可能提前终止得到不精确的结果。可以从1e-4开始调整。数值误差累积EPA迭代多次后顶点坐标可能积累误差。可以考虑定期对多边形顶点进行“清理”比如合并距离极近的点。7.3 性能瓶颈症状检测大量物体时帧率下降。优化粗检测先行永远先使用廉价的包围体如AABB、包围球进行快速拒绝测试。只有包围体相交的物体对才进入GJK/EPA检测。距离缓存对于运动连续的物体可以使用“分离轴”缓存。如果上一帧在某轴上分离且物体运动不大可以快速检查是否仍然分离。简化形状对于复杂的凸体可以用顶点数更少的凸包近似。或者使用GJK的特例比如对于两个球体直接计算圆心距离与半径和即可。并行化碰撞检测是天然可并行的。你可以将需要检测的物体对列表分发到多个线程或Job中处理。在Unity中可以考虑使用Burst Compiler和Job System来加速计算密集的支撑函数和向量运算。7.4 与引擎坐标系统一问题自己计算的碰撞法线和深度如何用于引擎的物理响应处理你需要将计算出的碰撞信息接触点、法线、深度转换为引擎物理系统期望的格式。例如在Unity中你可能需要填充ContactPoint结构或者直接计算并施加冲量Rigidbody.AddForceAtPosition(impulse, contactPoint)。注意坐标系的转换世界空间 vs 本地空间和单位的一致性。手写GJK/EPA是一个“知其然知其所以然”的深度实践过程。它可能会让你头疼一阵但一旦打通你对碰撞检测、计算几何乃至整个物理模拟的理解都会上升一个维度。这份代码不仅仅是一个工具更是你图形学与物理编程知识库中的一块坚实基石。当你再看到游戏中的物体自然碰撞、滚动时你看到的将不再是魔法而是优雅的数学在静静流淌。 从零实现GJK碰撞检测算法：原理、代码与Unity/Cocos Creator集成
1. 项目概述为什么我们要手写GJK碰撞检测在游戏开发中物理引擎是让虚拟世界“活”起来的关键。无论是角色跳跃、车辆碰撞还是物体被击飞背后都离不开一套精确且高效的碰撞检测系统。Unity和Cocos Creator等主流引擎都内置了强大的物理引擎如Box2D、Bullet或PhysX它们像黑盒一样为我们处理了所有复杂的物理计算。那么为什么我们还要“自讨苦吃”去手写一个听起来就很复杂的GJKGilbert–Johnson–Keerthi碰撞检测算法呢这恰恰是进阶与精通的分水岭。当你满足于调用Rigidbody和Collider组件却对“两个物体到底是如何被判定为碰撞的”感到好奇时当你的游戏需要处理大量、形状奇特的物体而通用物理引擎的性能或精度成为瓶颈时当你希望为自己的自定义物理系统或特效如精确的破碎、变形打下坚实基础时理解并实现GJK就成了一项极具价值的核心技能。GJK算法以其优雅的数学原理和高效的迭代特性成为处理凸体碰撞检测的黄金标准。它不直接计算复杂的几何交点而是通过一种称为“闵可夫斯基差”的数学工具将“两个物体是否相交”的问题巧妙地转化为“原点是否在一个凸包内”的问题从而极大地简化了计算。本文将带你从零开始在Unity或Cocos Creator的环境中用C#或TypeScript手写实现一个完整的GJK碰撞检测器。我们不仅会提供可直接运行的完整代码更会深入剖析算法每一步背后的几何直觉和数学原理分享我在实现过程中踩过的坑和优化技巧。无论你是希望深入理解物理引擎原理的开发者还是正在为特定项目寻找定制化碰撞解决方案的程序员这篇文章都将为你提供一条清晰的实践路径。2. GJK算法核心思想与数学基础拆解在动手写代码之前我们必须先吃透GJK算法的灵魂。如果直接跳进代码实现很容易迷失在循环和向量运算中。GJK的核心思想可以用一个生活中的比喻来理解想象你要判断两个房间凸多边形是否重叠你不需要测量每个墙角的位置关系。你可以派一个“盲人探路者”从某个点出发他每次只用手杖支撑函数去触摸离目标原点最近的那个房间墙壁的方向。通过不断向目标方向摸索并记录触摸点他最终能判断出自己是否站在了重叠区域原点在闵可夫斯基差内。2.1 闵可夫斯基差碰撞问题的空间转换GJK算法的基石是闵可夫斯基差Minkowski Difference。对于两个凸集物体A和B它们的闵可夫斯基差定义为M A - B {a - b | a ∈ A, b ∈ B}。这个集合的几何意义非常强大如果A和B相交那么原点O必定包含在M中。反之如果原点O在M中则A和B相交。这就把两个物体相对位置的问题转化为了一个点原点与一个形状M的关系问题。但M的形状可能非常复杂。GJK的聪明之处在于它并不需要显式地计算出整个M的形状而是通过迭代的方式去构建一个能包围原点的、M的凸包Simplex。2.2 支撑函数算法的“手杖”支撑函数Support Function是GJK算法的“手杖”。给定一个方向向量d形状C的支撑点S_C(d)是C中在方向d上投影最远的点。用公式表示就是S_C(d) argmax_{v ∈ C} (v · d)其中·表示点积。对于闵可夫斯基差M上的支撑点有一个关键性质S_{A-B}(d) S_A(d) - S_B(-d)。这意味着要得到M在方向d上的最远点我们只需要分别求出A在d方向上的最远点和B在反方向(-d)上的最远点然后相减即可。这让我们无需真正构造M就能获取其边界上的点。2.3 单纯形与迭代收敛GJK算法从一个初始方向通常是从A的中心指向B的中心开始通过支撑函数获得M上的一个点加入一个点集初始为单点集。然后它检查当前点集称为单纯形Simplex是否包含原点。如果不包含算法会计算一个新的搜索方向指向原点并获取该方向上的新支撑点将其加入点集。同时它会不断维护这个点集使其始终是当前已探索点中最接近原点的那个凸包对于2D是三角形3D是四面体。这个过程不断迭代直到单纯形包含原点碰撞或者新找到的支撑点无法让单纯形更靠近原点分离。关键理解为什么迭代会收敛因为每次找到的新支撑点都是在当前搜索方向下能到达的“最远点”这保证了新构建的单纯形比之前的更靠近原点或者至少不会更远。对于凸体这个过程是单调的最终要么包住原点要么证明原点不可达。3. 手把手实现2D版GJK算法核心代码解析理论足够扎实后我们开始动手实现。我们先从2D版本开始它更直观理解了2D扩展到3D就是顺理成章的事情。我们将创建一个名为GJKCollisionDetector的静态工具类。3.1 数据结构定义与支撑函数实现首先我们需要定义一些基础数据结构。在Unity中我们可以直接使用Vector2和Vector3在Cocos Creator中则使用Vec2和Vec3。为了通用性这里我们用伪代码风格描述你可以轻松替换为对应引擎的API。// Unity C# 示例结构 public struct Simplex { public ListVector2 points; // 当前单纯形的顶点列表 public int count; // 顶点数量 public Simplex(int capacity) { points new ListVector2(capacity); count 0; } public void Add(Vector2 point) { // 保持点集为凸包的前沿点移除不必要的内部点 // 具体逻辑在后续迭代中实现 points.Add(point); count; } public Vector2 this[int index] points[index]; } public static class GJKCollisionDetector { // 支撑函数计算形状在给定方向上的最远点 // 这里以多边形为例实际中可能是圆形、胶囊体等任何凸体 public static Vector2 GetSupport(ListVector2 vertices, Vector2 direction) { float maxDot float.MinValue; Vector2 supportPoint vertices[0]; foreach (var vertex in vertices) { float dot Vector2.Dot(vertex, direction); if (dot maxDot) { maxDot dot; supportPoint vertex; } } return supportPoint; } // 计算闵可夫斯基差上的支撑点 public static Vector2 Support(ListVector2 shapeA, ListVector2 shapeB, Vector2 direction) { Vector2 pointA GetSupport(shapeA, direction); Vector2 pointB GetSupport(shapeB, -direction); // B取反方向 return pointA - pointB; // 闵可夫斯基差 } }注意事项GetSupport函数的时间复杂度是O(n)n是顶点数。对于复杂形状这是性能瓶颈。在实际引擎中会对碰撞体如凸包进行预处理比如存储极值点或使用特殊数据结构加速。方向向量direction需要是归一化的吗在GJK中不需要。支撑函数只关心方向不关心长度。点积的大小比较与向量的模长成正比但最大值点不会因为归一化而改变。对于圆形、椭圆等有解析表达式的凸体可以直接计算支撑点无需遍历顶点效率极高。例如圆心的支撑点就是center radius * direction.normalized。3.2 GJK迭代过程与单纯形进化这是算法的核心循环。我们需要一个函数来判断两个形状是否相交并返回一个布尔值。public static bool GJKIntersect(ListVector2 shapeA, ListVector2 shapeB) { // 1. 初始化选择初始搜索方向通常从A中心指向B中心或任意方向如(1, 0) Vector2 centerA CalculateCenter(shapeA); Vector2 centerB CalculateCenter(shapeB); Vector2 direction centerB - centerA; // 如果两中心重合直接认为碰撞或需要特殊处理 if (direction.sqrMagnitude 1e-6) { direction Vector2.right; } // 2. 获取初始支撑点初始化单纯形一个点 Vector2 support Support(shapeA, shapeB, direction); Simplex simplex new Simplex(3); // 2D单纯形最多3个点 simplex.Add(support); // 3. 调整方向指向原点 direction -support; // 新的搜索方向是从支撑点指向原点 // 4. GJK主迭代循环最大迭代次数防止死循环 int maxIterations 20; for (int i 0; i maxIterations; i) { // 获取新方向上的支撑点 Vector2 newSupport Support(shapeA, shapeB, direction); // 判断终止条件如果新支撑点在方向上的投影小于0说明原点在此方向“后面”不可能相交 if (Vector2.Dot(newSupport, direction) 0) { return false; // 分离 } // 将新点加入单纯形 simplex.Add(newSupport); // 处理单纯形并更新下一次的搜索方向 // 这是GJK最精妙的部分根据单纯形是线段还是三角形判断是否包含原点并更新方向 if (HandleSimplex(ref simplex, ref direction)) { return true; // 单纯形包含原点碰撞发生 } // 否则用新的direction继续迭代 } // 理论上凸体迭代应收敛这里设置安全上限 return false; }3.3 单纯形处理算法的心脏HandleSimplex函数是GJK的灵魂它根据当前单纯形点集的状态判断是否包含原点并计算出下一个搜索方向。在2D中单纯形可以是1个点、2个点线段或3个点三角形。private static bool HandleSimplex(ref Simplex simplex, ref Vector2 direction) { switch (simplex.count) { case 2: // 单纯形是一条线段 (A, B) return HandleLineSegment(simplex[0], simplex[1], ref direction, ref simplex); case 3: // 单纯形是一个三角形 (A, B, C) return HandleTriangle(simplex[0], simplex[1], simplex[2], ref simplex); default: // 理论上不会进入这里因为初始点后第一次调用就是case 2 return false; } } private static bool HandleLineSegment(Vector2 a, Vector2 b, ref Vector2 direction, ref Simplex simplex) { Vector2 ab b - a; Vector2 ao -a; // 从a指向原点的向量 // 检查原点相对于线段AB的位置 // 使用向量叉积的符号在2D中叉积结果是一个标量表示有向面积 // 更通用的方法是使用向量投影和垂直分量 // 方法检查原点是否在AB的“前面”由A指向B的方向区域 // 计算AB的垂直向量法线指向原点一侧 Vector2 perp TripleProduct(ab, ao, ab); // 这是一个技巧得到垂直于AB且指向原点的向量 if (perp.sqrMagnitude 1e-6) { // 原点在线段AB上或非常接近 direction Vector2.zero; return true; // 实际上还需要进一步判断是否在线段内这里简化认为碰撞 } direction perp; // 更新单纯形保留离原点最近的点A或B移除另一个 // 通过点积判断如果AO在AB上的投影在AB之间保留AB如果超出B则方向指向B外侧保留B // 这里简化我们总是保留A和B因为下次迭代会由HandleSimplex重新处理 // 更精确的实现需要优化单纯形顶点 return false; } // 一个有用的向量运算a × (b × c) b(a·c) - c(a·b)在2D中可用于求垂直向量 private static Vector2 TripleProduct(Vector2 a, Vector2 b, Vector2 c) { float ac Vector2.Dot(a, c); float ab Vector2.Dot(a, b); return b * ac - c * ab; } private static bool HandleTriangle(Vector2 a, Vector2 b, Vector2 c, ref Simplex simplex) { // 检查原点是否在三角形ABC内 // 使用重心坐标法或连续边法Edge Test // 连续边法检查原点是否在每条边的“外侧” Vector2 ab b - a; Vector2 ac c - a; Vector2 ao -a; // 计算垂直于AB且指向三角形外侧的向量 Vector2 abPerp TripleProduct(ac, ab, ab); if (Vector2.Dot(abPerp, ao) 0) { // 原点在AB边的外侧 // 移除点C将单纯形退化为线段AB并设置搜索方向为abPerp simplex.points.RemoveAt(2); // 移除C simplex.count 2; direction abPerp; return false; } // 检查AC边 Vector2 acPerp TripleProduct(ab, ac, ac); if (Vector2.Dot(acPerp, ao) 0) { // 原点在AC边的外侧 // 移除点B将单纯形退化为线段AC simplex.points.RemoveAt(1); // 移除B (索引1是B因为A是0) simplex.count 2; direction acPerp; return false; } // 如果原点不在AB外侧也不在AC外侧那么它就在三角形ABC内部或非常接近 return true; // 碰撞 }实操心得TripleProduct技巧是2D GJK实现中的一个关键优化它避免了直接计算法向量和判断方向的复杂逻辑让代码更简洁。在HandleLineSegment中我们并没有真正优化单纯形移除多余点因为在下一次迭代中HandleSimplex会根据新的方向重新评估。一个更高效的实现会在每一步都保持单纯形是最小的即最接近原点的凸包子集。浮点数精度问题判断点积是否大于0时要使用一个很小的容差值如1e-6而不是直接与0比较以避免因浮点误差导致的误判或无限循环。4. 从GJK到EPA获取碰撞深度与法向量GJK算法只能告诉我们“是否碰撞”。但在游戏物理中我们通常还需要更多信息穿透深度Penetration Depth和碰撞法线Collision Normal以便于后续的碰撞响应如施加冲量、分离物体。这就需要EPAExpanding Polytope Algorithm算法登场了。EPA可以看作是GJK的延续当GJK判定为碰撞后EPA利用GJK最后得到的那个包含原点的单纯形一个三角形逐步扩展它使其逼近闵可夫斯基差M的边界从而找到原点到M边界的最短距离这个距离就是穿透深度方向就是碰撞法线。4.1 EPA算法原理简述输入GJK终止时得到的包含原点的单纯形2D为三角形3D为四面体。初始化多边形将这个单纯形作为初始的凸包多边形。迭代扩展 a. 在多边形的所有边2D或面3D中找到离原点最近的那条边面。 b. 沿着该边面的法线方向指向多边形外部调用支撑函数获得M边界上的一个新点。 c. 如果这个新点与旧边面的距离即原点到此边/面的距离在误差范围内则停止迭代。此时该最近边面的法线方向即为碰撞法线原点到该边面的距离即为穿透深度。 d. 否则将新点插入多边形分割最近的边面形成新的凸包重复此过程。输出穿透深度和碰撞法线。4.2 EPA核心代码实现2D版下面提供一个简化版的2D EPA实现用于演示原理。在实际应用中你需要处理更复杂的多边形插入和凸包维护逻辑。public static bool GJKEPAIntersect(ListVector2 shapeA, ListVector2 shapeB, out Vector2 normal, out float depth) { normal Vector2.zero; depth 0f; // 1. 先用GJK检测是否碰撞并获取最终的单纯形 Simplex simplex; if (!GJKIntersectWithSimplex(shapeA, shapeB, out simplex)) // 这是一个修改版的GJK返回最终单纯形 { return false; } // 2. EPA迭代 ListVector2 polytope new ListVector2(simplex.points); // 初始多边形就是GJK的最终单纯形 int maxEPAIterations 30; float tolerance 1e-4f; for (int i 0; i maxEPAIterations; i) { // 2a. 找到离原点最近的边 int edgeIndex; float minDistance; Vector2 closestNormal; FindClosestEdge(polytope, out edgeIndex, out minDistance, out closestNormal); // 2b. 沿着该边的法线方向获取支撑点 Vector2 support Support(shapeA, shapeB, closestNormal); // 2c. 计算支撑点到该边的距离实际上是原点到该边所在直线的有符号距离 float supportDistance Vector2.Dot(support, closestNormal); // 2d. 判断收敛如果新支撑点带来的“扩展”很小则认为已找到最近边界 if (supportDistance - minDistance tolerance) { normal closestNormal; depth supportDistance; // 或 minDistance根据实现略有不同 return true; } // 2e. 将新点插入多边形维护凸包 // 在最近边edgeIndex 和 edgeIndex1之间插入新点 polytope.Insert(edgeIndex 1, support); } // 迭代次数用尽返回近似结果或视为失败 // 通常这里会取最后一次迭代的结果 return false; } private static void FindClosestEdge(ListVector2 polytope, out int index, out float minDistance, out Vector2 normal) { index 0; minDistance float.MaxValue; normal Vector2.zero; for (int i 0; i polytope.Count; i) { int j (i 1) % polytope.Count; // 下一个顶点形成闭环 Vector2 a polytope[i]; Vector2 b polytope[j]; // 计算边AB的法线垂直于AB并指向多边形外部 Vector2 edge b - a; // 2D中获取垂直于边的向量(-edge.y, edge.x) 或 (edge.y, -edge.x)需要归一化并确保指向外部 Vector2 n new Vector2(-edge.y, edge.x).normalized; // 计算原点到边AB所在直线的距离有符号距离 float distance Vector2.Dot(n, a); // 因为a是边上的点n是单位法线点积即为距离 // 我们需要的是正距离原点在多边形外部在EPA中原点在内部距离应为正。 // 确保法线指向外部如果距离为负说明法线指向内部需要翻转 if (distance 0) { n -n; distance -distance; } if (distance minDistance) { minDistance distance; normal n; index i; // 记录边起始索引 } } }注意事项与常见问题凸包维护上述EPA实现中polytope.Insert非常简陋插入新点后可能破坏凸性。一个健壮的实现需要在插入后运行一次凸包算法如Andrews Monotone Chain来维护凸多边形或者更精细地处理边的替换。终止条件收敛条件supportDistance - minDistance tolerance是关键。supportDistance是新支撑点在法线方向上的投影理论上应等于原点到该边扩展后新边界的距离。当两者差值很小时说明扩展已微乎其微。法线方向碰撞法线normal的方向需要统一约定。通常约定为从物体A指向物体B或者指向需要施加冲量的方向即分离物体的方向。在计算响应时要注意方向的一致性。性能EPA的迭代次数通常很少10次但最坏情况下可能较多。设置最大迭代次数防止死循环并考虑使用更高效的数据结构如边列表来查找最近边。5. 在Unity与Cocos Creator中的集成与调试理论算法实现后我们需要将其集成到游戏引擎中并可视化调试确保它正确工作。5.1 Unity集成示例在Unity中我们可以创建一个MonoBehaviour脚本来驱动我们的GJK/EPA检测并使用Gizmos或新的Graphics.DrawMesh进行可视化。using UnityEngine; using System.Collections.Generic; public class GJKTest : MonoBehaviour { public Transform shapeA; public Transform shapeB; public Vector2[] verticesA; // 物体A的本地顶点坐标 public Vector2[] verticesB; // 物体B的本地顶点坐标 private ListVector2 worldVerticesA new ListVector2(); private ListVector2 worldVerticesB new ListVector2(); void Update() { // 将本地顶点转换到世界空间 UpdateWorldVertices(shapeA, verticesA, worldVerticesA); UpdateWorldVertices(shapeB, verticesB, worldVerticesB); // 执行碰撞检测 Vector2 collisionNormal; float penetrationDepth; bool isColliding GJKEPAIntersect(worldVerticesA, worldVerticesB, out collisionNormal, out penetrationDepth); // 在GUI或Log中显示结果 Debug.Log($碰撞: {isColliding}, 法线: {collisionNormal}, 深度: {penetrationDepth}); } void UpdateWorldVertices(Transform trans, Vector2[] localVerts, ListVector2 worldVerts) { worldVerts.Clear(); foreach (var localVert in localVerts) { Vector3 worldPos trans.TransformPoint(new Vector3(localVert.x, localVert.y, 0)); worldVerts.Add(new Vector2(worldPos.x, worldPos.y)); } } void OnDrawGizmos() { if (!Application.isPlaying) return; // 绘制形状A DrawPolygonGizmo(worldVerticesA, Color.blue); // 绘制形状B DrawPolygonGizmo(worldVerticesB, Color.green); // 如果碰撞绘制碰撞法线和深度 Vector2 normal; float depth; if (GJKEPAIntersect(worldVerticesA, worldVerticesB, out normal, out depth)) { // 计算一个参考点例如形状A的中心近似 Vector2 center GetCenter(worldVerticesA); Gizmos.color Color.red; Gizmos.DrawLine(center, center normal * depth); Gizmos.DrawSphere(center normal * depth, 0.05f); } } void DrawPolygonGizmo(ListVector2 vertices, Color color) { Gizmos.color color; for (int i 0; i vertices.Count; i) { int j (i 1) % vertices.Count; Gizmos.DrawLine(vertices[i], vertices[j]); } } Vector2 GetCenter(ListVector2 vertices) { Vector2 sum Vector2.zero; foreach (var v in vertices) sum v; return sum / vertices.Count; } }5.2 Cocos Creator (TypeScript) 集成示例在Cocos Creator中原理类似我们使用Graphics组件或DebugDraw来进行绘制。import { _decorator, Component, Vec2, Graphics, Color } from cc; const { ccclass, property } _decorator; ccclass(GJKTest) export class GJKTest extends Component { property({ type: Graphics }) graphics: Graphics | null null; property shapeAVertices: Vec2[] []; property shapeBVertices: Vec2[] []; private _worldVerticesA: Vec2[] []; private _worldVerticesB: Vec2[] []; update(deltaTime: number) { this.updateWorldVertices(this.node, this.shapeAVertices, this._worldVerticesA); // 假设shapeB是另一个节点 // this.updateWorldVertices(shapeBNode, this.shapeBVertices, this._worldVerticesB); let normal new Vec2(); let depth 0; let isColliding this.gjkepaIntersect(this._worldVerticesA, this._worldVerticesB, normal, depth); // 绘制逻辑可以放在这里或单独的渲染循环中 this.drawDebug(); } updateWorldVertices(node: Node, localVerts: Vec2[], outWorldVerts: Vec2[]) { outWorldVerts.length 0; let worldPos new Vec3(); for (let localVert of localVerts) { // 将本地坐标转换到世界坐标简化假设在2D平面 Vec3.set(worldPos, localVert.x, localVert.y, 0); node.getWorldPosition(worldPos); outWorldVerts.push(new Vec2(worldPos.x, worldPos.y)); } } drawDebug() { if (!this.graphics) return; this.graphics.clear(); // 绘制多边形A this.graphics.strokeColor Color.BLUE; this.graphics.moveTo(this._worldVerticesA[0].x, this._worldVerticesA[0].y); for (let i 1; i this._worldVerticesA.length; i) { this.graphics.lineTo(this._worldVerticesA[i].x, this._worldVerticesA[i].y); } this.graphics.close(); this.graphics.stroke(); // 绘制多边形B... // 绘制碰撞法线和深度... } // 将之前的C# GJK/EPA算法翻译成TypeScript here... gjkIntersect(shapeA: Vec2[], shapeB: Vec2[]): boolean { // ... 实现GJK算法 return false; } gjkepaIntersect(shapeA: Vec2[], shapeB: Vec2[], outNormal: Vec2, outDepth: number): boolean { // ... 实现GJKEPA算法 return false; } }调试技巧可视化单纯形在GJK迭代的每一步将当前的单纯形点、线、三角形绘制出来。观察它如何一步步逼近原点。这是理解算法动态过程的最佳方式。绘制搜索方向在每次迭代中绘制出当前的搜索方向向量。你会看到方向如何根据单纯形的状态而改变。EPA多边形可视化将EPA迭代过程中的扩展多边形绘制出来观察它如何从初始三角形“膨胀”并贴合闵可夫斯基差的边界。处理退化情况当两个物体刚好相切或者顶点共线时算法可能遇到数值不稳定。这时需要增加容错处理比如当单纯形面积接近零时视为分离或轻微穿透。6. 性能优化与高级话题一个基础的GJK/EPA实现已经能处理很多情况但在高性能游戏或处理大量物体时还需要进一步优化。6.1 缓存与增量计算对于运动中的物体其位置和旋转每帧变化。我们可以利用上一帧的碰撞信息来“预热”GJK算法缓存上一帧的单纯形如果两物体上一帧碰撞那么这一帧很可能仍然碰撞或非常接近。将上一帧GJK终止时的单纯形作为这一帧的初始单纯形可以极大减少迭代次数。缓存支撑点对于特定方向如果物体形状未变其支撑点可以缓存。但方向变化后缓存失效需权衡缓存开销与收益。6.2 形状特化支撑函数我们之前实现的GetSupport是通用的多边形遍历O(n)复杂度。对于特定形状可以O(1)计算圆形support center radius * direction.normalizedAABB轴对齐包围盒只需比较方向向量的正负号选择对应角落。OBB有向包围盒将方向向量变换到OBB的局部空间然后类似AABB处理。胶囊体计算线段两个端点的支撑点取点积更大的那个。 在引擎集成时你的碰撞检测系统应该根据碰撞体的类型分派到不同的支撑函数实现。6.3 扩展到3D将2D GJK扩展到3D核心思想完全一致但复杂度提升单纯形从点、线、三角形变为点、线、三角形、四面体。包含原点判断在3D中需要判断原点是否在四面体内。这可以通过计算四个面的有向体积标量三重积来判断所有面与原点同侧则在内部。搜索方向计算在HandleSimplex中情况更多。例如对于三角形单纯形需要判断原点在三角形的哪一侧利用法线并可能退化为边或保持为三角形。EPA从查找“最近边”变为查找“最近面”多边形扩展为多面体Polytope维护3D凸包更加复杂通常需要借助半边数据结构Half-Edge或现成的凸包库。6.4 与物理引擎的配合你手写的GJK/EPA通常不会完全替代引擎的物理引擎而是用于特定场景自定义碰撞过滤在引擎触发碰撞回调前用你的算法进行更精确或更定制化的预检测。特殊形状碰撞引擎不支持的复杂凸体或自定义复合形状。查询Raycast, OverlapGJK的思想可以用于其他空间查询如判断一个点是否在凸体内相当于与一个点形状进行GJK检测。性能对比与学习作为理解内置物理引擎的绝佳途径。7. 常见问题排查与实战心得在实际编码和调试中你几乎一定会遇到下面这些问题。7.1 算法陷入无限循环或提前退出症状两个明显相交的物体返回“未碰撞”或者程序卡死。排查浮点精度这是头号嫌犯。所有点积、距离的比较必须使用容差epsilon如1e-6f。例如if (dot 1e-6f)而不是if (dot 0)。方向向量零长在计算新的搜索方向direction后检查其长度。如果长度极小接近零说明单纯形可能已经包含原点或非常接近应直接返回碰撞。否则归一化或直接使用零向量可能导致除零错误或无效迭代。支撑函数错误确保你的支撑函数返回的是正确形状在给定方向上的最远点。用简单形状如两个正方形手动计算几个方向的支撑点进行验证。单纯形退化当三个点共线或四个点共面时单纯形退化体积为零无法判断原点在内还是在外。需要在代码中检测这种退化情况例如计算三角形面积或四面体体积并采取策略比如稍微扰动一个点或直接根据边缘情况判断。7.2 EPA结果不稳定或法线方向错误症状穿透深度时大时小碰撞法线方向跳动导致物理响应抖动。排查凸包维护EPA中插入新点后必须保证多边形/多面体始终是凸的。一个简单的插入可能产生凹点。实现一个快速的凸包维护例程或者使用更稳健的算法如“最近边插入后移除所有在新凸包内部的点”。法线方向一致性确保FindClosestEdge中计算的法线始终指向多边形外部对于内部的点距离为正。在3D中面的法线也要保持一致通常按顶点顺序右手定则。收敛条件过松或过紧容差值tolerance需要根据你的世界尺度调整。太小可能导致迭代次数过多太大可能提前终止得到不精确的结果。可以从1e-4开始调整。数值误差累积EPA迭代多次后顶点坐标可能积累误差。可以考虑定期对多边形顶点进行“清理”比如合并距离极近的点。7.3 性能瓶颈症状检测大量物体时帧率下降。优化粗检测先行永远先使用廉价的包围体如AABB、包围球进行快速拒绝测试。只有包围体相交的物体对才进入GJK/EPA检测。距离缓存对于运动连续的物体可以使用“分离轴”缓存。如果上一帧在某轴上分离且物体运动不大可以快速检查是否仍然分离。简化形状对于复杂的凸体可以用顶点数更少的凸包近似。或者使用GJK的特例比如对于两个球体直接计算圆心距离与半径和即可。并行化碰撞检测是天然可并行的。你可以将需要检测的物体对列表分发到多个线程或Job中处理。在Unity中可以考虑使用Burst Compiler和Job System来加速计算密集的支撑函数和向量运算。7.4 与引擎坐标系统一问题自己计算的碰撞法线和深度如何用于引擎的物理响应处理你需要将计算出的碰撞信息接触点、法线、深度转换为引擎物理系统期望的格式。例如在Unity中你可能需要填充ContactPoint结构或者直接计算并施加冲量Rigidbody.AddForceAtPosition(impulse, contactPoint)。注意坐标系的转换世界空间 vs 本地空间和单位的一致性。手写GJK/EPA是一个“知其然知其所以然”的深度实践过程。它可能会让你头疼一阵但一旦打通你对碰撞检测、计算几何乃至整个物理模拟的理解都会上升一个维度。这份代码不仅仅是一个工具更是你图形学与物理编程知识库中的一块坚实基石。当你再看到游戏中的物体自然碰撞、滚动时你看到的将不再是魔法而是优雅的数学在静静流淌。