CCD：连续碰撞检测与高速穿透

DYNAMIC EXPLAINER / ARTICLE FLOW

把章节变成可单步观察的过程

01 / 16

STEP 01 / CODE / LOGIC

先说结论

离散碰撞只检查一帧开始和结束的位置，高速物体可能在两次采样之间跨过障碍。CCD 检查整段运动区间，并尝试求出首次接触时间 TOI。

子弹上一帧位置：x = 0
子弹这一帧位置：x = 20
薄墙范围：x = [9.5, 10.5]

STEP 02 / CODE / LOGIC

高速物体为什么会穿透

普通离散碰撞检测只检查若干离散时刻的形状关系。

t0                墙                t1
[物体]             |                 [物体]

STEP 03 / CODE / LOGIC

离散检测的事实链

离散检测的典型链条是：

取得当前时刻的形状
    ↓
Broad Phase 筛候选
    ↓
Narrow Phase 判断当前是否重叠
    ↓
若重叠，生成接触并求解

STEP 04 / CODE / LOGIC

CCD 的核心：扫掠运动区间

CCD 不只看起点形状和终点形状，而是考虑形状在时间区间内扫过的空间。

起始形状  ===== 扫掠区域 =====>  结束形状

STEP 05 / CODE / LOGIC

TOI：首次碰撞时间

TOI 是 Time of Impact，即给定时间区间内的首次碰撞时刻。

t ∈ [0, 1]

STEP 06 / CODE / LOGIC

教学示例：一维点对区间扫掠

先看最简单的一维问题。

[wallMin, wallMax]

STEP 07 / CODE / LOGIC

扫掠 AABB 的进入与离开时间

对轴对齐包围盒，可以在每个坐标轴上计算运动盒与静止盒投影区间的进入时间和离开时间。

x 轴得到 [xEntry, xExit]
y 轴得到 [yEntry, yExit]

STEP 08 / CODE / LOGIC

形状扫掠

不同形状的连续检测难度不同。

点或射线对平面、球、盒。
球体扫掠其他形状。
胶囊体扫掠场景几何。
凸形状相对运动下的首次接触。

STEP 09 / CODE / LOGIC

保守推进的直觉

保守推进不直接猜最终 TOI，而是反复执行：

1. 计算当前时刻两个形状的距离。
2. 根据接近速度估算一个不会跨过首次接触的时间增量。
3. 向前推进这个增量。
4. 距离足够小则报告接触；否则继续。

STEP 10 / CODE / LOGIC

Broad Phase 也要覆盖运动区间

即使 Narrow Phase 支持 TOI，如果 Broad Phase 只使用物体在起点的包围盒，也可能根本筛不到路径中间的障碍。

起点包围盒与终点包围盒的并集。
能够包住扫掠轨迹的扩展包围体。
根据速度扩张的代理范围。

STEP 11 / CODE / LOGIC

找到 TOI 之后发生什么

检测到首次接触只是开始。

推进到最早 TOI
    ↓
建立接触约束
    ↓
求解速度或位置响应
    ↓
处理剩余时间
    ↓
剩余运动中可能再次发生碰撞

STEP 12 / CODE / LOGIC

适用边界

CCD 更值得用于：

单步位移相对自身尺寸或障碍厚度较大的物体。
漏检会造成明显错误的关键物体。
快速运动且碰撞形状适合系统连续检测能力的对象。

STEP 14 / CODE / LOGIC

正常、边界与失败情况

擦边是否算接触、初始重叠如何分类，都需要一致的容差和接触规则。

运动模型满足算法假设。
Broad Phase 找到覆盖运动区间的候选。
TOI 位于当前时间步内。
推进到 TOI 后生成有效接触。
剩余时间得到继续处理。

STEP 15 / CODE / LOGIC

复杂度与代价

CCD 没有一个适用于所有形状的统一复杂度。

运动包围体带来的 Broad Phase 候选数量。
每个候选对的形状扫掠或距离查询成本。
迭代求 TOI 的次数。
碰撞后处理剩余时间产生的额外子步。
多个连续碰撞之间的求解成本。

STEP 16 / CODE / LOGIC

最重要的收获

离散检测只看采样时刻，因此可能漏掉两帧之间的接触。
CCD 检查运动区间，并尝试求首次碰撞时间 TOI。
扫掠检测既需要 Narrow Phase 求接触，也需要 Broad Phase 覆盖整段运动。
找到 TOI 不等于完成响应，还要处理接触和剩余时间。
形状、旋转、初始重叠与迭代预算决定 CCD 的适用边界。
CCD 应按运动尺度、漏检后果和性能预算选择，而不是无条件全开。
不支持或未收敛必须作为失败暴露，不能伪装成没有碰撞。

分类：算法

先说结论

离散碰撞只检查一帧开始和结束的位置，高速物体可能在两次采样之间跨过障碍。CCD 检查整段运动区间，并尝试求出首次接触时间 TOI。

一帧跨墙的数字

子弹上一帧位置：x = 0
子弹这一帧位置：x = 20
薄墙范围：x = [9.5, 10.5]

离散检测看到 0 和 20 都不在墙内，可能判定没有碰撞；扫掠检测检查 [0, 20]，会发现它与墙区间相交。若速度恒定，首次进入墙面的归一化时间约为 9.5 / 20 = 0.475，应先推进到该时刻再处理碰撞响应。

高速物体为什么会穿透

普通离散碰撞检测只检查若干离散时刻的形状关系。

假设一个物体在当前帧位于墙左侧，下一帧已经到了墙右侧：

t0                墙                t1
[物体]             |                 [物体]

如果只检测 t0 和 t1：

t0 没有重叠。
t1 也没有重叠。

算法就可能看不到物体在两帧之间穿过墙的事实。这称为高速穿透或隧道效应。

问题的根源不是“速度超过某个固定值”，而是：

采样间隔内的位移，相对于参与碰撞的几何尺度过大。

因此同一个速度对厚墙可能安全，对薄墙却可能穿透；时间步改变后，结果也可能改变。

离散检测的事实链

离散检测的典型链条是：

取得当前时刻的形状
    ↓
Broad Phase 筛候选
    ↓
Narrow Phase 判断当前是否重叠
    ↓
若重叠，生成接触并求解

它擅长回答：

此刻两个形状是否相交？

但高速运动需要回答：

从上一状态运动到当前状态的整个时间区间里，是否曾经接触？
最早接触发生在什么时候？

这正是连续碰撞检测关注的问题。

CCD 的核心：扫掠运动区间

CCD 不只看起点形状和终点形状，而是考虑形状在时间区间内扫过的空间。

起始形状  ===== 扫掠区域 =====>  结束形状

对于简单形状，可以把问题表述成：

运动形状沿位移向量扫过静止形状时，是否发生首次接触？

如果两个物体都在移动，可以使用相对运动：

相对速度 = 物体 A 的速度 - 物体 B 的速度

然后把 B 视为静止，分析 A 相对 B 的运动。这个变换简化的是数学表达，不意味着实际系统只更新一个物体。

TOI：首次碰撞时间

TOI 是 Time of Impact，即给定时间区间内的首次碰撞时刻。

常把一帧时间归一化为：

t ∈ [0, 1]

其中：

t = 0：本时间步开始。
t = 1：本时间步结束。
0 < t < 1：时间步内部。

如果求得：

TOI = 0.35

这里的 0.35 是教学示例，表示首次接触发生在本时间步进度的 35%，不是固定引擎参数。

系统可以先推进到 TOI，生成接触，再处理剩余时间。如何求解接触后的反弹、滑动或停止属于碰撞响应，不是 CCD 检测本身自动决定的。

教学示例：一维点对区间扫掠

先看最简单的一维问题。

静止障碍占据区间：

[wallMin, wallMax]

运动点的位置为：

p(t) = start + velocity * t

求点进入区间的最早时间，就是解：

wallMin ≤ start + velocity * t ≤ wallMax

逐步状态

以下位置与速度都是教学示例：

运动点起点：0
本时间步位移：10
墙区间：[4, 5]

可视化状态：

状态	t	点的位置	结果
起点采样	0	0	未重叠
首次进入	0.4	4	接触
离开区间	0.5	5	即将离开
终点采样	1	10	未重叠

只看两端会得到两次“未重叠”，而扫掠检测能找到 t = 0.4 的首次接触。

交互演示可以允许拖动：

起点。
终点。
墙的左右边界。
时间滑块。

并同时显示：

离散采样结果。
扫掠区间。
进入时间与离开时间。
最终 TOI。

扫掠 AABB 的进入与离开时间

对轴对齐包围盒，可以在每个坐标轴上计算运动盒与静止盒投影区间的进入时间和离开时间。

二维情况下：

x 轴得到 [xEntry, xExit]
y 轴得到 [yEntry, yExit]

整体首次进入和最终离开为：

entryTime = max(xEntry, yEntry)
exitTime  = min(xExit, yExit)

若时间区间有有效重叠，才说明扫掠过程中发生接触。

最小 C# 示例

下面代码只演示“一维运动点进入静止区间”的核心计算，不是完整物理引擎：

public static bool TryGetEntryTime(
    float start,
    float displacement,
    float intervalMin,
    float intervalMax,
    out float toi)
{
    // 起点已经在区间内：本时间步开始时就处于接触/重叠状态。
    if (start >= intervalMin && start <= intervalMax)
    {
        toi = 0f;
        return true;
    }

    // 没有相对位移时，不可能从区间外进入。
    if (displacement == 0f)
    {
        toi = 0f;
        return false;
    }

    float t0 = (intervalMin - start) / displacement;
    float t1 = (intervalMax - start) / displacement;

    float entry = MathF.Min(t0, t1);
    float exit = MathF.Max(t0, t1);

    bool overlapsStep = entry <= 1f && exit >= 0f;
    toi = entry;
    return overlapsStep;
}

完整实现还要明确：

浮点容差。
端点接触是否算碰撞。
初始重叠如何处理。
多个坐标轴的时间区间求交。
碰撞法线如何确定。
多个候选碰撞体如何选最早 TOI。

这些规则不能从这个最小示例直接外推。

形状扫掠

不同形状的连续检测难度不同。

常见问题包括：

点或射线对平面、球、盒。
球体扫掠其他形状。
胶囊体扫掠场景几何。
凸形状相对运动下的首次接触。

对于只做平移的简单形状，可能存在直接解析解。

对于更一般的凸形状，可以基于形状距离、Minkowski 差、保守推进等方法迭代逼近 TOI。旋转会让问题进一步复杂，因为接触特征和扫掠区域都随时间变化。

因此“开启 CCD”不等于所有形状、所有旋转和所有复合碰撞体都获得同样的连续保证。支持范围必须查具体系统的文档。

保守推进的直觉

保守推进不直接猜最终 TOI，而是反复执行：

1. 计算当前时刻两个形状的距离。
2. 根据接近速度估算一个不会跨过首次接触的时间增量。
3. 向前推进这个增量。
4. 距离足够小则报告接触；否则继续。

“保守”意味着尽量避免一步跨过碰撞时刻。

可交互的迭代状态

演示面板可以显示：

迭代	当前 t	形状距离	沿分离方向的接近速度	下一时间增量
0	起始	当前距离	当前估计	计算结果
1	更新后	新距离	新估计	计算结果
…	…	…	…	…

表中不应预设通用固定阈值。收敛容差和最大迭代次数属于具体实现的精度与成本策略。

还可以切换失败原因：

相对运动正在分离。
接近速度过小。
达到迭代预算仍未收敛。
运动或旋转模型超出算法假设。

Broad Phase 也要覆盖运动区间

即使 Narrow Phase 支持 TOI，如果 Broad Phase 只使用物体在起点的包围盒，也可能根本筛不到路径中间的障碍。

连续检测的候选范围常需要覆盖整个运动区间，例如：

起点包围盒与终点包围盒的并集。
能够包住扫掠轨迹的扩展包围体。
根据速度扩张的代理范围。

这种包围通常更宽，会产生更多候选对。因此 CCD 的成本不仅来自精确 TOI 计算，也来自 Broad Phase 候选增多。

找到 TOI 之后发生什么

检测到首次接触只是开始。

一个时间步可能变成：

推进到最早 TOI
    ↓
建立接触约束
    ↓
求解速度或位置响应
    ↓
处理剩余时间
    ↓
剩余运动中可能再次发生碰撞

多个物体几乎同时接触时，处理顺序、求解器迭代和数值容差都会影响结果。

CCD 不能单独保证：

完全没有抖动。
堆叠永远稳定。
碰撞响应符合玩法预期。
不会出现初始重叠。
任意复杂运动都得到精确解析解。

它主要降低“在两个离散采样之间漏掉首次接触”的风险。

适用边界

CCD 更值得用于：

单步位移相对自身尺寸或障碍厚度较大的物体。
漏检会造成明显错误的关键物体。
快速运动且碰撞形状适合系统连续检测能力的对象。

离散检测可能已经足够：

物体移动缓慢，单步位移远小于相关几何尺度。
碰撞结果不要求时间步内的首次接触精度。
对象数量很大，而全部启用连续检测的成本不可接受。

选择依据应是运动尺度、几何尺度、失败后果和性能预算，不应仅凭“某类对象通常很快”就统一开启。

常见替代与补充方法

减小时间步

更密集的离散采样能降低穿透概率，但会增加模拟成本，而且不构成对任意薄障碍的绝对保证。

射线或形状查询

对于逻辑上只关心“沿这一段是否命中”的对象，可以对位移做射线或形状查询。

但查询结果如何与物理状态、旋转、尺寸和多次碰撞结合，需要单独设计。射线也不能自动代表有体积物体的完整扫掠。

限制位移

限制单步运动距离可以控制离散误差，但会改变运动行为。限制值是行为参数，必须来自明确设计，而不是由 CCD 概念自动给出。

膨胀目标形状

点扫掠球体可转换为点相对“半径增加后的目标”进行检测，这是 Minkowski 和的常见直觉。

它依赖具体形状关系，不能把任意复杂形状都简化成随意增加一个固定半径。

正常、边界与失败情况

正常情况

运动模型满足算法假设。
Broad Phase 找到覆盖运动区间的候选。
TOI 位于当前时间步内。
推进到 TOI 后生成有效接触。
剩余时间得到继续处理。

边界情况

时间步开始时已经接触或重叠。
轨迹刚好擦过形状边缘。
相对速度为零。
物体正在远离而不是接近。
多个候选具有非常接近的 TOI。
运动位移接近浮点精度可分辨范围。
高速平移同时伴随明显旋转。

擦边是否算接触、初始重叠如何分类，都需要一致的容差和接触规则。

失败情况

Broad Phase 没有覆盖扫掠区域，候选被漏掉。
形状组合不受连续算法支持。
迭代求 TOI 未在预算内收敛。
只处理平移，却把高速旋转当作已被覆盖。
找到 TOI 后没有正确处理剩余时间。
碰撞响应再次把物体推到非法位置。

失败不应被伪装成“本帧没有碰撞”。调试信息至少应区分无碰撞、算法不支持和计算未收敛。

复杂度与代价

CCD 没有一个适用于所有形状的统一复杂度。

成本可拆为：

运动包围体带来的 Broad Phase 候选数量。
每个候选对的形状扫掠或距离查询成本。
迭代求 TOI 的次数。
碰撞后处理剩余时间产生的额外子步。
多个连续碰撞之间的求解成本。

若 Broad Phase 产生 C 个候选，每个候选平均进行 I 次迭代距离查询，单次形状距离查询成本记为 D，则仅用于理解成本构成的粗略表达是：

O(C × I × D)

它不是所有 CCD 算法的严格统一复杂度。解析扫掠可能不需要迭代，而复杂凸形状的 D 也取决于形状表示和距离算法。

常见权衡是：

更保守的运动包围 → 更少漏候选，但更多误报。
更小的收敛容差 → 更高时间精度，但可能需要更多迭代。
更多子步 → 更完整地处理连续接触，但模拟成本上升。
只对关键对象启用 → 控制成本，但必须明确哪些交互仍使用离散检测。

最重要的收获

离散检测只看采样时刻，因此可能漏掉两帧之间的接触。
CCD 检查运动区间，并尝试求首次碰撞时间 TOI。
扫掠检测既需要 Narrow Phase 求接触，也需要 Broad Phase 覆盖整段运动。
找到 TOI 不等于完成响应，还要处理接触和剩余时间。
形状、旋转、初始重叠与迭代预算决定 CCD 的适用边界。
CCD 应按运动尺度、漏检后果和性能预算选择，而不是无条件全开。
不支持或未收敛必须作为失败暴露，不能伪装成没有碰撞。