两个阶段

碰撞检测的经典结构：

宽相（Broad Phase）:  快速找出"可能碰撞"的物体对
                      用包围盒，O(n log n) 或 O(n)
                      
窄相（Narrow Phase）: 对候选对做精确的相交测试
                      返回: 是否相交、穿透深度、法线、接触点

为什么要分两阶段：精确测试很贵（几百条指令）， $n$ 个物体有 $O(n^2)$ 对，全部精确测试不可行。宽相用便宜的包围盒先砍掉 99%。

宽相（Broad Phase）

包围体

类型	构造	紧凑度	相交测试
AABB	轴对齐包围盒	一般	极快（6 次比较）
Sphere	包围球	差	最快（1 次比较）
OBB	有向包围盒	好	中（15 条轴测试）
k-DOP	k 个方向的平面	较好	中
凸包	精确凸包	最好	慢（GJK）

AABB 是宽相的默认选择：便宜，且旋转后可以重新计算（或保守地扩大）。

空间划分

结构	思路	适用
均匀网格	空间切成格子，只检查同格/邻格	物体大小相近
BVH	层次包围盒树	通用，最常用
八叉树 / k-d 树	递归空间划分	分布不均时
SAP（Sweep and Prune）	按轴排序，扫描线找重叠	物体沿轴分散
空间哈希	网格 + 哈希（无限空间）	粒子系统

SAP（Sweep and Prune）

利用时间连贯性：物体位置每帧变化不大，排序几乎不变 → 插入排序近乎 $O(n)$ 。

1. 把所有 AABB 投影到 x 轴，排序（区间列表）
2. 扫描，找出 x 区间重叠的对
3. 对这些对再检查 y、z

关键优化：维护排序列表（用插入排序，因为几乎有序）。这是 Box2D、Bullet 的默认宽相。

BVH

     ┌─────┐
     │ root │  包含所有物体
     └──┬──┘
   ┌────┴────┐
┌──┴──┐   ┌──┴──┐
│AABB │   │AABB │
└──┬──┘   └──┬──┘
  ...       ...

构建：自顶向下（按中位数分割）或自底向上（合并最近对）
更新：物体移动后重拟合（refit，只更新包围盒不重建树）或重建
遍历：两棵树的节点两两测试，不相交就剪掉整棵子树

BVH 也是光线追踪的加速结构（见光线追踪章节）——同一套东西两个用途。

窄相（Narrow Phase）

凸体：GJK 算法

Gilbert-Johnson-Keerthi：判断两个凸体是否相交，不需求出完整交集。

核心思想：用 Minkowski 差。

A \ominus B = \{\mathbf{a} - \mathbf{b} \mid \mathbf{a} \in A, \mathbf{b} \in B\}

关键定理：

A \cap B \neq \varnothing \iff \mathbf{0} \in A \ominus B

于是问题变成：Minkowski 差里是否包含原点。

GJK 的巧妙之处：不需要显式构造 Minkowski 差（那是指数级的多面体）。只需要一个支撑函数（support function）：

S_{A\ominus B}(\mathbf{d}) = S_A(\mathbf{d}) - S_B(-\mathbf{d})

支撑函数返回"沿方向 $\mathbf{d}$ 最远的点"——对常见形状（球、盒、凸包）都是 $O(1)$ 或 $O(\log n)$ 。

算法

1. 选一个初始方向 d
2. 循环:
     p = support(d)                        // Minkowski 差中沿 d 最远的点
     if dot(p, d) < 0:  return false       // 原点不可能在里面
     把 p 加入单纯形（simplex）
     更新 simplex 和 d，使其"朝原点靠近"
     if simplex 包含原点: return true

单纯形：2D 是点/线段/三角形，3D 是点/线段/三角形/四面体。每步把单纯形缩减为"离原点最近的部分"。

GJK 只回答"是否相交"，不给出穿透深度。

穿透深度与法线：EPA

Expanding Polytope Algorithm：GJK 找到包含原点的单纯形后，逐步扩展多面体，找到离原点最近的面。

面的距离 = 穿透深度
面的法线 = 碰撞法线

GJK + EPA 是凸体碰撞检测的标准组合（Bullet、PhysX 都用它）。

常用形状的解析测试

通用凸体用 GJK，但常见形状有更快/更简单的解析法：

对	方法
球-球	距离 vs 半径和
球-平面	点到平面距离 vs 半径
球-AABB	找 AABB 上最近点，再球-点
AABB-AABB	6 次比较
射线-三角形	Möller–Trumbore
射线-AABB	slab 方法
三角形-三角形	分离轴定理（15 条轴）

分离轴定理（SAT）

定理：两个凸体不相交 $\iff$ 存在一条轴，使它们在该轴上的投影不重叠。

对每个候选轴:
  投影两个物体到该轴
  若不重叠 → 分离，不相交
全部重叠 → 相交

候选轴: 面法线 + 边叉积（3D）

SAT 同时给出最小穿透轴——就是重叠最小的那条轴，即碰撞法线。

2D 的 SAT 极简单（只需测边法线），是 2D 物理引擎的标准方法。3D 需要额外测 9 条边叉积轴。

连续碰撞检测（CCD）

问题：隧穿（tunneling）

高速物体一帧移动很远
  t:     [子弹]        [墙]
  t+dt:          [子弹]      ← 中间没采样到墙，直接穿过去了

解法：

方法	做法
扫掠测试（Swept）	把物体在这一帧的运动看作一个"扫掠体"，测试扫掠体与静态物体
保守推进（Conservative Advancement）	迭代计算"最早碰撞时间"（TOI），推进到那个时刻
speculative contact	检测"下一帧会碰撞"，提前约束
限制速度	简单粗暴（最大位移 < 最薄物体厚度）
子步	把一个大步拆成若干小步

保守推进：

loop:
  d = 两物体当前最近距离
  if d < eps: 碰撞，返回
  估计 TOI: t += d / (相对速度沿法线的分量)
  if t > dt: 本帧不碰撞，返回
  推进到 t

CCD 很贵，通常只对快速运动的物体（子弹、角色冲刺）开启（"CCD 标志"）。

接触流形（Contact Manifold）

两个物体接触时，通常不是一个点，而是一个面/边。

盒子放在地面上:
  4 个角接触 → 需要 4 个接触点才能稳定（1 个点会翻倒）

生成接触流形：

1. 找到穿透最深的特征（面/边/点）
2. 沿该特征生成 1~4 个接触点
3. 保留历史接触点（warm starting 需要一致的接触点 ID）

常见做法：

** clipping（Sutherland-Hodgman）**：用一个物体的面裁剪另一个的面
参考面 + incident 面：选"最平行"的面作为参考

接触点的数量：

2D：1~2 个
3D：1~4 个

接触点的持久性：跨帧要能匹配（用特征 ID），否则 warm starting 失效。

特殊情形

自碰撞

同一物体的不同部分相互碰撞（布料、绳索、柔体）。

难点： $O(n^2)$ 的候选对。

解法：

空间哈希（粒子）
只检测"拓扑上不相邻但空间上接近"的部分
曲率/法线剪枝（凸的部分不会自碰撞）
或者干脆不做（很多游戏接受穿模）

薄物体

薄板、布料与场景碰撞时容易漏检（因为很薄）。

解法：给薄物体一个"厚度"（碰撞半径），或双面检测。

静止堆叠

大量物体堆叠（箱子堆）需要稳定的接触流形 + 迭代求解 + 休眠。见刚体。

性能预算

典型游戏场景: 1000 个动态物体
  宽相:   ~0.5 ms（SAP 或 BVH）
  窄相:   ~1 ms（取决于接触数）
  求解器: ~2 ms（迭代 8 次）

大部分物体应该处于休眠状态 → 几乎不参与

优化优先级：

休眠（最有效）
宽相的空间划分
简单的碰撞形状（用凸包近似而不是三角形网格）
减少接触点数

常见坑

两个动态物体的碰撞漏检：宽相只处理"动态 vs 静态"，忘了"动态 vs 动态"
AABB 旋转后没更新：用一个固定的 AABB 会导致旋转时漏检。要么重算，要么用保守的球
GJK 的初始值：初始方向选得好能大幅减少迭代。用上一帧的相对位置作初值
GJK 不收敛：退化情况（两个形状相切）要加迭代上限
EPA 的面退化：数值精度问题导致面法线错误。要加容差
穿透深度太大导致弹飞：限制单帧最大修正量（或位置修正用 Baumgarte 松弛）
接触点抖动：接触点 ID 不稳定 → warm starting 失效 → 堆叠抖动
CCD 的性能：全部物体开 CCD 会拖垮性能。只对需要的开
忘记处理"已经在穿透中"的情况：碰撞检测通常返回"分离距离"和"穿透深度"两种状态，都要处理
三角形网格（非凸）的碰撞：需要先分解成凸块（convex decomposition），否则 GJK 不适用
浮点误差导致的抖动：用容差（slop）避免微小穿透反复触发