游戏引擎中的碰撞检测

碰撞检测是物理引擎的第一个环节，负责回答"谁和谁碰上了"。核心挑战在于：逐对检测 O(n²) 的复杂度不可接受，必须通过**宽相（快速排除）+ 窄相（精确检测）**两阶段，配合空间加速结构，将复杂度降至近似 O(n log n)。

一、碰撞检测：宽相 + 窄相

逐对检测所有物体是 O(n²)，不可接受。所以分两阶段：

宽相（Broad Phase）

用包围体 + 空间加速结构快速筛出"可能相碰"的候选对：

结构	说明
AABB	轴对齐包围盒，相交测试极快
BVH（层级包围体）	树形组织包围盒，O(log n) 查询
Sweep and Prune	沿轴排序端点，增量更新，适合帧间连续
空间哈希 / 网格	均匀网格分桶，适合均匀分布

BVH 结构示意：

                [根 AABB]
               /         \
        [子树 AABB]     [子树 AABB]
         /     \          /     \
     [叶:物体A][叶:物体B][叶:物体C][叶:物体D]
   查询时从根下潜，包围盒不相交的整枝剪掉

BVH 的构建通常在物体移动后采用增量 refit（自底向上更新包围盒），而非每帧从头重建。对于包含大量动静态物体的混合场景，双 BVH 方案（动态物体与静态场景各一棵树）配合 pair cache 管理宽相对是一种常见的优化手段。

Sweep and Prune（SAP）在每帧只需对上一帧已排序的端点列表做少量插入和交换操作（摊销接近 O(n)），而非完全重排。SAP 对轴向选择敏感——当物体沿某一轴分布较广时效率更高，细长物体则需要谨慎选择主轴。

空间哈希将世界划分为均匀网格，每个物体落入若干格子，碰撞检测仅在相同格子内进行。格子尺寸通常取物体平均大小的 2–3 倍效果最优。粒子系统、布娃娃等物体分布较为均匀的场景尤其适合。

窄相（Narrow Phase）

对候选对做精确几何相交，生成接触流形（接触点、法线、穿透深度）：

• GJK（Gilbert-Johnson-Keerthi）：判断两凸形是否相交。核心思路是对两形状计算闵可夫斯基差（Minkowski Difference），若差集包含原点则说明相交。通过支撑函数（Support Function）迭代构造单纯形（simplex），逐步逼近原点，效率极高。
• EPA（Expanding Polytope Algorithm）：GJK 判定相交后，EPA 在闵可夫斯基差边界上扩展多面体，外推得到穿透深度与分离法线，作为碰撞响应的输入。
• 简单形状（球、盒、胶囊、三角形）有解析的快速专用检测，通常作为 GJK 的前置快速路径（early out），避免进入代价更高的通用算法。
• 凹形通常拆成多个凸形（凸分解 Convex Decomposition）或使用凸包近似后再对每个凸片执行 GJK/EPA。

接触流形生成后，通常还需要对穿透点集做聚类与缩减（Contact Reduction），剔除冗余的接触点，避免向后续求解器提交过多约束。

二、连续碰撞检测（CCD）

高速物体在一步内可能穿过薄物体（隧穿 tunneling）。CCD 通过扫掠（swept）检测运动路径上的碰撞，防止穿透 —— 但开销高，通常只对高速关键物体开启。

常见做法是将物体的运动路径抽象为扫掠体（Swept Volume），并与场景进行窄相检测。步长细分法（Substep）也是一种实现思路：将单步拆为多个小时步，逐段检测碰撞。Speculative CCD 则预测当前步内的最早碰撞时间（TOI），在到达该时间前提前响应，避免额外的完整几何扫掠计算。

三、性能与实践

• 宽相是关键：好的空间结构（BVH/SAP）能将 O(n²) 降到近似 O(n log n)。静态几何与动态物体可分别使用不同加速结构，进一步减少无效候选对。
• 休眠（Sleeping）：静止物体进入睡眠后不再参与宽相检测，直到被其他运动物体扰动 —— 大幅节省 CPU 开销。
• 碰撞体简化：动态物体尽量用简单凸形（盒、球、胶囊、凸包），避免复杂网格碰撞检测的开销；静态物体可使用 triangle mesh collider。
• 分层过滤（Collision Matrix）：用层和掩码排除不需要检测的碰撞对，从源头减少宽相候选。
• CCD 按需开启：CCD 开销远高于普通离散检测，只对高速小物体（子弹、碎片）开启即可，避免全局性能损耗。
• Pair Cache 管理：宽相产生的候选对通常缓存起来，下一帧仅在缓存基础上增删，避免重复计算宽相结果。

四、总结

碰撞检测是物理引擎中独立的关键模块，通过宽相与窄相两阶段将 O(n²) 的暴力检测降低为近似 O(n log n)。宽相阶段利用 BVH、SAP、空间哈希等加速结构排除大量不可能碰撞的对；窄相阶段通过 GJK/EPA 完成精确的相交判定与接触流形生成。连续碰撞检测（CCD）解决了高速物体的隧穿问题。休眠、碰撞体简化、分层过滤、pair cache 管理等工程实践进一步平衡了精度与性能。碰撞检测的输出——接触流形——作为输入传递给后续的碰撞响应与约束求解。

附：核心概念速查

概念	说明
宽相 / 窄相	快速排除候选 / 精确检测生成接触
AABB / BVH / SAP	宽相的包围体与加速结构
空间哈希	均匀网格分桶加速宽相
GJK	凸形相交判断（闵可夫斯基差 + 支撑函数）
EPA	求穿透深度与分离法线（GJK 的后继算法）
接触流形	接触点、法线、穿透深度
扫掠体（Swept Volume）	CCD 中物体运动路径形成的体
CCD	连续碰撞检测，防高速隧穿
Sleeping	静止物体休眠省开销
碰撞矩阵	层 / 掩码过滤碰撞对