怎么知道它们重叠了

一句话总结

碰撞检测分为两个阶段。宽阶段用低成本过滤掉“不可能相交”的对象对，窄阶段只对剩余对象进行精确判定。凸形的精确判定可以用一个分离轴定理解决。

为什么需要它

物体数量为 n 时，对数为 n(n-1)/2。200 个物体有 19,900 对，2,000 个物体则有两百万对。每一步都对所有对象进行精密检测，物理计算还没开始，当前帧就已经结束。

实际上，真正相交的对象通常很少。在上述 200 个物体的例子中，真实相交往往不足 300 对。其余 19,600 对可以用便宜得多的方法判断“不值得精密检查”。这就是系统分成宽阶段与窄阶段的原因。

如何工作

**AABB（轴对齐包围盒）**是成本最低的判定。判断两个盒子是否相交，只需检查每条轴上的区间是否重叠。

겹친다  ⟺  a.maxx >= b.minx  그리고  b.maxx >= a.minx
           그리고  a.maxy >= b.miny  그리고  b.maxy >= a.miny

每条轴检查一次，四次比较即可完成。重叠深度也来自同一公式：每条轴上的 min(maxs) - max(mins) 就是该轴的重叠宽度，而重叠较浅的轴就是实际推出方向。

圆与球的判定成本也很低。圆心距离小于半径之和即相交；法线是连接两中心的方向，穿透深度为 r1 + r2 - 거리。需要注意两个中心完全重合的情况：距离为 0 时无法确定方向，必须指定任意方向，否则会除以零。

**分离轴定理（SAT）**适用于一般凸形。如果两个凸形不相交，就必然存在一条能将它们完全分开的直线，而且该直线的方向会与其中一个形状的边平行。因此，沿两个图形每条边的法线投影，只要找到一个区间分离的轴，就能判定不相交。

for 축 in A의 변 법선들 + B의 변 법선들:
    A 를 축에 투영 → [a0, a1]
    B 를 축에 투영 → [b0, b1]
    겹침 = min(a1, b1) - max(a0, b0)
    if 겹침 <= 0: 떨어져 있다 (여기서 즉시 끝낸다)
    가장 작은 겹침과 그 축을 기억해 둔다

如果找不到分离轴，两图形就相交，此时产生最小重叠值的轴，就是最短推出方向。它称为最小平移向量（MTV），下一模块的碰撞响应会使用这个方向。

宽阶段的经典方法是扫描与排序（sweep and prune）。把包围盒按 x 轴最小值排序后，与某个盒子可能相交的对象，只可能是排序后连续出现、且 minx 尚未超过该盒子 maxx 的对象；超过后即可停止。

宽阶段还有其他方法。**网格（spatial hash）**把空间分成固定大小的单元，每个物体登记到自己覆盖的单元中。物体尺寸相近且分布均匀时速度最快。**动态包围盒树（dynamic AABB tree）**把盒子组织成二叉树，以整个分支为单位跳过，面对尺寸差异很大的物体也能稳定工作。Box2D 与 Bullet 都使用这种树。

所有方法都有一个共同点：宽阶段绝不能漏掉真实相交的对象对，但把不相交的对象交给窄阶段没有关系。 漏掉会让物体互相穿过，多传一些只会由窄阶段滤除，结果不变。因此宽阶段判断始终偏向宽松。

在实际项目中

高速物体穿过薄墙的隧穿问题，来自离散检测的局限。系统只在一步的开始和结束检查相交，如果物体在一步内完整穿过墙壁，两端都不会发生重叠。解决方法是沿移动路径执行连续碰撞检测，或把步长切得更细。

另一个问题是边界值的一致性。如果代码不同位置对“刚好接触算不算重叠”采用不同规则，盒子会在接触地面与离开地面之间反复切换并抖动。判定规则应集中在一处，由所有代码共同调用。

还必须明确窄阶段应输出什么。只有“相交／不相交”的布尔值，下一阶段无法采取任何行动。碰撞响应需要三项信息：推出方向（法线）、穿透深度、接触位置（接触点）。本实验实现前两项而不处理接触点，因为接触点用于计算旋转，本身足以成为独立主题。

下一实验要做什么

依次实现 AABB、圆形与分离轴定理，把两个相交多边形与最小平移向量绘制成图。随后对 200 个盒子分别执行全量检查与扫描排序，通过数字验证以更少检查得到完全相同的结果。最后用 slab 方法求射线与盒子的相交，并绘制结果。