游戏物理引擎实战：用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避免了计算所有可能的分离轴，转而通过迭代逼近的方式判断碰撞。下面是一个简单的性能对比：

提示：虽然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) { List<Vector2> result = new List<Vector2>(); 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通过迭代构建单纯形来逼近原点，整个过程分为几个典型阶段：

1. 初始化：选择随机方向获取第一个支撑点
2. 线段阶段：两个点构成的单纯形
3. 三角形阶段：三个点判断是否包含原点
4. 终止条件：包含原点(碰撞)或无法更接近原点(无碰撞)

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[(i+1)%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 List<Vector2> points = new List<Vector2>(); 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[(i+1)%simplex.length]; graphics.moveTo(p1.x, p1.y); graphics.lineTo(p2.x, p2.y); } graphics.stroke(); }

6.3 迭代轨迹记录

记录并回放GJK的搜索过程，有助于理解算法行为：

List<Vector2> searchPath = new List<Vector2>(); 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 非凸体处理

通过凸分解将复杂形状拆分为多个凸体：

1. 使用V-HACD等算法进行自动分解
2. 对每个凸部分分别进行GJK检测
3. 合并检测结果

// 复合碰撞体检测 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 跨平台考量

不同平台的性能特性：

在移动项目中，可以适当降低迭代次数或使用定点数运算来提升性能。