25 Collision Detection

实时渲染中的碰撞检测

概述：碰撞处理的三部曲

在深入细节之前，我们首先要理解碰撞处理 (Collision Handling) 的完整流程。它不仅仅是检测“是否碰撞”，而是由三个紧密相连的阶段构成：

1. 碰撞检测 (Collision Detection): 判断两个或多个物体是否发生重叠。这个阶段的输出是一个布尔值（是/否）。
2. 碰撞确定 (Collision Determination): 如果检测到碰撞，此阶段将计算出精确的相交信息，例如交点、交线或重叠体积。
3. 碰撞响应 (Collision Response): 根据碰撞信息，决定物体应该如何反应，例如反弹、破碎、产生声音等。这是物理模拟的核心部分。

为了处理包含成千上万个物体的复杂场景，现代渲染引擎通常将碰撞检测本身也划分为一个多阶段的过滤流程，以实现从粗糙到精确的逐级筛选，极大地提高了效率。

• 宽阶段 (Broad Phase): 在整个场景中，快速剔除掉绝对不可能碰撞的物体对。目标是“大海捞针”，找出少数可能碰撞的候选者。
• 中阶段 (Mid Phase): 针对宽阶段筛选出的每一对物体，进一步检查它们内部的各个部分（例如，模型的不同组件）是否可能重叠。
• 窄阶段 (Narrow Phase): 对中阶段找出的可能重叠的几何图元（如三角形、顶点）进行精确的、数学上的相交测试。

---

25.1 宽阶段碰撞检测 (Broad Phase)

核心目标: 快速识别出包围体（Bounding Volume, BV）发生重叠的物体对，将需要进一步检查的候选对数量从 $O(n^2)$ 级别显著降低。

一个包含 $n$ 个动态物体和 $m$ 个静态物体的场景，若采用暴力破解法，每帧需要进行的碰撞测试次数为：

$nm+\frac{n(n-1)}{2}$

当 $n$ 和 $m$ 很大时，这个计算量是无法接受的。宽阶段算法的核心就是为了避免这种平方级别的复杂度。它通常使用计算简单的轴对齐包围盒 (AABB) 作为物体的代理。

25.1.1 扫描剪枝算法 (Sweep and Prune, SAP)

核心观点: 利用时间一致性（Temporal Coherence），即物体在两帧之间的位置变化很小，从而使得物体的排序状态也基本保持不变。

关键算法:

1. 降维处理: 将三维空间中的AABB重叠问题，分解为在X、Y、Z三个轴上独立的一维区间重叠问题。只有当两个AABBs在所有三个轴上的区间都重叠时，它们才可能发生碰撞。
2. 排序与扫描:
   • 为每个轴创建一个列表，包含所有AABBs在该轴上的起始点和结束点。
   • 对这个列表进行排序。
   • 从头到尾“扫描”该列表，维护一个“活动区间列表 (Active Interval List)”。
   • 当遇到一个区间的起始点时，该区间与当前“活动列表”中的所有区间都构成重叠。
   • 当遇到一个区间的结束点时，将其从“活动列表”中移除。
3. 利用时间一致性:
   • 由于物体帧间移动很小，上一帧排好序的端点列表在当前帧中几乎是“近似有序”的。
   • 因此，可以使用对近似有序列表性能极佳的排序算法，如插入排序 (Insertion Sort) 或冒泡排序，其时间复杂度可接近 $O(n)$。

性能特点:

• 期望时间复杂度: $O(n+k)$，其中 $n$ 是物体数量，$k$ 是报告的重叠对数量。性能极高。
• 最坏情况: 当大量物体在某个轴上聚集时（例如，所有物体都落在地板上），该轴的重叠区间会激增，算法性能会退化至 $O(n^2)$。
• 优化: 在上述最坏情况下，可以考虑忽略该轴（如Z轴），仅在X和Y轴上进行测试。

25.1.2 网格 (Grids)

核心观点: 将空间划分为均匀的单元格，仅对落在同一单元格内的物体进行碰撞检查。

关键算法:

1. 空间划分: 在场景中定义一个三维的、由同样大小的单元格组成的网格。
2. 物体插入: 将每个物体的BV（通常是AABB）插入到它所重叠的所有网格单元格中。
3. 碰撞测试: 遍历每个单元格，对该单元格内的所有物体对进行BV重叠测试。

关键挑战与解决方案:

• 单元格大小的选择: 这是性能的关键。
  • 过大: 导致每个单元格内物体过多，退化为暴力检测。
  • 过小: 导致大物体横跨大量单元格，增加了插入和管理的开销。
  • 一种常见的策略是让单元格大小略大于场景中最大物体的尺寸，这样可以保证每个物体最多只与8个单元格（在3D中）重叠。
• 内存消耗与场景边界:
  • 问题: 存储一个巨大的、可能大部分为空的网格数组会浪费大量内存，并且物体的活动范围受限于预设的网格边界。
  • 解决方案: 空间哈希 (Spatial Hashing)。不实际存储网格数组，而是使用一个哈希函数将单元格的坐标 (i, j, k) 映射到一个哈希表的索引上。这样既节省了内存，也隐式地创建了一个“无限大”的虚拟网格。

变体:

• 层次化网格 (Hierarchical Grids): 类似于八叉树，使用不同尺寸的网格层级来更高效地处理尺寸差异巨大的物体。

25.1.3 层次包围体 (Bounding Volume Hierarchies, BVH)

核心观点: 通过构建一个树状的层次结构来组织场景中的物体，从而能够以对数时间复杂度快速剔除不相关的物体群。

关键算法:

1. 构建BVH:
   • 为场景中所有需要进行碰撞检测的物体构建一个单一的BVH树。
   • 树的叶子节点是单个物体的AABB。
   • 内部节点是一个能完全包围其所有子节点的AABB。
   • 对于动态场景，这个BVH通常需要每帧重新构建或更新。
2. 自相交测试 (BVH vs. BVH):
   • 从根节点开始，让BVH与自身进行重叠测试：Test(root, root)。
   • 对于一个递归调用 Test(NodeA, NodeB)：
     • 如果 NodeA 和 NodeB 的AABB不重叠，则剪枝，其下的所有子节点都不可能碰撞。
     • 如果重叠，则向下递归，测试它们子节点之间的所有组合。例如，若NodeA有两个子节点A1, A2，NodeB有两个子节点B1, B2，则需要进行 Test(A1, B1), Test(A1, B2), Test(B1, A2), Test(B2, A2) 等测试（注意避免节点与自身及其兄弟节点的重复测试）。
     • 当递归到两个叶子节点且它们的AABB重叠时，就找到了一个潜在的碰撞对，并将其输出到下一阶段。

核心优势:

• 数据结构复用: 构建好的BVH是一种通用的空间加速结构，不仅可以用于宽阶段碰撞检测，还可以被无缝地用于视锥剔除、遮挡剔除和光线追踪等其他渲染任务，极具价值。

---

总结: 宽阶段是性能优化的第一道防线，也是至关重要的一环。选择哪种算法取决于具体的应用场景：

• 如果场景中物体移动具有高度的时间连贯性，SAP 通常是性能最好的选择。
• 如果场景物体分布较为随机或需要处理一个无边界的世界，基于空间哈希的网格是一个非常灵活和稳健的选择。
• 如果你希望构建一个可以被多任务复用的统一加速结构，BVH 是一个极具吸引力的方案。

25.2 中阶段碰撞检测 (Mid Phase)

核心目标: 承接宽阶段的结果，对每一对可能碰撞的复杂物体，利用层次包围体 (Bounding Volume Hierarchy, BVH) 进行遍历，从而精确定位出物体内部具体是哪些**部分（图元集合）**发生了重叠。

简单来说，如果宽阶段的回答是“物体A和物体B可能碰上了”，中阶段就要进一步回答“是物体A的头部和物体B的手臂可能碰上了”。对于简单的碰撞体（如球体、胶囊体），可以直接跳过此阶段进入窄阶段。

25.2.1 BVH 构建 (BVH Construction)

核心观点: 在进行碰撞检测前，需要为每个复杂模型预处理，构建一个高效的BVH。BVH的质量直接决定了中阶段的查询效率。

BVH 结构:

• 一种k叉树 ($k$-ary tree)，每个内部节点有最多 $k$ 个子节点（在现代SIMD架构下，$k$ 常取4或8）。
• 内部节点 (Internal Node): 存储一个能完全包围其所有子节点的BV。
• 叶子节点 (Leaf Node): 存储一个或多个几何图元（例如，三角形）。

四种主流构建方法:

1. 自下而上 (Bottom-up): 从图元开始，不断将邻近的图元或已形成的BV组合成更大的父BV，直到形成唯一的根节点。能很好地将空间上邻近的图元聚合在一起。
2. 增量树插 (Incremental Insertion): 从一棵空树开始，逐个将图元插入到能使BVH总体积或表面积增长最小的位置。
3. 自上而下 (Top-down): 最流行的方法。从一个包裹整个模型的根BV开始，递归地将图元集分裂成两（或k）部分，并为每个部分创建新的子BV，直到满足终止条件（如节点内的图元数量小于阈值）。
4. 线性BVH (Linear BVH, LBVH): 一种非常现代化且高效的方法，特别适合GPU并行构建。
   • 为每个图元的中心点计算一个莫顿码 (Morton Code)，这是一种能保持空间局部性的整数编码。
   • 根据莫顿码对所有图元进行快速排序。
   • 基于这个有序的图元列表，便可以高效地构建出BVH。

构建BVH的“黄金准则”——表面积启发式 (Surface Area Heuristic, SAH):

• 一个高质量的BVH，其节点的BV应该尽可能紧密。实践证明，最小化BV的表面积 (Surface Area) 通常是比最小化体积更优的启发式策略。
• SAH源自光线追踪，其核心思想是评估将一个节点分裂（成为内部节点）的成本与不分裂（成为叶子节点）的成本，并选择成本更低方案。其成本函数为： $$C(n)=\{\begin{array}{ll}{C}_{i}A(n)+C(n_l)+C(n_r),& \text{若n为内部节点}\\ C_{t}A(n)N(n),& \text{若n为叶子节点}\end{array}$$
  • $A(n)$ 是节点 $n$ 的BV表面积。
  • $C_i$ 是遍历内部节点的成本，$C_t$ 是测试图元相交的成本。
  • $N(n)$ 是叶子节点 $n$ 中的图元数量。

25.2.2 BVH间的碰撞测试

核心观点: 通过同时递归遍历两棵BVH树，利用BV间的相交测试进行高效剪枝。

关键算法 (MidPhaseCD(Node A, Node B)):

1. BV测试: 首先，检测 Node A 和 Node B 的包围体 $A_{BV}$ 和 $B_{BV}$ 是否重叠。
2. 剪枝: 如果 $A_{BV}$ 和 $B_{BV}$ 不重叠，那么它们各自包含的所有子孙节点和图元都不可能发生碰撞，直接返回，不再继续深入。这是BVH高效的核心。
3. 递归下降: 如果 $A_{BV}$ 和 $B_{BV}$ 重叠，则根据节点类型进行处理：
   • 都是叶子节点: 找到了真正可能碰撞的一对图元集合。将这对叶子节点 (A, B) 添加到结果列表中，交由窄阶段处理。
   • 一个是内部节点，一个是叶子节点: 递归地用内部节点的每个子节点与该叶子节点进行测试。
   • 都是内部节点: 递归地测试它们子节点之间的组合。
     • 优化策略: 一个常用的启发式方法是，优先下降表面积更大的那个节点。例如，若SurfaceArea(A) > SurfaceArea(B)，则用A的每个子节点去和B进行递归测试。这倾向于更快地深入到更稀疏的空间区域。

25.2.3 BVH成本函数

核心观点: 评估一个碰撞检测系统的整体性能，需要综合考虑多个方面的成本。这揭示了不同BV类型之间的核心权衡 (trade-off)。

一个完整的碰撞检测成本可以建模为：

$t=n_v{c}_v+n_p{c}_p+n_u{c}_u$

• $n_v{c}_v$: BV-BV测试总成本。$n_v$ 是BV重叠测试的次数，$c_v$ 是单次测试的成本。
• $n_p{c}_p$: 图元-图元测试总成本。这是窄阶段的成本。
• $n_u{c}_u$: BV更新总成本。$n_u$ 是因物体运动需要更新的BV数量，$c_u$ 是单次更新的成本。

核心权衡:

• 球体 (Spheres): 更新成本($c_u$)和测试成本($c_v$)极低，但包裹效果差，导致$n_v$（不必要的BV测试）很高。
• OBB: 包裹效果好 (能显著降低$n_v$和$n_p$)，但更新($c_u$)和测试($c_v$)成本相对较高。
• AABB: 介于两者之间，是性能和实现复杂度之间的一个很好的平衡点。

25.2.4 案例研究：OBB树 (OBB Trees)

核心观点: OBB树是BVH在中阶段应用的一个经典范例，它使用定向包围盒 (Oriented Bounding Box, OBB) 作为BV，因其紧密的包裹性而表现出色。

关键特性:

1. 选择包围体 (OBB): 相比AABB和球体，OBB能更紧密地贴合任意方向的几何体，从而极大减少了BV间的无效重叠，有效降低了$n_v$。
2. 建立层次结构: 通常采用自上而下的方式构建。在每一步递归中，沿父节点OBB的最长轴将图元集一分为二，再为两个子集分别计算新的紧密OBB。
3. 处理刚体运动:
   • BVH中存储的OBB都是相对于其父节点的局部坐标。
   • 在进行两个节点 $A$ 和 $B$ 的重叠测试时，需要计算出从 $A$ 的坐标系到 $B$ 的坐标系的相对变换矩阵 ${\mathbf{T}}_{AB}$。
   • ${\mathbf{T}}_{AB}={\mathbf{M}}_A^{-1}{\mathbf{M}}_B$
   • 当递归到 $A$ 的子节点 $C$ 时，这个相对变换会级联更新：${\mathbf{T}}_{CB}={\mathbf{M}}_C^{-1}{\mathbf{T}}_{AB}$。
4. 性能优化 - 简化SAT (SAT lite):
   • 完整的OBB-OBB重叠测试（基于分离轴定理）需要测试15个潜在的分离轴，计算量较大。
   • “SAT lite”是一种优化，它跳过了计算最昂贵的9个由两盒边向量叉乘构成的分离轴。
   • 这使得BV-BV测试 ($c_v$) 大幅加快，虽然可能会产生一些“假阳性”（将不重叠的OBB误判为重叠），但这些误判会在更深的递归层次中被修正，总体上能提升平均性能。

25.3 窄阶段碰撞检测 (Narrow Phase)

核心目标: 这是碰撞检测的最后一环，也是精度最高的一环。它负责处理由中阶段筛选出的、BV已经重叠的图元集合（叶子节点对），进行精确的几何相交测试，最终确认碰撞并计算必要的碰撞信息。

25.3.1 图元 vs 图元 (Primitive vs. Primitive)

核心观点: 这是最直接的窄阶段实现方式，即对两组可能碰撞的图元（如三角形）进行两两配对，执行精确的数学相交测试。

• 基本流程: 对于中阶段输出的每一对重叠的叶子节点 (LeafA, LeafB)，执行一个双重循环：
  • 遍历 LeafA 中的每一个三角形。
  • 遍历 LeafB 中的每一个三角形。
  • 执行三角形-三角形相交测试。
• 实现考量: 虽然可以将中阶段和窄阶段的代码逻辑合并，但将它们分开可以带来优化机会。例如，可以收集所有需要测试的图元对，然后根据类型（如 三角形-三角形、三角形-球体）进行排序，以便于使用SIMD指令进行并行化处理，从而大幅提升性能。

25.3.2 距离查询 (Distance Queries)

核心观点: 对于凸体，我们往往更关心它们之间的最小距离，而不仅仅是一个简单的“是否碰撞”的布尔值。距离查询提供了更丰富的信息，可用于更高级的物理响应。

• 关键应用:

  • 公差验证 (Tolerance Verification): 在CAD/CAM领域，检查零件之间是否保留了足够的安全间隙。
  • 路径规划 (Path Planning): 为机器人或游戏角色寻找无碰撞的移动路径。
  • 穿透深度 (Penetration Depth): 当物体已经发生穿透时，计算需要将它们推开多远的距离才能刚好分离。这是现代物理引擎进行碰撞响应的关键数据。

• 关键算法: GJK (Gilbert-Johnson-Keerthi)

  • 核心思想: 计算两个凸物体 $A$ 和 $B$ 之间的最小距离，等价于计算它们的闵可夫斯基差 (Minkowski Difference) 物体 $A-B$ 到坐标原点的最小距离。
  • 闵可夫斯基差: 这是一个通过将一个物体在另一个物体表面“扫过”而形成的新凸体。其定义为：
  $$A-B=\mathbf{x}-\mathbf{y}\mid \mathbf{x}\in A,\mathbf{y}\in B$$
  • 相交判定: 如果坐标原点被包含在闵可夫斯基差物体 $A-B$ 内部，则说明原始物体 $A$ 和 $B$ 发生了重叠。
  • 算法流程: GJK是一个高效的迭代算法。它在 $A-B$ 空间内维护一个单纯形 (simplex)（在3D中，最多由4个顶点构成的四面体），并逐步迭代，寻找离原点最近的点。如果最终找到的最近点就是原点本身，则物体相交。
  • 扩展算法 - EPA (Expanding Polytope Algorithm): 当GJK检测到碰撞后，通常会启动EPA。EPA可以从GJK的最终单纯形出发，“扩张”成一个多面体，从而精确地计算出穿透深度和方向。
  • 性能优化: 利用时间一致性，将上一帧计算出的分离轴作为当前帧GJK算法的初始搜索方向，往往能让算法在一步之内收敛，实现数量级的性能提升。

---

25.4 射线碰撞检测 (Ray Collision Detection)

核心观点: 在某些特定应用（尤其是游戏）中，可以用一组射线来近似一个复杂的物体，从而实现一种非常快速但非精确的碰撞检测。

• 典型场景: 模拟车辆的悬挂系统。
  • 实现方法: 在汽车的每个车轮下方放置一条垂直向下的射线。
  • 信息获取: 将这些射线与地面场景进行相交测试。
    • 射线与地面的交点距离，直接对应了悬挂的压缩长度。
    • 如果距离为负，说明车轮“陷入”了地面。
    • 如果距离很大，说明车轮悬空。
  • 碰撞响应: 物理系统可以直接利用这些距离信息来计算悬挂弹力，调整车身姿态。
• 优点: 算法简单、计算速度极快。
• 缺点: 是一种近似方法，无法处理复杂的碰撞情况（例如车辆翻滚时车顶与环境的碰撞），鲁棒性有限。
• 另一种用途: 当检测到两个物体BV重叠时，可以从一个物体表面上位于重叠区域内的顶点，沿着顶点法线的反方向发射射线，检测与另一个物体的交点。这个相交距离可以作为穿透深度的一种快速估算。

---

25.5 使用BSP树的动态CD (Dynamic CD with BSP Trees)

核心观点: 这是一种非常巧妙的技术，用于检测一个动态移动的简单凸体（如球体、圆柱体）与一个由BSP树表示的静态复杂环境之间的碰撞。它本质上是一种连续碰撞检测。

• 核心思想 - 空间变换: 该技术的核心是闵可夫斯基和思想的逆向应用。我们不直接测试一个“胖”的物体（如球体）与BSP树的几何表面，而是：

  1. 将BSP树的所有分割平面根据碰撞体的形状和尺寸向外侧“推”一段距离。
  2. 然后用一个“瘦”的物体（如球心这个点）来与这个动态调整后的BSP树进行测试。

• 算法流程:

  1. 预处理: 静态场景被构建成一棵表面对齐 (surface-aligned) 的BSP树（即树的分割平面就是场景中的墙面、地面等）。
  2. 动态调整: 在运行时，当一个半径为 $r$ 的球体需要与这棵BSP树进行碰撞检测时，对于树中任意一个平面 $\pi :\mathbf{n}\cdot \mathbf{x}+d=0$，测试时会临时使用一个调整后的平面 ${\pi }^{\prime }:\mathbf{n}\cdot \mathbf{x}+d\pm r=0$。
  3. 简化测试: 最终，复杂的“移动球体 vs 静态BSP”问题，被转化为了简单的“移动的点 vs 动态调整后的BSP”问题。

• 扩展性: 该方法可以扩展到圆柱体和任意移动凸包，只需推导并使用不同的平面调整公式即可。

• 问题与改进: 直接使用该方法会在场景的凸角处产生碰撞误差（过早检测到碰撞）。

  • 解决方案: 在构建BSP树时，在几何的凸角处手动添加一些额外的斜面 (Bevel Planes)，从而更好地近似一个“圆角”过渡，提高碰撞的精度。

• 优点: 仅需一套静态BSP树数据，就可以支持与任意尺寸的角色或物体进行高效的动态碰撞检测，极大节省了内存和预处理时间。

25.6 限时碰撞检测 (Time-Critical Collision Detection)

核心目标: 确保碰撞检测（CD）模块的计算不会超过一个预设的时间预算（例如，5毫秒），从而帮助游戏引擎维持一个稳定、平滑的帧率，避免因场景复杂度变化而导致的帧率剧烈波动。

核心思想: 放弃传统的深度优先 (depth-first) 遍历，转而采用广度优先 (breadth-first) 的方式遍历BVH。

• 深度优先的问题: 在时间有限的情况下，算法可能会把所有时间都花在深入探索BVH的某一个分支上，而完全忽略了其他分支，导致可能错过重要的碰撞。
• 广度优先的优势: 它逐层遍历BVH，优先处理那些体积更大、位于层级更高处的BV。如果在中途时间耗尽，算法至少对两个物体的整体轮廓进行了检查，得到一个虽不精确但“顾全大局”的近似结果。

关键算法:

1. 初始化: 将宽阶段检测出的所有重叠的物体根节点对放入一个队列 (Queue) $Q$ 中。
2. 迭代处理:
   • 只要时间和队列不为空，就从队列的头部取出一对BV (A, B)。
   • 对 A 和 B 的所有子节点进行两两重叠测试。
   • 将所有重叠的子节点对添加到队列的尾部。
3. 终止: 当队列为空（所有细节都已检查完毕）或时间预算耗尽时，算法停止。

优化: 可以使用优先级队列 (Priority Queue)，根据可见性、物体与摄像机的距离等因素为BV对分配优先级，优先处理玩家更关心的碰撞。

---

25.7 可变形模型 (Deformable Models)

核心目标: 为那些顶点在世界空间中不断运动，但拓扑结构（网格连接关系）保持不变的物体（如布料、蒙皮角色）提供高效的碰撞检测。

核心思想: 避免每帧从头重建BVH。由于树的层次结构仍然是有效的，我们只需更新（重整, Refit）树中每个节点的包围体，让它重新紧密地包裹变形后的模型部分。

关键策略1: 自下而上重整 (Bottom-up Refit)

• 流程: 从BVH的叶子节点开始，向上回溯至根节点。
• 首先，根据变形后的顶点重新计算所有叶子节点的BV。
• 然后，根据其子节点更新后的BV，重新计算每个父节点的BV。
• 优点: 实现简单，比完全重建快得多（约10倍）。
• 缺点: 即使某个分支在后续的碰撞查询中根本不会被访问到，它的BV也依然被更新了，造成了计算浪费。

关键策略2: 混合更新 (Hybrid Top-down/Bottom-up Update)

• 这是一种更智能、更高效的“懒更新”策略。
• 上层节点 (Top Levels): 对于靠近根节点的少数几层BVH，每帧都使用自下而上的方式进行更新。因为这些节点在碰撞查询的早期剪枝中起着至关重要的作用。
• 下层节点 (Lower Levels): 采用自上而下、按需更新的策略。也就是说，只有当碰撞查询算法遍历到某个深层节点时，这个节点的BV才会被即时计算和更新。如果一个分支被提前剪枝，那么它下方的所有节点都不会被更新，从而节省了大量计算。

---

25.8 连续碰撞检测 (Continuous Collision Detection, CCD)

核心目标: 解决隧穿效应 (Tunneling) 问题。在离散的帧更新模式下，一个高速移动的物体（如子弹）可能在上一帧还在墙前，下一帧就完全穿到了墙后，从而完美错过了碰撞检测。

核心思想: 保守推进 (Conservative Advancement) 这是一种通过计算一个绝对安全的“非碰撞时间”，来迭代式地推进物体，直到找到精确碰撞时刻的方法。

关键算法:

1. 计算距离: 在时间步开始时，使用GJK等算法计算两个凸物体 $A$ 和 $B$ 之间的最短距离向量 $\mathbf{d}$。
2. 计算速度上界: 估算在 $\mathbf{d}$ 方向上，两个物体靠近速度的保守上界 $c$。这个计算必须同时考虑物体的线速度和角速度。
3. 计算安全时间: 可以保证在时间间隔 $\Delta t$ 内绝不会发生碰撞。 $$\Delta t=\frac{\Vert \mathbf{d}\Vert }{c}$$ 其中 $c$ 是一个综合了线速度和角速度的复杂项，代表了最大接近速率。
4. 推进:
   • 如果计算出的安全时间 $\Delta t$ 大于当前帧的时间步长，那么本帧内不会发生碰撞。
   • 如果 $\Delta t$ 小于当前帧的时间步长，说明碰撞可能会发生。此时，我们将物体向前推进 $\Delta t$ 的时间，然后用剩余的帧时间重复步骤1-4，直到找到精确的碰撞点或走完整个时间步。

---

25.9 碰撞响应 (Collision Response)

核心目标: 在检测到碰撞后，决定物体应该如何运动，以模拟真实的物理反弹效果。

关键概念: 反射模型 (Reflection Model) 以最简单的“球体撞平面”为例：

1. 速度分解: 将球体的入射速度向量 $\mathbf{v}$ 分解为：
   • 法向分量 ${\mathbf{v}}_n$: 垂直于平面的分量。
   • 切向分量 ${\mathbf{v}}_p$: 平行于平面的分量。
   $${\mathbf{v}}_n=(\mathbf{v}\cdot \mathbf{n})\mathbf{n},{\mathbf{v}}_p=\mathbf{v}-{\mathbf{v}}_n$$
2. 计算反射速度: 碰撞后的新速度 ${\mathbf{v}}^{\prime }$ 由以下公式决定： $${\mathbf{v}}^{\prime }={\mathbf{v}}_p-k\cdot {\mathbf{v}}_n$$
3. 恢复系数 (Coefficient of Restitution) $k$: 一个在 $[0,1]$ 区间的物理参数，用于描述碰撞的“弹性”程度。
   • $k=1$: 完全弹性碰撞，能量守恒，球会以同样大小的法向速度反弹（像完美的弹力球）。
   • $k=0$: 完全非弹性碰撞，法向速度变为0，能量损失最大（像一团湿泥撞墙）。
   • $0<k<1$: 部分弹性碰撞，模拟现实世界中的大多数情况。

---

25.10 粒子 (Particles)

25.10.1 用于视觉特效的粒子 (For VFX)

核心目标: 为成千上万的装饰性粒子（如火花、雨滴、碎屑）提供廉价且近似的碰撞检测。

• 技术1: 深度缓冲法 (Depth Buffer Method)
  • 将粒子与摄像机渲染出的深度缓冲进行碰撞。
  • 优点: 速度极快，几乎没有额外开销。
  • 缺点: 只能与可见的物体表面碰撞，且没有厚度概念，是一种非常粗糙的近似。
• 技术2: 符号距离场法 (Signed Distance Field, SDF)
  • 将静态场景预处理成一个三维纹理，每个像素存储该点到最近表面的有向距离。
  • 优点: 检测碰撞只需一次纹理采样，非常快，并且可以处理场景的任何部分（无论可见与否），效果远超深度缓冲法。

25.10.2 用于物理模拟的粒子 (For Physics Simulation)

核心目标: 用于模拟流体、沙土等连续介质（如SPH方法），每个粒子代表一小块物质。

• CD需求: 核心是邻域搜索，即每个粒子都需要快速找到其一定作用半径内的所有其他粒子，以计算相互作用力。
• 解决方案: 这是一个经典的N体问题，通常使用高效的空间加速结构来解决，例如：
  • 均匀网格 (Uniform Grids) 或 空间哈希 (Spatial Hashing): 最常用且高效的方法。
  • 每帧动态构建的 BVH。

25.11 动态相交测试 (Dynamic Intersection Tests)

核心目标: 解决静态碰撞检测在离散时间步长（帧）下会产生的隧穿效应 (tunneling) 问题。动态测试的目的不是简单地判断“是否碰撞”，而是要精确计算出在 [0, 1] 的时间区间内（代表当前帧的开始到结束），两个运动物体首次发生碰撞的精确时间 $t$。

在深入具体算法前，有两个至关重要的简化思想贯穿始终：

1. 相对运动原理 (Principle of Relative Motion): 对于两个都在运动的物体 $A$（速度 ${\mathbf{v}}_A$）和 $B$（速度 ${\mathbf{v}}_B$），我们可以假定物体 $B$ 是静止的，而物体 $A$ 以相对速度 $\mathbf{v}={\mathbf{v}}_A-{\mathbf{v}}_B$ 运动。这能将复杂双运动体问题简化为单运动体问题。

2. 闵可夫斯基和 (Minkowski Sum): “一个移动的形状A vs 一个静止的形状B”的碰撞问题，可以等价地转化为“一个移动的点（射线） vs 一个静止的、被‘膨胀’了的形状C”的问题。这个膨胀后的形状C就是A和B的闵可夫斯基和。这个思想是动态测试的“核武器”。

25.11.1 移动球体 vs. 静态平面 (Moving Sphere vs. Plane)

核心观点: 这是一个基础的动态测试，可以通过简单的线性插值来求解碰撞时间。

关键算法:

1. 获取距离: 计算球心在起始位置 $\mathbf{c}$ 和终止位置 $\mathbf{e}$ 时，到平面的带符号距离，记为 $s_c$ 和 $s_e$。
2. 求解时间: 碰撞发生在球心到平面的距离刚好等于球体半径 $r$ 的那一刻。通过对距离进行线性插值，可以直接求出碰撞时间 $t$。 $$t=\frac{s_c-r}{s_c-s_e}$$

• 如果计算出的 $t$ 在 $[0,1]$ 区间内，则在本帧发生了碰撞。

25.11.2 移动球体 vs. 移动球体 (Moving Sphere vs. Sphere)

核心观点: 通过两次转换，将复杂的“移动球体 vs 移动球体”问题，简化为经典的“射线 vs 静态球体”问题。

转换步骤:

1. 应用相对运动: 让球体B静止，球体A以相对速度 ${\mathbf{v}}_{AB}={\mathbf{v}}_A-{\mathbf{v}}_B$ 运动。
2. 应用闵可夫斯基和: 将运动的球体A“收缩”成一个点（射线的起点），同时将静止的球体B“膨胀”，使其半径变为两个球体半径之和 $(r_A+r_B)$。

求解方法:

• 问题转化后，我们只需解一个关于时间 $t$ 的一元二次方程：$a{t}^2+bt+c=0$。

• 其中系数为：

  $$\begin{array}{rl}a& =(\mathbf{v}\ast AB\cdot \mathbf{v}\ast AB)\\ b& =2\cdot (({\mathbf{c}}_A-\mathbf{c}\ast B)\cdot \mathbf{v}\ast AB)\\ c& =({\mathbf{c}}_A-{\mathbf{c}}_B)\cdot ({\mathbf{c}}_A-{\mathbf{c}}_B)-(r_A+r_B{)}^2\end{array}$$

• 解这个方程得到的最小的、且在 $[0,1]$ 区间内的正实数解 $t$，就是首次碰撞时间。

25.11.3 移动球体 vs. 静态多边形 (Moving Sphere vs. Polygon)

核心观点: 同样利用闵可夫斯基和的思想，将问题转化为“射线 vs 一个被球体‘膨胀’过的‘胶囊’状多边形”。

“膨胀”后的多边形 (Minkowski Sum of Polygon and Sphere):

• 面 (Face): 变为两个平行的面，形成一个有厚度的“板”。
• 边 (Edges): 变为圆柱体。
• 顶点 (Vertices): 变为球体。

关键算法:

• 该测试分解为射线与这个复合形状的多个部分求交：
  1. 射线 vs “板” (Face)
  2. 射线 vs 圆柱体 (Edges)
  3. 射线 vs 球体 (Vertices)
• 取所有有效交点中时间 $t$ 最小的那个，即为首次碰撞点。
• 测试顺序很重要: 按照 面 → 边 → 顶点 的顺序测试通常最高效，因为与面的碰撞通常是最近的。

25.11.4 动态分离轴方法 (Dynamic SAT)

核心观点: 将经典的分离轴定理 (Separating Axis Test, SAT) 扩展到时域，用于检测两个移动的凸多面体之间的碰撞。

关键算法:

1. 投影运动: 对于每一个需要测试的分离轴，我们不再是投影一个静态的区间，而是投影一个随时间移动的区间。
2. 计算重叠时间: 对于每一个轴，计算出两个移动的投影区间开始重叠的时间 $t_s$ 和结束重叠的时间 $t_e$。
3. 寻找最终碰撞区间:
   • 两个物体真正开始碰撞的时刻，是所有轴上 $t_s$ 中的最大值：$T_{start}=\max (t_{s1},t_{s2},...)$。
   • 两个物体完全分离的时刻，是所有轴上 $t_e$ 中的最小值：$T_{end}=\min (t_{e1},t_{e2},...)$。
   • 最终，在 $[0,1]$ 时间内，两个物体的碰撞区间为 $[T_{start},T_{end}]$。
4. 提前退出优化: 在遍历所有轴的过程中，如果任意时刻发现已计算的 $T_{start}$ 大于了已计算的 $T_{end}$，说明在整个时间段内必然存在一条分离轴，两个物体不可能碰撞。此时可以立即终止测试。这个优化与射线和AABB求交的“slab test”思想异曲同工，是算法效率的关键。

---