1. 介绍

微信公众号链接

计算机图形学这个术语是用来描述使用计算机来创建和操纵图像的行为。本书将会介绍的这些算法和数学工具，可以用来创建各种各样的图像——逼真的特效，信息化的技术展示，或者美丽的计算机动画。图形学包括二维和三维；图像既可以完全电脑合成，也可以利用照片生成。本书主要介绍基础的算法和数学，尤其是用来合成三维物体和场景的图像的那部分算法。

实际上从事计算机图形学工作，不可避免需要了解特定的硬件，各种文件格式，还有通常需要了解一到两个图形学API。计算机图形学是快速发展的领域，所以各种知识也在不断变化。因此，本书会尽力避免讨论特定的硬件或者API。我们鼓励读者针对自己的软硬件环境去选择合适的文档作为本书的补充。幸运的是，计算机图形学领域已经有了足够多的标准术语，本书讨论的概念是可以适用于大多数的环境。

API : application program interface. 应用程序接口。

本章定义了一些基本术语，补充了部分历史背景，还有和计算机图形学相关的信息源。

1.1 图形学领域

对某个领域进行分类是个吃力不讨好的行为，但是大部分的图形学从业者都会认同计算机图形学的主要领域包含如下方面。

• 建模处理如何将物体的形状参数和外观属性存储到计算机的方法。
• 渲染，这个术语继承自艺术领域，指的是根据三维计算机模型生成着色的图片。
• 动画是通过一组图片来产生物体在运动错觉的技术。动画会利用建模和渲染的结果，但是会添加记录运动的关键数据，基础的建模和渲染模块通常不包含这些内容。

还有其他的很多领域和计算机图形学相关，至于它们是不是计算机图形学的核心内容，这个仁者见仁智者见智，但是也值得被提起。这些领域包括：

• 用户交互处理输入设备（如鼠标）和平板、应用之间的接口，给用户提供形象的感官反馈。从历史角度来看，这个领域和图形学有关联很大程度上是因为图形学研究员是最早接触到，而现在早已无处不在的输入/输出设备。
• 虚拟现实试图让用户沉浸在三维的虚拟世界。这通常需要立体图形学以及响应头部的运动。对于非常真实的虚拟现实，也需要声音和力学反馈。因为这个领域需要高级三维图形学和先进的显示技术，所以和图形学紧密关联。
• 可视化试图通过视觉展示让用户了解复杂信息。通常，在可视化难题中会涉及到图形学的一些议题。
• 图像处理处理二维图片的处理，在图形学领域和视觉领域都会涉及到。
• 三维扫描利用测距技术来创建测量三维模型。这些模型可以用来创建丰富的视觉画面，处理这些模型过程中通常会涉及到图形学算法。
• 计算摄影学是利用计算机图形学、计算机视觉和图像处理方法来实现以摄影方式捕捉物体、场景和环境的新方法。

1.2 主要应用

计算机图形学几乎无处不在，但是主要的计算机图形学技术的消费者来自以下行业：

• 电子游戏越来越多地使用复杂的三维模型和渲染算法。
• 卡通通常直接从三维模型渲染得到。很多传统的二维动画使用从三维模型渲染得到的背景，这样就不需要耗费大量艺术家的时间来处理移动的视角问题。
• 特效几乎使用了所有类型的计算机图形学技术。几乎每一部现代电影都会使用数码合成技术来叠加背景。许多电影也会使用三维模型和动画来创建几乎可以以假乱真的人工合成环境，物体，甚至角色本身。
• 动画电影使用了和特效相同的技术，但是对真实性的要求没那么高。
• CAD/CAM分别代表 计算机辅助设计（computer-aided design） 和 计算机辅助制造（computer-aided manufacturing）。这些领域利用计算机技术在计算机上设计零部件和产品，然后使用这些虚拟设计来指导制造流程。例如，许多机械部件是在一个三维计算机建模软件包中设计然后在一个计算机控制的铣削设备中自动生产。
• 仿真可以被认为是精确版的电子游戏。例如，飞行模拟器使用复杂的三维图形来模拟驾驶飞机的体验。这类仿真对于在安全至关重要的领域的初期训练非常重要，例如驾驶培训；例如特定的消防情景，如果要给经验丰富的使用者提供真实的实景训练，这样花费很大而且非常不安全（可以使用仿真训练替代）。
• 医学成像为扫描的患者数据创建有意义的图像。例如，CT(X射线计算机断层成像)数据集是一个存储了密度值的大型三维矩形数组构成。计算机图形学用来创建着色图像，来帮助医生提取最突出的信息。
• 信息可视化创建通常为没有“自然”视觉描述数据常见图像。例如，十个不同股票价值的时序趋势通常没有明显的视觉描述，但是智能化的绘图技术可以帮助人们看见隐藏在诸如这些数据背后的模式。

1.3 图形学API

使用图形学库的关键部分是和图形学API打交道。应用程序接口(application program interface, API) 是指用来执行相关操作的一组函数，图形学API就是一组执行如将图像或者三维表面绘制到屏幕的窗口这些基础操作的一组函数。

每个图形程序都需要两个相关的 API ：一个用于可视化的输出；另一个用来获取用户输入。对于图形学和用户交互API而言，目前有两种主流范式。一种是集成，以Java为例，其中图形和用户交互工具包被集成到标准的可移植的库，作为语言的一部分予以支持。还有一种是Direct3D和OpenGL的处理方式，绘制命令作为C++的软件库的一部分，用户界面软件是一个独立的部分，会因系统而异。后者的处理方法有一个问题，需要编写可移植的代码就会很麻烦，哪怕那个程序很简单，可能会选择使用一个可移植库来作为封装系统特定的用户交互部分的代码。

无论你使用哪种API，基础的图形学调用基本上都是一样的，这本书中的概念都会适用。

1.4 图形管线

如今每台电脑都有强大的三维图形管线。这是一套特殊的软/硬件子系统，用来高效绘制透视图中的三维图元。通常情况下，这些子系统是为处理共用定点的三维三角形而优化。流水线中的基本操作将三维位置映射到二维屏幕位置，并对三角形进行着色，让它们看起来真实，而且会以正确的前后顺序来展示。

虽然以合法的前后顺序绘制三角形曾经是计算机图形学中最重要的研究课题，但是目前总是用 z-buffer 来解决，使用了一个特别的内存缓冲区用蛮力解决这个问题。

事实证明，图形管线中的几何操作几乎完全可以在四维坐标系中完成，这个四维坐标由传统的三维顶点坐标和第四个 齐次坐标（homogeneous coordinate） 组成。这些四维坐标可以通过 矩阵和四维向量来运算。因此图形管线中会包含很多高效处理和组合这些矩阵以及向量的机制。这个四维坐标系是计算机科学中最微妙和精美的结构之一，同时也是在学习计算机图形学中最难以逾越的智力难关。每本计算机学图书的第一部分总要占据大量篇幅来介绍这些内容。

图像生成的速度很大程度上取决于绘制的三角形数量。因为在很多应用中，交互性要比视觉效果更重要，所以减少表示模型的三角形数目是值得的。此外，如果从远处观测模型，和从近处观测相比，只需要更少的三角形。这表明使用 层次细节（level of detail, LOD） 来表示模型是很有效的方法。

1.5 数值问题

很多图形学程序实际上就是处理三维数学的代码。数值问题在这类程序中至关重要。在“旧时代”，想要以健壮并且可移植的方式处理这些问题非常困难，因为机器对数值有不同的表示方法，更糟糕的是，处理异常的方式也各不相同，并且不兼容。幸运的是，几乎所有的现代计算机都会遵循 IEEE 浮点数标准 （IEEE 标准协会， 1985）。 这样就允许程序能够确定特定的数值问题会如何被处理。

尽管IEEE浮点数标准有很多对编写数值算法很有价值的特性，但是对于图形学中遇到的大部分情况，只有少数特性非常重要。首先，也是最重要的一点，IEEE浮点数中有三个“特殊”值：

1. 无穷大 。这是一个比其他所有合法数字都大的合法数字。
2. 负无穷大 。这是一个比其他所有合法数字都小的合法数字。
3. 非数值（NaN，not a number）。这是一个由未定义结果的操作造成的非法数字，例如0除以0的情况。

IEEE浮点数的设计者制定了一些对于程序员来说非常方便的规则。其中的很多与上面处理异常（例如除以0）产生的三个特殊值有关。在这些情况下，异常会被记录，但是很多情况下，程序员可以忽略这些。具体来说，对于任何正实数 ，下面的规则涉及到除以无穷大的情况：

IEEE 浮点数有两种表示零的方式，一种被视为正数，一种被视为负数。 和 只会在少数情况下有区别，但是也需要记住这个事情。

另外一些涉及到无穷大值的操作符合人们的期望。同样对于正实数 ,行为如下：

和无穷大数值相关的布尔表达式的规则如下：

1. 所有有限合法数值都比正无穷大 要小；
2. 所有优先合法数值都比负无穷大 要大；
3. 负无穷大 比正无穷大 要小。

IEEE浮点数中重要的的一个方面就是定义了除以零的问题；对于任意正整数 , 定义了如下的行为：

需要注意 的情况。

如果程序员利用了IEEE的规则，很多数值计算就会变得很简单：

这种表达式经常出现在电阻和透镜相关问题上。如果除以零将会导致程序崩溃（在IEEE浮点数之前的很多系统确实如此），所以那时候就需要两个 if 语句来检查 和 是否为很小的数或者零。反而，如果使用IEEE浮点数，如果 或者 的值为零，我们将会得到 也为零。另一个避免特殊的检查方法是利用NaN的布尔特性。考虑下面的代码：

a = f(x)
if (a > 0) then
 do something

此时，函数 可能会返回一个例如 NaN 或者 之类的“丑值”，但是如果 if 语句是定义良好的：对于 是 NaN 或者 的情况，判定条件为 false，如果 是 则为 true。再决定返回哪些值的时候要小心， if 语句通常可以做出正确的判断，不需要额外的检查。这些手段使得代码更小，更健壮和高效。

1.6 效率

并没有魔力法则来让代码更高效。效率是通过仔细的权衡来实现的，而这些权衡通常因架构而异。然而，在可预见的未来，一个合理的启发是，相较于运算次数，程序员应该更加关注内存访问模式。这和二十年前的经验刚好相反。发生这种转变的原因是内存访问的速度没有赶上处理器的速度。由于这种趋势仍在继续，有限和连续的内存访问对于优化至关重要。

让代码高效的一个合理方法是按照下面的步骤来进行，只采取必要的步骤：

1. 尽可能以最直接的方式来写代码。每次都直接计算中间变量，不缓存。
2. 用优化模式编译代码。
3. 使用剖析工具找到关键的性能瓶颈。
4. 检查数据结构，找到有没有方法利用局部性原理改善性能。如果可以的话，尽量让数据单位大小和目标平台的缓存/页面大小匹配。
5. 如果剖析工具表示数值计算存在瓶颈，可以检查编译器生成的汇编代码找到低效的原因。重写代码来解决找到的任何问题。

这些步骤中最重要的是第一步。大多数所谓的“优化”代码并没有提升性能，反而让代码更加难以阅读。此外，预先优化代码的时间其实更应该花在修复缺陷和添加特性上。另外，需要警惕来自古老文本里面的优化建议；一些古老的技巧，例如尽可能使用整数来代替实数，在现代的CPU架构下面通常不太有效，因为现代的CPU在处理两种运算时速度一样快。在所有情况下，任何优化都需要在特定机器和编译器上通过剖析器来确认是有价值的。

1.7 设计和编码图形学程序

在图形学编程中有一些常用的策略。这一节，我们提供了一些实现书中方法可能很有用的建议。

我强烈推崇 KISS （“Keep it simple, stupid”，保持简单，易于理解） 原则，从这个角度来看，两个类的论点不足以为增加复杂性而辩解。 ——P.S. 【P.S. 代指本书的一位作者 Peter Shirley。同理，S.M. 代指另外一位作者 Steve Marschner】

1.7.1 类设计

任何图形程序的一个关键点就是为向量和矩阵，以及如 RGB 颜色和图像等图形实体设计良好的类和例程。这些例程应该设计得尽可能简单和高效。一个通常的设计问题是，位置和位移是否应该拆成两个独立的类，因为它们有不同的操作；例如，位置的一半没有几何意义，而一个位移的一半有意义（Goldman, 1985; DeRose, 1989）。这个问题上几乎没有共识，可能会让图形学从业人员引发数小时的激烈辩论，但是为了举例，我们假设我们不会区分它们。

我喜欢把点和向量分来，这样让代码更易读，编译器也可以捕获到一些缺陷。 —— S.M.

一些需要编写的基础类如下：

• vector2 二维向量，存储 和 坐标分量。应该使用一个长度为2的数组来存储，这样就可以支持下标来访问。同时也应该支持向量加法，向量减法，点乘，叉乘，标量乘法，和标量除法这些操作。
• vector3 类同于二维向量的三维向量。
• hvector 有四个分量的齐次向量（参见第8章）。
• rgb 存储了三个分量的RGB颜色。也应该支持RGB加法，RGB减法，RGB乘法，和RGB标量乘法和RGB标量除法。
• transform 用来表示变换的 矩阵。应该包含向量乘法和成员函数来处理位置、方向、表面法向量。正如第7章所展示的，这些都不相同。
• image 一个存储了RGB像素值的二维数组，支持输出操作。

除此之外，你可能想（也有可能不想）添加一些用来处理区间，标准正交基和坐标系的类。

你获取还考虑使用一个特殊类来处理单位向量，但我发现它们带来的痛苦超过它们的价值。

1.7.2 单精度浮点数和双精度浮点数

现代架构表明，降低内存使用和保持内存连续访问是提高效率的关键。所以建议使用单精度浮点数。然后，想要避免数值问题又建议使用双精度浮点数。这个权衡取决于程序，但是类定义中有一个默认值开关是很好的。

我建议在几何运算中使用双精度浮点数，在颜色计算中使用单精度。对于占用大量内存的数据，例如三角形网格，我建议存储成单精度浮点数，但是在成员函数访问的时候，将其转换成双精度浮点数。—— P.S.

我主张使用单精度浮点数进行所有计算，直到你发现代码的特性部分需要使用双精度浮点数的明显证据时。——S.M.

1.7.3 调试图形程序

如果你到处打听，你就会发现当程序员变得越来越有经验，他们就越少使用传统的调试器。其中的一个原因就是和简单程序相比，对于复杂程序而言，使用这样的调试器会更加难以处理。另外一个原因是，最困难的错误往往是因为实现错误导致的概念性错误，这种情况往往浪费了大量时间调试却难以找到问题原因。我们发现了几种在图形学领域比较有用的调试技巧。

科学方法

在图形程序中，有一种替代传统调试的方法通常非常有用。它的缺点是，它非常类似于在程序员的职业生涯早期被教导不要去做的事情，所以如果你这样做，你可能会觉得自己非常“淘气”：我们创建一个图像，来观察它错误的地方。然后，我们提出一个假设来猜想问题的原因然后开始测试。例如，在光线追踪程序中，我们可能会遇到个问题，有一些随机的像素比较暗。这个是很多人在写光追器会遇到的经典“暗疮”问题。传统的调试器丝毫没用；相反，我们必须认识到阴影射线射中了已经在阴影中的表面。我们可能会注意到，暗像素的颜色往往是漫反射的颜色，所以丢失的是直接光照。直接光照可以在阴影中关闭，所以你可以假设这些点被错误地标记到了阴影中，虽然它们并不在其中。为了验证这个猜想，我们关闭掉阴影检测然后重新编译。这就可以标明这些是错误的阴影测试，然后我们可以继续我们的侦探工作。这个方法有时候非常有用的原因是我们从来不需要定位到错误的现场或者真正确定概念性错误。相反，我们只是不断在实验中缩小错误原因的范围。通常情况下，只需要进行几次尝试我们就可以搞定事情，这种类型的调试是非常愉快的。

将调试结果作为图像输出

在很多情况下，从图形程序获得调试信息的最简单的方式就是输出图片自身。如果你想要知道在所有像素上都会计算的某些变量值，你可以临时修改程序，将这个值直接拷贝到输出图像上，然后跳过剩下的计算过程。例如，如果你怀疑是法线向量引起的着色问题，你可以将法向量的值直接拷贝到图像上（ 代表红色， 代表绿色， 代表蓝色），这样就将计算过程中的向量值转成了颜色编码的值。或者，如果你怀疑某个特定值有时候超出了它的有效范围，可以在这些异常值的地方写入亮红色像素值。其他常用的技巧包括用明显的颜色绘制处在背面的表面（当它们理论上是不可见的时候），通过对象的ID来给图像着色，或者通过计算花费的时间来给像素着色。

使用调试器

仍然存在某些情况，特别是当使用 科学方法 导致了矛盾的时候，当没有什么替代项来观测究竟发生了什么的时候。问题在于，图像程序通常是很多相同的代码的执行（例如，每个像素执行一次，或者每个三角形执行一次），这使得从头开始调试几乎不可能。而且一些很难的缺陷通常是因为特定的输入引起的问题。

一个有用的方式是为缺陷“设置一个陷阱”。首先，确保你的程序是确定性的——在单个线程中运行程序，并且确保所有的随机数都是通过固定的种子计算得到。然后，找到出现问题的像素或者三角形，然后在你怀疑有问题的代码前面添加一个语句，只有当你怀疑的原因出现时才会执行这个语句。例如，如果你发现像素（126，247）是有问题的，你可以添加如下的代码：

if x = 126 and y = 247 then
 print "blarg"

如果在print语句上设置了断点，你就可以在只感兴趣的像素上进入调试器。有些调试器有“条件断点”特性，可以在不修改代码的情况下实现相同的功能。

在程序崩溃的情况下，传统的调试器可以用来定位崩溃的位置。然后，你应该在程序中开始回溯，利用断言和重新编译代码，找到出问题的地方。这些断言应该留在程序中，防止后面添加的特性引发新的缺陷。这就可以避免了有一次的一步步调试，因为也不会向程序中添加新的断言程序。

使用固定的随机数种子的特殊调试模式非常有用。

数据可视化的调试方法

通常，很难理解你的程序正在做什么，因为在最终出问题之前计算了大量的中间结果。这种情况和测量大量数据的科学实验很相似，所有有一个相同的解决方案：为自己制作良好的图标和插图来帮助理解数据的含义。例如，在光线追踪器中，你可以编写代码来可视化射线树，这样你就可以看到哪些路径贡献了某个像素，或者在图像重采样中，使用图表来确定输入中的哪些点被用作采样点。花费在将程序的内部状态可视化的时间是值得的，可以帮助更好的理解代码行为，从而帮助后面的优化过程。

我喜欢把调试的打印语句格式化成为 MATLAB 或者 Gnuplot 的脚本，这样可以直接绘图。—— S.M.

参考资料

关于软件工程的讨论受 Effective C++ 系列（Meyers，1995，1997），Extreme Programming运动（Beck & Andres，2004），The Practice of Programming （Kernighan & Pike，1999） 影响。关于实验性调试的讨论是基于和 Steve Parker的讨论基础之上。

有很多和计算机图形学相关的年度会议，包括 ACM SIGGRAPH 和 SIGGRAPH Asia，Graphics Interface，GDC（Game Developers Conference，游戏开发者大会），Eurographics， Pacific Graphics， High Performance Graphics，The Eurographics Symposium on Rendering，以及IEEE VisWeek。这些都很容易通过名字在网络搜索上找到信息。