连续碰撞检测

到目前为止，我们讨论的碰撞检测都是离散 (Discrete) 的。我们在离散的时间点 $t_n$ 和 $t_{n+1}$ 对物体的位置进行采样，并检查它们在这些“快照”时刻是否重叠。这种方法对于大多数速度较慢的物体来说是有效的。然而，当物体运动速度非常快，或者非常薄时，离散检测会产生一个严重的问题——隧穿效应 (Tunneling)。

一个快速移动的子弹，在时间点 $t_n$ 时可能还在墙的一侧，而在下一个时间点 $t_{n+1}$，它已经完全穿越到了墙的另一侧。由于在这两个采样点上它都没有与墙发生重叠，离散碰撞检测会完全错过这次碰撞。为了解决这个问题，我们需要一种更强大的技术：连续碰撞检测 (Continuous Collision Detection, CCD)。

CCD 的核心思想：寻找首次碰撞时间 (Time of Impact, TOI)

CCD 不再检查物体在某个时刻是否重叠，而是检查它们在某个时间段 $[t_n,t_{n+1}]$ 内的运动轨迹是否相交。它的目标是计算出在这个时间段内，两个物体首次发生接触的精确时间点，即首次碰撞时间 (Time of Impact, TOI)。

如果计算出的 TOI 小于时间步长 $\Delta t$，那么碰撞就在这个时间步内发生。引擎可以采取以下措施：

1. 将整个物理系统推进到 TOI 时刻。
2. 在该时刻进行精确的碰撞响应。
3. 用剩余的时间 dt - TOI 继续模拟系统的剩余部分。

实现 CCD 的方法

实现 CCD 的算法通常比离散检测复杂得多，它们的核心都是在时间维度上求解一个方程。

1. 基于根查找的保守推进 (Root-Finding with Conservative Advancement)

这是一种迭代方法，它试图找到函数 $f(t)=distance(A(t),B(t))$ 的根（即距离为零的时刻）。

算法流程：

1. 初始化: 设定时间间隔为 $[0,\Delta t]$。
2. 迭代: a. 在当前时间 $t_{current}$，使用离散的距离算法（如 GJK）计算出两个物体之间的距离 $d$。 b. 如果 $d$ 小于某个容差，我们就找到了一个碰撞，返回 $t_{current}$ 作为 TOI。 c. 保守推进: 计算两个物体相对速度的最大值 $v_{max}$。我们可以保证，在至少 $t_{advance}=d/v_{max}$ 的时间内，两个物体是绝对不会碰撞的。这是一个“安全”的时间步长。 d. 将当前时间向前推进 $t_{current}+=t_{advance}$。 e. 如果 $t_{current}>\Delta t$，说明在这个时间步内没有碰撞发生。 f. 回到步骤 a。

• 优点: 概念上相对清晰，利用了现有的 GJK 距离计算功能。
• 缺点: 对于旋转运动，计算 $v_{max}$ 会比较复杂和保守，可能导致推进的步长过小，迭代次数过多。

2. 基于 GJK 的 CCD

这是一个更优雅和高效的方法，它将时间维度直接引入到 GJK 算法中。其核心思想与离散 GJK 类似：判断原点是否在两个运动物体在时间段 $[0,\Delta t]$ 内扫过的闵可夫斯基差集 (Swept Minkowski Difference) 中。

算法思想：

• 运动的闵可夫斯基差集: 想象物体 A 和 B 都在做线性运动。它们的闵可夫斯基差集 $C(t)=A(t)-B(t)$ 也在随时间运动。GJK-CCD 的目标是在时间 $t\in [0,\Delta t]$ 上，找到一个最小的 $t$，使得原点 $O\in C(t)$。
• 分离轴的变化: 在离散 GJK 中，我们寻找一个静态的分离轴。在 CCD 中，我们寻找一个随时间变化的分离轴。如果能找到一个在整个时间段内都有效的静态分离轴，那么就不会发生碰撞。
• 迭代求解 TOI: 算法通过迭代，不断地缩小 TOI 的可能范围 $[t_{min},t_{max}]$，直到找到一个精确的碰撞时间。

这个版本的 GJK 远比离散版本复杂，它需要在四维空间（3D 空间 + 1D 时间）中进行思考，但它提供了一个统一的框架来处理平移和旋转运动。

3. 特殊形状的解析解

对于一些简单的形状组合，我们可以通过解析方法直接求解 TOI。

• 运动的点 vs. 静态的平面: 这是一个简单的线性方程，可以直接解出点接触平面的时间。
• 运动的球体 vs. 静态的球体: 这涉及到求解一个关于时间 $t$ 的二次方程。方程的最小正实数根就是 TOI。

这些解析方法非常快速，但适用范围有限。在通用物理引擎中，它们通常作为特殊情况进行优化，而通用的凸体-凸体 CCD 则依赖于像 GJK-CCD 这样的迭代算法。

CCD 的性能权衡与实践

CCD 的计算成本极高，比离散检测要昂贵一个数量级以上。在一个有数百个物体的场景中，为所有物体启用 CCD 是不现实的。因此，如何在实践中有效地使用 CCD 是一个关键的工程决策。

1. 选择性启用

物理引擎通常允许开发者为特定的刚体启用 CCD。这个标志通常被称为 isBullet 或 useCCD。

• 应该为谁启用？

  • 快速移动的物体: 子弹、炮弹、高速飞行的导弹等。
  • 非常重要的物体: 玩家角色、关键任务道具等，它们的物理行为绝对不能出错。
  • 薄片物体: 纸张、布料等，即使速度不快，也容易因为厚度太小而发生隧穿。

• 谁不需要启用？

  • 大型、慢速的物体，如平台、建筑、慢速移动的箱子等。
  • 绝大多数场景中的静态背景物体。

2. 两阶段策略

一个常见的引擎架构是：

1. 主模拟阶段: 对所有物体（包括启用了 CCD 的物体）进行常规的离散碰撞检测和模拟。
2. CCD 清扫阶段: 在主模拟之后，单独对所有启用了 CCD 的物体，进行一次 CCD 检测。检查它们从上一个位置到当前位置的运动轨迹，是否与场景中的任何其他物体发生了碰撞。
3. 回溯与重模拟: 如果 CCD 检测到了一个在离散步骤中被错过的碰撞（即 TOI < $\Delta t$），引擎需要进行时间回溯 (Time Rewind)。它会将所有物体的位置重置到 TOI 时刻，在该点执行碰撞响应，然后用剩余的时间步长重新进行一次模拟。

这个过程非常复杂，需要引擎能够保存和恢复物理状态，但它确保了即使在高速运动下，关键物体的碰撞也不会被错过。

总结

连续碰撞检测 (CCD) 是解决高速物体“隧穿”问题的终极武器。它通过在时间维度上进行检测，寻找运动轨迹上的首次碰撞时间 (TOI)，从而保证了物理模拟的鲁棒性。虽然 GJK 等算法可以被扩展来高效地执行 CCD，但其固有的高计算成本决定了它不能被滥用。

在实践中，CCD 是一种需要审慎使用的“奢侈品”。通过为关键物体选择性地启用 CCD，并采用两阶段的检测与回溯策略，现代物理引擎在性能开销和物理真实性之间取得了精妙的平衡。理解这种权衡 (trade-off)，并懂得何时以及如何应用 CCD，是高级物理引擎开发者进行性能优化和保证系统鲁棒性的核心技能之一。