计算机图形学几何工具算法详解PDF电子书下载

第1章　绪论 1

1.1　如何使用本书 1

1.2　关于数值计算的若干问题 1

1.2.1　低层问题 2

1.2.2　高层问题 3

1.3　各章内容概要 4

第2章　矩阵和线性系统 6

2.1 导言 6

2.1.1　动机 6

2.1.2　组织 9

2.1.3　符号约定 10

2.2 多元组 10

2.2.1　定义 10

2.2.2　算术运算 11

2.3 矩阵 11

2.3.1 符号与术语 12

2.3.2　转置 12

2.3.3　算术运算 13

2.3.4　矩阵乘法 14

2.4.1　线性方程 17

2.4　线性系统 17

2.4.2　两个未知数的线性系统 19

2.4.3 一般线性系统 20

2.4.4　减行、阶梯形和秩 21

2.5 方阵 22

2.5.1 对角矩阵 23

2.5.2　三角形矩阵 23

2.5.3　行列式 24

2.5.4　逆矩阵 26

2.6　线性空间 28

2.6.2　定义和性质 29

2.6.1　数域 29

2.6.3 子空间 30

2.6.4　线性组合和生成空间 30

2.6.5　线性无关、维数和基底 31

2.7　线性映射 32

2.7.1　映射基础 32

2.7.2　线性映射 34

2.7.3　线性映射的矩阵表示 35

2.7.4　克莱姆定理 35

2.8　特征值和特征向量 37

2.9.1　内积空间 38

2.9　欧几里得空间 38

2.9.2　正交和标准正交集 39

2.10　最小二乘法 40

2.11 推荐的阅读材料 43

第3章　向量代数 44

3.1 向量基础 44

3.1.1 向量等价 44

3.1.2 向量加法 45

3.1.4　向量数乘 46

3.1.3　向量减法 46

3.1.5 向量加法和数乘的性质 47

3.2 向量空间 48

3.2.1 生成空间 49

3.2.2　线性无关 49

3.2.3　基底、子空间和维数 49

3.2.4　方向 51

3.2.5　基底变化 52

3.2.6　线性变换 53

3.3　仿射空间 56

3.3.1 欧几里得几何 59

3.3.2　体积、行列式和数量三重积 66

3.3.3　坐标系 67

3.4　仿射变换 69

3.4.1 仿射映射的类型 72

3.4.2　仿射映射的合成 72

3.5　重心坐标和单形 73

3.5.1 重心坐标和子空间 74

3.5.2　仿射无关 74

4.2　点和向量的矩阵表示 76

第4章　矩阵、向量代数和变换 76

4.1 导言 76

4.3　加法、减法和乘法 78

4.3.1 向量加法和减法 79

4.3.2　点与向量的加法和减法 79

4.3.3　点的减法 80

4.3.4　数乘 80

4.4 向量乘积 80

4.4.1　点积 80

4.4.2　叉积 81

7.5.3　椭圆之间的相交 1 83

4.4.4 正交运算符和正交点积 84

4.4.3　张量积 84

4.5　仿射变换的矩阵表示 88

7.7　轴分离方法 1 88

4.6　基底变化／帧／坐标系统 89

4.7　向量几何和仿射变换 92

4.7.1　标记法 93

4.7.2　平移 93

4.7.3　旋转 95

4.7.4　缩放 100

4.7.5　反射 104

4.7.6　剪切 108

4.8　投影 111

4.8.1　正射投影 112

4.8.2　斜轴投影 113

4.8.3　透视投影 114

4.9　变换法线向量 116

推荐的阅读材料 118

第5章　二维几何图元 120

5.1 线形对象 120

5.1.1　隐含形式 120

5.1.2　参数形式 121

5.2　三角形 122

5.1.3　表示法之间的转换 122

5.3　矩形 124

5.4　折线和多边形 124

5.5　二次曲线 127

5.5.1 圆 129

5.5.2　椭圆 129

5.6　多项式曲线 130

5.6.1 贝塞尔曲线 130

5.6.3 非均匀有理B样条曲线 131

5.6.2　B样条曲线 131

第6章　二维距离 133

6.1 点到线形对象的距离 133

6.1.1 点到直线的距离 133

6.1.2　点到射线的距离 134

6.1.3　点到线段的距离 135

6.2　点到折线的距离 136

6.3.1 点到三角形的距离 138

6.3　点到多边形的距离 138

6.3.2　点到矩形的距离 150

6.3.3 点到正交平截面的距离 151

6.3.4　点到凸多边形的距离 154

6.4　点到二次曲线的距离 155

6.5　点到多项式曲线的距离 156

6.6　线形对象之间的距离 157

6.6.1 直线到直线的距离 157

6.6.2　直线到射线的距离 158

6.6.3 直线到线段的距离 159

6.6.4　射线到射线的距离 159

6.6.5　射线到线段的距离 162

6.6.6　线段到线段的距离 162

6.7　线形对象到折线或多边形的距离 163

6.8　线形对象到二次曲线的距离 164

6.9　线形对象到多项式曲线的距离 166

6.10　GJK算法 166

6.10.1　集合运算 167

6.10.2　算法概述 168

6.10.3　其他算法 170

7.1　线形对象之间的相交 171

第7章　二维相交 171

7.2　线形对象与折线的相交 174

7.3.1 线形对象与一般二次曲线的相交 175

7.3　线形对象与二次曲线的相交 175

7.3.2　线形对象与圆形曲线的相交 176

7.4　线形对象与多项式曲线的相交 176

7.4.1　代数方法 177

7.4.2　折线逼近 178

7.4.3　分级包围 178

7.4.4　单调分解 179

7.4.5　栅格方法 180

7.5.1 一般二次曲线之间的相交 181

7.5　二次曲线之间的相交 181

7.5.2　圆形二次曲线之间的相交 182

7.6　多项式曲线之间的相交 186

7.6.1　代数方法 186

7.6.2　折线逼近 186

7.6.3　分级包围 186

7.6.4　栅格方法 187

7.7.1　投影到直线上的分离 188

7.7.2　固定凸多边形的分离 189

7.7.3　运动凸多边形的分离 194

7.7.4　固定凸多边形的交集 196

7.7.5　运动凸多边形的接触点集 197

第8章　其他二维问题 204

8.1　三点确定的圆 204

8.2　与三条直线相切的圆 204

8.3　与圆相切于给定点的直线 205

8.4　通过给定点并与圆相切的直线 205

8.5　与两圆相切的直线 208

8.6　两点和给定半径决定的圆 213

8.7　通过一点并与一条直线相切且具有给定半径的圆 214

8.8　与两条直线相切且具有给定半径的圆 216

8.9　经过一点并与一个圆相切且具有给定半径的圆 218

8.10　具有给定半径并与一条直线和一个圆相切的圆 222

8.11 具有给定半径并与两圆相切的圆 225

8.12　与一条给定直线垂直并通过一个给定点的直线 227

8.13　位于两点之间并与该两点等距的直线 228

8.14　与一条给定直线平行且相距指定值的直线 229

8.15　与给定直线平行且垂直（水平）距离为指定值的直线 230

8.16　与给定圆相切并与给定直线垂直的直线 232

第9章　三维几何图元 234

9.1 线形对象 234

9.2　平面对象 235

9.2.1　平面 235

9.2.2 相对于一个平面的坐标系统 237

9.2.3　平面上的二维对象 238

9.3 多边形网格、多面体和有限多面体 240

9.3.1 顶点一边一面表 244

9.3.2　互连网格 244

9.3.3 复式网格 246

9.3.4　闭合网格 247

9.3.5　一致次序 247

9.3.6　柏拉图立体 249

9.4　二次曲面 253

9.4.1 三个非零特征值 253

9.4.2　两个非零特征值 254

9.4.3　一个非零特征值 256

9.5 环面 256

9.6　多项式曲线 257

9.6.1 贝塞尔曲线 258

9.6.2　B样条曲线 258

9.6.3　非均匀有理B样条曲线 259

9.7　多项式曲面 259

9.7.1 贝塞尔曲面 260

9.7.2　B样条曲面 262

9.7.3　非均匀有理B样条曲面 263

10.2　点到线形对象的距离 264

10.1　导言 264

第10章　三维距离 264

10.2.1 点到直线或射线的距离 265

10.2.2　点到折线的距离 267

10.3　点到平面对象的距离 270

10.3.1 点到平面的距离 270

10.3.2 点到三角形的距离 272

10.3.3 点到矩形的距离 277

10.3.4　点到多边形的距离 278

10.3.5　点到圆或圆盘的距离 281

10.4.1　一般问题 283

10.4　点到多面体的距离 283

10.4.2　点到有向有界箱的距离 285

10.4.3 点到正交平截体的距离 287

10.5　点到二次曲面的距离 291

10.5.1 点到一般二次曲面的距离 291

10.5.2　点到椭球面的距离 292

10.6　点到多项式曲线的距离 293

10.7　点到多项式曲面的距离 295

10.8　线形对象之间的距离 297

10.8.1 直线与直线之间的距离 297

10.8.2　线段／线段、直线／射线、直线／线段、射线／射线、射线／线段之间的距离 299

10.8.3　计算线段到线段的距离的另一种方法 310

10.9.1　线形对象到三角形的距离 316

10.9　线形对象与三角形、矩形、四面体和有向有界箱之间的距离 316

10.9.2　线形对象到矩形的距离 322

10.9.3　线形对象到四面体的距离 326

10.9.4　线形对象到有向有界箱的距离 328

10.10　直线到二次曲面的距离 341

10.11 直线到多项式曲面的距离 342

10.12　GJK算法 343

10.13　杂项 343

10.13.1 直线与平面曲线之间的距离 343

10.13.2　直线与平面实心物体之间的距离 345

10.13.3　平面曲线之间的距离 345

10.13.4 曲面上的测地距离 349

第11章　三维相交 352

11.1　线形对象与平面对象的相交 352

11.1.1　线形对象与平面的相交 352

11.1.2　线形对象与三角形的相交 354

11.1.3　线形对象与多边形的相交 357

11.1.4　线形对象与圆盘的相交 360

11.2　线形对象与多面体的相交 361

11.3　线形对象与二次曲面的相交 365

11.3.1 线形对象与一般二次曲面的相交 365

11.3.2　线形对象与球面的相交 367

11.3.3　线形对象与椭球面的相交 369

11.3.4　线形对象与圆柱面的相交 372

11.3.5 线形对象与圆锥面的相交 375

11.4　线形对象与多项式曲面的相交 380

11.4.1 代数曲面 381

11.4.2 自由形态曲面 382

11.5　平面对象之间的相交 388

11.5.1　两个平面之间的相交 388

11.5.2　三个平面之间的相交 390

11.5.3　三角形与平面的相交 392

11.5.4　三角形与三角形的相交 396

11.6　平面对象与多面体的相交 398

11.6.1 三角网格 399

11.6.2　一般多面体 400

11.7　平面对象与二次曲面的相交 401

11.7.1 平面与一般二次曲面的相交 401

11.7.2　平面与球面的相交 402

11.7.3　平面与圆柱面的相交 404

11.7.4　平面与圆锥面的相交 413

11.7.5　三角形与圆锥面的相交 428

11.8　平面对象与多项式曲面的相交 431

11.8.1　埃尔米特曲线 432

11.8.2　几何定义 433

11.8.3　计算曲线 434

11.8.4　算法 435

11.9.1 一般相交问题 437

11.8.5　实现要点 437

11.9 二次曲面之间的相交 437

11.9.2　椭球面 443

11.10　多项式曲面之间的相交 446

11.10.1　细分方法 447

11.10.2　格子评测 447

11.10.3　解析方法 448

11.10.4　步进方法 448

11.11　轴分离方法 448

11.11.1 固定凸多面体的分离 448

11.11.2　运动凸多面体的分离 451

11.11.4　固定凸多面体的接触集 453

11.11.3 固定凸多面体的交集 453

11.12　杂项 459

11.12.1 有向有界箱与正交平截体的相交 459

11.12.2　线形对象与轴对齐有界箱的相交 461

11.12.3　线形对象与有向有界箱的相交 464

11.12.4　平面与轴对齐有界箱的相交 467

11.12.5　平面对象与有向有界箱的相交 468

11.12.6　轴对齐有界箱之间的相交 470

11.12.7　有向有界箱之间的相交 470

11.12.8　球面与轴对齐有界箱的相交 474

11.12.9　圆柱面之间的相交 475

11.12.10　线形对象与环面的相交 485

第12章　其他三维问题 488

12.1 点在平面上的投影 488

12.2　向量在平面上的投影 489

12.3　直线与平面的夹角 490

12.4　两平面之间的夹角 491

12.5 以一条直线为法线并通过一给定点的平面 491

12.6　三点决定的平面 492

12.7　两条直线之间的夹角 493

第13章　关于计算几何学的话题 495

13.1 二维空间分区二叉树 495

13.1.1 多边形的空间分区二叉树表示 495

13.1.2　最小分解与平衡树 501

13.1.3　用空间分区二叉树进行点在多边形内的检测 502

13.1.4　用空间分区二叉树分解线段 503

13.2　三维空间分区二叉树 505

13.2.1 多面体的空间分区二叉树表示 506

13.2.2　最小分解与平衡树 507

13.2.3　用空间分区二叉树进行点在多面体内的检测 508

13.2.4　用空间分区二叉树分解线段 509

13.2.5　用空间分区二叉树分解凸多边形 510

13.3　点在多边形内的检测 511

13.3.1 点在三角形内的检测 512

13.3.2　点在凸多边形内的检测 513

13.3.3　点在一般多边形内的检测 515

13.3.5　栅格方法 520

13.3.4　点在多边形内的快速检测法 520

13.4　点在多面体内的检测 521

13.4.1 点在四面体内的检测 521

13.4.2　点在凸多面体内的检测 522

13.4.3 点在一般多面体内的检测 524

13.5　与多边形有关的布尔运算 526

13.5.1　抽象运算 526

13.5.2　两种基础运算 528

13.5.3 使用空间分区二叉树的布尔运算 529

13.5.4　其他算法 532

13.6.2　使用空间分区二叉树的布尔运算 534

13.6　与多面体有关的布尔运算 534

13.6.1　抽象运算 534

13.7 凸包 536

13.7.1　二维凸包 537

13.7.2　三维凸包 548

13.7.3 高维凸包 552

13.8　德洛奈三角剖分 556

13.8.1　二维增量构建 558

13.8.2　一般维度增量构建 561

13.8.3　用凸包实现构建 564

13.9.1　一个简单多边形的可见性图 565

13.9　多边形分解 565

13.9.2　三角剖分 568

13.9.3　水平分解三角剖分 571

13.9.4　凸分解 582

13.10　外接球与内切球 589

13.10.1　外接球 590

13.10.2　内切球 591

13.11 点集的最小区域 592

13.11.1　最小面积矩形 592

13.11.2　最小体积箱体 595

13.11.3　最小面积的圆 595

13.11.4　最小体积的球 599

13.11.5　杂项 600

13.12　面积和体积测量 602

13.12.1　二维多边形的面积 602

13.12.2　三维多边形的面积 605

13.12.3　多面体的体积 608

附录A　数值方法 610

附录B　三角几何 682

附录C　几何图元基础公式 700

参考文献 709

图索引 720

表索引 735