3、静态碰撞检测：分离轴定理（SAT）原理与实现、GJK算法原理与实现

各位同学，今天我们来啃一块硬骨头——静态碰撞检测。说白了，就是判断两个物体在某一时刻是否“挨着”或“穿模”。

我刚开始做物理引擎时，觉得碰撞检测不就是算算距离嘛。结果第一次做多边形碰撞，两个矩形明明叠在一起了，我的代码却说没碰到……嗯，从那以后我老老实实学了分离轴定理（SAT）。

3.1 分离轴定理（SAT）原理

SAT的核心思想其实很简单：如果两个凸多边形没有重叠，那么一定能找到一条直线（分离轴），使得两个多边形在这条轴上的投影不重叠。

你想想看，两个物体在空间里，如果它们之间有一条缝隙，那从某个方向看过去，它们的影子肯定也是分开的。反过来，如果所有方向上的影子都重叠了，那它们肯定撞上了。

3.2 SAT的数学基础

我们需要做三件事：

1. 找到所有可能的分离轴——其实就是每个边的法线
2. 计算投影——把多边形顶点投影到这些轴上
3. 判断重叠——检查投影区间是否相交

我记得第一次实现时，卡在了“如何计算边的法线”上。其实很简单：

// 计算边的法线（二维）
Vector2 edge = p2 - p1;
Vector2 normal = new Vector2(-edge.y, edge.x).normalized;

注意，这里要归一化。不归一化也能判断是否碰撞，但计算穿透深度时会出问题。我踩过这个坑。

3.3 SAT的实现步骤

直接上代码吧，这样更直观：

bool SATCollision(Polygon a, Polygon b) {
    // 获取两个多边形的所有边法线
    List<Vector2> axes = new List<Vector2>();
    
    // 添加多边形a的边法线
    for (int i = 0; i < a.vertices.Length; i++) {
        Vector2 edge = a.vertices[(i+1) % a.vertices.Length] - a.vertices[i];
        axes.Add(new Vector2(-edge.y, edge.x).normalized);
    }
    
    // 添加多边形b的边法线
    for (int i = 0; i < b.vertices.Length; i++) {
        Vector2 edge = b.vertices[(i+1) % b.vertices.Length] - b.vertices[i];
        axes.Add(new Vector2(-edge.y, edge.x).normalized);
    }
    
    // 对每个轴进行投影测试
    foreach (Vector2 axis in axes) {
        float minA, maxA, minB, maxB;
        ProjectPolygon(a, axis, out minA, out maxA);
        ProjectPolygon(b, axis, out minB, out maxB);
        
        // 如果任何一个轴上投影不重叠，则没有碰撞
        if (maxA < minB || maxB < minA) {
            return false;
        }
    }
    
    return true;
}

void ProjectPolygon(Polygon poly, Vector2 axis, out float min, out float max) {
    float dot = Vector2.Dot(poly.vertices[0], axis);
    min = max = dot;
    
    for (int i = 1; i < poly.vertices.Length; i++) {
        dot = Vector2.Dot(poly.vertices[i], axis);
        if (dot < min) min = dot;
        if (dot > max) max = dot;
    }
}

3.4 GJK算法原理

SAT虽然直观，但有个问题——当多边形顶点很多时，要检测的轴也很多。GJK算法就聪明多了，它用迭代的方式，效率更高。

GJK的核心思想是：两个凸多边形的闵可夫斯基差如果包含原点，则它们碰撞。

什么叫闵可夫斯基差？说白了就是：把多边形A的所有点，减去多边形B的所有点，得到一个新的点集。如果这个新点集包含原点(0,0)，说明A和B有重叠。

我刚开始也觉得这个概念有点绕。但你可以这样理解：

• 如果A和B碰撞，那么A中至少有一个点a，B中有一个点b，使得a - b = 0
• 也就是说，原点在闵可夫斯基差里

3.5 GJK的实现步骤

GJK不直接计算整个闵可夫斯基差，而是通过迭代构建一个单纯形（simplex），逐步逼近原点：

bool GJKCollision(ConvexShape a, ConvexShape b) {
    // 初始方向，随便选一个
    Vector2 direction = new Vector2(1, 0);
    
    // 获取第一个支撑点
    Vector2 support = GetSupport(a, b, direction);
    
    // 单纯形（这里用列表表示）
    List<Vector2> simplex = new List<Vector2>();
    simplex.Add(support);
    
    // 反向搜索
    direction = -support;
    
    // 迭代
    for (int i = 0; i < 20; i++) {  // 防止死循环
        support = GetSupport(a, b, direction);
        
        // 如果支撑点没有越过原点，则无碰撞
        if (Vector2.Dot(support, direction) < 0) {
            return false;
        }
        
        simplex.Add(support);
        
        // 检查单纯形是否包含原点
        if (CheckSimplex(simplex, ref direction)) {
            return true;
        }
    }
    
    return false;
}

Vector2 GetSupport(ConvexShape a, ConvexShape b, Vector2 direction) {
    // 获取a在direction方向上的最远点
    Vector2 pointA = a.GetFarthestPointInDirection(direction);
    // 获取b在-direction方向上的最远点
    Vector2 pointB = b.GetFarthestPointInDirection(-direction);
    // 闵可夫斯基差
    return pointA - pointB;
}

3.6 SAT vs GJK：怎么选？

特性	SAT	GJK
适用形状	凸多边形（2D/3D）	凸形状（任意维度）
实现难度	简单直观	中等，概念较抽象
性能	O(n*m)，n和m为边数	O(log n)，迭代收敛快
额外信息	可直接得到穿透深度和法线	需要额外算法（如EPA）获取穿透信息
适用场景	顶点数少的2D碰撞	顶点数多或3D碰撞

我个人习惯是：2D游戏用SAT，3D游戏用GJK。为什么？因为2D中SAT的轴数量可控，代码也容易调试。3D中SAT的轴会爆炸（每个面的法线+边的叉积），GJK反而更高效。

3.7 避坑指南

我曾经在项目中遇到一个诡异的bug：两个物体明明没碰到，SAT却说碰撞了。查了两天才发现，是顶点顺序搞反了——多边形顶点必须是顺时针或逆时针顺序，不能乱。

还有一次，GJK在边缘情况（刚好相切）时返回了错误结果。这是因为浮点数精度问题。解决方案是加一个很小的epsilon：

if (Mathf.Abs(dot) < 1e-6f) {
    // 视为刚好接触，按碰撞处理
    return true;
}

好了，静态碰撞检测的核心就这些。下节课我们讲动态碰撞检测——物体在运动过程中如何检测碰撞，那又是另一番天地了。

---

公众号:蓝海资料掘金营，微信deep3321