分离轴定理（SAT）

问题：形状会旋转

上一篇的 AABB 测试快，是因为盒子的边永远与坐标轴平行，可以把 x、y 两个方向拆开处理。可是游戏里的东西会转：被炸飞的箱子、斜坡、俯视角游戏里朝向鼠标的坦克、横版游戏里的多边形地形。

给旋转的形状套一个 AABB 再测试，会得到大量“假相交”。比如两个旋转 45° 的正方形，它们的包围盒已经重叠了，本体之间却还隔着一道缝。本文的单元测试里就有这样一个例子。

我们需要一个对任意朝向的凸多边形都成立的精确测试。

思路：找一个能把影子分开的方向

想象从某个方向打一束平行光，两个形状在地上各投下一段影子。如果存在某个方向，让两段影子不重叠，那么这两个形状一定不相交。这很直观：影子分开了，说明中间能插进一块垂直于光线的薄板。

反过来呢？分离轴定理（Separating Axis Theorem，SAT）说：对于两个凸形状，如果它们不相交，就一定能找到这样一个方向。这个方向称为分离轴。

所以判断两个凸形状是否相交，就变成了“能不能找到一条分离轴”。

投影

“影子”在数学上就是投影：形状在单位向量 axis 上的投影，是所有点与 axis 点积的范围，也就是一个区间 [min, max]。凸多边形的投影只需要看顶点：

cpp/collision/sat/sat.h

// 形状在单位向量 axis 上的投影是一个区间：所有顶点与 axis 点积的最小值和最大值
struct Interval {
    float min, max;
};

inline Interval project(const ConvexPolygon& p, Vec2 axis) {
    float lo = dot(p.v[0], axis), hi = lo;
    for (int i = 1; i < p.size(); ++i) {
        float d = dot(p.v[i], axis);
        lo = std::min(lo, d);
        hi = std::max(hi, d);
    }
    return {lo, hi};
}

// 圆的投影：圆心的投影 ± 半径
inline Interval project(const Circle& c, Vec2 axis) {
    float m = dot(c.center, axis);
    return {m - c.radius, m + c.radius};
}

只需要检查有限条轴

方向有无穷多个，不可能一个个试。好在对凸多边形来说，只需要检查两者所有边的法线。

原因是：两个凸多边形分开时，能把它们隔开的那块“薄板”总可以转到与其中某一条边贴合的位置。薄板的方向是这条边，分离轴就是这条边的法线。所以，如果所有边的法线上投影都重叠，就不可能存在其他分离轴。

cpp/collision/sat/sat.h

// 凸多边形。顶点按屏幕上的顺时针排列（y 朝下），此时边 e 的外法线是 (e.y, -e.x)
struct ConvexPolygon {
    std::vector<Vec2> v;

    int size() const { return static_cast<int>(v.size()); }
    Vec2 vertex(int i) const { return v[i % v.size()]; }
    Vec2 edge(int i) const { return vertex(i + 1) - vertex(i); }
    // 第 i 条边（v[i] → v[i+1]）的单位外法线
    Vec2 normal(int i) const {
        Vec2 e = edge(i);
        return normalized({e.y, -e.x});
    }
};

cpp/collision/sat/sat.h

// 只要有一条轴把两个投影分开，就一定不相交 —— 可以立即返回
template <class A, class B>
bool separatedOn(const A& a, const B& b, Vec2 axis) {
    Interval ia = project(a, axis), ib = project(b, axis);
    return ia.max <= ib.min || ib.max <= ia.min;
}

inline bool overlaps(const ConvexPolygon& a, const ConvexPolygon& b) {
    for (int i = 0; i < a.size(); ++i)
        if (separatedOn(a, b, a.normal(i))) return false;
    for (int i = 0; i < b.size(); ++i)
        if (separatedOn(a, b, b.normal(i))) return false;
    return true;  // 所有候选轴上都重叠：相交
}

注意两件事：

• 两个形状的边法线都要检查。只检查一个形状的边，会漏掉“只有另一个形状的边才能把它们分开”的情况。下面演示的初始状态就是这样：A 的五条边法线上投影全都重叠，直到 B 的第一条边才找到分离轴。
• 找到一条分离轴就可以立即返回。实际游戏中，大部分物体对是分开的，往往一两条轴就能得出结论。

亲手试一试

图 2.2每一步检查一条候选轴：朱红粗线是生成这条轴的边，箭头是它的法线；旁边的长直线就是这条轴，与 A、B 同色的两条线段分别是它们的投影，虚线标出投影的端点来自哪个顶点。找到间隙（gap）就立即停止。拖动形状移动，拖动空心小圆旋转；上方按钮切换形状 B。单独打开 ↗

几个值得做的小实验：

1. 单步执行初始状态，观察右侧列表：A 的五条轴都重叠，第六条轴（B0）才出现间隙。
2. 把 B 拖进 A 里，等所有轴检查完：每条轴都显示一个推出距离（push），最小的那条被标为 min，它就是最小分离向量的方向。两个朱红圆点是接触点。
3. 切换到 circle。圆没有边，候选轴变成 A 的五条边法线，再加上一条从 A 最近的顶点指向圆心的轴（v->C）。把圆拖到 A 的某个角附近，看看哪条轴把它们分开。
4. 切换到 box，旋转 B，注意 B0 与 B2、B1 与 B3 的结果总是相同：盒子的对边平行，法线只差一个符号，实际上只有两条不同的轴。

最小分离向量

和上一篇一样，知道“相交了”还不够，物理系统需要知道往哪个方向推、推多远。SAT 顺带就能给出答案：在每条轴上，算出把 B 推出去需要的距离，所有轴里最小的那个就是最小分离向量（MTV）。

cpp/collision/sat/sat.h

// 在一条轴上，b 可以往 +axis 推出（推到 a 的投影之外），也可以往 -axis 推出，取较短的一个。
// push ≤ 0 表示这条轴已经把两者分开了
struct AxisTest {
    Vec2 axis;    // 推出方向（已带符号）：把 b 沿它移动 push 就能在这条轴上分开
    float push;
};

inline AxisTest testAxis(Interval a, Interval b, Vec2 axis) {
    float forward = a.max - b.min;   // 沿 +axis 推出 b 需要的距离
    float backward = b.max - a.min;  // 沿 -axis 推出 b 需要的距离
    return forward < backward ? AxisTest{axis, forward} : AxisTest{-axis, backward};
}

这里沿用了上一篇的教训：推出距离不是两个区间的重叠长度。一个区间包含另一个时，要推的距离比重叠长度更长。本文的单元测试里，把这一行改成重叠长度后，有 133 个随机物体对推开之后仍然重叠。

cpp/collision/sat/sat.h

// 最小分离向量：所有候选轴里 push 最小的那条。返回的 normal 从 a 指向 b
inline std::optional<Contact> contact(const ConvexPolygon& a, const ConvexPolygon& b) {
    AxisTest best{{0, 0}, std::numeric_limits<float>::infinity()};
    auto consider = [&](Vec2 axis) {
        AxisTest t = testAxis(project(a, axis), project(b, axis), axis);
        if (t.push < best.push) best = t;
        return t.push > 0;  // false：找到了分离轴
    };
    for (int i = 0; i < a.size(); ++i)
        if (!consider(a.normal(i))) return std::nullopt;
    for (int i = 0; i < b.size(); ++i)
        if (!consider(b.normal(i))) return std::nullopt;
    return Contact{best.axis, best.push, {0, 0}};  // 接触点由 collide() 计算
}

为什么最小值就是正确答案

沿任何一条候选轴推出 push 的距离，两个形状都会分开，所以真正的最小分离距离不会比这些值里的最小值更大。另一方面，两个凸多边形的“最短逃离方向”一定垂直于它们的某条边（严格地说，是它们的闵可夫斯基差的某条边，下一篇 GJK 会讲到），也就在候选轴里。单元测试也验证了这一点：随机选 8 个方向，在每个方向上二分查找至少要推多远，结果从来不会比 MTV 更短。

多边形与圆

圆没有边，也就没有边法线。它的投影很简单：圆心的投影加减半径。那么候选轴是什么？

多边形的边法线照样要检查。除此之外，当圆靠近多边形的角时，能把它们分开的方向是“角点 → 圆心”，这个方向不是任何一条边的法线。所以要再加一条轴：离圆心最近的顶点指向圆心的方向。

cpp/collision/sat/sat.h

// 多边形与圆：圆没有边，候选轴是多边形的边法线，再加上"离圆心最近的顶点 → 圆心"这一条
inline Vec2 closestVertexAxis(const ConvexPolygon& p, Vec2 center) {
    Vec2 best = p.v[0];
    for (Vec2 q : p.v)
        if (lengthSq(q - center) < lengthSq(best - center)) best = q;
    Vec2 d = normalized(center - best);
    return d == Vec2{0, 0} ? Vec2{1, 0} : d;
}

inline bool overlaps(const ConvexPolygon& a, const Circle& b) {
    for (int i = 0; i < a.size(); ++i)
        if (separatedOn(a, b, a.normal(i))) return false;
    return !separatedOn(a, b, closestVertexAxis(a, b.center));
}

接触点：参考边与入射边

MTV 告诉我们怎么把两个物体分开，但物理引擎还需要知道在哪里接触，才能计算让物体转动的力矩。

一个点往往不够。一个箱子平放在地面上，底边与地面是一整条线段在接触。如果只记录一个接触点，箱子会绕着这个点摇晃，永远放不平。所以通常用 1 到 2 个点来描述接触，称为接触流形（contact manifold）。

计算方法是 Box2D 等引擎使用的裁剪（clipping）：

1. 在 A 上找外法线与 MTV 方向最接近的边，在 B 上找外法线与 MTV 方向最相反的边。两者中更“正对”MTV 的那条称为参考边，另一条称为入射边。
2. 用参考边两端的两个侧面（垂直于参考边、经过端点的直线）裁剪入射边，切掉伸出参考边范围的部分。
3. 剩下的线段端点里，只保留已经穿过参考边（在参考边“后面”）的点。

cpp/collision/sat/sat.h

// 接触流形：物理引擎需要的不只是一个点。两个盒子面贴面压在一起时，接触是一条线段，
// 用两个端点表示，才能让箱子稳稳地放平而不是绕着一个点摇晃。
struct Manifold {
    Vec2 normal;        // 从 a 指向 b
    float depth;
    int count = 0;      // 接触点个数：1 或 2
    Vec2 points[2];
    float depths[2];    // 每个接触点各自的穿透深度
};

// 外法线与 n 最接近的边
inline int mostAlignedEdge(const ConvexPolygon& p, Vec2 n) {
    int best = 0;
    float bestDot = -std::numeric_limits<float>::infinity();
    for (int i = 0; i < p.size(); ++i) {
        float d = dot(p.normal(i), n);
        if (d > bestDot) bestDot = d, best = i;
    }
    return best;
}

// 保留线段 in 上满足 dot(p, dir) ≤ limit 的部分
inline int clipSegment(const Vec2 in[2], Vec2 out[2], Vec2 dir, float limit) {
    int k = 0;
    float d0 = dot(in[0], dir) - limit, d1 = dot(in[1], dir) - limit;
    if (d0 <= 0) out[k++] = in[0];
    if (d1 <= 0) out[k++] = in[1];
    if (d0 * d1 < 0) out[k++] = in[0] + (in[1] - in[0]) * (d0 / (d0 - d1));
    return k;
}

inline std::optional<Manifold> collide(const ConvexPolygon& a, const ConvexPolygon& b) {
    auto c = contact(a, b);
    if (!c) return std::nullopt;
    Vec2 n = c->normal;
    // 1. 两边各找一条最"正对"对方的边。更垂直于 n 的那条作为参考边，另一条是入射边
    int ea = mostAlignedEdge(a, n), eb = mostAlignedEdge(b, -n);
    bool refIsA = dot(a.normal(ea), n) >= dot(b.normal(eb), -n) - 1e-3f;  // 略偏向 a，避免来回跳
    const ConvexPolygon& ref = refIsA ? a : b;
    const ConvexPolygon& inc = refIsA ? b : a;
    int er = refIsA ? ea : eb, ei = refIsA ? eb : ea;

    // 2. 用参考边两端的侧面裁剪入射边
    Vec2 r0 = ref.vertex(er), r1 = ref.vertex(er + 1);
    Vec2 t = normalized(r1 - r0);
    Vec2 seg[2] = {inc.vertex(ei), inc.vertex(ei + 1)}, tmp[2], out[2];
    if (clipSegment(seg, tmp, -t, -dot(r0, t)) < 2) return Manifold{n, c->depth, 1, {seg[0]}, {c->depth}};
    if (clipSegment(tmp, out, t, dot(r1, t)) < 2) return Manifold{n, c->depth, 1, {tmp[0]}, {c->depth}};

    // 3. 只保留在参考边"后面"（已经穿透进去）的点
    Manifold m{n, c->depth};
    Vec2 rn = ref.normal(er);
    float face = dot(r0, rn);
    for (Vec2 p : out) {
        float sep = dot(p, rn) - face;
        if (sep <= 0) {
            m.points[m.count] = p;
            m.depths[m.count++] = -sep;
        }
    }
    if (m.count == 0) {  // 数值误差导致两个点都在外面：退化为一个点
        m.count = 1;
        m.points[0] = (out[0] + out[1]) * 0.5f;
        m.depths[0] = c->depth;
    }
    return m;
}

高亮的那一行有个细节：两条边几乎同样“正对”时，如果每帧因为浮点误差而交替选择不同的参考边，接触点就会来回跳，箱子会微微抖动。给其中一方一点偏向，就能让选择稳定下来。

裁剪出的点只是近似

单元测试发现，穿透很深时，裁剪得到的接触点可能落在参考多边形外面：它们只保证在入射边上、在参考边的范围内、在参考边后面。物理引擎每帧都会把物体推开，穿透始终很浅，这时接触点是准确的。测试也据此分成两部分：任意穿透时只检查点在入射边上，浅穿透时才检查点在重叠区域附近。

实测：多快？

在随机放置、随机旋转的正多边形对上测量每次测试的耗时（每组 20000 对，取多次运行中的最快值）：

顶点数	物体对	overlaps	不单位化法线	contact（求 MTV）
4	约 30% 相交	34 ns	26 ns	40 ns
4	全部相交	46 ns	34 ns	57 ns
8	约 30% 相交	79 ns	59 ns	89 ns
8	全部相交	175 ns	119 ns	190 ns
16	约 30% 相交	282 ns	231 ns	283 ns
16	全部相交	684 ns	557 ns	717 ns

几点观察：

• 相交时的代价随顶点数平方增长。两个 n 边形有 2n 条候选轴，每条轴都要投影 2n 个顶点，一共 4n² 次点积。顶点数翻倍，耗时约变为 3.8~3.9 倍。这也是物理引擎限制多边形顶点数的原因之一，Box2D 默认最多 8 个。
• 分开的物体对很便宜。随机物体对平均只需检查 1.4~1.9 条轴就能找到分离轴，提前返回的效果非常明显。
• 判断是否相交时，法线不需要单位化。轴的长度只会把两个区间同比例放大，比较结果不变。省掉每条轴一次开方，快了约 20%~30%。只有要计算 MTV 的穿透深度时才需要单位向量。
• 求 MTV 几乎是免费的：相交时本来就要检查所有轴，顺手记下最小值，只比单纯判断多花 0~25%。

一个没有带来提速的优化：缓存分离轴

物体每帧只移动一点点，上一帧找到的分离轴，这一帧很可能还有效。一个常见的建议是把它记下来，下一帧先试这一条：

cpp/collision/sat/sat.h

// 时间相干性：物体每帧只移动一点点，上一帧的分离轴这一帧很可能仍然有效。
// 记住它，下一帧先试这一条。axis 是候选轴的编号：[0, a.size()) 属于 a，之后属于 b
struct SatCache {
    int axis = -1;
};

inline bool overlapsCached(const ConvexPolygon& a, const ConvexPolygon& b, SatCache& cache) {
    int na = a.size(), n = na + b.size();
    auto axisAt = [&](int i) { return i < na ? a.normal(i) : b.normal(i - na); };
    if (cache.axis >= 0 && cache.axis < n && separatedOn(a, b, axisAt(cache.axis))) return false;
    for (int i = 0; i < n; ++i) {
        if (i != cache.axis && separatedOn(a, b, axisAt(i))) {
            cache.axis = i;
            return false;
        }
    }
    cache.axis = -1;
    return true;
}

为了模拟真实情况，测试只保留了包围盒重叠的物体对（宽相之后才轮到 SAT），让 2000 对八边形缓慢移动、旋转 300 帧：

	分开的测试平均检查几条轴	每次测试
不缓存	2.69	168 ns
缓存分离轴	1.20（95% 命中）	173 ns

缓存的命中率很高，检查的轴也少了一半多，总耗时却没有下降。原因是：通过宽相筛选的物体对，有 74% 真的相交，而相交时无论如何都要检查所有轴，缓存帮不上忙；剩下 26% 分开的物体对，每次也只省下一两次投影，被缓存本身的读写抵消了。

这个优化在三维中更有价值：两个盒子之间有 15 条候选轴，其中 9 条要用叉积临时计算，省下的工作多得多。在二维、顶点不多的情况下，不值得增加这份复杂度。

测试环境

Apple M3，Apple clang 21，-O2。测试时机器上还有其他程序在运行，因此每组取 15 次中的最快值，三次独立运行的结论一致。代码在 cpp/collision/sat/sat_bench.cpp。

凹多边形怎么办

SAT 只对凸形状成立。一个 L 形的物体，可能在所有边法线上投影都重叠，却并不相交：另一个物体正好卡在 L 的拐角里。

通常的做法是把凹多边形分解成几个凸多边形，分别测试。大多数物理引擎（Box2D、Chipmunk）都要求碰撞形状是凸的，凹形状由多个凸形状组合而成。

常见陷阱

问题	原因	解决
明显没碰到却判定相交	只检查了一个形状的边法线	两个形状的边法线都要检查
推出后仍然重叠，或被推向反方向	穿透深度用了区间的重叠长度；或者法线方向没有统一成“从 A 指向 B”	分别计算两个方向的推出距离取较小者，并让法线带上符号
顶点顺序不一致导致法线朝内	有的多边形顺时针、有的逆时针	构造时统一顶点顺序（本文的 makePolygon）
凹多边形判断出错	SAT 只适用于凸形状	分解成多个凸多边形
箱子静止时微微抖动	两条边几乎同样正对 MTV，参考边每帧来回切换	选择参考边时给一方一点偏向
高速物体穿透	每帧只测一次	把速度方向也作为一条候选轴（扫掠 SAT），或见 2.9 连续碰撞检测

在游戏中的应用

• 2D 物理引擎的窄相：Box2D 2.x 的多边形碰撞就是 SAT 加参考边裁剪，与本文的思路相同（实现上对每条边法线只找对方的一个支撑点，计算“最大分离距离”，不必求完整的投影区间）。
• 旋转的包围盒（OBB）：子弹打中旋转的敌人、旋转的平台、斜坡上的角色。OBB 只有两条不同的轴，加上对方的两条，一共 4 次投影就能判断。
• 俯视角与横版游戏的多边形地形：地形切成若干凸多边形，角色用盒子或胶囊体。
• 三维：两个 OBB 之间的 SAT 要检查 15 条轴（各自 3 个面法线，再加上 3×3 条边与边的叉积），是 3D 游戏里最常用的盒子碰撞测试。

练习

1. OBB 的快速投影：盒子在轴 u 上的投影是 dot(center, u) ± (hx·|dot(ex, u)| + hy·|dot(ey, u)|)，其中 ex、ey 是盒子的两个单位朝向。用它为两个 OBB 写一个只检查 4 条轴、每条轴 O(1) 投影的 SAT，并与本文的通用版本比较速度。
2. 去掉平行的轴：盒子、正六边形都有平行的对边。构造多边形时预先去掉重复的法线，测一测能快多少。
3. 扫掠 SAT：多边形 A 这一帧移动 v、B 静止。在每条轴上，A 的投影区间随时间平移 t·dot(v, axis)，求出两个区间开始重叠和结束重叠的时间，所有轴的“开始”取最大、“结束”取最小，就得到了碰撞时刻。
4. 实现胶囊体（两端是半圆的线段）与多边形的 SAT。提示：候选轴包括多边形的边法线、胶囊线段的法线，以及多边形每个顶点到线段最近点的方向。

延伸阅读

• Christer Ericson，Real-Time Collision Detection（2004）第 4.4 节与第 5 章：OBB 的 SAT 测试与各种基本形状的相交测试
• William Bittle，SAT (Separating Axis Theorem) 与 Contact Points Using Clipping：dyn4j 作者写的两篇图解，本文的接触点算法与其思路相同
• Erin Catto，Contact Manifolds（GDC 2007）：Box2D 作者讲解参考边、入射边与裁剪
• Metanet Software，N Tutorial A: Collision Detection and Response：平台游戏《N》的开发者写的 SAT 教程，配有可交互的示意图