AABB 碰撞检测：从成千上万次比较，到几个区间的交集

一颗子弹飞向敌人，画面只需要把它画在正确的位置。游戏逻辑却必须回答另一个问题：它碰到了谁？

如果场景里只有一颗子弹和一个敌人，这个问题很简单。当子弹、敌人、障碍物和掉落物同时出现，麻烦就来了：我们应该检查哪些对象？又该用什么形状判断接触？

AABB 是这条计算链中最基础、也最容易被误解的一环。它用一个与坐标轴对齐的盒子包住对象，把几何关系化成区间比较。但要理解它为什么快，还得先看碰撞检测究竟在忙什么。

01　碰撞检测，检测的究竟是什么

角色的头发、衣摆可以越过墙边，身体却不能穿墙；挥剑的命中区域可能是一段扇形；捡取金币时，判定范围往往比金币图像更大。参与检测的是碰撞形状，它可以独立于用于显示的精灵或模型。

检测本身还要与响应分开。判断两个形状是否接触，只产生几何结果；扣血、阻挡、反弹或触发机关，是后续处理。一个返回 true 的函数，并不能替代完整的物理求解器。

为了控制计算量，碰撞流水线通常分成两层：宽相位先找到“值得继续检查”的对象对，窄相位再根据实际碰撞形状确认接触，并按需要计算接触点、法线与穿透信息。AABB 常用于前一层；如果游戏本身就采用轴对齐矩形作为碰撞形状，它也可以直接给出精确的重叠判断。

02　性能灾难，来自两层乘法

最直觉的办法，是把对象两两配对。

如果有 n 个对象，每对只检查一次，不检查自己，那么一轮需要：

对象对数 = n × (n − 1) / 2。

这里算的是无过滤、全量两两遍历的次数，不是某台机器的耗时。实际成本还取决于数据布局、检测算法和硬件。对象数量扩大十倍，对象对数却接近扩大一百倍。

另一层成本藏在“检查一次”里面。如果为了判断两个复杂网格是否相交，直接穷举两边的三角形组合，两者分别有 m、k 个三角形，组合数就是 m × k。精灵也一样：如果每次都逐像素检查重叠区域，成本会随待检查像素数量增长。

这些是朴素实现的代价，不代表成熟引擎会这样硬算。问题的关键在于：大量昂贵计算，被花在了根本不可能接触的对象上。

改进于是有两个方向：让一次排除更便宜，以及让需要检查的对象对更少。AABB 主要解决前者；网格、扫描排序、动态树等结构进一步解决后者。只把所有对象换成盒子再两两遍历，整体仍然是 O(n²)。

03　AABB 的核心：把空间关系拆成区间

AABB 的全称是 Axis-Aligned Bounding Box，即轴对齐包围盒。“轴对齐”意味着盒子的边始终平行于选定坐标系的坐标轴。

在二维中，只需要保存两个点：min = (minX, minY) 和 max = (maxX, maxY)。它们分别记录每个坐标分量的最小值与最大值，不依赖屏幕的 Y 轴朝上还是朝下。

于是一个矩形可以写成两个闭区间的笛卡尔积：

A = [AminX, AmaxX] × [AminY, AmaxY]。

先只看 X 轴。两个区间不相交，只有两种情况：A 完全在 B 左边，或者 B 完全在 A 左边。反过来，X 轴有交集需要同时满足：

AminX <= BmaxX AmaxX >= BminX

Y 轴执行相同判断。每条轴上的区间都有交集，两个 AABB 才有交集；任何一条轴分离，都足以否定接触。

这不是经验近似。轴对齐盒子本来就是各轴区间的乘积，它们的交集等于各轴交集的乘积。只要某个轴的交集为空，整个空间交集就为空；反之，可以从每条轴的交集中各取一个坐标，组成同时位于两个盒子中的点。

最小实现只需要比较：

// 输入为有限数，且各轴 min <= max；边界接触算相交。
function overlaps(a, b) {
  return a.minX <= b.maxX && a.maxX >= b.minX &&
         a.minY <= b.maxY && a.maxY >= b.minY;
}

固定二维最多四个比较，固定三维再加上 Z 轴的两个比较，不需要开平方，也不需要三角函数。单对盒子检测是 O(1)；短路求值还能在发现分离时提前结束。

如果只把正面积重叠算作命中，可以对具有正宽、正高的盒子改用严格不等式。若允许退化盒子，更稳妥的表达是直接检查各轴交集长度是否大于零。触边是否算命中，应由玩法确定并在整个流程中保持一致。

04　让数值动起来：接近、触边、重叠、离开

固定 A 的范围为 [2, 5] × [2, 4]，让 B 保持宽 2、高 2，沿 X 轴移动，Y 范围为 [3, 5]。

用下面两个值观察每条轴的交集：

dx = min(AmaxX, BmaxX) − max(AminX, BminX) dy = min(AmaxY, BmaxY) − max(AminY, BminY)

正数表示交集长度，零表示在该轴上触边，负数表示间隙的相反数。按本文的闭区间规则，dx >= 0 && dy >= 0 就是相交。

当 B 的 X 范围为 [6, 8] 时，dx = −1，两者分离；移动到 [5, 7] 时，dx = 0，刚好触边；继续到 [4, 6]，dx = 1，产生宽度为 1 的交集。整个过程中 dy = 1，因此状态完全由 X 轴决定。

注意：这里的 dx、dy 是交集长度，不能直接当作所有情况下的最小推出距离。如果一个小盒子完整落在大盒子里，交集宽度只是小盒子的宽度，把它移动这么远未必能推出去。检测交集与解决穿透，是两个不同的问题。

05　对象运动后，包围盒怎样更新

平移最简单。位移为 Δ 时，把 min 和 max 同时加上 Δ 即可。盒子的尺寸不变。

旋转则不同：对象可以转，世界坐标系里的 AABB 仍然要保持轴对齐，所以它的尺寸通常会变化。

一种直接的方法，是变换局部盒子的全部角点，再对变换后的坐标逐轴取最小值与最大值。二维有四个角点，三维有八个。只变换旧 min、max 两个对角点并不可靠，因为旋转后坐标极值可能出现在另外的角点上。

还有一个等价的紧凑写法。设局部盒子的中心为 c，半尺寸为 e；仿射变换的线性部分为 M，平移为 t，则：

c' = M c + t e' = |M| e min' = c' − e' max' = c' + e'

这里 |M| 是对矩阵的每个元素取绝对值，不是行列式。

为什么成立？局部盒内任一点可写成 c + u，其中每个分量满足 |u_j| <= e_j。变换后第 i 个坐标相对中心的偏移为 Σ M_ij u_j，其最大绝对值就是 Σ |M_ij| e_j；选择各个 u 分量的正负号即可达到该极值。

对二维矩形，若只旋转 θ，公式变成：

ex' = |cosθ| ex + |sinθ| ey ey' = |sinθ| ex + |cosθ| ey

这个公式对被变换的局部盒子给出精确包围结果，但对于盒子里一个不规则模型，结果可能比直接包住变换后模型顶点更松。

实现时应始终从稳定的局部边界和当前变换重新计算，不要反复旋转上一帧已经放大的世界 AABB。骨骼动画或顶点变形还需要能覆盖当前形状的边界，单靠刚体变换不会自动补上这些变化。

06　包围盒相交，不等于物体相撞

设实际形状 S 被盒子 A 包住，T 被盒子 B 包住。若 S 与 T 有公共点，这个点也一定同时属于 A 和 B。因此，两个保守包围盒不相交，就能排除实际形状的相交。

但反过来不成立。两条互相平行、彼此错开的斜长条，可能完全没有接触，它们的 AABB 却有大片交集。

这就是宽相位允许的假阳性：先保留可能性，再交给实际形状的检测算法确认。盒子越松，送进下一阶段的无效候选往往越多；但维护更紧的边界也可能更贵。包围体的选择，本质上是更新成本、检测成本与剔除能力之间的取舍。

要让大量对象真正跑得动，还需避免扫描全部对象对。例如动态 AABB 树把对象边界组织成层次结构；查询盒子若与某个内部节点不相交，该节点下的整组对象都可以跳过。Box2D 就提供了这种结构。

树结构并不保证所有场景都“变成 O(n log n)”。当大量包围盒挤在一起、候选对本来就接近平方级时，仅输出这些候选也要付出相应成本。空间分布、对象尺寸以及运动方式，都会影响实际收益。

07　每帧都检测，为什么子弹仍然穿墙

到这里，我们一直回答的是：某一个时刻，两个盒子有没有交集？

假设一颗宽度为 1 的子弹，本帧开始位于 X 区间 [0, 1]，结束时位于 [10, 11]。墙的 X 区间是 [5, 5.5]，Y 方向一直重叠。

开始与结束都不相交，但子弹在途中经过了墙。提高采样频率可以减小漏检机会，却不会让任意速度下的离散检测天然可靠。

对于尺寸不变、没有旋转、在一个时间步内匀速平移的两个 AABB，可以把运动也纳入区间计算。把本时间步归一化为 τ ∈ [0, 1]，令相对位移 d = ΔA − ΔB，相当于让 B 静止，只让 A 移动。

对每条轴，计算两个边界相遇的时刻：

t1 = (Bmin − Amax) / d t2 = (Bmax − Amin) / d 轴进入时间 = min(t1, t2) 轴离开时间 = max(t1, t2)

每条轴给出一个“在该轴上重叠”的时间区间。空间里要所有轴同时重叠，时间上也一样：

enter = max(0, 各轴进入时间) exit = min(1, 各轴离开时间) 存在接触 ⇔ enter <= exit

这是把射线与盒子的 slab 区间裁剪思路应用到相对运动上。

若某轴 d = 0，不能直接除法：该轴初始分离，就不可能在本步相交；该轴初始重叠，就不限制时间区间。初始已经接触的情况返回 τ = 0，已有穿透的处理仍需后续逻辑。

代入子弹的例子，进入时间是 (5 − 1) / 10 = 0.40，离开时间是 (5.5 − 0) / 10 = 0.55。它在本时间步的 40% 处第一次触墙。

下面是对应的二维实现，返回本时间步内的首次接触比例；没有接触则返回 null：

function sweptAabb(a, b, d) {
  let enter = 0, exit = 1;
  for (const axis of ['X', 'Y']) {
    const amin = a['min' + axis], amax = a['max' + axis];
    const bmin = b['min' + axis], bmax = b['max' + axis];
    const move = d[axis]; // 相对位移，不是速度
    if (move === 0) {
      if (amax < bmin || amin > bmax) return null;
      continue;
    }
    const t1 = (bmin - amax) / move;
    const t2 = (bmax - amin) / move;
    enter = Math.max(enter, Math.min(t1, t2));
    exit = Math.min(exit, Math.max(t1, t2));
    if (enter > exit) return null;
  }
  return enter;
}

宽相位还可以先合并起点与终点的 AABB，得到覆盖这段平移的扫掠包围盒，用它查找候选。但这个大盒子只说明运动可能经过某个区域，并没有给出准确的接触时刻。存在旋转时，起终点盒子的并集甚至未必覆盖中间姿态。

同样，若 AABB 只是复杂形状的外包盒，上面的时刻只是盒子的接触时刻；要得到真实形状的结果，还需要相应的连续碰撞算法。

AABB 的价值在于一个很朴素的观察：复杂形状或许难以直接比较，但它们在每条坐标轴上占据的范围很容易比较。用便宜而保守的排除，把精细计算留给真正可能接触的对象，才是它在碰撞系统里最重要的位置。