3.2 窄相检测：SAT 与 GJK

3.2 窄相检测：SAT 与 GJK

本节摘要：窄相吃宽相候选，吐出分离或接触。球对球、球对平面用闭式公式；凸多边形和盒子用分离轴定理 SAT；一般凸体用 GJK 测距离，穿透时用 EPA 找回法向和深度。窄相的产品是一致的接触法向与深度，布尔值只留给触发器。

本节导航

阅读完本节，你应当能够：

1. 写出球对球、球对 AABB 的接触法向和深度
2. 用 SAT 判断两个凸多边形是否分离，并取最小穿透轴
3. 说明 GJK 在做什么：在闵可夫斯基差里找原点
4. 在 SAT 与 GJK 之间按形状类型选型，而不是只追一个算法名字

一、先把能闭式写的形状写完

球对球：中心距 d，半径和 R。d>=R 分离；否则法向沿中心连线，深度 R-d。d 接近 0 时连线不稳定，用上一帧法向或任意稳定轴。球对平面：深度 = 半径 - 有符号距离，法向即平面法向。球对 AABB：把球心钳到盒子内得最近点，再当球对点。这些是引擎的快路径，占游戏碰撞的很大比例，不要全部丢给 GJK。

function sphereSphere(a, b):
    d = b.x - a.x
    dist2 = lengthSq(d)
    r = a.r + b.r
    if dist2 > r*r: return 空
    dist = sqrt(dist2)
    n = dist > eps ? d/dist : 上次法向
    return Contact(n, r - dist, 点在中点)
​

胶囊是线段扫过的球，最近点在两条线段之间，再当球对球。角色控制器爱胶囊，值得单独写，比凸包稳。圆柱、圆台可以当凸包，也可以特化。特化快路径的原则：该形状在场景里出现频繁，且数值比 GJK 稳。

凹体 GJK 会给出错误的“凸包碰撞”，角色卡在门洞外侧。门洞必须凸分解或用网格查询。

二、SAT：沿轴投影，有一条缝就分开

分离轴定理：两个凸体，若存在一条轴，它们的投影区间不重叠，则不相交。二维凸多边形的候选轴是两边的法向。三维盒子还要加边叉积轴。投影重叠最小的那条轴，当作接触法向，重叠量当深度。法向方向要指向“把 A 推离 B”的一侧，用中心差的点积校正符号。

轴必须单位化。未单位化时重叠量没有可比性，会选错最小穿透轴，盒子沿对角线弹开。边退化（长度近 0）跳过。三维边叉积轴在两盒平行时长度近 0，必须跳过，否则 NaN。

minPen = inf
axisBest = 0
for axis in candidateAxes:
    pa = project(A, axis)
    pb = project(B, axis)
    if 区间分离: return 不相交
    overlap = 重叠长度
    if overlap < minPen:
        minPen = overlap
        axisBest = axis 带符号
return Contact(axisBest, minPen)
​

SAT 相交只给轴和深度，接触点要靠裁剪：用参考面和入射面切出多边形，再夹到参考面，最多留 4 个点。那是 3.3 的事。窄相这一层先保证轴对。

GJK 回答“凸体间最近距离或是否相交”。它在 A-B 的闵可夫斯基差上维护一个单纯形，迭代寻找原点。分离时能给出最近点和法向，适合连续检测和容差分离。一旦原点在差集内部（穿透），GJK 本身不给深度，要 EPA 扩展多面体。GJK 对几乎相切很稳，对深深穿透可能迭代多次，需要迭代上限和失败回退（比如用上一帧法向把物体分开）。

💡 关键直觉：SAT 像用卡尺从各个方向量两堆货有没有缝；GJK 像在差空间里摸黑找原点。轴少而明确时 SAT 简单；顶点多、轴组合爆炸时 GJK 更合适。

不要对每个三角形网格跑 GJK。先凸分解或用三角形 vs 凸的专用测试。三角形 vs 凸可用 SAT（轴：三角法向、凸体面法向、边叉积）。数量大时靠 BVH 把三角形候选砍掉。

三、数值、容差与连续检测

接触容差：AABB 可以略膨胀，窄相允许“距离小于 skinRadius 也当接触”。皮肤半径 1 到 5 厘米量级（按世界单位），让接触提前生成，求解器有时间在真正穿透前把速度刹住。皮肤太大，物体看起来悬浮；太小，又回到穿透再弹。

图 SAT 卡尺与 GJK 差空间

连续碰撞检测 CCD：对高速子弹做射线或扫掠凸体，求第一次撞击时刻，把这一步积分截断到该时刻再生成接触。全场景 CCD 极贵。做法是：只对“速度 × dt 超过自身最小半宽”的物体开 CCD，其余靠扫掠 AABB + 离散窄相。角色落地不要靠 CCD，靠胶囊和台阶处理。

⚠️ 常见坑：最小穿透轴选成了边叉积轴，两个盒子沿接触面滑动时法向突然跳到几乎相切的怪方向，接触力把物体弹飞。要对轴做偏好：优先面法向，边轴只有在面轴都分不开且重叠明显更小时才用，并加滞后。

GJK 实现细节：支持函数 support(dir) 返回凸体在该方向最远点。盒子的 support 是半长按 dir 符号取顶点。球的 support 是中心加 radius*normalize(dir)。两个凸体差的 support 是 supportA(dir) - supportB(-dir)。迭代上限 20 到 40，超限当分离或回退，不要死循环。用距离包络避免浮点来回翻转。

测试：重叠的两个单位盒子，法向应是分量最大的轴，深度应是重叠量。一个盒子完全包住另一个，SAT 仍应给出最小平移分离向量，而不是随便一个轴。完全包含是 SAT 的压力测试。GJK 在包含时必须走 EPA，只跑 GJK 会误报分离或迭代耗尽。

窄相失败要有日志：形状类型、下标、迭代次数。上线后“偶发弹飞”往往是某一对 EPA 失败后用了零法向。零法向进求解器等于往随机方向加冲量。检测到长度小于 epsilon 的法向就丢弃该接触，宁可漏一帧，不要 NaN。

把快路径和慢路径的接触结构做成同一个 Contact，求解器不关心来源。布尔触发器可以在窄相早退，不填深度。物理接触必须填。这一契约在 3.2 结束时就要定死，3.3 只负责点的个数和缓存。

凹包、缩放、镜像：非均匀缩放会把球变成椭球，闭式球公式失效，要么禁止非均匀缩放碰撞体，要么当凸包。镜像（负行列式）会翻转法向，SAT 轴方向错。资源导入时把缩放烘焙进顶点，运行时碰撞体只刚体变换。这比运行时支持任意仿射省心。

四、失败回退与形状分桶

GJK 超限或 EPA 失败时：用上一帧流形法向把物体沿该方向分开一个皮肤半径，并打日志。不要输出零法向。连续失败则把这对标成“本帧忽略”，防止每帧刷屏。失败率进统计，高于千分之一就要查退化形状。

形状分桶：宽相候选先按类型对排序，球-球连续、盒-盒连续、杂项在后。球-球用闭式，不要进 GJK。你若发现球-球走了 GJK，是类型表没写对。胶囊当“线段加半径”快路径，角色会感谢你。

非均匀缩放：导入时烘焙。运行时只允许均匀缩放碰撞体，且半径、局部顶点一起乘。负缩放当镜像，翻转三角形绕序。运行时检测负行列式就断言，比静默吸地好。

SAT 三维边轴：两盒 15 条轴。实现时用一张小表，退化轴用叉积长度阈值跳过。优先面轴的滞后：上一帧若是面轴且本帧面轴重叠仍很小，即使边轴更小也沿用面轴。这能消灭“滑动时法向跳到边”的弹飞。

实践问答

完全包含时 SAT 还有效吗？

有效，给出最小平移分离。这是压力测试。GJK 在包含时必须 EPA，只跑 GJK 会误报。写一个盒套盒测试。

边叉积轴弹飞怎么抑制？

面轴优先加滞后。上一帧面轴且本帧仍几乎分离得开，就沿用面轴。边轴只在明显更小时启用。滑动接触尤其需要。

皮肤半径怎么取？

厘米到几厘米量级，按世界单位。太大悬浮，太小来不及刹速度。和角色胶囊皮肤分开调，不要一个全局皮肤打天下。

凹门洞为什么不能当一个凸包？

凸包会封住洞，角色卡在门外。凸分解或网格查询。导入时检查亏格和洞，自动凸包要有警告。

参数扫描笔记：窄相失败

扫描 1：轴未单位化

最小重叠不可比，对角线弹开。

扫描 2：退化边当轴

NaN。长度近 0 跳过。

扫描 3：GJK 超限当相交乱填零法向

随机方向冲量。丢弃接触。

扫描 4：球-球走 GJK

类型分桶没写对。闭式快路径必须命中。

扫描 5：非均匀缩放碰撞体

球变椭球公式失效。导入烘焙。

扫描 6：完全包含不测

SAT 压力测试漏了。盒套盒要写。

扫描 7：CCD 对所有物体开

极贵。只对位移超过半宽的开。

扫描 8：凹体直接 GJK

得到凸包碰撞。门洞失败。

工程备忘录

备忘 1

「02-窄相SAT与GJK」的预分配策略：按关卡上限留容量，超出打日志并降级，不要在 step 中途默默扩容。扩容是卡顿尖峰，也是回放时分配顺序不同导致的潜在分叉源。 本条对应「02-窄相SAT与GJK」第 1 号备忘，和相邻条目不要合并成一句空话，分开验收。

备忘 2

把「02-窄相SAT与GJK」相关的失败做成最小复现：关掉渲染特效、关掉音频、只留固定 dt 的 step 和一份输入日志。能在十秒内重放出来的 bug 才叫被抓住。不能重放就先补录制，再谈修。很多人在这一步省时间，后面用几天陪着偶发抖动。 本条对应「02-窄相SAT与GJK」第 2 号备忘，和相邻条目不要合并成一句空话，分开验收。

备忘 3

在「02-窄相SAT与GJK」路径上加计数器要进 step 末尾快照，不要在热循环里格式化字符串。计数器本身若分配内存，你会优化一个被测量污染的世界。发布版可用宏剥掉绘制，但计数器的定义要保留，方便线上开一个极轻的统计开关。 本条对应「02-窄相SAT与GJK」第 3 号备忘，和相邻条目不要合并成一句空话，分开验收。

备忘 4

「02-窄相SAT与GJK」一旦和随机数沾边，随机必须绑在 tick 上。墙钟、哈希表遍历、线程完成顺序都是隐藏输入。隐藏输入会让哈希校验在某一帧突然红，而你却以为是公式写错。先排除隐藏输入，再怀疑有效质量。 本条对应「02-窄相SAT与GJK」第 4 号备忘，和相邻条目不要合并成一句空话，分开验收。

备忘 5

调「02-窄相SAT与GJK」时一次只改一个量，写下场景名、旧值、新值、醒岛数或能量变化。没有笔记的调参会在一周后变成传说。传说不能回归，不能交给同事，也不能在换库时当合同。 本条对应「02-窄相SAT与GJK」第 5 号备忘，和相邻条目不要合并成一句空话，分开验收。

核心回顾

• 球、胶囊、AABB 走闭式快路径；一般凸才 GJK。
• SAT 用法向轴投影，最小重叠轴当接触法向，轴要单位化，退化轴跳过。
• GJK 测距离与相交，穿透靠 EPA；超限必须回退。
• 凹形状先分解；门洞不要当一个凸包。
• 皮肤半径让接触提前出现；CCD 只给真正高速的物体。
• 零法向丢弃；面轴优先于边叉积轴。
• 碰撞体不要带非均匀缩放，导入时烘焙。

下一节把“一个法向”变成稳定的一组接触点，并让下一帧还认得它们。