第1章 概述 1
1.1 内容概览 1
1.1.1 第2章：碰撞检测系统中的设计问题 2
1.1.2 第3章：数学和几何学入门 2
1.1.3 第4章：包围体 2
1.1.4 第5章：基本图元测试 2
1.1.5 第6章：层次包围体技术 2
1.1.6 第7章：空间划分 2
1.1.7 第8章：BSP树层次结构 3
1.1.8 第9章：凸体算法 3
1.1.9 第10章：基于GPU的碰撞检测 3
1.1.10 第11章：数值健壮性 3
1.1.11 第12章：几何健壮性 3
1.1.12 第13章：优化操作 3
1.2 关于本书的代码 4
第2章 碰撞检测系统中的设计问题 5
2.1 碰撞算法的设计因素 5
2.2 应用程序中对象的表达方式 5
2.2.1 对象的表达方式 6
2.2.2 碰撞与几何渲染 7
2.2.3 特定的碰撞检测算法 8
2.3 查询类型 9
2.4 环境模拟参数 9
2.4.1 物体对象的数量 9
2.4.2 顺序移动和同步移动 10
2.4.3 不连续移动与连续移动 11
2.5 性能 12
2.5.1 优化概览 12
2.6 健壮性 13
2.7 实现与使用的简洁性 13
2.7.1 碰撞检测系统的调试 14
2.8 小结 14
第3章 数学和几何学入门 15
3.1 矩阵 15
3.1.1 矩阵运算 16
3.1.2 矩阵的几何代数符号 17
3.1.3 行列式 17
3.1.4 利用克莱姆法则计算线性方程组 19
3.1.5 2×2矩阵和3×3矩阵的逆矩阵 20
3.1.6 行列式断言 21
3.2 坐标系统和顶点 23
3.3 向量 23
3.3.1 向量运算 24
3.3.2 向量的代数恒等式 25
3.3.3 点积 26
3.3.4 点积的代数恒等式 27
3.3.5 叉积 27
3.3.6 叉积的代数恒等式 29
3.3.7 标量三重积 29
3.3.8 标量三重积的代数恒等式 30
3.4 质心坐标 30
3.5 直线、光线和线段 35
3.6 平面和半空间 36
3.7 多边形 37
3.7.1 多边形凸性测试 39
3.8 多面体 41
3.8.1 凸体测试 43
3.9 凸包计算 43
3.9.1 Andrew算法 43
3.9.2 Quickhull算法 44
3.10 域 46
3.11 Minkowski和与Minkowski差 47
3.12 小结 48
第4章 包围体 49
4.1 BV期望特征 49
4.2 轴对齐包围盒 50
4.2.1 AABB间的相交测试 51
4.2.2 AABB的计算与更新 53
4.2.3 基于包围球的AABB 54
4.2.4 基于原点的AABB重构 54
4.2.5 利用爬山法构造AABB 55
4.2.6 旋转AABB后的重计算 56
4.3 Spheres球体 58
4.3.1 其他相交测试 58
4.3.2 计算包围球 58
4.3.3 最大离散方向上的包围球 60
4.3.4 采用迭代修正的包围球 66
4.3.5 最小包围球 66
4.4 方向包围盒 68
4.4.1 相交测试 68
4.4.2 健壮的分离轴测试 72
4.4.3 计算紧凑的OBB 72
4.4.4 基于PCA的OBB优化 74
4.4.5 蛮力法实现OBB的拟合 76
4.5 球扫掠体 76
4.5.1 球扫掠体的相交测试 77
4.5.2 球体扫掠体包围体的计算 78
4.6 半空间相交体 78
4.6.1 Kay-Kajiya平行平面空间包围体 79
4.6.2 离散有向多面体（k-DOP） 79
4.6.3 k-DOP—k-DOP相交测试 81
4.6.4 k-DOP的计算与重对齐 81
4.6.5 近似凸体相交测试 83
4.7 其他类型的包围体 83
4.8 小结 84
第5章 基本图元测试 85
5.1 最近点计算 85
5.1.1 点到面的最近点 85
5.1.2 点至线段的最近点 86
5.1.3 点至AABB的最近点 88
5.1.4 点至OBB的最近点 90
5.1.5 点至三角形的最近点 93
5.1.6 点到四面体的最近点 97
5.1.7 点到凸多面体的最近点 99
5.1.8 两条直线间的最近点 100
5.1.9 两线段上的最近点 101
5.1.10 线段和三角形最近点 105
5.1.11 两个三角形之间的最近点计算 106
5.2 图元测试 107
5.2.1 分离轴测试 107
5.2.2 球体与平面间的测试 110
5.2.3 盒体与平面间的测试 111
5.2.4 锥体与平面间的测试 113
5.2.5 球体与AABB之间的测试 113
5.2.6 球体与OBB之间的测试 114
5.2.7 球体与三角形之间的测试 115
5.2.8 球体与多边形之间的测试 115
5.2.9 AABB与三角形之间的测试 116
5.2.10 三角形之间的测试 119
5.3 直线、光线和有向线段的相交测试 120
5.3.1 线段与平面的相交测试 120
5.3.2 光线或线段与球体的相交测试 122
5.3.3 光线或线段与盒体的相交测试 123
5.3.4 直线与三角形之间的相交测试 127
5.3.5 直线与四边形之间的相交测试 130
5.3.6 光线或线段与三角形之间的相交测试 131
5.3.7 光线或线段与圆柱体之间的相交测试 135
5.3.8 光线或线段与凸多面体之间的相交测试 137
5.4 其他类型的测试 139
5.4.1 点与多边形之间的测试 139
5.4.2 点与三角形之间的测试 141
5.4.3 点与多面体之间的测试 143
5.4.4 两个平面间的相交测试 144
5.4.5 3个平面间的相交测试 146
5.5 动态相交测试 148
5.5.1 运动物体的区间半分法相交测试 149
5.5.2 运动凸体对象的分离轴测试 152
5.5.3 运动球体与平面间的相交测试 152
5.5.4 运动AABB与平面间的相交测试 154
5.5.5 运动球体与球体之间的相交测试 155
5.5.6 运动球体与三角形以及多边形之间的相交测试 157
5.5.7 运动球体与AABB之间的相交测试 158
5.5.8 运动AABB之间的测试 160
5.6 小结 162
第6章 层次包围体技术 163
6.1 层次结构设计问题 164
6.1.1 BVH的期望特征 164
6.1.2 性能函数 164
6.1.3 树的度数 165
6.2 层次结构的构建策略 165
6.2.1 自顶向下的构造方法 166
6.2.2 自底向上的构造方法 170
6.2.3 扩充（插入）构造策略 174
6.3 层次结构的遍历 176
6.3.1 下降规则 177
6.3.2 通用的启发式深度优先遍历 178
6.3.3 同步深度优先遍历 180
6.3.4 优化的有向叶节点深度优先遍历 181
6.4 包围体层次结构示例 182
6.4.1 OBB TreesOBB树 182
6.4.2 AABB树和盒体树 183
6.4.3 采用8叉树子划分的球体树 184
6.4.4 采用球体覆盖表面的球体树 184
6.4.5 生成－修剪球体覆盖 184
6.4.6 k-DOP树 185
6.5 合并包围体 186
6.5.1 合并两个AABB 186
6.5.2 合并两个球体 187
6.5.3 合并两个OBB 188
6.5.4 合并两个k-DOP 188
6.6 高效的树型表达方式及遍历 189
6.6.1 数组表达方式 189
6.6.2 前序遍历 190
6.6.3 采用偏移量而非指针 191
6.6.4 采用缓存友好的结构（非二叉树） 192
6.6.5 树节点和图元排序 192
6.6.6 递归遍历 193
6.6.7 分组查询 194
6.7 通过缓存机制改善查询 196
6.7.1 表面缓存：缓存相交图元 196
6.7.2 前界面追踪 198
6.8 小结 199
第7章 空间划分 200
7.1 均匀网格 200
7.1.1 网格单元的尺寸 200
7.1.2 采用链表数组表示的网格 201
7.1.3 哈希存储与无限网格 202
7.1.4 静态数据存储 204
7.1.5 隐式网格 204
7.1.6 使用均匀网格的对象间的测试 207
7.1.7 网格的其他注意事项 210
7.2 层次网格 211
7.2.1 基本的层次网格实现方式 212
7.2.2 其他类型的层次网格表达方式 216
7.2.3 其他层次网格 216
7.3 树 217
7.3.1 8叉树（以及4叉树） 217
7.3.2 8叉树对象的分配 218
7.3.3 位置码和8分体的定位 221
7.3.4 基于哈希存储的线性树 222
7.3.5 计算Morton键 223
7.3.6 松散8叉树 224
7.3.7 k-d树 225
7.3.8 混合方案 227
7.4 光线和有向线段的遍历 228
7.4.1 k-d树相交测试 228
7.4.2 均匀网格的相交测试 229
7.5 排序扫掠算法 233
7.5.1 排序链表实现方案 234
7.5.2 基于数组的排序 238
7.6 网格单元和伪入口 240
7.7 避免重复测试 242
7.7.1 位标志 242
7.7.2 时间戳 243
7.7.3 分时清除时间戳 244
7.8 小结 246
第8章 BSP树层次结构 248
8.1 BSP树 248
8.2 BSP树的类型 249
8.2.1 采用节点存储的BSP树 249
8.2.2 采用叶节点存储的BSP树 251
8.2.3 实体叶节点BSP树 251
8.3 构造BSP树 252
8.3.1 分割面的选择 254
8.3.2 分割面的评估 256
8.3.3 基于分割面的多边形分类 258
8.3.4 多边形分割计算 260
8.3.5 更多讨论 264
8.3.6 BSP树的性能调试 265
8.4 BSP树的应用 266
8.4.1 点与实体叶节点BSP树间的测试 266
8.4.2 光线与实体叶节点BSP树间的相交测试 267
8.4.3 基于实体叶节点BSP树的多面体查询 269
8.5 小结 272
第9章 凸体算法 273
9.1 基于边界的碰撞检测 273
9.2 最近特征算法 274
9.2.1 V-Clip算法 274
9.3 层次多面体表达形式 276
9.3.1 Dobkin-Kirkpatrick层次结构 277
9.4 线性规划和二次规划 278
9.4.1 线性规划 279
9.4.2 二次规划 283
9.5 Gilbert-Johnson-Keerthi算法 284
9.5.1 算法概述 284
9.5.2 计算单形体内的最小范数顶点 286
9.5.3 GJK算法、最近点以及接触流形 287
9.5.4 利用爬山法计算极值顶点 288
9.5.5 与顶点缓存相关的一致性问题 289
9.5.6 旋转对象的优化 290
9.5.7 移动对象的GJK算法 290
9.6 Chung-Wang分离向量算法 291
9.7 小结 292
第10章 基于GPU的碰撞检测 294
10.1 GPU接口 294
10.1.1 缓冲区读取 295
10.1.2 遮挡查询 295
10.2 凸体对象间的测试 296
10.3 测试凹体对象 298
10.4 基于GPU的碰撞过滤 301
10.5 小结 303
第11章 数值健壮性 304
11.1 健壮性问题的分类 304
11.2 实数表示法 305
11.2.1 IEEE-754浮点格式 307
11.2.2 无穷运算 309
11.2.3 浮点误差源 311
11.3 健壮的浮点数用法 313
11.3.1 浮点值的误差容值比较 313
11.3.2 采用厚平面实现算法的健壮性 315
11.3.3 采用共享计算实现算法的健壮性 316
11.3.4 厚对象的健壮性 318
11.4 区间计算 319
11.4.1 区间计算实例 319
11.4.2 碰撞检测中的区间计算 320
11.5 精确计算和近似计算 321
11.5.1 采用整型数据实现精确计算 321
11.5.2 整型除法 324
11.5.3 采用整型运算处理线段相交问题 325
11.6 提高数值健壮性的进一步讨论 327
11.7 小结 328
第12章 几何健壮性 329
12.1 顶点焊接 330
12.2 计算邻接信息 335
12.2.1 计算顶点－面表 338
12.2.2 计算边－面表 339
12.2.3 连通性测试 341
12.3 孔、缝隙、间隙以及t－连接 343
12.4 共面数据面的合并操作 345
12.4.1 测试多边形的共面性 346
12.4.2 多边形的共面测试 347
12.5 三角形剖分和凸划分 350
12.5.1 耳式剪裁实现三角剖分 350
12.5.2 多边形的凸剖分 353
12.5.3 多面体的凸剖分 355
12.5.4 不可剖分的凹几何体 357
12.6 采用欧拉公式的一致性测试 358
12.7 小结 360
第13章 优化操作 361
13.1 CPU缓存 362
13.2 指令缓存优化 363
13.3 数据缓存优化 365
13.3.1 结构优化 366
13.3.2 顶点数据的量化操作和压缩操作 369
13.3.3 预取和预载操作 369
13.4 基于缓存感知的数据结构和算法 371
13.4.1 紧凑型静态k-d树 371
13.4.2 紧凑型AABB树 374
13.4.3 缓存参数无关性 375
13.5 软件缓存 376
13.5.1 缓存线性化操作实例 376
13.5.2 基于分摊机制的预测线性化缓存 379
13.6 数据别名 380
13.6.1 基于类型的别名分析 381
13.6.2 restrict指针 382
13.6.3 避免别名问题 384
13.7 采用SIMD优化的并行操作 385
13.7.1 4球体－4球体SIMD测试 386
13.7.2 4球体－4AABB SIMD测试 386
13.7.3 4AABB-4AABB SIMD测试 387
13.8 分支结构 388
13.9 小结 390
参考文献 392