计算机图形学几何工具算法详解——计算机专业人员书库 (2008 年度畅销榜NO.740 )

本书对计算机图形学和其他领域的二维和三维几何学算法进行了全面的解析和合理的组织。全书先复习了向量和矩阵代数的基本概念，而后详细地描述了图形几何学涉及的各种二维和三维对象的几何测量、相交等问题的各种算法，并提供了关于计算几何学主题的大量材料以便于快速参考。\r\n 本书适合作为计算机图形学几何算法课程的教材，也可作为参考指南，供经验丰富的业界人士参考查阅。

第1章 绪论\r\n 1.1 如何使用书本\r\n 1.2 关于数值计算的若干问题\r\n 1.2.1 低层问题\r\n 1.2.2 高层问题\r\n 1.3 各章内容概要\r\n第2章 矩阵和线性系统\r\n 2.1 导言\r\n 2.1.1 动机\r\n 2.1.2 组织\r\n 2.1.3 符号约定\r\n 2.2 多元组\r\n 2.2.1 定义 \r\n 2.2.2 算术运算\r\n 2.3 矩阵\r\n 2.3.1 符号与术语\r\n 2.3.2 转置\r\n 2.3.3 算术运算\r\n 2.3.4 矩阵乘法\r\n 2.4 线性系统\r\n 2.4.1 线性方程\r\n 2.4.2 两个未知数的线性系统\r\n 2.4.3 一般线性系统\r\n 2.4.4 减行、阶梯形和秩 \r\n 2.5 方阵\r\n 2.5.1 对角矩阵\r\n 2.5.2 三角形矩阵\r\n 2.5.3 行列式\r\n 2.5.4 逆矩阵\r\n 2.6 线性空间\r\n 2.6.1 数域\r\n 2.6.2 定义和性质\r\n 2.6.3 子空间\r\n 2.6.4 线性组合和生成空间\r\n 2.6.5 线性无关、维数和基底 \r\n 2.7 线性映射\r\n 2.7.1 映射基础\r\n 2.7.2 线性映射\r\n 2.7.3 线性映射的矩阵表示\r\n 2.7.4 克莱姆定理\r\n 2.8 特征值和特征向量\r\n 2.9 欧几里得空间\r\n 2.9.1 内积空间\r\n 2.9.2 正交和标准正交集\r\n 2.10 最小二乘法\r\n 2.11 推荐的阅读材料\r\n第3章 向量代数\r\n 3.1 向量基础\r\n 3.1.1 向量等价\r\n 3.1.2 向量加法\r\n 3.1.3 向量减法\r\n 3.1.4 向量数乘\r\n 3.1.5 向量加法和数乘的性质\r\n 3.2 向量空间\r\n 3.2.1 生成空间\r\n 3.2.2 线性无关\r\n 3.2.3 基底、子空间和维数\r\n 3.2.4 方向\r\n 3.2.5 基底变化\r\n 3.2.6 线性变换\r\n 3.3 仿射空间\r\n 3.3.1 欧几里得几何\r\n 3.3.2 体积、行列式和数量三重积\r\n 3.4 仿射变换\r\n 3.4.1 仿射映射的类型\r\n 3.4.2 仿射映射的合成\r\n 3.5 重心坐标和单形\r\n 3.5.1 重心坐标和子空间\r\n 3.5.2 仿射无关\r\n第4章 矩阵、向量代数和变换\r\n第5章 二维几何图元\r\n第6章 二维距离\r\n第7章 二维相交\r\n第8章 其他二维问题\r\n第9章 三维几何图元\r\n第10章 三维距离\r\n第11章 三维相交\r\n第12章 其他三维问题\r\n第13章 关于计算几何学的话题\r\n附录A 数值方法\r\n附录B 三角几何 \r\n附录C 几何图元基础公式\r\n参考文献\r\n图索引\r\n表索引

我的书架上有一本名为《程序员的几何学》(A Programmer's Geometry)的老书, 作者是Bowyer和Woodwark. 该书初版于1983年, 1984年和1985年再版两次后未再重印. 多年来, 我一直珍藏该书, 仔细地记录谁借阅了它. 我最近在万维网上搜索该书, 结果发现6本旧书, 它们的价格在50美元～100美元之间. 对于一本只有140页的平装书来说, 这样的价格是非常高的. 这本书能值那么多钱, 是因为它说明了如何编程实现与二维几何学相关的各种操作. 它不仅介绍了几何公式, 而且还描述了在程序中实现这些公式的有效方法, 并且提供了代码片断(用FORTRAN编写的代码片断). 现在, 几乎过去了20年, 我们发现了一本新书, 堪当这本薄书的继承者. 呈现在你面前的这本书从浩如烟海的几何学文献中萃取了对程序设计人员最为有用的内容. 自1993年以来, 计算机图形学领域已经有了很大的发展, 本书反映了这些巨变. 受惠于计算机处理器性能的持续改善, 过去需要脱机运行的许多运算, 现在一般都可在交互程序中完成. 多边形的三角剖分. 碰撞检测和响应, 以及曲面建模和修正, 现在都可能按实时的速率完成. 本书提供了实现上述及其他许多算法的坚实理论和代码. 除了提供与几何学相关的各种不同领域的任务的可靠参考, 本书还介绍了隐藏在算法后面的基础理论. 与采用纯粹的菜谱方式(这种方式仅让读者留下可运行的代码, 却难以让读者理解代码是如何工作的)的一般书籍不同, 作者在本书中解释了一系列关键的概念, 这对读者是非常有益的. 本书的阐述方法使每一个算法都能成为一种能进一步与其他工具重组的工具. 计算机图形学具有不断动态发展的特性, 这使它成为一个特别令人感兴趣的学习领域. 着色方法的研究和实现随着所使用硬件的不断发展而发展. 例如, 在交互式着色领域中, 图形加速器的可编程特性一出现, 就已经改变了不同技术的相对成本. 更通俗地说, CPU的发展已经使内存访问和高速缓存显得比过去用减少运算符次数(例如, 计算乘法和加法)的方法来提高运算速度更为重要. 然而, 基础的理论和算法, 比如得到物体凸面外壳的算法就相当经典, 受这类变化的影响较小. 当然, 更加有效的算法总是在不断被发现, 而且哪种方法被认为是当前最快的算法还受硬件的影响, 但是基本的原理保持不变. 固而, 在把有关DirectX9和Intel的64位Itanium体系结构的书籍从书架上撤下多年以后, 你很可能还会在书架上保留本书的一些版本. 本书的价值之所以将持续存在, 还因为有因特网. 本人是"图形珍宝(GraphicsGems)"系列书籍代码库的管理者. 在这一系列书籍于20世纪90年代早期出版时, 这系列书籍的代码, 包括PhilipSchneider编写的代码, 很明智地免费提供给读者使用. 这些年来, 读者不断给代码库寄来缺陷修正和代码改进, 使所有用户从中受益. 同样地, DaveEbefiy一直认真地维护他的"魔法软件(MagicSoftware)"网站(www. magic-software. com), 其中包含了本书提供的许多算法的工作版本. 计算机图形学领域的一位前沿研究者认为该网站是'国宝", 在任何需要的时候这一网站会立刻增加附录和勘误信息. 代码不会过时, 而是会在有效的支持下不断改进. 本书中的算法更是如此, 因为它们与特定硬件. 网络协议或其他短暂的事物并不相关. 多年来, 我和其他的许多人已经在产品和研究项目中使用了作者们编写的算法和代码. 程序设计人员工作一个小时的价值通常高于本书的价格. 从这个意义来说, 你拥有了一本潜在价值为数千美元的书籍. 花费这一价值的一小部分即可购得本书, 这真是一个现代的奇迹. 本书包含了令人难以置信的信息量. 数学语言可能降低你的阅读速度, 然而如果使用其他的描述方法替换, 则必然会包含赘言, 且对有些算法可能会描述得不是很精确. 如果你想寻找能使阅读更轻松的描述方式, 请继续搜索. 就像想获得世界上大部分有价值的东西一样, 完全地理解本书的内容, 是需要付出努力和奋斗的. Eric Haines

快速而廉价的大众化图形硬件的出现, 已经引起了人们对计算机图形学知识日渐热切的渴求, 人们希望了解在计算机游戏. 科学可视化. 医学图像分析. 仿真和虚拟世界等应用程序中如何编程实现各种各样的几何任务. 各种应用程序的类型没有改变, 但应用方向却利用技术的优势不断发展(Crawford 2002). 新的应用方向甚至已经包括以代码分析和可视化调试为目的的三维环境, 以及政党联合形式的分析, 即将政党的信念表示为不同的凸体, 它们之间的相交表明潜在的联合性. 在书籍. Web站点. 新闻组. 期刊文章或行业杂志中, 均可以找到许多关于图形的知识. 有时这类资源容易理解, 但更多的时候却显得晦涩难懂. 有时它们提供了足够多的细节来阐明潜在的原理, 但有时却没有提供细节. 有时提出一个概念时考虑到了使用浮点运算时出现的数值问题, 但在其他很多情形中, 概念的提出仅仅局限在纯粹的理论层面上. 有时甚至(特别是在一些在线文章中)表述都可能不正确. 在查找这类资源, 评价其适用性. 有效性和正确性, 以及将它们改编以适应你自己的需求等方面所花的时间远远超过在其他任务上所用的时间. 本书就是针对这类问题而设计编写的. 本书为你提供了许多在实际应用中经常遇到的二维和三维几何学算法, 并对它们进行了全面的解析和合理的编排. 我们之所以将这些算法称为几何工具算法, 是因为这些算法和概念实际上是一些用来实现应用目标的工具. 本书所涉及的不同主题的难易程度相差很大. 有的非常浅显, 比如计算点到线段的距离：而有的又非常复杂, 比如计算两个非凸的简单闭合多面体之间的相交. 有些工具算法仅需用到向量代数中的若干简单概念. 而其他很多工具算法却需要使用微积分中一些较高深的概念, 比如函数的导数. 水平集(levelsets)和使用拉格朗日乘子(Lagrange multipliers)的约束极小化(constrained minimization). 大多数书籍的重点一般都集中在某一部分章节, 但我们编写的这本书却非如此. 我们想使本书既适用于图形学领域的新手, 也适用于经验丰富的老手. 我们为需要复习向量和矩阵代数的读者提供了三章, 简明地介绍了与本书相关的内容. 本书提供了几个附录, 其中一个附录简要地概述了三角几何的基本公式, 还有一个附录涵盖了用于几何工具算法的各种不同的数值方法. 本书有两种使用方式. 第一种是作为教科书使用. 从某种意义上来说, 本书介绍的内容是为传授算法的重要思想服务的, 因此, 本书适合作为大学图形学几何算法课程的教材. 虽然本书没有为各章节配备练习, 但本书提供了大量的伪码(pseudocode). 用一种实际的编程语言实现这些伪码就是非常合适的一组课程作业. 这里引用一句著名的谚语：空谈不如实践. 本书的第二种使用方式是作为参考指南. 关于算法的各章是按空间维来组织的, 首先介绍二维的内容, 然后再介绍三维的内容. 只有关于计算几何学的那一章没有按维来组织, 但它是作为独立的一章来编排的, 这样也很合理. 这种组织方式便于读者查找感兴趣的算法. 用空间维来划分内容的尝试稍微增加了一些写作的代价. 有些适用于任意维空间并且一般只需写作一次的内容现在被重复了. 例如, 点到线段的距离可以按不分空间维和自由坐标的方式来描述, 然而我们选择了在二维和三维中分别讨论该问题的方式. 我们认为, 这种选择使各章节相对独立, 因而可帮助读者避免一种通常的做法, 即用许多的纸片粘贴于书的不同位置以便能快速翻到与手头的问题相关的所有章节. 在计算机科学书籍中包含可运行的源代码已经成为出版界的一种惯例. 在大部分情形中, 编写阐明书中概念的代码需要花费相当可观的时间. 对于本书这种涵盖了庞大数量的算法的大型书籍来说, 提供阐明所有算法的完整代码集是很不切实际的. 因为即使对商业机构来说, 这也是一个艰巨的任务. 作为一种替代方案, 我们在书中增加了尽可能多的伪码. 参考文献中包括了许多提供或连接到算法实现的Web网站(在本书第一次印刷时都是有效的连接)的参考条目. 其中提供了大量的算法实现的一个网站是www. magic-software. com, 它的主机由魔术软件公司(Magic Software, Inc. )提供, DaveEbedy负责维护. 可以从这个站点免费下载该网站提供的源代码. 该网站还为本书建立了一个网页, 即WWW. magic-software.com／GeometricTools. html, 其中包含了与本书有关的信息. 勘误表, 以及代码更新历史(其中包括一些通知, 说明了新增的源代码的有关信息和对老的源代码的错误更正). 网页www. mkp.com／gtcg中也提供了与本书相关的资源. 我们感谢本书的评审人员, Tomas Akenine-Moller(Chalmers University of Technology), Ian Ashdown(byHeart Consultants Limited), Eric Haines(Autodesk, Inc. ), George Innis(Magic Software, Inc. ), PeterLipson(ToysforBob, Inc. ), JohnStone(University of lllinois), DanSunday(Johns Hopkins University)和Dennis Wenzel(True Matrix Software), 以及技术编辑ParveenKaler(Simon Fraser University). 评审如此规模庞大且涵盖面广的书是困难的, 然而他们的勤奋已经得到了回报. 评审者的意见和批评已经帮助我们改进了本书许多方面的内容. 我们特别感谢Peter和Dennis的意见, 因为他们承担了审阅全书这一艰难的任务, 并且对本书的几乎每一个方面都提出了详细的意见, 既有关于细节的意见也有关于全局的意见. DavidM. Ebefie(Walt Disney Feature Animation)提供了若干章节的许多伪码和一些额外的技术评论, 我们非常感谢他的帮助. 我们也感谢我们的编辑Diane Cerra和她的助手Belinda Breyer, 感谢她们帮助我们组编如此浩大的书籍所花费的时间, 她们理解作者需要不断的鼓励才能完成如此巨量的工作, 在此感谢她们所表现的耐心. 本书的成功不仅是由于我们的努力, 同时也是由于上述人员的共同努力. 请享受阅读的乐趣吧!