中文版序
本书最早是用英文出版于2009年7月。在不到一年后的我一次定期访华的时候，中国科学技术大学
的邓建松教授与我讨论了出版这本书中文版的可能性。我当然很乐见我的书有更多的读者，因此我马上就对
他的努力表示了支持。
在计算机图形学方面已出版了大量的优秀教材，其中有些教材所涵盖的内容远远超过了本书。
在几何造型和计算机辅助几何设计方面也颇有一些好书。但是迄今为止，我们好像还未见到一本专著把
这两个学科令人信服地集成一起。本书的目标就是想填补这个空白。
本书适用于那些想在一两个学期内同时讲授或学习上述两个学科的教师和学生。
大多数章节都是有意保持为很短的篇幅，因此可以一次性读完，或者在一两个小时内教完。
在每章后面提供有练习，供学生检验自己对正文的理解，并且强化对知识点的掌握。
本书第一部分讲解二维计算机图形学，特别集中于对分形的讨论上。分形是一个令我和我的学生感到无限着迷
的对象，它为计算机图形学（仿射变换和渲染技术）和几何造型（不动点方法以及为细分曲面所进行的令
人叹为观止的准备）提供了出色的介绍。
本书第二部分探讨理解和掌握计算机图形学和几何造型所必需的数学方法。这里强调的重点是与坐标无关的
向量技术，这是学生在数学课程中经常遇到的内容，但是他们通常没有意识到其实际应用价值。这一部分对
仿射和射影变换、矩阵方法以及四元数都进行了详细介绍，这为后续的三维计算机图形学和
几何造型讲解铺平了道路。
本书第三部分考虑三维计算机图形学中的经典主题，如颜色和亮度、递归光线跟踪、明暗处理、隐藏面消除算法
以及辐射度方法等。这一部分也有些篇幅讲解曲面和实体造型，因为我的本意就是同时讲授
几何造型和计算机图形学。
最后，本书第四部分集中于几何造型的传统主题，如B\'ezier、开花和B样条技术等，并且介绍了细分曲面。
有两条主线把本书的这一部分内容与前面的内容联系在一起。首先，对显示这些自由形式曲线和曲面的算法的强调
把这部分材料与三维计算机图形学联系在一起。其次，细分曲面和分形之间的联系也被着重讨论，从而本书
结尾与本书开始的主题完成了一个轮回。
本书中文版还包含一些不在英文版中的内容。在本书英文版出版后几周的2009年夏天，
代数几何和几何造型（Algebraic Geometry and Geometric Modeling,
AGGM）会议在中国云南丽江举行。 此次会议上，Rida
Farouki教授的学术报告讨论了非平面PH曲线（Pythagorean hodograph
curves）与四元数
的关系。受Farouki教授的报告以及随后与他进行的几次交流的启发，我意识到可以采用一种更直观的方法
讲述和理解四元数代数的几何意义。因此我专门为中文版重写了讲解
四元数乘法的第十五章。
如果英文版有第二版的话，那么我会把这些新内容包含进去。
任何一本书都不是一个人所能完成的。家人和朋友、出版商和译者、同事和学生、文化和传统都在其中
扮演着重要的角色。限于本序言的有限篇幅，请原谅我不能对他们一一表示感谢。我的出版商Taylor
and
Francis在本书英文版面市不久就支持出版中文版，我在此表示谢意。邓建松教授启动了本书中文版的出版，
对他在完成本书翻译过程中的坚持和努力也一并表示感谢。
美国德州休斯敦
2011年2月25日
序
计算机图形学领域已发展到相当成熟的水平了。哪怕是在初学者所用的个人计算机上，
我们都能看到图形功能的踪影；图形软件变得相当普及，艺术工作者们可以利用这些软件设计出
令人眼花缭乱的图像和动画，但他们却并不需要掌握这些软件背后的工作机理。
这些都是成熟的明证。与此同时，计算机图形学领域也在不停地扩展和演化，
年复一年关于计算机图形学的研究论文的数目在不停地增长，这就是一个证明。高速的发展
也给编著新的计算机图形学教材的作者们提出了挑战，新书的作者必须要确定不断增长的知识中
有哪些是对学生最有用的，会在书架上保存的时间最长。
在计算机图形学中，多年以来，已颇有几本写得不错的书籍，其中有一些书籍，其最新
版本现在还在使用。从百科全书式的教材到只讲一些要点的讲义，什么形式都有。本书采用
的是与众不同的方式。其内容划分为一节一节的“讲座”，这一组织方式使得其内容正好可以在一个学期
的入门性课程中讲完，每次课一章，共30次。所选择的主题几乎涵盖了计算机图形学所有的
重要概念。数学基础和几何造型部分的讲座内容更是突出。本书没有程序示例，
因为图形语言的短命天性会使得这样的材料很快就过时。
作为计算机图形学的软件开发人员、研究人员和教育工作者，本书作者所拥有的
职业履历受人敬重。在获得数学的博士学位后，他在那时还是新生的计算机图形学和
计算机辅助设计（CAD）企业中工作了多年，主要从事早期的图形学软件开发。
即使从事如此的职业，他还有兴趣担任全国各地一些高校的博士研究生的导师，尽管
这并不是他正式工作的一部分。他这样做，部分是因为他热爱研究，但更多的是因为
他乐于帮助学生获得成功。作为这些幸运学生中的一员，我见证了他在开展专业课题的研究，
提炼清晰易懂的表述，追求简洁明了的写作风格，注重数学理论的严谨等方方面面所展示的
极具感染力的热情。Goldman博士把自己职业生涯的刚刚过去的二十年奉献给了教育和科研事业，
先后在滑铁卢大学和莱斯大学的计算机科学专业担任教授。经过他多年来用这些材料进行
授课实践，本书的教学风格才慢慢凝练形成。他是学生们的良师益友，我很高兴
通过本书的出版，他的影响力能扩展得更远。
\hfill \kaishu 美国杨伯翰大学
前言
耶和华说：“日子将到，我要另立新约...。”
---耶利米书31:31
好消息：计算机图形学很有趣。看起来有趣，用起来有趣，甚至只要正确操作，编程和调试也很有趣。
计算机图形学还有许多有趣的应用，如：视频游戏、卡通动画、电影长片等。如果你学习了计算机图形学
和几何造型，那么你甚至可以在一个充满乐趣的行业中找到工作。在艺术和建筑、生物医学图像、计算摄影学等
领域，只要是你看到的，或者是你想象自己能看到的，无论什么东西都可以用几何造型的方法进行设计，
然后用计算机图形学的技术显示出来。
然而，很长时间以来，对许多不幸的大学学生而言，大学的计算机图形学和几何造型课程似乎永远
在乏味和深奥之间摇摆。沉闷的教材，迂腐的教员，好像只注重无尽的低层次技巧，如直线的绘制、
多边形的填充、反走样和裁剪等，很少或者根本不去探讨计算机图形学与其他计算机科学的内在联系。
许多优秀的教育手段被冷落：层次被混淆，数学被乱用，直观被无视，高雅被抛弃，神秘被忽略等。
乐趣和刺激从这些学科中流失。令人悲伤的是，我承认我自己就教过这样的课程。这个领域的所有人员
都需要做得更好。本书的主要目的就是希望为有同感的老师和学生提供一个新的佐证，一个新的
启示。
本作品是有意保持为一个较短的篇幅的。这不是一本关于计算机图形学的百科全书，
而只是这个学科的一个简明介绍。
基本内容可以在有15周时间的一个学期的课程中讲完，听课对象为计算机科学专业
的高年级本科生或者研究生一年级学生。
但是，本书确实涵盖了本学科重要主题的大多数。
概括而言，这些主题可以分为三类：图形学、造型和数学基础。图形学部分由光照和明暗处理组成，包括：
反射和折射、递归光线跟踪、辐射度方法、光照模型、多边形的明暗处理以及隐藏面消除算法等。
造型部分由曲线、
曲面和实体的理论组成，包括：平面和多边形，球面和二次曲面，代数和参数形式，构造实体几何、
边界表示和八叉树，插值和逼近，B\'ezier和B样条方法，分形算法和细分技术等。数学基础主要就是
线性代数，但从某些特别的角度来看，在标准的线性代数课堂上并没有讲到这些知识，
如向量几何和向量代数、仿射空间和质点空间、仿射映射和射影变换、矩阵和四元数等。
计算机图形学仍然是一个相对年轻的学科。因此我不是在旧瓶中装新酒。相反，在把这些材料讲授给
计算机科学专业的学生的时候，我会谨慎地寻求一些创新方法。我大量地借鉴了其他作者的想法，
但是重新编排了各个主题的顺序，我相信我所给出的过程使得表达更简洁，能吸引学生去学习，
而且在教育手段上也是合情合理的。相比于那些关注于低层次
图形学算法的标准教材而言，我把注意力主要集中在更高层次的图形学、造型和数学基础上，
如光线跟踪、多边形明暗处理、辐射度方法、分形、自由形式曲线和曲面、向量方法以及变换技术等。
下面列出这些材料的组织方式。
开篇就是分形。本课程的第一个主题就具有很高的视觉感染力，而且不失理论深度。这一主题
与其他的计算机科学也具有自然的联系。分形的形状就是
实实在在的递归。计算机科学专业
的学生习惯于编写递归程序；现在这些学生将会见到在计算机科学以外的视觉艺术中的递归，
这有可能是他们一生中的第一次体验。分形在视觉、智力以及计算等方面都是令人感到刺激
的。因此学生们有可能被吸引进来，为了生成新的分形，他们会自觉学习许多重要的技术。
我是采用乌龟绘图（turtle
graphics）的方式介绍分形的。得益于向小孩子们
传授编程的系统，LOGO语言和乌龟绘图已变得相当普及。但LOGO语言也是学习
计算机图形学和计算几何的具有强大功能的工具。本书把乌龟
绘图的想法进行了提升，认为它是介绍支撑当代计算机图形学许多基本概念的一种简单而有效的手段。
按照这里所采用的LOGO语言的版本，乌龟的状态是由定义乌龟位置的点$P$以及定义乌龟头在平面上指向的
向量$v$表示的。命令FORWARD和TURN用于调整乌龟的位置和指向。当乌龟在平面上根据乌龟程序员的控制，
沿着某条路径移动时，相邻两个点之间用直线段连接起来，从而绘制出曲线。
从这个简单的乌龟身上可以学到很多东西。FORWARD和TURN命令等价于平移和旋转，因此学生很早就会
接触到对图形流水线中这些基本变换的介绍，只是这里给出的变换是二维版本。（还有一个RESIZE命令，它改变
方向向量的长度，因而学生就会在学习平移和旋转的同时，也学习到放缩。）在程序内部，所有的计算都是
采用直角坐标进行的，但是乌龟程序员无权应用这些坐标。因而这些高层次命令要与这些低层次计算截然分开，
这是在本书中一直反复强调的计算机科学的主旨。为了让学生练习在其他计算机科学课程中学到的技能，
可以让他们尝试编写上述LOGO语言的解释器。
点可以平移，向量可以旋转和放缩。因此，虽然平面中的点和向量本质上都是采用直角坐标表示的，
但是在乌龟绘图中，对点和向量的处理是不同的。在本书中，一直保持对点和向量的这种区分，这也是计算机
图形学中所采用的方式；这种区分是非常基本的，但有时会被忽视，乌龟模型是引入这种区分的便捷手段。
乌龟模型也预示了本书在后面要应用仿射坐标对点和向量进行区分。
学生可以通过简单地递归乌龟编程，生成类似于Sierpinski三角形和Koch雪花曲线之类的分形。通过对
生成具体的视觉效果诱人的递归程序的思考，学生对递归的理解大多会得到提高，变得更加深刻。
生成分形的递归乌龟程序通常是很容易编写的；一般有一个显然的基础情形，递归的主体是由一些递归调用
组成，这些调用之间就用基本乌龟命令的各种序列连接起来。但是，在许多此类分形程序中，马上就会
显现出一种神秘现象。虽然基础情形的选择受一些限制，但是对基础情形的修改看起来并没有
改变递归极限所生成的分形。我们需要对这一神秘现象进行解释，这个解释就会引出生成分形的
另一重要方法，即迭代函数系统。
一个迭代函数系统就是一个压缩变换的有限集合。对一个紧致集合重复应用一组固定的压缩变换，就会生成
一个分形。对类似于Sierpinski地垫之类的分形，我们通常可以很容易地猜出生成这些分形的变换是哪些。
但是，相比于用递归乌龟程序生成分形而言，如何向计算机科学专业的学生介绍这一生成分形的
一般方法，就要困难得多。然而，通过对递归乌龟程序的直接分析，我们就会发现
由递归乌龟程序生成的分形等价于对乌龟几何形状（即在基础情形中由乌龟命令生成的形状）
应用一个迭代函数系统，这个迭代函数系统是由递归中出现的乌龟命令所生成的。
因而对递归乌龟程序的分析就引出了对迭代函数系统的研究。
另外，对迭代函数系统的理解是帮助学生理解前面遇到的神秘现象的关键。
学生在前面研究用递归乌龟程序生成分形的时候，发现修改基础情形看起来并没有改变递归极限
所生成的分形。这里的核心结果就是不动点定理。这个定理指的是，在一个完备度量空间中，
对一点的压缩映射的迭代总是收敛到一个唯一的不动点。在这里为了让学生理解不动点定理的
内容和证明，我们要克服许多技术上的数学困难，因此强有力的动机是非常重要的。
递归乌龟程序引出的神秘现象就提供了这一动机。
对这个定理的深刻理解是完全物有所值的，因为在本书中关于辐射度方法的一章中会再次用到这个不动点定理。
求解大规模线性方程组的Jacobi和Gauss-Seidel松弛法都是基于这个不动点定理的。某些超越方程的
递归求根算法也可以应用这个定理导出。在本书的结尾部分，通过细分方法，学生会发现B\'ezier和B样条
曲线也是迭代函数系统的不动点。这就有点儿令人吃惊了，光滑的多项式和分片多项式曲线居然与
分形也有关系。
从乌龟绘图和迭代函数系统的角度研究分形一般会用掉四周左右的时间，占一个学期15周时间的
四分之一稍多。这个时间安排是完全合理的。在这个过程中，学生除了得到视觉上过瘾的图形外，
还学习了点和向量，仿射坐标和仿射变换，矩阵计算，以及一个重要的不动点定理等。
他们还掌握了对高层次概念和低层次计算的清晰区分。有了这些准备，学生们可以开始学习三维空间
的知识了。
三维空间需要新的数学基础。在二维空间中，学生只需要用到坐标几何就可以将就了，但是在三维空间中，
坐标是有点儿令人难以理解的，而且有时会被繁琐的分析过程所困住。因此本书的第二部分开头就
给出三维向量几何的详细介绍，包括加法、减法、标量乘法、点积、叉积和行列式等。大多数计算机科学专业的学生在
之前的物理或者线性代数课程中已学过向量代数，但是他们对这些向量运算的几何理解是非常薄弱的。
这里给出的是从几何角度对向量方法的介绍，帮助学生掌握三维空间中的造型和解析几何知识。
计算机图形学既要用到点，也要用到向量。点不是向量，它通常是显示在图形终端上，因此本书在讨论了向量
空间和线性变换外，还讨论了仿射空间（点的空间）以及仿射变换。对大多数学生而言，仿射空间是一个新
的概念（他们第一次见到仿射组合这一限定时，可能会觉得非常生硬），但这种不熟悉就更是采用与坐标无关方法的
理由了。当层次没有被混淆的时候，当理论与计算是分开的时候，学生就会发现对点和向量的区分既是计算
上的需求，也是理论上的需求。因为点可以平移，而向量不平移。
应用向量技术，我们马上就可以导出所有的仿射变换和射影变换的与坐标无关的向量公式，这些变换
包括平移、旋转、镜像、放缩、错切以及正交和
透视投影等。它们在计算机图形学中有着广泛的应用。我们稍后还会采用矩阵方法表示这些变换。
我们给出的向量公式突出了变换（高层次概念）和对应的矩阵表示（低层次计算工具）之间的
区分。而这一观念在学生的思想中是经常被混淆的。当稍后引入矩阵以加速计算时，这些向量公式就用于推导
每个变换相应的矩阵表示。由于初始的向量公式是与坐标无关的，因此这些矩阵表示就不会像所描述
的那样，只能向坐标平面进行投影，或者绕坐标轴进行旋转，而是对于任意位置的投影平面
和旋转轴也行得通。
本书通篇用向量几何代替坐标计算。坐标是只用在低层次子程序中的，对加法、减法、标量乘法、点积、叉
积和行列式等进行计算。向量方法则是随处可见，用于推导度量公式，曲面方程以及求交算法等；
向量代数也用于计算光照模型的法向量，以及生成递归光线跟踪中的反射向量和折射向量。
坐标的正确用法是与计算机进行通讯，加速常用的特定计算。当引入了坐标后，在仿射空间中要对点和向量
进行理论上的区分，自然就导致了第四个坐标分量（这就是仿射坐标）的引入，用来对点和向量的直角坐标
进行区分。点的仿射坐标是1，而向量的仿射坐标是0。仿射坐标的引入导致要采用$4
\times 4$阶矩阵 表示仿射变换。
仿射空间的仿射变换类似于向量空间的线性变换。仿射变换把点映射为点，向量映射为向量，并且保持
仿射组合。因此仿射变换用矩阵表示时，第四个坐标（即仿射坐标）要被保持。平移、旋转、镜像、
放缩、错切以及正交投影等就是所有的仿射变换。
令人遗憾的是，只有仿射空间和仿射变换，还不足于对计算机图形学中遇到的所有几何进行建模。
透视投影就不是一个仿射变换。透视投影是不能用向量进行定义的变换；另外，如果点是位于过透视中心的
平面上，而且平面平行于透视平面，那么该点不被映射为仿射点，而更好像是被透视投影映射到无穷远。
因此为了讨论透视投影，我们需要一个更一般的包装空间以及更一般的变换集合。
为了解决这个问题，大多数的计算机图形学教材采用的是射影空间和射影变换。
射影变换包含所有的仿射变换以及透视投影。但是射影空间有几个很大的缺陷，
因而使得它不适合于作为计算机图形学的代数或者几何基础。
射影空间包含两种点：\kaishu
仿射点以及无穷远点。无穷远点对仿射空间进行了完备，即在仿射
空间中的平行线相交于射影空间中的无穷远点，因而透视投影定义在射影空间中
除透视中心外的所有点上。但是为了处理这些无穷远点，我们还需要额外付出很大的代价。
在一个观察者前面的无穷远点与观察者后面的无穷远点是相同的。因此在射影空间中，沿一个没有任何
遮挡的方向看去，观察者竟然会看到自己的后脑勺\!！上下、左右、前后，这些方向概念在视觉世界中扮演
着非常基础的角色，但是在射影空间中这些方向概念却没有了。射影空间的这一古怪几何让计算机科学专业
的没有经过复杂数学训练的学生感到非常不直观和难以理解。
更糟糕的是，在射影空间中的无穷远点取代了仿射空间中向量的地位。为了采用射影几何，计算机图形学
要抛弃掉向量几何，而向量几何又提供了大多数必要的数学分析的基础。例如，真实感光照模型需要用到曲面
的法向量：漫反射光和镜面光、反射和折射的计算都要用到曲面的法向量。
最后，射影空间不是一个线性空间。在射影空间中，我们不能对点进行加法，甚至不能进行点的仿射组合。
因此射影空间不是一个适合于用计算机进行大多数计算的恰当模型。矩阵计算是可以进行的，因此图形流水线
中用到的标准变换可以在射影空间中实现。但是，不提供点的代数，那么在射影空间中我们是不可能构造诸
如B\'ezier曲线或者B样条曲线之类的大量经典参数曲线和曲面的。类似地，没有加法或者标量乘法的概念，射影
空间也不支持基于线性插值的明暗处理算法。
如果我们用质点空间取代射影空间，那么就能克服上面所有的根本问题，无论是理论的或计算的，几何
的或代数的问题都包括在内。
质点形成一个向量空间。为了用一个标量乘以一个质点，只需要用标量乘以质量即可（质量可以是负数）；
为了把两个质点加在一起，则要应用杠杆的Archimede定律，即在初始两个质点的质心处放置的质量等于给定
两个质量的和。质点空间是四维的向量空间：前三维用于点，第四维用于质量。向量包括在质点空间中，定义
为零质量的质点对象；通过令所有点的质量为1，可以把仿射空间嵌入到质点空间中。
用质点空间取代射影空间，就是用一个四维的向量空间取代一个紧致的、不可定向的、非线性的三维流形。
维数的增加可以消除射影空间中几何上的不协调，方便了代数计算，而所需要做的只是对前述的表示进行
很小的修改。
质点空间拥有射影空间上述所有优点，而没有其任一缺陷。质点空间把仿射空间中的点和向量都包括进来，
因此在质点空间中，向量代数和向量几何仍然成立。质点空间是一个线性空间，因此在质点空间中
可以构造B\'ezier和B样条曲线和曲面，以及这些曲线和曲面的有理形式。由于质点空间是一个向量空间，
在质点空间中自然的变换就是线性变换。保质量的线性变换就恰是仿射变换；在质点空间中，透视
投影也是线性变换，只是它并不是保质量的变换。
在质点空间中工作还有另外的好处。在质点空间中，杠杆的Archimede定律可以用来导出
从任一投影中心向任一平面进行透视投影的公式。另外，从视景体（形状为平截头体）到立方体的经典变换的推导也
很简单，只需要对任意点经透视投影得到的像加上该点到投影平面的深度向量即可。只是这里的加法
是质点空间中的质点和向量间的加法，而不是通常的仿射空间中点和向量间的加法。在质点空间中的透视投影
给仿射点引入了额外的质量。为了得到从视景体到立方体映射的正确公式，这个质量是必须要考虑的。
由于质点空间是四维的向量空间，需要用四个坐标表示质点。第四个坐标保存着质量；前三个坐标保存
的是直角坐标乘以质量的结果。因此可以通过在前三个坐标中除以质量，恢复出点的直角坐标。注意，
上述对仿射坐标进行推广得到质点坐标的方式，使得第四个坐标，即质量可以取任意值。
质点的这种坐标定义方式看起来类似于射影点的齐次坐标，但有如下差别：具有不同质量的同一仿射点
在质点空间中表示不同的质点；具有不同齐次坐标的同一仿射点在射影空间中表示相同的射影点。实际上，
射影点是质点的等价类，这里如果质量是位于仿射空间中相同点处，就认为两个质点是等价的。
质点空间是四维的向量空间，因此质点空间上的线性变换是用$4 \times
4$阶矩阵表示的。从而无论是
在质点空间中，还是在射影空间中，我们都用相同的矩阵表示在仿射空间中相同的变换。这样，在质点空间中，
齐次坐标和射影变换的那些熟悉的计算公式仍然成立。
但这里有一个很大的意外收获，即可以在四维空间中进行向量乘法。在实际用到的向量空间中，只有在实数（一维）、
复数（二维）和四元数（四维）空间中可以定义有逆元的满足结合律的乘法。因此
四元数乘法就是质点空间中的乘法。我们工作在四维空间中，而不是在三维空间中，这并不是一个异常
现象；而应当认为我们是相当幸运的，因为在四维空间中，我们可以充分利用这个额外的
乘法结构。
从经典意义上讲，我们可以应用四元数代数中的丰富研究成果表示三维空间中向量的保形变换，这里
的方法就是把向量组装到四元数中，而不是给向量乘以$4 \times
4$阶矩阵。因此可以认为四元数
为保形变换提供了一种比矩阵表示更紧致的表示。另外，应用四元数乘法进行保形变换的复合
比应用矩阵乘法进行保形变换的复合，在速度上要更快一些。
在计算机图形学中，我们可以应用四元数更有效地避免保形变换中的退化情形（四元数很容易重新标准化），
从而（通过球面线性插值）可以进行关键帧动画的构造。在各种文献中散落着关于四元数的大量论述，但
我还从来没有见到一本好的教材，讲解计算机图形学中的四元数。很偶然地，质点的四维向量空间
把四元数很自然地包含进来；我们在引入四元数时，并不需要把它作为一个与射影空间无关的
额外特设的结构。
虽然四元数的形式代数在计算机图形学中已广为人知，但是对这一代数的几何原理
却没有被很好地理解。用于旋转和反射的夹心变换公式是有效的，但是对于学生来说
很难想到当初为什么会有人想到这个公式。
我们给出了更好的方法观察四元数。基于对复数平面上的乘法的代数和几何意义的研究，
我们可以了解四元数与三维空间中向量相乘的效果。我们提供了用于旋转和反射
的标准夹心变换公式的简单而直观的证明，在练习中还提供了用于透视投影
的夹心变换新公式。
我们的关键视点是来自于几何的。用单位四元数进行的乘法代表四维空间中的双等角旋转，
也就是说，在四维空间中存在着两个相互正交的平面，在其上四元数旋转同样的角度。
其中一个平面同构于复数，因此用单位四元数在其上进行的左乘和右乘把向量沿同一方向旋转同样的角度；
第二个平面同构于复数的四元数倍，因此用单位四元数在其上进行的左乘和右乘
把向量沿相反的方向旋转同样的角度。因此对于左乘而言，在两张平面上的旋转
都是逆时针方向的，但对于右乘而言，在一个平面上的旋转是逆时针的，而在另一个平面上的
旋转是顺时针的；所以四元数的左乘和右乘生成四维空间中的左右拧动。这一观察
结论使我们可以应用夹心变换把两个旋转组合在一起，以消去在两个平面中一张平面上
的旋转，因而导致在四维空间中另一个平面上的简单旋转。这些结论也就是
最终使我们可以应用单位四元数的夹心变换表示三维空间中的旋转和反射（以及透视投影）的理由。
因此在三维空间中这些基本变换就可以用四维空间中的简单旋转所表示。
在准备好这些适当的数学基础（包括向量几何和向量代数、质点和四元数乘法、仿射变换和透视投影等）
后，那么进行三维计算机图形学研究的所有技术工具就齐全了。
真实感渲染可以通过三种方法实现，即光线跟踪、多边形明暗处理和辐射度方法。本书对这三个主题
都进行了介绍。从概念上来讲，最直接的方法是递归光线跟踪，因此本书首先讲解这个方法。
递归光线跟踪是建立在递归计算反射光线和折射光线基础上的。通过利用前几章中研究的变换，这里引进了
两个新举措：反射光线是根据反射定律计算得到的，利用了相对于任意镜面的镜像映射；
折射光线可以根据Snell定律计算得到，利用了绕任意轴的旋转变换。实际上，这些反射和折射
计算方法都是留给学生的简单练习题。本书采用了一个更简单的方法，即把反射和折射向量分解为
正交分量，然后利用适当的光学定律和点积、叉积的简单数学运算对每个分量进行直接地分析。
因而由于所需要的数学基础知识已准备好，反射和折射光线就很容易计算出来了。
只有当学生要渲染的是极具视觉吸引力的曲面的时候，光线跟踪才有可能成为一个引人入胜的方法。
因此目前的状况为介绍某些经典曲面提供了自然的时间和地点。此处对曲面的研究只是局限在
对光线跟踪所需要的性质和计算上，如曲面的方程，曲面的法向量以及光线与曲面的交点等。
同样，向量方法和变换技术在曲面光线跟踪的创新方法中扮演着关键\linebreak
角色。
球面是最简单的非平面曲面。由于在球面上一点处垂直于球面的向量平行于从球心到该点确定的向量，
所以直线与球面的交点可以简化为直线与一个共面圆的交点。一旦球面研究清楚了，利用仿射和
投影变换，我们就可以很容易分析其他几种二次曲面的性质了。
椭球面是球面在非均匀放缩后的像。因此在椭球面法向量的计算中，可以先求出球面的法向量，然后
把这些法向量映射到椭球面上。光线与椭球面的交点也可以类似计算，即把光线和椭球面映射为
新的光线和球面，在计算新的光线与球面的交点后，把得到的交点映射回椭球面上。
接下来我们就研究圆柱面和锥面。球面是到一个点的所有等距点形成的轨迹。圆柱面是到一条直线的
所有等距点形成的轨迹。根据这个定义，我们就可以利用向量技术很容易地计算出圆柱面的法向量。
对于圆锥面，我们也可以给出类似的定义和法向量计算方法。在光线与圆柱面交点的计算中，
进行一个正交投影，把光线和圆柱面映射到一个垂直于圆柱轴线的平面上，从而转化为新光线与圆的
交点计算；接着再调用在光线跟踪球面时建立的算法，计算光线与圆的交点；最后，利用交点在直线上
的参数值求出在圆柱上的交点。光线与圆锥的交点可以类似地计算，只是要用从圆锥顶点进行透视投影
取代前面的正交投影。
任意的代数曲面和一般的参数曲面也可以用光线跟踪算法处理。对这些广泛的曲面类型而言，
我们提供了计算曲面法向量和光线与曲面交点的一般算法。圆环面既可以表示为代数曲面，
也可以表示为参数曲面，是一个形状熟悉，计算简单的（四次）曲面，因此
我们就把这些一般算法应用到圆环面上作为示例。
在曲面造型之后，我们接着讲解实体造型。本书介绍了实体造型的三种常用方法：构造实体几何（constructive
solid geometry，CSG），边界表示（boundary file
representation，\linebreak B-REP）以及八叉树。
构造实体几何方法非常适用于前述研究的光线跟踪和曲面造型。在CSG树中的基本形状通常是由平面
围成的实体、常见的二次曲面以及圆环面等。可以应用光线投射算法对CSG树进行渲染以及整体
性质的计算。边界表示在几何（即形状信息）之外，引进了拓扑（即连接信息）的概念，
方便了在模型中对重要特征的搜索。由于从CSG树向边界表示转化的算法通常都很复杂，
边界结构一般限定为多边形模型。为了使在渲染这些多边形模型时看起来为光滑的曲面，
我们需要应用多边形明暗处理方法。
多边形明暗处理方法是本书介绍的三种真实感渲染技术的第二种。本书对Gouraud和Phong明暗处理方法都
进行了讲解。虽然这两种明暗处理算法属于低层次的扫描线过程，但是我们则着重于如何应用向量方法，
设计出算法的精巧、快速、增量式的实现。鉴于学生在关键帧动画中用四元数表示旋转时曾
遇到了球面线性插值的应用，在Phong明暗处理方法中，我们也引入了球面线性插值技术。
隐藏面消除算法也是多边形模型真实感渲染所需要的技术。存在着大量的实用隐藏面消除算法，
本书综述了四种代表性的方法：$z$缓冲区算法、扫描线算法、深度排序方法以及BSP树方法。
$z$缓冲区算法
的实现是很简单的，但是扫描线算法是一种与Gouraud和Phong明暗处理方法结合得最好的隐藏面消除过程。
在本书中，仅当要描述扫描线算法时，我们才有意陷入到对低层次的坐标技术的讨论中去。
只当有对速度是相当渴求的时候，坐标技术才是适宜的。学生要知道，确实有那么几次，为了
快速地渲染，我们需要暂时局限到基于坐标的方法（\kaishu
凯撒的物当归还给凯撒$\cdots$）。与之相反，
深度排序方法却提供了对向量技术的几个巧妙应用，用于度量相对深度和寻找阻挡平面。最后，
BSP树是计算机科学中众所周知的重要的数据结构；当模型是固定的，而观察点或者光源可以改变位置的
时候，BSP树结构是寻找隐藏面的最有用的方法。
辐射度方法是能提供具有最真实感漫反射效果的图像的渲染方法。相对于递归光线跟踪方法，辐射度方法
柔化了阴影，刻划了渗色的现象。为了介绍辐射度方法，本书首先讲解了光照方程的连续形式，
然后把连续形式对应的积分方程简化为一个大规模的稀疏线性方程组。为了求解这个线性方程组，我们推荐使
用Jacobi和Gauss-Seidel松弛技术，这是学生在考察分形时，在不动点方法中已遇到的一种技术。这里对光能收集方法
和射击方法进行了探讨。
自由形式曲线和曲面构成本书的最后一个主题。至此为止，学生渲染的只是有限几张僵硬曲面，主要是
平面和二次曲面。但是为了忠实地表示更丰富的形状，如车体、轮船外壳、飞机机翼、玩具、鞋子，以及
大量的卡通动画角色等，几何造型主要研究自由形式的几何形状。因此本书就用表示、分析和渲染自由形式
曲线和曲面的技术作为结束。一般的计算机图形学教材至多对B\'ezier和B样条技术进行一个粗略的单独介绍。
与其形成鲜明对比的是，本书对B\'ezier和B样条逼近以及细分曲面的介绍提供了一个全面的统一的方法。
由于这些主题一般会用到一些复杂的数学，因此这里我们进行了一些创新，对陈述进行了简化。
在Gouraud和Phong明暗处理方法中，学生已熟悉了线性插值。对于B\'ezier和B样条曲线和曲面，我们提供了
基于逐次线性插值的动态规划过程：对B\'ezier曲线和曲面，这个过程称为$de
Casteljau$\kaishu 算法； 对B样条，这个方法就是$de
Boor$\kaishu 算法。
图示通常要比公式更容易理解。本书采用简单的数据流程图（即金字塔算法）为这些动态规划过程设计出了
一个通用的直接方法。我们鼓励学生绕过公式，直接根据这些流程图进行思考。一个通用的方法使得我们
能对通用的性质给出一个通用的推导，这些性质包括仿射不变性和非退化性等。从这些流程图中，
我们也可以生成B\'ezier曲线和曲面框架的混合函数的显式表达式以及递推公式。
开花为推导B\'ezier和B样条曲线和曲面的许多独特性质提供了一种最简单的，也是最直接的方法。根据格言“学生应当
\kaishu
用最恰当的数学解决手头的问题”，我尝试对开花方法进行了条理清晰和通俗易懂的介绍。
虽然对大多数学生而言，开花方法是全新的，但开花方法并不难。除了介绍开花的公理定义外，本书还讲解了
利用金字塔算法具体计算开花的过程。开花的金字塔算法与B\'ezier曲线的金字塔算法基本一致，只有一个
小小的修改，即在金字塔算法的每一层引入了不同的参数。因此开花方法的核心也是线性插值。
开花的标准性质，如对称性、多仿射性、对角性质、对偶泛函性质，以及存在性和唯一性等，
都可以直接从这些金字塔流程图中导出。
B\'ezier框架与开花是密切联系的，这是因为对应的金字塔算法就是紧密关联在一起的。根据对偶泛函性质，
一个单变量多项式的开花在参数区间的端点求值，就得到对应的B\'ezier控制点。因此开花方法就提供了B\'ezier框
架中对基函数进行变换的一般方法。利用开花方法，可以得到幂基与B\'ezier形式之间的转化，
升阶技术以及细分算法的推导。进一步地，基于de
Casteljau算法，利用开花的齐次变体可以推导出B\'ezier曲线的微分算法。
B样条与开花方法也是密切联系的。只要对B\'ezier曲线的de
Casteljau算法相应的开花解释进行一个小小的修改，
就得到B样条曲线的de
Boor求值算法，这里的修改就是开花不是在参数定义域的端点处求值，而是在相邻
的节点处求值。有许多入门性书籍中就用de
Boor算法作为B样条的定义。但是如果没有一个合适的诱因，
学生就不会理解这个递推公式的特殊之处。开花方法就提供了这个合适的诱因，而且它把de
Casteljau算法与de
Boor算法自然地联系在一起。与B\'ezier曲线时的情形一样，对样条的开花在一个节点处求值，就得到
对应的B样条控制点。因此开花也提供了对B样条的基函数进行变换的一般方法，从而在这里利用开花方法，
很容易推导出B样条的节点插入算法。同B\'ezier曲线时的情形一样，基于de
Boor算法，利用开花的齐次变体也可以
推导出B样条曲线的微分算法。随后我们就用这个微分算法证明B样条曲线的多项式段在节点处光滑相接。
细分技术是对B\'ezier曲面进行显示的关键。经过递归细分，de
Casteljau细分算法会生成收敛于B\'ezier曲面的
多边形近似。然后就可以应用光线跟踪、多边形明暗处理或者辐射度方法渲染这个多边形近似。对于B样条
曲面，节点插入算法扮演着类似的角色。
可以通过在控制点上乘以矩阵实现细分。对于B\'ezier框架，这些细分矩阵形成一个迭代函数系统。因此，
相当引人注目的一点是，可以通过在任意紧致集合上应用这个迭代函数系统，把B\'ezier曲线和曲面作为分形进行渲染。
因此本书内容完成了回归，以几乎是在本书开头部分引入的分形方法的讨论作为结束。
B样条的节点插入类似于B\'ezier曲线和曲面的细分。节点插入也可以用矩阵乘法表示，这些矩阵也形成一个
迭代函数系统。因此可以通过在任意紧致集合上应用这个迭代函数系统，把B样条曲线和曲面作为分形进行
渲染。本书在这里有一个创新之处，就是给出了如何把适用于均匀节点（即等距节点）
B样条的Lane-Riesenfeld细分算法推广到由Scott
Schaefer给出的适用于非均匀节点B样条的细分算法。
等距节点B样条的Lane-Riesenfeld节点插入算法是更一般细分框架的基本样式。因此本书最后一章
简要介绍了四边形和三角形网格上的一般细分曲面，包括箱样条、质心平均、Loop细分以及Catmull-Clark细分，
这些主题仍是目前研究的前沿。我们采用三种简单的示意图对每种方法进行解释：分裂和平均（箱样条），
质心平均（任意拓扑的网格），以及模板（Loop细分和Catmull-Clark细分）。模板
包括顶点、边和表面的模板以及异常点处的特殊模板。
至此我们就完成了对本书涵盖的所有主题的一个简短的概括。我们在本书中
有意忽略了许多主题，这并不是因为
它们是令人厌倦的，或者是无足轻重的，只是因为对于一个入门性的课程来说，它们要么
很高深（如基于物理的造型技术、科学可视化、虚拟现实等），要么太专门（如用户界面、图形硬件、输入设备等）。
一本优秀的教科书应当包括悠久历史的概览，短暂现在的略述，以及未知将来的猜测。编写一本优秀的教科书，
更像讲授一门引人注目的课程，就是在不停地做选择。包含哪些内容，删除哪些内容，
是由时间和体验做的决定。我尽力把注意力集中在
那些经得起时间考验的主题上，避免包括那些昙花一现的内容。显然，图形学软硬件的发展变化非常迅速，
但是如果图形学算法是基于已为大家接受的光照物理模型和有说服力的数学方法，那么这些算法的应用
时间应当很长。因此在本书中，我没有描述当前的图形学硬件，并且避免应用特定的编程语言（如C++）
和API（如OpenGL）。对诸如直线的绘制、多边形的填充和裁剪等低层次算法，我们都是一带而过，
以留下更多的时间和空间讨论诸如光线跟踪、多边形明暗处理和辐射度方法等高层次图形学技术。
在编写本书时，我尽力把内容写得读起来令人兴奋但不肤浅，严谨但不迂腐，创新但不怪诞。
我尽力把书稿保持
在较短的篇幅，期望学生和教师都能完整地读完本书。为了充实本书，我提供了大量的习题和编程作业，
但对许多主题，我是有意识地没有包含进来。我的计划是写一本“A Guide
for the Perplexed”\footnote书名中文直译为“困惑者指南”。该书是E.
F. Schumacher于1977年出版的一本很薄的专著。
Schumacher成名于他在1974年出版的环境经济学 畅销书“Samll Is
Beautiful”，但他本人认为“A Guide for the
Perplexed”是自己最重要的成就--- \kaishu 译者注。，而不是“Summa
Theologica”\footnote书名为拉丁文，中文直译为“神学概述”。该书
是由Thomas
Aquinas（1225--1274）写于1265---1274年，但未完成---\kaishu
译者注。。
当然，我要感谢所有在我之前进入计算机图形学领域的人们，包括图形学的奠基者和革新者、
科学家和数学家、纯粹学术人员和实践工程人员、认真的学生以及勤奋的教授们。
没有过去的启示，就不可能在其上建立起新的处理方法。但是$\cdots$，
每年有上万人参加Siggraph会议\footnote 会议名称为Special Interest
Group on GRAPHics and Interactive Techniques的缩写，是由ACM
Siggraph组织
的关于计算机图形学的每年一次的会议，为计算机图形学领域中最高水平的学术会议。
第一届会议开始于1974年---\kaishu 译者注。，
有上百篇论文投稿到Siggraph会议。即使其中只有很小百分比的人员和文章是重要的，也不能期望我
在这里把他们都列出来。
作为结束，我要请求我以前学生的原谅。原谅在过去我提供给你的那些沉闷的教学时光。我希望
借助于这些经历，我在这里可以做得更好。我从我的前辈们那里汲取了灵感，从我的同事们那里得到了鼓励，
从我的研究生们那里收获了建设性的评判。我相信这些对于完成本书是绰绰有余的。
每本书的寿命都是屈指可数的。本书与以前的书一样，由于理论和技术的创新，也不可避免地要被
淘汰。现在，三维图形硬件在技术上已是可行的。如果这些硬件变得普及，那么目前对二维
投影的关注在将来某一天就会过时，用户界面显然也要改变。随着在数学方面（如Clifford代数）
或者物理方面（如量子计算）的创新，本书的其他部分内容最终也会看起来就像它原来取代的那些
大部头一样枯燥和陈旧。教员今后在为课程选择教科书时，应当随时记住这一点。权威在争辩，
屏障在瓦解，原则在改变，共识在崩溃，学科在衰落，认识在落伍，时尚在逝去，思想在分裂，
规律在失效，方法在变异，正统在僵化，榜样在迷失；\kaishu
谁都无法逃脱机会与时间的掌控。
作者简介
Ron Goldman是美国德州休斯敦莱斯大学的计算机科学教授。
Goldman教授于1968年获得麻省理工学院的数学本科学位，然后于1973年获得约翰·霍普金斯大学
数学硕士和博士学位。担任期刊《Computer Aided Geometric
Design》副编辑，于2002年出版了题为《Pyramid Algorithms: A Dynamic
Programming Approach to Curves and Surfaces for Geometric Modeling》
的专著。
Goldman博士目前的研究兴趣集中在利用计算机对几何形状进行数学表示、操作和分析上。他的研究工作
包括了计算机辅助几何设计、实体造型、计算机图形学和样条。他对多项式和分片多项式
曲线、曲面的算法尤感兴趣，目前正在研究代数几何和微分几何在几何造型中的应用。
他在期刊、书籍和会议论文集中发表了关于上述课题及相关课题的学术文章超过100篇。
在返回到学术界之前，Goldman博士曾在企业界工作了十年之久，主要解决计算机图形学、
几何造型和计算机辅助设计中的问题。他担任“制造数据系统公司”(Manufacturing
Data System Inc.)
的数学研究员（Mathematician），帮助实现了一个早期的工业实体造型系统。随后他任
福特汽车公司的高级设计工程师（Senior Design
Engineer），主要负责增强公司所整合的图形学
和计算机辅助设计软件的功能。在福特工作了一段时间后，他又就职于“控制数据公司”（Control
Data
Corporation），担任计算机辅助设计和制造研发团队的首席顾问。他的职责包括数据
库设计、算法、教学、调查和研究等。
Goldman博士于1987年离开控制数据公司，成为加拿大安大略省滑铁卢大学计算机科学专业的副教授。
随后于1990年加盟位于美国德州休斯敦的莱斯大学，担任计算机科学专业的教授。
