计算机图形学几何工具算法详解

第1章 绪论

1. 1 如何使用本书

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

1. 2. 1 低层问题

1. 2. 2 高层问题

1. 3 各章内容概要

第2章 矩阵和线性系统

2. 1 导言

2. 1. 1 动机

2. 1. 2 组织

2. 1. 3 符号约定

2. 2 多元组

2. 2. 1 定义

2. 2. 2 算术运算

2. 3 矩阵

2. 3. 1 符号与术语

2. 3. 2 转置

2. 3. 3 算术运算

2. 3. 4 矩阵乘法

2. 4 线性系统

2. 4. 1 线性方程

2. 4. 2 两个未知数的线性系统

2. 4. 3 一般线性系统

2. 4. 4 减行. 阶梯形和秩

2. 5 方阵

2. 5. 1 对角矩阵

2. 5. 2 三角形矩阵

2. 5. 3 行列式

2. 5. 4 逆矩阵

2. 6 线性空间

2. 6. 1 数域

2. 6. 2 定义和性质

2. 6. 3 子空间

2. 6. 4 线性组合和生成空间

2. 6. 5 线性无关. 维数和基底

2. 7 线性映射

2. 7. 1 映射基础

2. 7. 2 线性映射

2. 7. 3 线性映射的矩阵表示

2. 7. 4 克莱姆定理

2. 8 特征值和特征向量

2. 9 欧几里得空间

2. 9. 1 内积空间

2. 9. 2 正交和标准正交集

2. 10 最小二乘法

2. 11 推荐的阅读材料

第3章 向量代数

3. 1 向量基础

3. 1. 1 向量等价

3. 1. 2 向量加法

3. 1. 3 向量减法

3. 1. 4 向量数乘

3. 1. 5 向量加法和数乘的性质

3. 2 向量空间

3. 2. 1 生成空间

3. 2. 2 线性无关

3. 2. 3 基底. 子空间和维数

3. 2. 4 方向

3. 2. 5 基底变化

3. 2. 6 线性变换

3. 3 仿射空间

3. 3. 1 欧几里得几何

3. 3. 2 体积. 行列式和数量三重积

3. 3. 3 坐标系

3. 4 仿射变换

3. 4. 1 仿射映射的类型

3. 4. 2 仿射映射的合成

3. 5 重心坐标和单形

3. 5. 1 重心坐标和子空间

3. 5. 2 仿射无关

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

4. 1 导言

4. 2 点和向量的矩阵表示

4. 3 加法. 减法和乘法

4. 3. 1 向量加法和减法

4. 3. 2 点与向量的加法和减法

4. 3. 3 点的减法

4. 3. 4 数乘

4. 4 向量乘积

4. 4. 1 点积

4. 4. 2 叉积

4. 4. 3 张量积

4. 4. 4 正交运算符和正交点积

4. 5 仿射变换的矩阵表示

4. 6 基底变化／帧／坐标系统

4. 7 向量几何和仿射变换

4. 7. 1 标记法

4. 7. 2 平移

4. 7. 3 旋转

4. 7. 4 缩放

4. 7. 5 反射

4. 7. 6 剪切

4. 8 投影

4. 8. 1 正射投影

4. 8. 2 斜轴投影

4. 8. 3 透视投影

4. 9 变换法线向量

推荐的阅读材料

第5章 二维几何图元

5. 1 线形对象

5. 1. 1 隐含形式

5. 1. 2 参数形式

5. 1. 3 表示法之间的转换

5. 2 三角形

5. 3 矩形

5. 4 折线和多边形

5. 5 二次曲线

5. 5. 1 圆

5. 5. 2 椭圆

5. 6 多项式曲线

5. 6. 1 贝塞尔曲线

5. 6. 2 B样条曲线

5. 6. 3 非均匀有理B样条曲线

第6章 二维距离

6. 1 点到线形对象的距离

6. 1. 1 点到直线的距离

6. 1. 2 点到射线的距离

6. 1. 3 点到线段的距离

6. 2 点到折线的距离

6. 3 点到多边形的距离

6. 3. 1 点到三角形的距离

6. 3. 2 点到矩形的距离

6. 3. 3 点到正交平截面的距离

6. 3. 4 点到凸多边形的距离

6. 4 点到二次曲线的距离

6. 5 点到多项式曲线的距离

6. 6 线形对象之间的距离

6. 6. 1 直线到直线的距离

6. 6. 2 直线到射线的距离

6. 6. 3 直线到线段的距离

6. 6. 4 射线到射线的距离

6. 6. 5 射线到线段的距离

6. 6. 6 线段到线段的距离

6. 7 线形对象到折线或多边形的距离

6. 8 线形对象到二次曲线的距离

6. 9 线形对象到多项式曲线的距离

6. 10 GJK算法

6. 10. 1 集合运算

6. 10. 2 算法概述

6. 10. 3 其他算法

第7章 二维相交

7. 1 线形对象之间的相交

7. 2 线形对象与折线的相交

7. 3 线形对象与二次曲线的相交

7. 3. 1 线形对象与一般二次曲线的相交

7. 3. 2 线形对象与圆形曲线的相交

7. 4 线形对象与多项式曲线的相交

7. 4. 1 代数方法

7. 4. 2 折线逼近

7. 4. 3 分级包围

7. 4. 4 单调分解

7. 4. 5 栅格方法

7. 5 二次曲线之间的相交

7. 5. 1 一般二次曲线之间的相交

7. 5. 2 圆形二次曲线之间的相交

7. 5. 3 椭圆之间的相交

7. 6 多项式曲线之间的相交

7. 6. 1 代数方法

7. 6. 2 折线逼近

7. 6. 3 分级包围

7. 6. 4 栅格方法

7. 7 轴分离方法

7. 7. 1 投影到直线上的分离

7. 7. 2 固定凸多边形的分离

7. 7. 3 运动凸多边形的分离

7. 7. 4 固定凸多边形的交集

7. 7. 5 运动凸多边形的接触点集

第8章 其他二维问题

8. 1 三点确定的圆

8. 2 与三条直线相切的圆

8. 3 与圆相切于给定点的直线

8. 4 通过给定点并与圆相切的直线

8. 5 与两圆相切的直线

8. 6 两点和给定半径决定的圆

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

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

8. 9 经过一点并与一个圆相切且具有给定半径的圆

8. 10 具有给定半径并与一条直线和一个圆相切的圆

8. 11 具有给定半径并与两圆相切的圆

8. 12 与一条给定直线垂直并通过一个给定点的直线

8. 13 位于两点之间并与该两点等距的直线

8. 14 与一条给定直线平行且相距指定值的直线

8. 15 与给定直线平行且垂直(水平)距离为指定值的直线

8. 16 与给定圆相切并与给定直线垂直的直线

第9章 三维几何图元

9. 1 线形对象

9. 2 平面对象

9. 2. 1 平面

9. 2. 2 相对于一个平面的坐标系统

9. 2. 3 平面上的二维对象

9. 3 多边形网格. 多面体和有限多面体

9. 3. 1 顶点一边一面表

9. 3. 2 互连网格

9. 3. 3 复式网格

9. 3. 4 闭合网格

9. 3. 5 一致次序

9. 3. 6 柏拉图立体

9. 4 二次曲面

9. 4. 1 三个非零特征值

9. 4. 2 两个非零特征值

9. 4. 3 一个非零特征值

9. 5 环面

9. 6 多项式曲线

9. 6. 1 贝塞尔曲线

9. 6. 2 B样条曲线

9. 6. 3 非均匀有理B样条曲线

9. 7 多项式曲面

9. 7. 1 贝塞尔曲面

9. 7. 2 B样条曲面

9. 7. 3 非均匀有理B样条曲面

第10章 三维距离

10. 1 导言

10. 2 点到线形对象的距离

10. 2. 1 点到直线或射线的距离

10. 2. 2 点到折线的距离

10. 3 点到平面对象的距离

10. 3. 1 点到平面的距离

10. 3. 2 点到三角形的距离

10. 3. 3 点到矩形的距离

10. 3. 4 点到多边形的距离

10. 3. 5 点到圆或圆盘的距离

10. 4 点到多面体的距离

10. 4. 1 一般问题

10. 4. 2 点到有向有界箱的距离

10. 4. 3 点到正交平截体的距离

10. 5 点到二次曲面的距离

10. 5. 1 点到一般二次曲面的距离

10. 5. 2 点到椭球面的距离

10. 6 点到多项式曲线的距离

10. 7 点到多项式曲面的距离

10. 8 线形对象之间的距离

10. 8. 1 直线与直线之间的距离

10. 8. 2 线段／线段. 直线／射线. 直线／线段. 射线／射线. 射线／线段之间的距离

10. 8. 3 计算线段到线段的距离的另一种方法

10. 9 线形对象与三角形. 矩形. 四面体和有向有界箱之间的距离

10. 9. 1 线形对象到三角形的距离

10. 9. 2 线形对象到矩形的距离

10. 9. 3 线形对象到四面体的距离

10. 9. 4 线形对象到有向有界箱的距离

10. 10 直线到二次曲面的距离

10. 11 直线到多项式曲面的距离

10. 12 GJK算法

10. 13 杂项

10. 13. 1 直线与平面曲线之间的距离

10. 13. 2 直线与平面实心物体之间的距离

10. 13. 3 平面曲线之间的距离

10. 13. 4 曲面上的测地距离

第11章 三维相交

11. 1 线形对象与平面对象的相交

11. 1. 1 线形对象与平面的相交

11. 1. 2 线形对象与三角形的相交

11. 1. 3 线形对象与多边形的相交

11. 1. 4 线形对象与圆盘的相交

11. 2 线形对象与多面体的相交

11. 3 线形对象与二次曲面的相交

11. 3. 1 线形对象与一般二次曲面的相交

11. 3. 2 线形对象与球面的相交

11. 3. 3 线形对象与椭球面的相交

11. 3. 4 线形对象与圆柱面的相交

11. 3. 5 线形对象与圆锥面的相交

11. 4 线形对象与多项式曲面的相交

11. 4. 1 代数曲面

11. 4. 2 自由形态曲面

11. 5 平面对象之间的相交

11. 5. 1 两个平面之间的相交

11. 5. 2 三个平面之间的相交

11. 5. 3 三角形与平面的相交

11. 5. 4 三角形与三角形的相交

11. 6 平面对象与多面体的相交

11. 6. 1 三角网格

11. 6. 2 一般多面体

11. 7 平面对象与二次曲面的相交

11. 7. 1 平面与一般二次曲面的相交

11. 7. 2 平面与球面的相交

11. 7. 3 平面与圆柱面的相交

11. 7. 4 平面与圆锥面的相交

11. 7. 5 三角形与圆锥面的相交

11. 8 平面对象与多项式曲面的相交

11. 8. 1 埃尔米特曲线

11. 8. 2 几何定义

11. 8. 3 计算曲线

11. 8. 4 算法

11. 8. 5 实现要点

11. 9 二次曲面之间的相交

11. 9. 1 一般相交问题

11. 9. 2 椭球面

11. 10 多项式曲面之间的相交

11. 10. 1 细分方法

11. 10. 2 格子评测

11. 10. 3 解析方法

11. 10. 4 步进方法

11. 11 轴分离方法

11. 11. 1 固定凸多面体的分离

11. 11. 2 运动凸多面体的分离

11. 11. 3 固定凸多面体的交集

11. 11. 4 固定凸多面体的接触集

11. 12 杂项

11. 12. 1 有向有界箱与正交平截体的相交

11. 12. 2 线形对象与轴对齐有界箱的相交

11. 12. 3 线形对象与有向有界箱的相交

11. 12. 4 平面与轴对齐有界箱的相交

11. 12. 5 平面对象与有向有界箱的相交

11. 12. 6 轴对齐有界箱之间的相交

11. 12. 7 有向有界箱之间的相交

11. 12. 8 球面与轴对齐有界箱的相交

11. 12. 9 圆柱面之间的相交

11. 12. 10 线形对象与环面的相交

第12章 其他三维问题

12. 1 点在平面上的投影

12. 2 向量在平面上的投影

12. 3 直线与平面的夹角

12. 4 两平面之间的夹角

12. 5 以一条直线为法线并通过一给定点的平面

12. 6 三点决定的平面

12. 7 两条直线之间的夹角

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

13. 1 二维空间分区二叉树

13. 1. 1 多边形的空间分区二叉树表示

13. 1. 2 最小分解与平衡树

13. 1. 3 用空间分区二叉树进行点在多边形内的检测

13. 1. 4 用空间分区二叉树分解线段

13. 2 三维空间分区二叉树

13. 2. 1 多面体的空间分区二叉树表示

13. 2. 2 最小分解与平衡树

13. 2. 3 用空间分区二叉树进行点在多面体内的检测

13. 2. 4 用空间分区二叉树分解线段

13. 2. 5 用空间分区二叉树分解凸多边形

13. 3 点在多边形内的检测

13. 3. 1 点在三角形内的检测

13. 3. 2 点在凸多边形内的检测

13. 3. 3 点在一般多边形内的检测

13. 3. 4 点在多边形内的快速检测法

13. 3. 5 栅格方法

13. 4 点在多面体内的检测

13. 4. 1 点在四面体内的检测

13. 4. 2 点在凸多面体内的检测

13. 4. 3 点在一般多面体内的检测

13. 5 与多边形有关的布尔运算

13. 5. 1 抽象运算

13. 5. 2 两种基础运算

13. 5. 3 使用空间分区二叉树的布尔运算

13. 5. 4 其他算法

13. 6 与多面体有关的布尔运算

13. 6. 1 抽象运算

13. 6. 2 使用空间分区二叉树的布尔运算

13. 7 凸包

13. 7. 1 二维凸包

13. 7. 2 三维凸包

13. 7. 3 高维凸包

13. 8 德洛奈三角剖分

13. 8. 1 维增量构建

13. 8. 2 一般维度增量构建

13. 8. 3 用凸包实现构建

13. 9 多边形分解

13. 9. 1 一个简单多边形的可见性图

13. 9. 2 三角剖分

13. 9. 3 水平分解三角剖分

13. 9. 4 凸分解

13. 10 外接球与内切球

13. 10. 1 外接球

13. 10. 2 内切球

13. 11 点集的最小区域

13. 11. 1 最小面积矩形

13. 11. 2 最小体积箱体

13. 11. 3 最小面积的圆

13. 11. 4 最小体积的球

13. 11. 5 杂项

13. 12 面积和体积测量

13. 12. 1 二维多边形的面积

13. 12. 2 三维多边形的面积

13. 12. 3 多面体的体积

附录A 数值方法

附录B 三角几何

附录C 几何图元基础公式

参考文献

图索引

表索引