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

游客，本帖隐藏的内容需要积分高于 1 才可浏览，您当前积分为 0

资源信息： 中文名: 计算机图形学几何工具算法详解 版本: PDF 发行日期: 2005年 地区: 大陆 概述:

【作者】[美]Philip J.Schneider,David H.Eberly 【出版社】电子工业出版社 【版次】2005年01月 第一版 【页数】734 【ISBN】7-121-00515-8 【开本】16K 简介: 本书提供了计算机图形学基础问题的各种有效算法，以及相关的数学和几何背景知识，对计算机图形学和其他领域的二维和三维几何学问题进行了全面的解析和合理的组织。本书包括建立基础图元、距离计算、近似值处理、包含性分析、分解、相交确定、分离等方面的算法，对每一个问题都有清晰的论述和图示，并利用易于理解的伪码来表示各种完整详尽的算法。除此之外，本书还在多个附录中提供了丰富的参考资料。 本书适合作为计算机图形学几何算法课程的教材，也可作为参考指南，供经验丰富的业界人士参考查阅。 目录: 第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 线性系统 17 2.4.1 线性方程 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.1 数域 29 2.6.2 定义和性质 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 欧几里得空间 38 2.9.1 内积空间 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.3 向量减法 46 3.1.4 向量数乘 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章 矩阵、向量代数和变换 76 4.1 导言 76 4.2 点和向量的矩阵表示 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 4.4.3 张量积 84 4.4.4 正交运算符和正交点积 84 4.5 仿射变换的矩阵表示 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.1.3 表示法之间的转换 122 5.2 三角形 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.2 b样条曲线 131 5.6.3 非均匀有理b样条曲线 131 第6章 二维距离 133 6.1 点到线形对象的距离 133 6.1.1 点到直线的距离 133 6.1.2 点到射线的距离 134 6.1.3 点到线段的距离 135 6.2 点到折线的距离 136 6.3 点到多边形的距离 138 6.3.1 点到三角形的距离 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章 二维相交 171 7.1 线形对象之间的相交 171 7.2 线形对象与折线的相交 174 7.3 线形对象与二次曲线的相交 175 7.3.1 线形对象与一般二次曲线的相交 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 二次曲线之间的相交 181 7.5.1 一般二次曲线之间的相交 181 7.5.2 圆形二次曲线之间的相交 182 7.5.3 椭圆之间的相交 183 7.6 多项式曲线之间的相交 186 7.6.1 代数方法 186 7.6.2 折线逼近 186 7.6.3 分级包围 186 7.6.4 栅格方法 187 7.7 轴分离方法 188 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章 三维距离 264 10.1 导言 264 10.2 点到线形对象的距离 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 点到多面体的距离 283 10.4.1 一般问题 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 线形对象与三角形、矩形、四面体和有向有界箱之间的距离 316 10.9.1 线形对象到三角形的距离 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.8.5 实现要点 437 11.9 二次曲面之间的相交 437 11.9.1 一般相交问题 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.3 固定凸多面体的交集 453 11.11.4 固定凸多面体的接触集 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.4 点在多边形内的快速检测法 520 13.3.5 栅格方法 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 与多面体有关的布尔运算 534 13.6.1 抽象运算 534 13.6.2 使用空间分区二叉树的布尔运算 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 多边形分解 565 13.9.1 一个简单多边形的可见性图 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 共享时间：08:00 AM - 18:00 PM(星期一至星期六) 共享条件：电信ADSL 2M带宽，上载理论64K，平均50K 连接服务器：DONKEY SERVER NO1 或 NO2 运行系统：98/XP/2000 经NOD32_V2.5版，病毒库1903-20061205检测无毒 文档提供的所有资源均是网上搜集或私下交流学习之用，版权归原作者及原软件公司所有。 所有资源请在下载后24小时内删除。如果您觉得满意，请购买正版！ 本文档仅仅提供一个观摩学习的环境，将不对任何资源负法律责任！ 严厉谴责和鄙夷一切利用本文档资源进行牟利的盗版行为！ 任何涉及商业盈利目的均不得使用，否则产生的一切后果将由您自己承担！