想象你是一家快递公司的打包员，每天要处理成千上万个包裹。你的工作台上有好几个箱子要装进一个大纸箱里——你得反复调整它们的角度和位置，看它们会不会互相挤压、装不装得下。如果两个箱子挤在一起，你得换个摆法；如果一个大箱子和另一个大箱子重叠了，那可不行，快递车装不下还得返工。 电脑游戏里的“物理引擎”就是这位打包员的数字化化身。当你在游戏里推一把箱子、开车撞墙、或者让雪球滚下山坡时，背后的“碰撞检测”系统就像打包员一样，在几毫秒内回答三个问题：两个物体碰到没有？在哪儿碰到的？碰到之后该咋办？ 而在近年大火的世界模型与视频生成技术中（比如能预测未来几秒画面的AI模型），碰撞检测更是扮演了“物理世界的裁判”——它确保AI生成的每一帧画面都符合现实规律，不会出现人手穿透桌子的恐怖画面。 本文就用“快递打包员”这条主线，带你从零理解碰撞检测的完整知识体系。

岗位关联

掌握碰撞检测，你就掌握了物理模拟的“地基”。无论做游戏开发、机器人仿真还是世界模型训练，判断“物体何时相撞、如何相撞”都是 AI 从业者绕不开的核心技能。

目录
  1. 可视化演示
  2. 碰撞检测概述
  3. AABB包围盒
  4. 分离轴定理
  5. 连续碰撞检测
  6. 碰撞流形求解
  7. 优化加速技术
  8. 世界模型应用
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

展示碰撞检测的两阶段架构、BVH包围盒层次树遍历及SAT分离轴定理投影检测，揭示物理引擎中碰撞检测的核心算法机制。

本节配有交互动效（进入视口后自动加载，约 3KB）。

两阶段碰撞检测 宽阶段：AABB包围盒快速排除不可能碰撞的物体对 窄阶段：对候选对进行精确几何检测（SAT/GJK） 碰撞响应：检测到碰撞后触发物理响应处理 T_total = T_broad + T_narrow × N_pairs 两阶段架构将O(n²)检测优化到可接受的实时性能

碰撞检测概述

快递打包员老王每天的工作从清点一批包裹开始。他把所有箱子摊在台面上，先快速扫一眼：哪两个箱子靠得太近了？哪两个可能装不进同一个大箱？这个“扫一眼”就是碰撞检测的雏形——用最少的计算量快速排除明显不相干的物体对，只对“可疑”的配对做精确检查。

在计算机物理模拟中，碰撞检测的目标是回答一个布尔问题：两个物体是否发生接触或重叠？ 但这个问题背后藏着两个相互拉扯的指标——精确性（不能漏报也不能误报）和性能（必须在 16 毫秒的一帧内完成成千上万次检测）。这正是老王面对的现实：他既不能漏掉一个装不下的箱子（漏报会导致物体互穿），也不能花十分钟研究每个箱子的棱角（误报或超时会让整个流水线停摆）。

于是，碰撞检测被拆成了两个阶段。宽阶段（Broad Phase） 像老王的“扫一眼”——用极廉价的包围盒快速排除 90% 不相干的物体对；窄阶段（Narrow Phase） 像老王拿起可疑的两个箱子仔细比对——对剩余少量候选对做精确的几何相交测试。这两个阶段配合，构成了碰撞检测的黄金架构。

理解了宽窄两阶段的分工，你会发现老王的工作哲学——“先粗后细、先快后准”——正是碰撞检测最核心的工程智慧。无论多复杂的物理引擎，这条主线始终不变。

CollisionDetection=BroadPhase+NarrowPhase\text{CollisionDetection} = \text{BroadPhase} + \text{NarrowPhase}
碰撞检测 = 快速扫描 + 精确比对。宽阶段负责“猜”，窄阶段负责“验”。
  1. 宽阶段过滤用简单的包围体（如球形、AABB）快速筛除距离较远的物体对，只保留可能相交的候选对。
    BroadPhase:O(n)→candidate pairs≪O(n2)\text{BroadPhase}: O(n) \rightarrow \text{candidate pairs} \ll O(n^2)
  2. 窄阶段精确检测对候选对执行精确的几何相交测试，输出碰撞点、法线和穿透深度。
    NarrowPhase:candidate pairs→collision details\text{NarrowPhase}: \text{candidate pairs} \rightarrow \text{collision details}

AABB包围盒

老王收到一箱不规则形状的艺术品摆件。他没时间研究每个摆件的流线型曲面，而是拆开包装，给它套上一个刚好能装下的长方体纸盒——纸盒的每个面都平行于仓库的墙（即坐标轴）。这个纸盒就叫 AABB（Axis-Aligned Bounding Box，轴对齐包围盒）。

AABB 的精髓在于“轴对齐”这三个字。因为纸盒的边永远和坐标轴平行，检查两个盒子是否重叠就变成了三次一维区间测试：比较它们在 X、Y（三维中还有 Z）方向上的投影区间是否都重叠。老王只需要量六个数据——每个盒子的最小 x、最大 x、最小 y、最大 y——就能完成检测，这比其他任何形状都便宜。

判定两个 AABB 是否重叠的条件是四组不等式（三维是六组）：对于每个轴，一个盒子的最大坐标必须大于另一个盒子的最小坐标，且反过来也成立。物理引擎每帧都要做几十万次这样的检查，所以这些比较操作被优化到了极致——甚至没有乘除法，只有加减法和比较指令。

AABB 就像老王的万能通用纸箱——虽然不够贴身（对旋转的物体不够精确），但胜在便宜、快速、容易计算。大多数物理引擎都在宽阶段使用 AABB，让老王能在一秒内扫完整个仓库的箱子。

overlap(A,B)=(Amin⁡x<Bmax⁡x)∧(Amax⁡x>Bmin⁡x)∧(Amin⁡y<Bmax⁡y)∧(Amax⁡y>Bmin⁡y)\text{overlap}(A,B) = (A_{\min x} < B_{\max x}) \wedge (A_{\max x} > B_{\min x}) \wedge (A_{\min y} < B_{\max y}) \wedge (A_{\max y} > B_{\min y})
两个 AABB 重叠，当且仅当它们在每个坐标轴上的投影区间都有交集。任何一个轴上没交集，就一定不会重叠，可以立即排除。
  1. X 轴区间重叠A 的左边界要在 B 的右边界左边，同时 A 的右边界要在 B 的左边界右边——两个区间在 X 轴上相交。
    Amin⁡x<Bmax⁡x∧Amax⁡x>Bmin⁡xA_{\min x} < B_{\max x} \wedge A_{\max x} > B_{\min x}
  2. Y 轴区间重叠同样的逻辑搬到 Y 轴上，确保竖直方向也有交集。
    Amin⁡y<Bmax⁡y∧Amax⁡y>Bmin⁡yA_{\min y} < B_{\max y} \wedge A_{\max y} > B_{\min y}
  3. 合取判定两个轴都有交集才能断定碰撞，只要有一轴不满足就安全分离。
    overlap(A,B)=ovlx∧ovly\text{overlap}(A,B) = \text{ovl}_x \wedge \text{ovl}_y

分离轴定理

老王遇到新挑战：一个装满艺术品的三角形展示盒。三角形不能简单套用 AABB——它旋转 45 度后，AABB 会多出一大圈空白，误报率飙升。这时老王换了个方法：从侧面打手电筒，把三角形投影到墙上，看影子。

这就是分离轴定理（Separating Axis Theorem，简称 SAT）的直觉：如果两个凸多边形没有碰撞，那一定能找到一条轴线，使得它们在那条轴上的投影互不重叠。反过来，如果所有可能的轴上都重叠，那它们一定碰撞了。这条“用手电筒找投影分开的方向”的轴，就是分离轴。

SAT 只需要检查有限条轴：每个多边形的每条边法线。两个三角形最多检查 6 条轴（3+3），两个矩形也是 4+4=8 条轴。对每条轴，把两个多边形的所有顶点投影上去，得到两个一维区间，然后做三次 AABB 式的区间测试。只要有一条轴上的区间分离，立即判定不碰撞并跳出循环——这就是“短路求值”的威力。

SAT 让老王从“靠纸盒猜”升级为“靠手电筒验”——当物体的形状不那么规则时，投影法能精确到毫米级。不过 SAT 只适用于凸多边形，凹多边形需要先拆成多个凸块，这就是后话了。

SAT(A,B):∀axis a⃗i∈{edges of A}∪{edges of B},proj(A,a⃗i)∩proj(B,a⃗i)≠∅\text{SAT}(A,B) : \forall \text{axis } \vec{a}_i \in \{\text{edges of } A\} \cup \{\text{edges of } B\}, \quad \text{proj}(A, \vec{a}_i) \cap \text{proj}(B, \vec{a}_i) \neq \emptyset
SAT 说：两个凸多边形分离，当且仅当存在一条边法线轴，使它们在该轴上的投影不相交。检测时一旦发现某条轴分离即可退出。
  1. 提取候选轴取出 A 的每条边和 B 的每条边，计算各自的法线方向，作为候选分离轴集合。
    axes={n⃗i∣e⃗i∈Edges(A)∪Edges(B)}\text{axes} = \{ \vec{n}_i \mid \vec{e}_i \in \text{Edges}(A) \cup \text{Edges}(B) \}
  2. 投影到轴将多边形所有顶点投影到候选轴上，取最小值和最大值构成区间。
    IA=[min⁡k(v⃗k⋅a⃗),max⁡k(v⃗k⋅a⃗)],v⃗k∈AI_A = [\min_k(\vec{v}_k \cdot \vec{a}), \max_k(\vec{v}_k \cdot \vec{a})], \quad \vec{v}_k \in A
  3. 区间分离判断检查两个区间是否分离，若有间隙立即判定不碰撞。
    ∃a⃗:IA∩IB=∅⇒no collision\exists \vec{a}: I_A \cap I_B = \emptyset \Rightarrow \text{no collision}

连续碰撞检测

深夜加班的老王遇到了最头疼的事：一颗子弹飞向一堵墙。前一帧子弹还在墙的左边，后一帧已经在墙的右边了——穿墙了！这就像老王手一抖，把一个小包裹从快递车的一侧直接甩到了另一侧，完全跳过了“检查能不能装得下”的步骤。

这就是离散碰撞检测的致命缺陷：物理引擎按固定时间步长（比如 1/60 秒）采样物体的位置，只在采样的瞬间检查碰撞。如果物体移动速度太快，一帧内走了超过自身尺寸的距离，就可能跳过整个碰撞区域。这在游戏里表现为子弹穿过墙壁、飞车掉出地图——玩家最痛恨的 BUG。

连续碰撞检测（Continuous Collision Detection，CCD）改变了思路：不再问“现在是否重叠”，而是问“在这段时间内，两者是否会在某个时刻接触”。它计算首次碰撞时间（Time of Impact，TOI）——即从本帧到下一帧之间，那个精确的接触瞬间。一旦算出 TOI，引擎就把物体移动到那个位置，再触发碰撞响应。

有了 CCD，老王的快递车再也不会把包裹甩飞了。作为补偿，CCD 的计算量比离散检测贵得多，所以通常只在高速物体上启用——就像老王只在装高速运转的精密仪器时才上全套防震包装。

TOI=arg⁡min⁡t∈[0,1]{t  |  dist(A(t),B(t))=0}\text{TOI} = \arg\min_{t \in [0,1]} \left\{ t \;\middle|\; \text{dist}(A(t), B(t)) = 0 \right\}
CCD 不检查“此刻是否碰”，而是求解“何时会碰”。把子弹的移动视为一条线段，检查线段是否穿过墙的包围盒。
  1. 扫掠体构造将物体从起点到终点平移形成的扫掠范围（如子弹画出一条线段，球体画出一个胶囊体），转化为等效静止形状。
    Swept(A)={A(0)+t⋅v⃗⋅Δt∣t∈[0,1]}\text{Swept}(A) = \{ A(0) + t \cdot \vec{v} \cdot \Delta t \mid t \in [0,1] \}
  2. 求解首个接触时刻对扫掠体与目标做交点计算，得到最小时刻参数。
    thit=min⁡{t∣Swept(A)∩B≠∅}t_{\text{hit}} = \min\{ t \mid \text{Swept}(A) \cap B \neq \emptyset \}
  3. 判断有效性若 t 在 [0,1] 内，说明本时间步内确实会碰撞，移动物体至 $t_{\text{hit}}$ 并触发响应。
    0≤thit≤1⇒collision at thit0 \le t_{\text{hit}} \le 1 \Rightarrow \text{collision at } t_{\text{hit}}

碰撞流形求解

当老王确认两个包裹确实会撞上之后，他需要知道的不只是“会撞”，还要知道“怎么撞”：从哪个方向施力、撞了多深、怎么把它俩分开。这个完整的碰撞信息集合，在物理引擎中叫做碰撞流形（Contact Manifold）。碰撞流形包含三个关键数据：碰撞点（接触发生在哪个位置）、碰撞法线（推开的方向，即最短分离方向）、穿透深度（重叠有多深）。

可以把它想象成老王在给两个挤在一起的箱子贴“强力胶”标签：标签上写着“从这边推、推多远、着力点在哪儿”。物理引擎拿到流形后，就能计算一个冲量——沿法线方向的瞬时力——把两个物体推开。推的力度由弹性系数（bounce）和摩擦系数（friction）决定：纸箱碰撞几乎不弹（弹性系数趋近 0），而皮球碰撞会高高弹起。

法线和穿透深度通常用最小平移向量（MTV）来表示：沿法线方向移动穿透深度的距离，就能把两个物体恰好分开且移动量最小。计算 MTV 在 SAT 中很自然——当所有轴都有重叠时，重叠量最小的那条轴的法线就是碰撞法线。

老王把这份“碰撞报告”贴在两个箱子上，物理引擎就据此调整它们的位置和速度——箱子被轻轻弹开或停下。碰撞流形和冲量响应，构成了物理模拟中“撞击之后”的完整叙事。

j⃗=−(1+e)(v⃗AB⋅n⃗)1mA+1mB+(r⃗A×n⃗)2/IA+(r⃗B×n⃗)2/IB⋅n⃗\vec{j} = \frac{-(1 + e)(\vec{v}_{AB} \cdot \vec{n})}{\frac{1}{m_A} + \frac{1}{m_B} + (\vec{r}_A \times \vec{n})^2 / I_A + (\vec{r}_B \times \vec{n})^2 / I_B} \cdot \vec{n}
冲量公式：碰撞就像两个快递员推箱子。e 是“回弹参数”（0 到 1 之间），质量 m 决定了谁推得动谁。箱子砸向桌面时，桌面几乎不动，因为它的“质量”趋近无穷大。
  1. 相对速度计算两物体接触点处的速度差沿法线方向的分量，作为碰撞冲击强度的度量。
    vAB=(v⃗A+ω⃗A×r⃗A−v⃗B−ω⃗B×r⃗B)⋅n⃗v_{AB} = (\vec{v}_A + \vec{\omega}_A \times \vec{r}_A - \vec{v}_B - \vec{\omega}_B \times \vec{r}_B) \cdot \vec{n}
  2. 冲量大小利用动量守恒和恢复系数 e，解出沿着法线方向的冲量标量。
    j=−(1+e)vAB1mA+1mBj = \frac{-(1+e) v_{AB}}{\frac{1}{m_A} + \frac{1}{m_B}}
  3. 速度更新把冲量分别加到两个物体上，A 减速、B 加速（或反向），完成碰撞响应。
    v⃗A′=v⃗A+jn⃗mA,v⃗B′=v⃗B−jn⃗mB\vec{v}_A' = \vec{v}_A + \frac{j \vec{n}}{m_A}, \quad \vec{v}_B' = \vec{v}_B - \frac{j \vec{n}}{m_B}

优化加速技术

仓库里堆着 10 万个包裹，老王不可能两两比对各 50 亿次。他得想一套“快速排除”的方案来减少无效劳动。空间分区（Spatial Partitioning）应运而生：把仓库的地面画成方格网，每个包裹只和同格或相邻格的包裹比较。这就是空间网格哈希（Spatial Hash Grid）——用数学公式把格子的坐标映射到一个哈希表里，查找“谁在我旁边”只要 O(1) 时间。

网格哈希适合物体分布较均匀的场景（比如大量碎石、雪花）。但如果物体有大有小、分布极度不均（一个巨型BOSS站在城门口，旁边挤着上千个小喽啰），网格就不好使了了。这时要用层次包围盒树（Bounding Volume Hierarchy，BVH）——这是一种树形数据结构，树叶是每个物体的 AABB，树枝是包含多个子节点的较大 AABB，树根是覆盖全场景的最大盒子。判断碰撞时，从上往下递归搜索：如果两个父节点不重叠，整个子树直接跳过——这叫剪枝，是老王的“隔空判断”绝技。

层次树的查询效率是 O(log n)，比网格更灵活。现代物理引擎（如 Bullet、PhysX）通常两者混合使用：静态环境用 BVH，动态物体用网格哈希或每帧重建 BVH。

网格哈希和 BVH 让老王从“逐一比对”升级为“按区巡检”——把 O(n²) 的暴力搜索降为接近 O(n) 的实际开销。没有这些加速技术，任何大型物理场景都会因碰撞检测而帧率崩溃。

SpatialHash(p)=hash(⌊pxc⌋,⌊pyc⌋)\text{SpatialHash}(p) = \text{hash}\left(\left\lfloor \frac{p_x}{c} \right\rfloor, \left\lfloor \frac{p_y}{c} \right\rfloor\right)
空间哈希：把二维坐标映射到一维哈希表。C 是格子边长，格子大小决定了“邻居”范围。哈希能让老王瞬间找到“这个箱子旁边的格子是哪些”。
  1. 网格坐标计算将物体的位置除以格子边长后取整，得到所在格子的整数坐标。
    (gx,gy)=(⌊xc⌋,⌊yc⌋)(g_x, g_y) = \left(\left\lfloor \frac{x}{c} \right\rfloor, \left\lfloor \frac{y}{c} \right\rfloor\right)
  2. 哈希映射将二维网格坐标通过哈希函数压缩成一维整数，存入哈希表。
    h=hash(gx,gy)=(gx×73856093)⊕(gy×19349663)h = \text{hash}(g_x, g_y) = (g_x \times 73856093) \oplus (g_y \times 19349663)
  3. 邻居遍历检测时只检查同格子和周围 8 个邻格内的物体对，排除远处的“隔空喊话”。
    candidates(A)=⋃∥g⃗−g⃗A∥∞≤1objects(g⃗)\text{candidates}(A) = \bigcup_{\| \vec{g} - \vec{g}_A \|_\infty \le 1} \text{objects}(\vec{g})

世界模型应用

王老师最近有了新身份——AI 公司的“物理规律顾问”。公司正在开发一个世界模型（World Model）：给 AI 输入一段视频，它要能预测未来几秒的画面。可 AI 预测的画面经常出现诡异现象：人的手直接穿过杯子、球不受重力地悬浮、两个物体叠加在一起像幽灵一样。王老师一看就明白了：“这 AI 脑子里没有碰撞检测，它在'想象'世界时绕过了打包员。”

世界模型是近年 AI 领域的热门方向：它让机器在大脑中建立对物理世界的“模拟器”，从而预测动作后果。而碰撞检测，正是这个世界模拟器最不可或缺的“物理约束器”。如果 AI 生成的视频里双手能无阻力地穿透桌面，那它就没有真正理解“固体不可穿透”这一定律。

解决思路有两个方向。显式集成：在世界模型内部嵌入一个轻量级物理引擎（包含碰撞检测），先用它模拟出下一帧的物体位置，再让 AI 根据这些位置生成画面。隐式学习：通过大量带碰撞标注的视频训练 AI，让它从数据中学会“手碰到杯子时，杯子应该被推开”的规律——王老师负责给训练数据打标注，告诉 AI 每条视频里碰撞发生在哪一帧、法线方向是什么。

有了碰撞检测这位“AI脑海中的打包员”，世界模型才能理解：手推杯，杯会动；球落地，会弹起。这不仅是视频预测的质量保障，更是机器人从视觉世界学到可执行物理规律的关键一步。

WorldModel:(It,at)→physics priorI^t+1=Gen(It,CollisionSolve(It,at))\text{WorldModel}: \quad (I_t, a_t) \xrightarrow{\text{physics prior}} \hat{I}_{t+1} = \text{Gen}(I_t, \text{CollisionSolve}(I_t, a_t))
世界模型 = 视频 + 动作 → 未来画面。碰撞检测作为物理先验，约束生成器输出的每一帧都满足“物体不可穿透”。
  1. 碰撞约束注入将当前帧所有物体的位置和速度送入碰撞检测模块，求解下一时刻的合法空间位置。
    CollisionSolve:{(pi,vi)}→{pivalid}\text{CollisionSolve}: \{(p_i, v_i)\} \to \{p_i^{\text{valid}}\}
  2. 条件生成以带物理约束的画面为条件，让视频生成模型产出符合现实规律的未来帧。
    I^t+1=Gen(It,{pivalid})\hat{I}_{t+1} = \text{Gen}(I_t, \{p_i^{\text{valid}}\})
  3. 一致性损失额外计算预测帧与物理仿真结果之间的一致性损失，惩罚“穿透”和“悬浮”伪影。
    Lphys=∥I^t+1⋅Maskcollide−It+1sim⋅Maskcollide∥2\mathcal{L}_{\text{phys}} = \| \hat{I}_{t+1} \cdot \text{Mask}_{\text{collide}} - I_{t+1}^{\text{sim}} \cdot \text{Mask}_{\text{collide}} \|_2

AI 应用场景

机器人抓取操作的路径规划

阶段：数据生成与环境仿真

解决的问题：训练机器人“手眼配合”抓取物体时，若使用真实机械臂反复试验，成本高且容易损坏设备。传统方式靠人工编写碰撞规避规则，遇到新物体就得重新调整。AI 在仿真环境中大量试错时，碰撞检测实时给出“机械爪是否碰到障碍物”的反馈，驱动强化学习策略逐渐学会安全抓取——手应该伸到哪儿、抓多深、用多大力。

具体案例：OpenAI 的机器人抓取项目中，仿真环境里同时运行数千个机械臂实例，每个实例都在用碰撞检测盒（AABB/网格）判断夹具与物件的接触状态。一帧内完成上万次碰撞查询，失败数据自动标记，指导策略网络调整抓取角度。

自动驾驶的车辆碰撞预警

阶段：感知融合与决策预测

解决的问题：自动驾驶汽车每时每刻都要回答“前方车辆是否在我的行驶轨迹上”。传统方法用毫米波雷达的距离阈值判断，误差大、反应慢。AI 路径规划模块把自车和周围车辆建模为矩形 AABB/Polygon，以 10Hz 频率执行碰撞检测——一旦预测到未来几秒的轨迹重叠，立即触发刹车或变道的决策信号。

具体案例：特斯拉 FSD 的占用网络（Occupancy Network）将道路空间离散为体素网格，配合碰撞检测判断“哪些区域被占用、哪些可行驶”。当行人横穿马路，物理模拟模块在 20ms 内算出潜在的碰撞时间（TTC），优先触发紧急制动。

世界模型的训练数据增强与物理约束

阶段：模型训练与推理约束

解决的问题：视频生成模型常生成物体穿透、漂浮的“违背物理”画面。传统后处理修复成本高且效果不自然。在训练阶段，把碰撞检测结果作为物理损失函数的一部分——生成帧如果出现 AABB 重叠就加大惩罚；推理阶段，先用轻量碰撞检测模拟下一帧状态，再让模型在这个“合规”状态下生成画面。

具体案例：DeepMind 的 Genie 等世界模型在生成游戏视频时，约束虚拟角色不能穿墙。训练数据中每个视频片段都附带一个逐帧的碰撞标注（哪两个物体在哪个像素位置重叠）。模型学会在这些标注约束下预测未来帧，生成的画面不再出现“手穿桌”的恐怖谷现象。

Python 演示

python145 行
import mathimport random  class Vec2:    def __init__(self, x, y):        self.x = x        self.y = y     def __add__(self, other):        return Vec2(self.x + other.x, self.y + other.y)     def __sub__(self, other):        return Vec2(self.x - other.x, self.y - other.y)     def dot(self, other):        return self.x * other.x + self.y * other.y     def length(self):        return math.sqrt(self.dot(self))  class Ball:    """圆形碰撞体 - 小皮球"""     def __init__(self, x, y, r):        self.pos = Vec2(x, y)        self.vel = Vec2(0, 0)        self.r = r     def move(self):        self.pos = self.pos + self.vel  class Box:    """AABB碰撞体 - 快递箱"""     def __init__(self, x, y, w, h):        self.min_x = x        self.min_y = y        self.max_x = x + w        self.max_y = y + h  def ball_ball(a, b):    """圆-圆碰撞检测"""    dist = (a.pos - b.pos).length()    return dist < a.r + b.r, (a.r + b.r) - dist  def aabb_aabb(a, b):    """AABB-AABB重叠检测"""    overlap_x = min(a.max_x, b.max_x) - max(a.min_x, b.min_x)    overlap_y = min(a.max_y, b.max_y) - max(a.min_y, b.min_y)    if overlap_x <= 0 or overlap_y <= 0:        return False, 0    return True, min(overlap_x, overlap_y)  def ball_aabb(ball, box):    """圆-AABB碰撞 - 圆心投影到盒子上然后测距，像老王打手电筒"""    closest_x = max(box.min_x, min(ball.pos.x, box.max_x))    closest_y = max(box.min_y, min(ball.pos.y, box.max_y))    dx = ball.pos.x - closest_x    dy = ball.pos.y - closest_y    if dx * dx + dy * dy < ball.r * ball.r:        return True, math.sqrt(dx * dx + dy * dy)    return False, 0  class SpatialHashGrid:    """宽阶段加速 - 仓库格子分区"""     def __init__(self, cell_size):        self.cell = cell_size        self.map = {}     def _cell_coords(self, x, y):        return (int(x // self.cell), int(y // self.cell))     def insert(self, ball):        c = self._cell_coords(ball.pos.x, ball.pos.y)        if c not in self.map:            self.map[c] = []        self.map[c].append(ball)     def query_neighbors(self, ball):        """返回同格及相邻格子中的所有球"""        cx, cy = self._cell_coords(ball.pos.x, ball.pos.y)        result = []        for ix in range(cx - 1, cx + 2):            for iy in range(cy - 1, cy + 2):                for other in self.map.get((ix, iy), []):                    if other is not ball:                        result.append(other)        return result  def resolve_ball_ball(a, b, depth):    """碰撞响应 - 用冲量公式将两球推开"""    normal = (b.pos - a.pos)    dist = normal.length()    if dist < 1e-6:        return    normal = Vec2(normal.x / dist, normal.y / dist)    a.pos = a.pos + normal * (-depth / 2)    b.pos = b.pos + normal * (depth / 2)  def main():    random.seed(42)    grid = SpatialHashGrid(120)    balls = [Ball(random.randint(30, 570), random.randint(30, 370), 15)             for _ in range(25)]    for b in balls:        b.vel = Vec2(random.uniform(-2, 2), random.uniform(-2, 2))        grid.insert(b)     walls = [Box(-10, -10, 10, 400), Box(600, -10, 10, 400),             Box(-10, -10, 620, 10), Box(-10, 380, 620, 10)]     for frame in range(10):        for b in balls:            b.move()        for i, b in enumerate(balls):            for other in grid.query_neighbors(b):                hit, depth = ball_ball(b, other)                if hit:                    resolve_ball_ball(b, other, depth)        for b in balls:            for wall in walls:                hit, depth = ball_aabb(b, wall)                if hit:                    b.vel = Vec2(-b.vel.x * 0.9, -b.vel.y * 0.9)                    if wall.min_x < 0 or wall.max_x > 600:                        b.pos.x += wall.min_x < 0 and (depth + 1) or -(depth + 1)                    else:                        b.pos.y += wall.min_y < 0 and (depth + 1) or -(depth + 1)        if frame % 5 == 0:            print("frame", frame, "active_balls", len(balls))    print("simulation done")  if __name__ == "__main__":    main()
目的：演示碰撞检测从宽阶段（网格哈希）到窄阶段（圆-圆/AABB/圆-AABB 检测）再到响应（冲量推开）的完整流程。
  1. grid = SpatialHashGrid(120)创建格子边长为 120 像素的空间哈希网格，只需 O(1) 时间查找邻居球。
  2. def ball_ball(a, b)窄阶段的圆-圆检测器，用圆心距离与半径和比较判断是否碰撞。
  3. def aabb_aabb(a, b)AABB 检测器，用四组不等式判定快递箱是否重叠并返回穿透深度。
  4. def ball_aabb(ball, box)圆-AABB 混合检测，将圆心“投影”到盒子上再测距，像打包员用手电筒照影子。
  5. def query_neighbors(ball)宽阶段的关键：只查周围 8 个格子里的球，避免全量 O(n²) 比对。
  6. def resolve_ball_ball(a, b, depth)用冲量思想将两球沿法线方向推开一半深度，消除穿透。
  7. b.vel = Vec2(-b.vel.x * 0.9, -b.vel.y * 0.9)撞墙后反弹，反弹系数 0.9（接近弹性碰撞），模拟“皮球撞墙”效果。

常见误区

误区我一直以为碰撞检测就是写一句 `if (a.x == b.x && a.y == b.y)` 就完事了。反正游戏里物体不就是在某个坐标点上吗？碰到就是相等嘛。

正解这种理解忽略了三个关键事实。第一，物体有体积，碰撞是“区域重叠”而非“点重合”，所以要用包围盒/包围球而非坐标相等来判断。第二，物理引擎按离散时间步进，物体在一帧内可能从 A 点飞到 B 点（速度很快），“碰没碰”需要看整个运动轨迹。第三，碰撞检测不仅要回答“是否碰”，还要输出法线、深度、碰撞点等流形信息，用来驱动后续的物理响应。就像快递打包员不仅要确认“两个箱子是不是挤在一起”，还得知道“哪个方向挤、挤了多深、往哪边推才能分开”。

为何常见：新手从“点与点的关系”理解几何，容易先把物体抽象为“坐标点”。但实际上物理模拟中的物体是有形状、大小、朝向的实体，碰撞是形状交集问题，比“坐标相等”复杂得多。

误区分离轴定理听起来很通用——把形状投影到所有轴上看有没有间隙。那我把任何形状（包括凹多边形、圆、甚至不规则曲线）都塞进去投影，不就行了吗？

正解SAT 只对凸多边形严格成立。凹多边形、圆和曲线都有各自的数学条件问题：凹多边形需要先拆分为多个凸多边形才能用 SAT；圆虽然可以用 SAT 的退化形式（把圆心投影到法线轴上），但圆与圆的检测本质是距离比较而非投影；带曲线边界的形状（如胶囊体）需要额外的解析公式。快递打包员老王如果拿到一个“L 形”的异形箱子，他不会直接套正方形纸箱，而是先把它拆成两个矩形分别装——这就是凹多边形的“凸分解”思想。

为何常见：SAT 的证明过程（“存在分离轴 ⟺ 无碰撞”）看起来很漂亮，让人误以为它是普适真理。但实际上这个定理的成立依赖于凸性——凹多边形投影间隔可能误导判断。

误区既然空间哈希能把碰撞检测从 O(n²) 加速到接近 O(n)，那只要用了网格哈希，所有碰撞检测问题就都解决了，不必再考虑其他数据结构。

正解空间网格的加速效果严重依赖格子大小与物体分布的匹配。如果格子太小，一个物体跨越多个格子，重复计算变多；如果格子太大，每个格子里的物体太多，退化回暴力搜索。而且物体有大有小、分布极度不均匀时（比如一棵 50 米高的树和一堆蚂蚁在同一个场景），网格哈希的效率远不如层次包围盒树（BVH）。BVH 自顶向下剪枝，对“大小悬殊”的场景更鲁棒。工程实践中常是“网格 + BVH”混合使用：静态大环境用 BVH，动态密集小物体用网格。

为何常见：网上教程常单独讲网格哈希或 BVH，让人以为它们是互斥的二选一。实际物理引擎的架构是分层配合，而非单点最优。

误区我的游戏跑 120 帧甚至 240 帧，每帧间隔很短，物体在一帧内最多移动一丁点。那肯定不会再穿墙了吧？CCD 的开销可以省掉了。

正解帧率提高确实减小了每帧位移，但不能消除高速穿透。一颗以 3000 m/s 速度飞行的子弹，即使 240 帧每秒，每帧还是移动 12.5 米——远超墙壁厚度。CCD 的必要性不取决于帧率，而取决于物体速度与场景中最小特征尺寸（如墙壁厚度、小物体直径）的比值。真正专业的做法是按需启用：对高速物体（子弹、飞驰的车）开 CCD，对静态或慢速物体用离散检测。老王不会给每个包裹都上全套防震包装，只给贵重易碎品上。

为何常见：人们直觉上觉得“帧率越高越牛逼”，却忽略了物理模拟中的速度是连续量，离散采样点再密也覆盖不了全部时间轴。CCD 的“线段求交”比“帧间采样”数学上更完备。

误区碰撞检测不就是要“发现碰撞后把物体反弹”吗？写成 `velocity = -velocity` 不就行了，再乘个弹性系数，感觉挺简单的。

正解直接反转速度在多数场景会导致抖动、穿透或能量异常。真正的物理求解器先用碰撞流形（碰撞点+法线+深度）构造约束，再通过求解器（如投影高斯-赛德尔迭代）同时满足所有接触约束——这与单纯的“反弹”在数学本质上不同。反弹只是法向冲量的结果，忽略了切向摩擦力、旋转效应（角速度变化）和多点接触的耦合（一个盒子同时压着两个箱子，必须同时求解）。快递打包员整理一摞箱子时，也不能只推最上面那个——得同时考虑底板、侧板、叠在上面的所有箱子的受力平衡。

为何常见：教学演示里“弹球”的代码就这么几行，让人误以为碰撞响应就是速度变号。但那是单物体、单接触的特例，多物体堆叠时表现出的是约束求解问题，复杂度高一个数量级。

面试题

Q1. AABB 的全称是什么？它的核心设计约束是什么？

单选题 · easy

  • A.任意朝向包围盒，可随物体旋转
  • B.轴对齐包围盒，各边平行于坐标轴← 正确答案
  • C.最小体积包围盒，支持任意形状
  • D.球形包围盒，用一个球包住物体

答案：B。AABB 是 Axis-Aligned Bounding Box，关键特征就是“轴对齐”——盒子边永远平行于坐标轴。这带来两个好处：内存仅存 6 个浮点数，重叠测试只有加减法和比较。选项 A 是 OBB（定向包围盒），C 是理想但不现实的“最小体积包围盒”，D 是包围球。快递打包员的“通用纸箱”就是轴对齐的——因为仓库的墙是直的。

Q2. 两个 AABB 发生重叠的必要条件是什么？

单选题 · easy

  • A.至少有两条坐标轴上的投影区间相交
  • B.三条坐标轴上的投影区间全部相交← 正确答案
  • C.X 轴上投影相交即可
  • D.两盒子的中心距离小于半径之和

答案：B。AABB 重叠判定的核心是“所有轴上的投影区间都相交”。在三维中，X、Y、Z 三个轴必须同时满足区间重叠才能判定碰撞；如果任何一轴上区间分离，两个盒子必然不重叠。选项 A 说“至少两条”是数量理解错误。宽阶段的加速恰恰利用“一轴分离即排除”的短路求值。

Q3. 分离轴定理（SAT）适用于下列哪种形状组合？

单选题 · mid

  • A.凹多边形与凹多边形
  • B.两个凸多边形← 正确答案
  • C.任意曲线包围的形状
  • D.带孔洞的多边形

答案：B。SAT 的正确性依赖凸性——凸多边形沿任何方向投影都是一个连续区间，凹多边形投影可能分裂成多段，区间测试会失效。选项 A/C/D 都涉及凹形或曲线。工程上处理凹形时，先做凸分解（把 L 形拆成两个矩形），再对每个凸块跑 SAT。快递打包员遇到 L 形异形箱，也是拆成两个矩形分别装。

Q4. 连续碰撞检测（CCD）要解决的核心问题是什么？

单选题 · mid

  • A.提高碰撞检测的精度到子像素级
  • B.解决高速物体在离散帧间“穿透”薄墙的问题← 正确答案
  • C.减少碰撞检测的 CPU 占用率
  • D.让物体碰撞后产生更真实的形变

答案：B。CCD 的核心动机是离散采样的缺陷——物体移动过快时可能从墙的一侧直接跳到另一侧，完全跳过碰撞检测区域。它通过计算首次接触时刻（TOI）并检查扫掠体与目标的交点来规避“穿墙”。选项 A 是窄阶段分辨率问题，C 是优化加速问题，D 是软体物理问题，都与 CCD 的动机不直接相关。

Q5. 在 SAT 检测中，若两个凸多边形没有碰撞，则一定存在一条分离轴。这条轴必定是：

单选题 · mid

  • A.任意方向的随机轴
  • B.两个多边形质心连线的方向
  • C.两个多边形中某条边的法线方向← 正确答案
  • D.两个多边形中某条对角线方向

答案：C。SAT 理论保证：如果凸多边形分离，则至少存在一条边法线作为分离轴。这是因为两个分离多边形的最近特征（顶点-边接触）中，那条边的法线方向必然能分开二者的投影。不需要检查任意方向的轴，只需检查所有边法线即可——这就是 SAT 高效的原因。老王用手电筒照箱子时，最有效的角度总是垂直于某条边的方向。

Q6. 给定恢复系数 e=0.5、两质量相等的球以速度 v 和 -v 相对碰撞，碰撞后两球的速度大小最接近：

单选题 · hard

  • A.保持原速 v 和 -v
  • B.各自接近静止状态附近的速度范围← 正确答案
  • C.交换速度后变为 -v 和 v
  • D.速度变为原来的 1.5 倍

答案：B。冲量公式中，恢复系数 e 表示碰撞后相对速度与碰撞前相对速度的比值（方向相反）。初始相对速度为 2v，碰撞后相对速度应为 -e × 2v = -v，即两球分别以 0.5v 和 -0.5v 分离。e=0.5 不是完全弹性（e=1），也不是完全非弹性（e=0），处于中间态。用能量视角理解：动能损失了一半以上，所以两球速度显著降低。这就像两个快递箱对撞，不是完全弹开的皮球，也不是黏在一起的泥巴。

Q7. 空间哈希网格和 BVH 层次包围盒树的对比，哪些说法正确？

多选题 · mid

  • A.空间哈希适合动态物体均匀分布的场景← 正确答案
  • B.BVH 是自底向上构建的层次树结构
  • C.空间哈希的查询时间与格子大小无关
  • D.BVH 处理大小悬殊物体的效率优于均匀网格← 正确答案

答案：AD。A 正确——网格哈希适合物体分布较均匀的场景（碎石、雪花）。D 正确——BVH 自顶向下剪枝，对“大树+蚂蚁”这类大小悬殊场景更高效。B 错误——BVH 是自顶向下（或增量式）构建的树，根节点是全场景包围盒，子节点递归细分。C 错误——格子大小直接决定哈希效率：格子太大退化回暴力搜索，太小则重复遍历增多。打包员大仓库里既画方格线（网格）也分货架区（BVH），按场景选择。

Q8. 关于碰撞流形（Contact Manifold），下列描述正确的是：

多选题 · hard

  • A.流形包含碰撞点位置与法线方向← 正确答案
  • B.流形包含穿透深度和最分离方向
  • C.流形是求解碰撞响应的输入数据← 正确答案
  • D.流形计算完成后可直接输出渲染画面

答案：AC。碰撞流形是窄阶段输出的“碰撞报告”，包含碰撞点、法线、穿透深度，供物理求解器计算冲量和位置修正。A 正确、C 正确。B 错误——流形包含的是“最小分离方向”（MTV），而非“最分离方向”；它告诉引擎沿哪个方向推开最省力。D 错误——流形不能直接渲染，它还需要经过求解器处理后才能驱动渲染更新。老王贴的“强力胶标签”就是流形，内容写着“从这边推、推多远”的业务数据。

Q9. 宽阶段（Broad Phase）的主要目的是什么？

单选题 · easy

  • A.精确计算碰撞点和穿透深度
  • B.快速排除大量不相干的物体对← 正确答案
  • C.计算碰撞后的摩擦力和旋转
  • D.生成物体的渲染网格

答案：B。宽阶段用廉价包围体（AABB/球体）快速排除没可能碰撞的物体对，减少后续精确检测的候选数量。正是宽阶段让碰撞检测从 O(n²) 暴力搜索降至接近线性。选项 A 是窄阶段的工作，C 是求解器的工作，D 是渲染管线的工作。现代物理引擎 80% 的计算节省都来自宽阶段的过滤效果。

Q10. 在基于世界模型的视频生成中，碰撞检测的作用体现在哪些方面？

多选题 · hard

  • A.约束预测帧中物体不相互穿透← 正确答案
  • B.提供物理损失函数增强训练信号← 正确答案
  • C.直接生成高清晰度渲染画面
  • D.推断手与物体接触时的交互方向← 正确答案

答案：ABD。在世界模型中，碰撞检测扮演“物理先验”角色。A 正确——约束物体不可穿透，消除“手穿桌”伪影。B 正确——把碰撞标注转化为物理一致性损失，惩罚生成帧的违反物理现象。D 正确——用碰撞流形推断接触时的法线方向，让 AI 学会“推”而非“穿”。C 错误——碰撞检测不负责渲染，渲染由生成模型（如扩散模型）完成，碰撞检测只是前置约束环节。AI 脑海中的打包员负责“核验”，不负责“画画”。