实时碰撞检测算法技术

第1章 概述

1.1 内容概览

1.1.1 第2章 ：碰撞检测系统中的设计问题

1.1.2 第3章 ：数学和几何学入门

1.1.3 第4章 ：包围体

1.1.4 第5章 ：基本图元测试

1.1.5 第6章 ：层次包围体技术

1.1.6 第7章 ：空间划分

1.1.7 第8章 ：BSP树层次结构

1.1.8 第9章 ：凸体算法

1.1.9 第10章 ：基于GPU的碰撞检测

1.1.10 第11章 ：数值健壮性

1.1.11 第12章 ：几何健壮性

1.1.12 第13章 ：优化操作

1.2 关于本书的代码

第2章 碰撞检测系统中的设计问题

2.1 碰撞算法的设计因素

2.2 应用程序中对象的表达方式

2.2.1 对象的表达方式

2.2.2 碰撞与几何渲染

2.2.3 特定的碰撞检测算法

2.3 查询类型

2.4 环境模拟参数

2.4.1 物体对象的数量

2.4.2 顺序移动和同步移动

2.4.3 不连续移动与连续移动

2.5 性能

2.5.1 优化概览

2.6 健壮性

2.7 实现与使用的简洁性

2.7.1 碰撞检测系统的调试

2.8 小结

第3章 数学和几何学入门

3.1 矩阵

3.1.1 矩阵运算

3.1.2 矩阵的几何代数符号

3.1.3 行列式

3.1.4 利用克莱姆法则计算线性方程组

3.1.5 2x2矩阵和3x3矩阵的逆矩阵

3.1.6 行列式断言

3.2 坐标系统和顶点

3.3 向量

3.3.1 向量运算

3.3.2 向量的代数恒等式

3.3.3 点积

3.3.4 点积的代数恒等式

3.3.5 叉积

3.3.6 叉积的代数恒等式

3.3.7 标量三重积

3.3.8 标量三重积的代数恒等式

3.4 质心坐标

3.5 直线、光线和线段

3.6 平面和半空间

3.7 多边形

3.7.1 多边形凸性测试

3.8 多面体

3.8.1 凸体测试

3.9 凸包计算

3.9.1 Andrew算法

3.9.2 Quickhull算法

3.10 域

3.11 Minkowski和与MinkowSki差

3.12 小结

第4章 包围体

4.1 BV期望特征

4.2 轴对齐包围盒

4.2.1 AABB间的相交测试

4.2.2 AABB的计算与更新

4.2.3 基于包围球的AABB

4.2.4 基于原点的.AABB重构

4.2.5 利用爬山法构造AABB

4.2.6 旋转AABB后的重计算

4.3 SPlleres球体

4.3.1 其他相交测试

4.3.2 计算包围球

4.3.3 最大离散方向上的包围球

4.3.4 采用迭代修正的包围球

4.3.5 最小包围球

4.4 方向包围盒

4.4.1 相交测试

4.4.2 健壮的分离轴测试

4.4.3 计算紧凑的OBB

4.4.4 基于PCA的OBB优化

4.4.5 蛮力法实现OBB的拟合

4.5 球扫掠体

4.5.1 球扫掠体的相交测试

4.5.2 球体扫掠体包围体的计算

4.6 半空间相交体

4.6.1 Kay.Kajiya平行平面空间包围体

4.6.2 离散有向多面体（k.DOP）

4.6.3 k.DOP-k.DOP相交测试

4.6.4 k.DOP的计算与重对齐

4.6.5 近似凸体相交测试

4.7 其他类型的包围体

4.8 小结

第5章 基本图元测试

5.1 最近点计算

5.1.1 点到面的最近点

5.1.2 点至线段的最近点

5.1.3 点至AABB的最近点

5.1.4 点至OBB的最近点

5.1.5 点至三角形的最近点

5.1.6 点到四面体的最近点

5.1.7 点到凸多面体的最近点

5.1.8 两条直线间的最近点

5.1.9 两线段上的最近点

5.1.10 线段和三角形最近点

5.1.11 两个三角形之间的最近点计算

5.2 图元测试

5.2.1 分离轴测试

5.2.2 球体与平面间的测试

5.2.3 盒体与平面间的测试

5.2.4 锥体与平面间的测试

5.2.5 球体与AABB之间的测试

5.2.6 球体与OBB之间的测试

5.2.7 球体与三角形之间的测试

5.2.8 球体与多边形之间的测试

5.2.9 AABB与三角形之间的测试

5.2.10 三角形之间的测试

5.3 直线、光线和有向线段的相交测试

5.3.1 线段与平面的相交测试

5.3.2 光线或线段与球体的相交测试

5.3.3 光线或线段与盒体的相交测试

5.3.4 直线与三角形之间的相交测试

5.3.5 直线与四边形之间的相交测试

5.3.6 光线或线段与三角形之间的相交测试

5.3.7 光线或线段与圆柱体之间的相交测试

5.3.8 光线或线段与凸多面体之间的相交测试

5.4 其他类型的测试

5.4.1 点与多边形之间的测试

5.4.2 点与三角形之间的测试

5.4.3 点与多面体之间的测试

5.4.4 两个平面间的相交测试

5.4.5 3个平面间的相交测试

5.5 动态相交测试

5.5.1 运动物体的区间半分法相交测试

5.5.2 运动凸体对象的分离轴测试

5.5.3 运动球体与平面间的相交测试

5.5.4 运动AABB与平面间的相交测试

5.5.5 运动球体与球体之间的相交测试

5.5.6 运动球体与三角形以及多边形之间的相交测试

5.5.7 运动球体与AABB之间的相交测试

5.5.8 运动AABB之间的测试

5.6 小结

第6章 层次包围体技术

6.1 层次结构设计问题

6.1.1.BVH的期望特征

6.1.2 性能函数

6.1.3 树的度数

6.2 层次结构的构建策略

6.2.1 自顶向下的构造方法

6.2.2 自底向上的构造方法

6.2.3 扩充（插入）构造策略

6.3 层次结构的遍历

6.3.1 下降规则

6.3.2 通用的启发式深度优先遍历

6.3.3 同步深度优先遍历

6.3.4 优化的有向叶节点深度优先遍历

6.4 包围体层次结构示例

6.4.1 OBBTreesOBB树

6.4.2 AABB树和盒体树

6.4.3 采用8叉树子划分的球体树

6.4.4 采用球体覆盖表面的球体树

6.4.5 生成.修剪球体覆盖

6.4.6 k.DOP树

6.5 合并包围体

6.5.1 合并两个AABB

6.5.2 合并两个球体

6.5 13合并两个OBB

6.5.4 合并两个k.DOP

6.6 高效的树型表达方式及遍历

6.6.1 数组表达方式

6.6.2 前序遍历

6.6 13采用偏移量而非指针

6.6.4 采用缓存友好的结构（非二叉树）

6.6.5 树节点和图元排序

6.6.6 递归遍历

6.6.7 分组查询

6.7 通过缓存机制改善查询

6.7.1 表面缓存：缓存相交图元

6.7.2 前界面追踪

6.8 小结

第7章 空间划分

7.1 均匀网格

7.1.1 网格单元的尺寸

7.1.2 采用链表数组表示的网格

7.1.3 哈希存储与无限网格

7.1.4 静态数据存储

7.1.5 隐式网格

7.1.6 使用均匀网格的对象间的测试

7.1.7 网格的其他注意事项

7.2 层次网格

7.2.1 基本的层次网格实现方式

7.2.2 其他类型的层次网格表达方式

7.2.3 其他层次网格

7.3 树

7.3.1 8叉树（以及4叉树）

7.3.2 8叉树对象的分配

7.3.3 位置码和8分体的定位

7.3.4 基于哈希存储的线性树

7.3.5 计算Morton键

7.3.6 松散8叉树

7.3.7 缸d树

7.3.8 混合方案

7.4 光线和有向线段的遍历

7.4.1 缸d树相交测试

7.4.2 均匀网格的相交测试

7.5 排序扫掠算法

7.5.1 排序链表实现方案

7.5.2 基于数组的排序

7.6 网格单元和伪入口

7.7 避免重复测试

7.7.1 位标志

7.7.2 时间戳

7.7.3 分时清除时间戳

7.8 小结

第8章 BSP树层次结构

8.1 BSP树

8.2 BSP树的类型

8.2.1 采用节点存储的BSP树

8.2.2 采用叶节点存储的BSP树

8.2.3 实体叶节点BSP树

8.3 构造BSP树

8.3.1 分割面的选择

8.3.2 分割面的评估

8.3.3 基于分割面的多边形分类

8.3.4 多边形分割计算

8.3.5 更多讨论

8.3.6 BSP树的性能调试

8.4 BSP树的应用

8.4.1 点与实体叶节点：BSP树间的测试

8.4.2 光线与实体叶节点BSP树间的相交测试

8.4.3 基于实体叶节点BSP树的多面体查询

8.5 小结

第9章 凸体算法

9.1 基于边界的碰撞检测

9.2 最近特征算法

9.2.1 v.Clip算法

9.3 层次多面体表达形式

9.3.1 Dobkin.Kirkpatrick层次结构

9.4 线性规划和二次规划

9.4.1 线性规划

9.4.2 二次规划

9.5 Gilbert.Johnson.Keerthi算法

9.5.1 算法概述

9.5.2 计算单形体内的最小范数顶点，

9.5.3 GJK算法、最近点以及接触流形

9.5.4 利用爬山法计算极值顶点

9.5.5 与顶点缓存相关的一致性问题

9.5.6 旋转对象的优化

9.5.7 移动对象的GJK算法

9.6 chung.wang分离向量算法

9.7 小结

第10章 基于GPU的碰撞检测

10.1 GPU接口

10.1.1 缓冲区读取

10.1.2 遮挡查询

10.2 凸体对象间的测试

10.3 测试凹体对象

10.4 基于GPU的碰撞过滤

10.5 小结

第11章 数值健壮性

11.1 健壮性问题的分类

11.2 实数表示法

11.2.1 IEEE.7 54浮点格式

11.2.2 无穷运算

11.2.3 浮点误差源

11.3 健壮的浮点数用法

11.3.1 浮点值的误差容值比较

11.3.2 采用厚平面实现算法的健壮性

11.3.3 采用共享计算实现算法的健壮性

11.3.4 厚对象的健壮性

11.4 区间计算

11.4.1 区间计算实例

11.4.2 碰撞检测中的区间计算

11.5 精确计算和近似计算

11.5.1 采用整型数据实现精确计算

11.5.2 整型除法

11.5 13采用整型运算处理线段相交问题

11.6 提高数值健壮性的进一步讨论

11.7 小结

第12章 几何健壮性

12.1 顶点焊接

12.2 计算邻接信息

12.2.1 计算顶点.面表

12.2.2 计算边.面表

12.2.3 连通性测试

12.3 孔、缝隙、间隙以及t.连接

12.4 共面数据面的合并操作

12.4.1 测试多边形的共面性

12.4.2 多边形的共面测试

12.5 三角形剖分和凸划分

12.5.1 耳式剪裁实现三角剖分

12.5.2 多边形的凸剖分

12.5.3 多面体的凸剖分

12.5.4 不可剖分的凹几何体

12.6 采用欧拉公式的一致性测试

12.7 小结

第13章 优化操作

13.1 CPU缓存

13.2 指令缓存优化

13.3 数据缓存优化

13.3.1 结构优化

13.3.2 顶点数据的量化操作和压缩操作

13.3.3 预取和预载操作

13.4 基于缓存感知的数据结构和算法

13.4.1 紧凑型静态k-d树

13.4.2 紧凑型AABB树

13.4.3 缓存参数无关性

13.5 软件缓存

13.5.1 缓存线性化操作实例

13.5.2 基于分摊机制的预测线性化缓存

13.6 数据别名

13.6.1 基于类型的别名分析

13.6.2 restrict指针：

13.6.3 避免别名问题

13.7 采用SIMD优化的并行操作

13.7.1 4球体.4 球体SIMD测试

13.7.2 4球体.4 AABBSIMD测试

13.7.3 4AABB.4 AABBSIMD测试

13.8 分支结构

13.9 小结

参考文献

《实时碰撞检测算法技术》详细阐述了与碰撞检测问题相关的高效解决方案及相应的数据结构和算法，主要包括：碰撞检测系统中的设计问题、数学和几何学入门、包围体、基本图元测试、层次包围体技术、空间划分、BSP树层次结构、凸体算法、基于GPU的碰撞检测、数值健壮性、几何健壮性以及优化操作。另外，《实时碰撞检测算法技术》还提供了相应的算法、代码以及伪代码，以帮助读者进一步理解计算方案的实现过程。 　　《实时碰撞检测算法技术》适合作为高等院校计算机及相关专业的教材和教学参考书，也可作为相关开发人员的自学教材和参考手册。