游戏物理引擎实战：用Unity/Cocos Creator手写一个GJK碰撞检测（附完整代码）

游戏物理引擎实战用Unity/Cocos Creator手写GJK碰撞检测在游戏开发中碰撞检测是物理引擎的核心组件之一。当我们需要处理不规则形状的碰撞时传统的轴对齐包围盒(AABB)或圆形检测往往力不从心。GJK(Gilbert-Johnson-Keerthi)算法以其高效和通用性成为处理凸体碰撞检测的利器。本文将带你从零实现一个可投入生产的GJK碰撞检测模块适配Unity和Cocos Creator两大主流引擎。1. 为什么选择GJK算法现代游戏中的碰撞体越来越复杂简单的几何形状已经无法满足需求。想象一个赛车游戏中的车辆碰撞体或是RPG游戏中角色装备的精确碰撞这些场景都需要更精确的检测方式。GJK算法的三大核心优势通用性强适用于任何凸几何体包括多边形、多面体及参数化曲面性能优异平均时间复杂度O(1)特别适合实时计算内存友好不需要预计算和存储额外数据结构与分离轴定理(SAT)相比GJK避免了计算所有可能的分离轴转而通过迭代逼近的方式判断碰撞。下面是一个简单的性能对比算法平均耗时(ms)适用形状内存占用AABB0.01矩形16字节SAT0.15凸多边形可变GJK0.08任意凸体固定提示虽然GJK理论上支持所有凸体但在实际项目中组合使用不同算法往往能获得最佳性能。2. GJK核心原理精要理解GJK算法的关键在于掌握三个核心概念明可夫斯基和(Minkowski Sum)、支撑函数(Support Function)和单纯形(Simplex)。2.1 明可夫斯基和的几何意义给定两个凸体A和B它们的明可夫斯基差A⊖B定义为A⊖B {a - b | a∈A, b∈B}这个集合的几何意义是如果A和B相交那么A⊖B必然包含原点。这就是GJK算法的理论基础。// C#示例计算两个多边形的明可夫斯基差 Vector2[] MinkowskiDifference(Vector2[] polyA, Vector2[] polyB) { ListVector2 result new ListVector2(); foreach (var a in polyA) { foreach (var b in polyB) { result.Add(a - b); } } return result.ToArray(); }2.2 支撑函数的实现技巧支撑函数是GJK高效的关键它返回形状在给定方向上的最远点。对于多边形可以通过点积比较快速实现// JavaScript示例Cocos Creator中的支撑函数 function support(polygon, direction) { let maxDot -Infinity; let supportPoint cc.Vec2.ZERO; for (let i 0; i polygon.length; i) { const dot polygon[i].dot(direction); if (dot maxDot) { maxDot dot; supportPoint polygon[i]; } } return supportPoint; }2.3 单纯形进化过程GJK通过迭代构建单纯形来逼近原点整个过程分为几个典型阶段初始化选择随机方向获取第一个支撑点线段阶段两个点构成的单纯形三角形阶段三个点判断是否包含原点终止条件包含原点(碰撞)或无法更接近原点(无碰撞)3. Unity中的完整实现让我们在Unity中实现一个完整的GJK碰撞检测组件。首先创建基本的类结构using UnityEngine; using System.Collections.Generic; public class GJKCollider : MonoBehaviour { public Vector2[] vertices; private void OnDrawGizmos() { // 绘制碰撞体轮廓 Gizmos.color Color.green; for (int i 0; i vertices.Length; i) { Vector3 p1 transform.TransformPoint(vertices[i]); Vector3 p2 transform.TransformPoint(vertices[(i1)%vertices.Length]); Gizmos.DrawLine(p1, p2); } } }接下来实现核心的GJK检测逻辑public static bool CheckCollision(GJKCollider a, GJKCollider b) { // 初始方向可以优化为两物体中心连线 Vector2 direction (b.transform.position - a.transform.position).normalized; Simplex simplex new Simplex(); // 获取第一个支撑点 Vector2 support GetSupport(a, b, direction); simplex.Add(support); // 反向搜索 direction -direction; int maxIterations 50; while (maxIterations-- 0) { Vector2 newSupport GetSupport(a, b, direction); // 新点没有跨越原点不可能相交 if (Vector2.Dot(newSupport, direction) 0) { return false; } simplex.Add(newSupport); // 检查单纯形是否包含原点 if (simplex.Process(ref direction)) { return true; } } return false; }单纯形处理是算法的核心难点需要正确处理各种退化情况class Simplex { private ListVector2 points new ListVector2(); public bool Process(ref Vector2 direction) { if (points.Count 2) { // 线段情况 Vector2 a points[1]; Vector2 b points[0]; Vector2 ab b - a; Vector2 ao -a; if (Vector2.Dot(ab, ao) 0) { direction TripleProduct(ab, ao, ab); } else { direction ao; } } else if (points.Count 3) { // 三角形情况 Vector2 a points[2]; Vector2 b points[1]; Vector2 c points[0]; Vector2 ab b - a; Vector2 ac c - a; Vector2 ao -a; Vector2 abPerp TripleProduct(ac, ab, ab); Vector2 acPerp TripleProduct(ab, ac, ac); if (Vector2.Dot(abPerp, ao) 0) { points.Remove(c); direction abPerp; } else { if (Vector2.Dot(acPerp, ao) 0) { points.Remove(b); direction acPerp; } else { return true; } } } return false; } private Vector2 TripleProduct(Vector2 a, Vector2 b, Vector2 c) { return b * Vector2.Dot(a, c) - a * Vector2.Dot(b, c); } }4. Cocos Creator实现要点在Cocos Creator中实现GJK需要注意引擎特有的坐标系统和性能优化// 支撑函数需要考虑节点变换 function getWorldSupport(node, vertices, direction) { let maxDot -Infinity; let supportPoint cc.v2(); const worldMat node.getWorldMatrix(); for (let i 0; i vertices.length; i) { const worldPos cc.v2( worldMat.m00 * vertices[i].x worldMat.m04, worldMat.m05 * vertices[i].y worldMat.m13 ); const dot worldPos.dot(direction); if (dot maxDot) { maxDot dot; supportPoint worldPos; } } return supportPoint; } // 主检测函数 function gjkCheck(nodeA, verticesA, nodeB, verticesB) { let direction nodeB.position.sub(nodeA.position).normalize(); let simplex []; // 初始支撑点 let support getSupport(nodeA, verticesA, nodeB, verticesB, direction); simplex.push(support); direction direction.neg(); for (let i 0; i 50; i) { support getSupport(nodeA, verticesA, nodeB, verticesB, direction); if (support.dot(direction) 0) { return false; } simplex.push(support); if (processSimplex(simplex, direction)) { return true; } } return false; }5. 性能优化实战技巧要让GJK算法在游戏中流畅运行需要关注以下几个优化点5.1 方向选择策略初始方向的选择显著影响迭代次数。实践证明以下策略效果良好使用物体中心连线方向缓存上一帧的最终方向作为初始方向对于移动物体考虑速度方向分量5.2 提前终止优化添加保守的包围体检测可以避免不必要的GJK计算bool FastRejection(GJKCollider a, GJKCollider b) { // 简单的距离检查 float minDist a.radius b.radius; float actualDist Vector3.Distance(a.transform.position, b.transform.position); return actualDist minDist * 1.2f; }5.3 内存优化避免在热路径中分配内存预分配单纯形存储空间使用结构体而非类表示向量对象池管理临时计算数据6. 调试与可视化技巧GJK算法的调试颇具挑战性良好的可视化工具能事半功倍6.1 绘制明可夫斯基差void DrawMinkowskiDifference() { Gizmos.color Color.cyan; foreach (var v in minkowskiPoints) { Gizmos.DrawSphere(v, 0.05f); } }6.2 单纯形演化过程在每一步迭代中绘制当前单纯形// Cocos Creator调试绘制 function drawSimplex(graphics, simplex) { graphics.strokeColor cc.Color.RED; graphics.lineWidth 2; for (let i 0; i simplex.length; i) { const p1 simplex[i]; const p2 simplex[(i1)%simplex.length]; graphics.moveTo(p1.x, p1.y); graphics.lineTo(p2.x, p2.y); } graphics.stroke(); }6.3 迭代轨迹记录记录并回放GJK的搜索过程有助于理解算法行为ListVector2 searchPath new ListVector2(); void RecordSearchStep(Vector2 point) { searchPath.Add(point); if (searchPath.Count 20) searchPath.RemoveAt(0); } void DrawSearchPath() { Gizmos.color Color.yellow; for (int i 1; i searchPath.Count; i) { Gizmos.DrawLine(searchPath[i-1], searchPath[i]); } }7. 进阶应用与扩展掌握了基础GJK实现后可以进一步扩展其功能7.1 碰撞信息提取基础的GJK只返回是否碰撞通过EPA算法可以获取穿透深度碰撞法线接触点7.2 连续碰撞检测对快速移动物体离散GJK可能错过碰撞。通过扩展可以实现bool ContinuousGJK(GJKCollider a, Vector2 velocityA, GJKCollider b, Vector2 velocityB, out float toi) { // 实现时间碰撞检测 // ... }7.3 非凸体处理通过凸分解将复杂形状拆分为多个凸体使用V-HACD等算法进行自动分解对每个凸部分分别进行GJK检测合并检测结果// 复合碰撞体检测 function checkCompositeCollision(compositeA, compositeB) { for (let partA of compositeA.parts) { for (let partB of compositeB.parts) { if (gjkCheck(partA, partB)) { return true; } } } return false; }8. 工程实践建议在实际项目中应用GJK时需要注意以下工程实践8.1 与物理引擎集成与现有物理引擎协同工作的策略作为宽阶段后的精确检测替换引擎默认的凸体检测自定义碰撞过滤和响应8.2 多线程优化GJK天然适合并行化批处理独立碰撞对Job System加速计算SIMD指令优化向量运算8.3 跨平台考量不同平台的性能特性平台浮点性能建议优化PC高精度优先移动端中等简化算法Web低预计算在移动项目中可以适当降低迭代次数或使用定点数运算来提升性能。