《实时碰撞检测算法技术》权威学习地图

学习地图把几何谓词、包围体、空间结构、精确查询、鲁棒性与优化串成一条工业级碰撞管线。逐项覆盖15个权威目录坐标，并用退化几何、误差边界和目标机轨迹复核。

为什么碰撞检测必须从查询合同开始

学习地图把几何谓词、包围体、空间结构、精确查询、鲁棒性与优化串成一条工业级碰撞管线。本课程不复制原书正文、插图或配套代码，而把公开目录中的算法组织成输入合同、几何谓词、交互实验、退化样本和验收证据。本页逐项覆盖15个目录坐标：前置资料：版本、作者、图表与前言、Chapter 1 Introduction、Chapter 2 Collision Detection Design Issues、Chapter 3 A Math and Geometry Primer、Chapter 4 Bounding Volumes、Chapter 5 Basic Primitive Tests、Chapter 6 Bounding Volume Hierarchies、Chapter 7 Spatial Partitioning、Chapter 8 BSP Tree Hierarchies、Chapter 9 Convexity-based Methods、Chapter 10 GPU-assisted Collision Detection、Chapter 11 Numerical Robustness、Chapter 12 Geometrical Robustness、Chapter 13 Optimization、后置资料：参考文献、索引与配套光盘。

实时碰撞检测不是“两个盒子是否相交”的单一布尔问题。上层可能需要最近距离、命中顺序、首次接触时间、穿透方向或稳定接触流形；下层又受到坐标尺度、浮点误差、非流形网格、缓存布局和候选对规模约束。只有先冻结查询类型、输入域、边界包含规则和失败状态，才能比较算法是否正确且足够快。

版次、目录与改编合同

本路径同时固定原版与中译本：Christer Ericson《Real-Time Collision Detection》，Morgan Kaufmann，2005，ISBN 9781558607323；刘天慧译《实时碰撞检测算法技术》，清华大学出版社，2010年6月，ISBN 9787302224112。O’Reilly授权电子书目录与Morgan Kaufmann原书目录预览列出前置资料、13章所有层级小节，以及参考文献、索引和光盘说明，共357个正式目录节点。课程按15个正式单元逐项覆盖，另设学习地图与全书复核，共17页。

原书代码与GPU接口来自2004至2005年前后的硬件和编译器语境。课程保留几何证明、数据结构和优化推理，但接口、SIMD宽度与GPU同步必须在当前目标平台重新测量；旧代码的运行结果不能替代今天的鲁棒性证据。

五个贯穿全书的术语

、、、、。

查询合同决定算法；候选对连接粗筛与精算；几何谓词决定拓扑分类；首次接触时间避免高速穿透；碰撞证据包则让退化场景可以回放。类名和成功截图都不能代替这些状态合同。

四个可复算模型

点到线段的参数投影与钳制为：

t=operatorname{clamp}left( rac{(p-a)cdot(b-a)}{lVert b-a Vert^2},0,1 ight),qquad q=a+t(b-a)

两个AABB在每个轴都重叠时才相交：

A_{min}^{i}le B_{max}^{i};land;B_{min}^{i}le A_{max}^{i},qquad iin{x,y,z}

BVH构建和遍历可用表面积启发式比较：

C=C_t+ rac{S_L}{S_P}N_LC_i+ rac{S_R}{S_P}N_RC_i

浮点比较的容差同时包含绝对项与相对项：

|a-b|le arepsilon_{abs}+ arepsilon_{rel}max(|a|,|b|)

最近点必须处理零长度线段；AABB边界要明确相切是否算碰撞；SAH只是查询分布近似；容差不能脱离几何尺度。每项公式都要通过一般、退化和极端尺度样本复算。

分步可视化：结构、规模与故障

前置资料：版本、作者、图表与前言

目录节点 1/15。 “前置资料：版本、作者、图表与前言”位于“定义查询合同 → 建立几何内核 → 生成候选对 → 执行精确查询 → 复核鲁棒性能”链路中；实现时必须声明输入域、退化情况、误差界、输出状态与复杂度。

实现“前置资料：版本、作者、图表与前言”时，沿“定义查询合同 → 建立几何内核 → 生成候选对 → 执行精确查询 → 复核鲁棒性能”写出输入几何、坐标空间、参数区间、所有权和返回状态，并把查询合同变成可观测字段。至少覆盖一般位置、相切/共面、零尺寸、极端尺度和高速运动，任何提前退出都要能说明所依据的保守界。

验收必须保存固定种子、原始几何、归一化尺度、中间谓词、误差界、迭代次数和最终接触。若不同优化路径给出不同分类，先定位第一处分支差异，再判断是数值误差、几何缺陷、缓存失效还是算法适用域被破坏。

Chapter 1 Introduction

目录节点 2/15。 学习地图把几何谓词、包围体、空间结构、精确查询、鲁棒性与优化串成一条工业级碰撞管线。

实现“Chapter 1 Introduction”时，沿“定义查询合同 → 建立几何内核 → 生成候选对 → 执行精确查询 → 复核鲁棒性能”写出输入几何、坐标空间、参数区间、所有权和返回状态，并把几何内核变成可观测字段。至少覆盖一般位置、相切/共面、零尺寸、极端尺度和高速运动，任何提前退出都要能说明所依据的保守界。

Chapter 2 Collision Detection Design Issues

目录节点 3/15。 学习地图把几何谓词、包围体、空间结构、精确查询、鲁棒性与优化串成一条工业级碰撞管线。

实现“Chapter 2 Collision Detection Design Issues”时，沿“定义查询合同 → 建立几何内核 → 生成候选对 → 执行精确查询 → 复核鲁棒性能”写出输入几何、坐标空间、参数区间、所有权和返回状态，并把候选对变成可观测字段。至少覆盖一般位置、相切/共面、零尺寸、极端尺度和高速运动，任何提前退出都要能说明所依据的保守界。

Chapter 3 A Math and Geometry Primer

目录节点 4/15。 学习地图把几何谓词、包围体、空间结构、精确查询、鲁棒性与优化串成一条工业级碰撞管线。

实现“Chapter 3 A Math and Geometry Primer”时，沿“定义查询合同 → 建立几何内核 → 生成候选对 → 执行精确查询 → 复核鲁棒性能”写出输入几何、坐标空间、参数区间、所有权和返回状态，并把精确查询变成可观测字段。至少覆盖一般位置、相切/共面、零尺寸、极端尺度和高速运动，任何提前退出都要能说明所依据的保守界。

Chapter 4 Bounding Volumes

目录节点 5/15。 学习地图把几何谓词、包围体、空间结构、精确查询、鲁棒性与优化串成一条工业级碰撞管线。

实现“Chapter 4 Bounding Volumes”时，沿“定义查询合同 → 建立几何内核 → 生成候选对 → 执行精确查询 → 复核鲁棒性能”写出输入几何、坐标空间、参数区间、所有权和返回状态，并把鲁棒性能变成可观测字段。至少覆盖一般位置、相切/共面、零尺寸、极端尺度和高速运动，任何提前退出都要能说明所依据的保守界。

Chapter 5 Basic Primitive Tests

目录节点 6/15。 学习地图把几何谓词、包围体、空间结构、精确查询、鲁棒性与优化串成一条工业级碰撞管线。

实现“Chapter 5 Basic Primitive Tests”时，沿“定义查询合同 → 建立几何内核 → 生成候选对 → 执行精确查询 → 复核鲁棒性能”写出输入几何、坐标空间、参数区间、所有权和返回状态，并把查询合同变成可观测字段。至少覆盖一般位置、相切/共面、零尺寸、极端尺度和高速运动，任何提前退出都要能说明所依据的保守界。

Chapter 6 Bounding Volume Hierarchies

目录节点 7/15。 学习地图把几何谓词、包围体、空间结构、精确查询、鲁棒性与优化串成一条工业级碰撞管线。

实现“Chapter 6 Bounding Volume Hierarchies”时，沿“定义查询合同 → 建立几何内核 → 生成候选对 → 执行精确查询 → 复核鲁棒性能”写出输入几何、坐标空间、参数区间、所有权和返回状态，并把几何内核变成可观测字段。至少覆盖一般位置、相切/共面、零尺寸、极端尺度和高速运动，任何提前退出都要能说明所依据的保守界。

Chapter 7 Spatial Partitioning

目录节点 8/15。 自顶向下构建按轴和分割点划分图元，需控制空子树、深度与表面积代价。

实现“Chapter 7 Spatial Partitioning”时，沿“定义查询合同 → 建立几何内核 → 生成候选对 → 执行精确查询 → 复核鲁棒性能”写出输入几何、坐标空间、参数区间、所有权和返回状态，并把候选对变成可观测字段。至少覆盖一般位置、相切/共面、零尺寸、极端尺度和高速运动，任何提前退出都要能说明所依据的保守界。

Chapter 8 BSP Tree Hierarchies

目录节点 9/15。 学习地图把几何谓词、包围体、空间结构、精确查询、鲁棒性与优化串成一条工业级碰撞管线。

实现“Chapter 8 BSP Tree Hierarchies”时，沿“定义查询合同 → 建立几何内核 → 生成候选对 → 执行精确查询 → 复核鲁棒性能”写出输入几何、坐标空间、参数区间、所有权和返回状态，并把精确查询变成可观测字段。至少覆盖一般位置、相切/共面、零尺寸、极端尺度和高速运动，任何提前退出都要能说明所依据的保守界。

Chapter 9 Convexity-based Methods

目录节点 10/15。 凸性允许用半空间和支持点简化查询；非凸几何通常先分解或交给层次结构。

实现“Chapter 9 Convexity-based Methods”时，沿“定义查询合同 → 建立几何内核 → 生成候选对 → 执行精确查询 → 复核鲁棒性能”写出输入几何、坐标空间、参数区间、所有权和返回状态，并把鲁棒性能变成可观测字段。至少覆盖一般位置、相切/共面、零尺寸、极端尺度和高速运动，任何提前退出都要能说明所依据的保守界。

Chapter 10 GPU-assisted Collision Detection

目录节点 11/15。 GPU批量测试只有在候选规模足够且避免同步读回时才获益，评估必须包含提交、延迟和结果压缩。

实现“Chapter 10 GPU-assisted Collision Detection”时，沿“定义查询合同 → 建立几何内核 → 生成候选对 → 执行精确查询 → 复核鲁棒性能”写出输入几何、坐标空间、参数区间、所有权和返回状态，并把查询合同变成可观测字段。至少覆盖一般位置、相切/共面、零尺寸、极端尺度和高速运动，任何提前退出都要能说明所依据的保守界。

Chapter 11 Numerical Robustness

目录节点 12/15。 鲁棒性由退化几何、尺度、误差边界和一致分类共同决定；调试记录必须能定位第一个谓词分歧。

实现“Chapter 11 Numerical Robustness”时，沿“定义查询合同 → 建立几何内核 → 生成候选对 → 执行精确查询 → 复核鲁棒性能”写出输入几何、坐标空间、参数区间、所有权和返回状态，并把几何内核变成可观测字段。至少覆盖一般位置、相切/共面、零尺寸、极端尺度和高速运动，任何提前退出都要能说明所依据的保守界。

Chapter 12 Geometrical Robustness

目录节点 13/15。 鲁棒性由退化几何、尺度、误差边界和一致分类共同决定；调试记录必须能定位第一个谓词分歧。

实现“Chapter 12 Geometrical Robustness”时，沿“定义查询合同 → 建立几何内核 → 生成候选对 → 执行精确查询 → 复核鲁棒性能”写出输入几何、坐标空间、参数区间、所有权和返回状态，并把候选对变成可观测字段。至少覆盖一般位置、相切/共面、零尺寸、极端尺度和高速运动，任何提前退出都要能说明所依据的保守界。

Chapter 13 Optimization

目录节点 14/15。 学习地图把几何谓词、包围体、空间结构、精确查询、鲁棒性与优化串成一条工业级碰撞管线。

实现“Chapter 13 Optimization”时，沿“定义查询合同 → 建立几何内核 → 生成候选对 → 执行精确查询 → 复核鲁棒性能”写出输入几何、坐标空间、参数区间、所有权和返回状态，并把精确查询变成可观测字段。至少覆盖一般位置、相切/共面、零尺寸、极端尺度和高速运动，任何提前退出都要能说明所依据的保守界。

后置资料：参考文献、索引与配套光盘

目录节点 15/15。 “后置资料：参考文献、索引与配套光盘”位于“定义查询合同 → 建立几何内核 → 生成候选对 → 执行精确查询 → 复核鲁棒性能”链路中；实现时必须声明输入域、退化情况、误差界、输出状态与复杂度。

实现“后置资料：参考文献、索引与配套光盘”时，沿“定义查询合同 → 建立几何内核 → 生成候选对 → 执行精确查询 → 复核鲁棒性能”写出输入几何、坐标空间、参数区间、所有权和返回状态，并把鲁棒性能变成可观测字段。至少覆盖一般位置、相切/共面、零尺寸、极端尺度和高速运动，任何提前退出都要能说明所依据的保守界。

可迁移实现骨架

返回值要携带分类、距离/时间、特征和诊断，不要让布尔值吞掉退化状态。

struct CollisionResult {
  enum class State { Separated, Touching, Penetrating, Degenerate } state;
  double distance;
  double toi;
  Vec3 point_a, point_b, normal;
  uint32_t iterations;
  double error_bound;
};

碰撞管线从稳定候选开始，精确查询可按类型分派，但所有实现共享同一边界语义。

freeze transforms and geometry generations
  -> update conservative bounding volumes
  -> generate and deduplicate candidate pairs
  -> run exact static or continuous query
  -> record predicates, error bounds and first-contact state

机器可读证据让同一退化样本跨编译器、标量精度和优化版本比较。

{
  "seed": 7319,
  "scale": 1000.0,
  "query": "closest|overlap|ray|toi",
  "expected": "touching",
  "observed": "touching",
  "errorBound": 1.2e-8
}

本单元的验收工件

第一件工件是查询合同：为“定义查询合同 → 建立几何内核 → 生成候选对 → 执行精确查询 → 复核鲁棒性能”逐步写出输入域、坐标空间、边界包含、误差界、复杂度和返回状态。第二件是退化语料库：覆盖零长度、共线、共面、相切、近并行、巨大/微小尺度和高速跨越。第三件是目标机轨迹：记录对象数、候选对、节点访问、图元测试、迭代、缓存未命中和P50/P95/P99。第四件是差分报告：用高精度或独立实现作参照，定位第一处分歧而不是只统计最终错误率。

先预测再运行

运行交互前先预测：对象规模翻倍时候选对、节点访问还是精确测试先增长；几何接近共面时哪一个谓词先进入不确定区；SIMD宽度增加后数据整理和尾处理是否抵消收益。观察不一致时先检查查询合同、尺度归一、缓存代际和统计口径。

本章回顾

《实时碰撞检测算法技术》权威学习地图是“定义查询合同 → 建立几何内核 → 生成候选对 → 执行精确查询 → 复核鲁棒性能”中的完整算法合同。掌握本页意味着能逐项定位15个权威目录节点，解释查询合同、几何内核、候选对、精确查询、鲁棒性能的边界，复算几何与复杂度指标，并让一般、退化、压力和故障轨迹可重现。