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

第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  几何图元基础公式
 参考文献
 图索引
 表索引