实时碰撞检测算法技术【2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载】

实时碰撞检测算法技术PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第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　基于包围球的AABB54

4.2.4　基于原点的AABB重构54

4.2.5　利用爬山法构造AABB55

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　计算紧凑的OBB72

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 合并两个AABB186

6.5.2　合并两个球体187

6.5.3 合并两个OBB188

6.5.4　合并两个k-DOP188

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