Chapter 1  Introduction

第一章简介

计算机图形学涵盖了任何使用计算机去创建和对图像进行处理的事儿。这本书介绍了大量的可用来创建所有类型图像的算法和数学工具-写实的视觉效果、提供了大量信息的技术图像或者是好看的电脑动画。画面可以是2维或者是三维的，可以完全是由人工合成的也可以是通过对照片进行处理得到的。这本书主要讲的是关于基础算法和数学工具，尤其是那些处理3D物体和场景生成画面的算法。

在涉及到计算机图形学的时候不可避免的需要知道某些特定的硬件架构、文件格式并且通常你还需要了解某一两个图形硬件API（参考1.3章节）。计算机图形学是一个经常会被别的领域所使用的领域，所以牵涉到的相关的特定的知识也是因为领域不一样而不一样的。因此，本书我们将尽可能的避免去依赖任何硬件或者API来进行知识的讲解。我们非常鼓励读者们自行补充自己的软件和硬件开发环境下的与图形学编程相关的其他知识。幸运的是，计算机图形学已经形成了足够多标准的词汇，并且在本书中我们讨论的这些概念能够非常好的被映射到大部分的开发环境中去。

本章节定义了一些基本的术语并且提供一些计算机图形学的历史背景，以及与计算机图形学相关的信息源。

1.1 图形学领域

通常来说，把概念强行套在事物上是非常不好的，但是大部分图形学的专家都会同意下面的这些计算机图形相关的论述：

● 建模主要是指一种能把形状以及形状外观的描述以数学的方式存储在计算机上的方法。举个例子，一只喝咖啡的杯子可能会通过一堆顶点来进行描述以及存储了如何使用这些顶点通过何种插值方法来连接成为这个杯子，附带的还存储了这个杯子会如何与灯光进行交互。

● 渲染则是从艺术那边借用过来的一个词汇，它是指如何通过一个3D计算机模型来生成一张图像。

● 动画是一个通过连续的图片序列来生成动画的这种错觉的技术。动画在使用了建模以及渲染的同时还增加了根据时间进行运动这一关键事物，而这部分内容通常来说不是基本的建模和渲染所需要处理的事情。

其他的很多领域也涉及到图形学的应用，那些领域是否是计算机图形学的核心研究领域则见仁见智。本书将会简单那的提及一下那些领域。那些相关的领域包括了这些：

● 用户交互处理的是输入设备比如鼠标和手写板与应用程序之间的交互接口，应用程序会通过画面改变的方式来反馈给用户输入结果。这一部分内容之所以跟计算机图形学有关是非常可能的原因是图形学的研究人员可能是最早一批接触输入输出设备的人，这些输入输出设备在今天看来已经变得非常的普遍了。

● 虚拟现实则试图让用户沉浸在3D的虚拟世界中。这种一般来说都需要至少两个画面并且产生的画面要对头部的动作做出及时的反馈。对于真正的虚拟现实来说，声音以及力的反馈也应该被支持。由于这一块需要高级的3D图形技术以及高级的显示技术，它通常情况下是紧密的与图形学相联系的。

● 可视化试图通过可视化的展示方式给到用户复杂数据的深度解读。通常情况下，在可视化方案中会出现很多与图形学相关的问题要解决。

● 图像处理说的是2D图像运算的部分，并且通常情况下载计算机图形学和计算机视觉领域都会涉及到图像处理的模块。

● 3D扫描使用范围查找的技术去丈量3D模型。这些模型在创造优质画面效果方面是非常有用的，通常情绪下，处理这样的模型会牵涉到图形学的算法。

● 计算机摄影学通过计算机图形学，计算机视觉以及图像处理的方法来创造了全新的为物体，场景以及环境进行摄影的方式。

1.2 主要应用

计算机图形学几乎可以在任何领域内使用，但下面列出来的这些产业是主要的计算机图形学的应用者：

●电子游戏业对复杂3D建模和渲染算法的要求日益增加。

●卡通动画通常是直接通过3D模型渲染出来的。很多传统的2D卡通动画使用的背景是直接通过3D模型渲染出来的，如此一来，既能够生成连续的序列帧动画，又不需要画师花费大量的时间去手工的绘制出来这些动画帧。

●视觉效果几乎会用到全部种类的计算机图形学技术。几乎所有的电影都会使用数字合成的方式去把电影的背景和前景进行合成。很多电影也会使用3D建模技术以及动画技术来对环境、物体甚至是电影角色进行合成，并且观影者不会觉得视觉上有什么不妥的地方。

●动画片会使用跟视觉效果一样的技术，只不过做视觉效果的时候你不需要去让图片看起来显得真实。

●CAD/CAM是Computer-Aided Design和Computer-Aided Manufacturing的缩写。这些领域会使用计算机技术去设计部件以及产品，然后使用这些虚拟的设计去指导工厂的生产流水线。比如说，很多机械设备通过一个3D建模软件设计然后自动的通过电脑控制的设备进行生产。

●虚拟模拟技术可以被想象成为一个精确的视频游戏。比如一个飞行模拟器会使用复杂的3D图形技术来模拟控制一个飞机时候的感觉。这样的一些虚拟模拟在需要注意安全的领域训练菜鸟是非常有帮助的，比如说驾驶技术，另外，对于那些在现实世界中要进行训练花费太大或者太危险的训练，即便是为有经验的人准备的，比如消防灭火模拟，也可以使用虚拟模拟技术来实现。

●医疗造影能够通过扫描病理数据生成有意义的图片。比如CT，它就是通过一大堆密度数据来合成图像来帮助医生找到那些密度数据里有用的信息。

●数据可视化可以将一些并非“天然”具备可视形式的数据转换生成图片。比如随着时间的推移，十只不同股票的价格没有呈现出比较明显的趋势，但是通过一些有效的绘图技术可以帮助人们发现那些数据的规律。

1.3 图形API

与某个图形API打交道最重要的一个方法是使用图形库。一个应用程序编程接口是一个标准的执行一系列相关操作的函数的集合，图形API就是一些执行基本的诸如把图像和3D表面绘制到屏幕上的窗口里去的操作的函数集合。

每一个图形程序都需要使用两套相关的API：一个是图形API用于视觉效果的输出，另一个是用户API获取用户的输入。当下有两种主要的途径来使用图形和用户API，其中的第一种方式被称为集成方法，比如说Java，在Java编程语言中，图形和用户API已经被充分的进行了标准化，被当成编程语言的一个部分通过可发布的包的方式进行发布。另一种方式就是通过Direct3D或者OpenGL的方式来使用，当你使用这种方式的时候，绘制指令就是软件库的一个部分，你可以通过某种编程语言去访问，比如C++，这时用户API部分会因为具体的操作系统的不一样而不一样，它是一个独立于编程语言的存在。在后面的这种方式中，要撰写出可移植的代码是非常有难度的。

无论你选择哪种方式，基本的图形调用方式是差不多的，并且本书中的这些概念都适用。

1.4 图形管线

现在每一个台式机都有一个非常强大的3D图形渲染管线。这是一套特殊的能够高效绘制3D图元的软/硬件子系统。通常情况下，这些系统都对共享顶点的3D三角形的绘制进行了优化。这套3D渲染管线最基本的操作就是把一个3D顶点投影到2D屏幕上并且给这些三角形涂上颜色使得它们不仅看起来很真实而且能够正确的表达出3D世界中物体的前后遮挡关系。

尽管曾经在计算机图形学领域研究将三角形从后往前的按照顺序绘制出来是一个非常重要的问题，它现在基本上已经通过z-buffer的方式解决了，z-buffer使用的是一个特殊的内存缓冲区，它非常简单粗暴的就把这个问题给搞定了。

在图形渲染管线中的几何运算基本上可以通过传统的三维几何坐标额外的加上第四个分量组成四维的齐次坐标在4维空间中完成运算。4维坐标运算使用的是4x4的矩阵和4维向量。因此，这些图形管线包含了大量的能够高速处理这些矩阵和向量的硬件。这套4维的坐标系统是计算机科学里最精妙的一套设计了，所以要学计算机图形学的人也面临着掌握这套系统的挑战。每一本图形学书籍的第一部分都会花费大量的篇幅来讲解这些坐标系统。

绘制图像的速度很大程度上取决于绘制三角形的数量。在很多应用程序中，程序的可交互性的重要性是大于视觉效果的，所以有时候我们会需要去用尽可能少的三角形去表达一个模型。另外，一个模型在比较远的地方的时候对其进行呈现所需要的三角形的数量会比它放在更近位置时候要更少，因此，使用多级的LOD（level of detail）去表达一个模型非常有用。

1.5 数值问题

有很多图形应用程序本质上来说仅仅是由一些处理3D数值计算的代码构成。在这样的程序中处理好数值问题非常关键。以前，做出既稳定又可移植的代码是比较困难的，因为不同的设备对数值的内部编码方式是不一样的，更糟糕的是异常处理的方式是不同且互不兼容。幸运的是，几乎现代所有的计算机都遵循了IEEE浮点数标准。这就使得程序员们能够在解决某个特定的数值问题的时候做出很多合理的假设。

在实现数值算法的时候，尽管IEEE的浮点数标准能够提供很多有价值的特性，但在解决图形学问题的时候，只有一小部分是比较关键的。第一个也是最重要的一点就是在IEEE的浮点数标准里的三个“特殊”的值定义：

1、正无穷(∞)。这是一个大于任何其他数值的有效数。

2、负无穷(−∞)。这是一个小于任何其他数值的有效数。

3、非数值（NaN)。这是一个无效数，它可能是由一系列未定义非法操作序列引起的，比如某个计算过程中出现了一个操作0除以0。

IEEE浮点数标准的设计者做出了一些对程序员非常友好的决定。其中在处理异常的时候很多都跟上面提到的三个特殊的数值有关系，比如除0异常。在处理这些情况的时候会报一个异常，但是大部分情况下，程序员你可以忽略这个异常。特别是对于一个任意的正实数a，在涉及到被无穷除的时候有下面这些规则：

+a/(+∞) = +0,

−a/(+∞) = −0,

+a/(−∞) = −0,

−a/(−∞) = +0.

其他牵涉到无穷数值的操作会表现得跟你期望的那样。再一次对于一个正实数a，有下面这样的一些运算规则：

∞+∞ = +∞,

∞−∞ = NaN,

∞×∞ = ∞,

∞/∞ = NaN,

∞/a = ∞,

∞/0 = ∞,

0/0 = NaN.

做布尔运算的时候，无穷数值的运算会有下面这样的规则：

1、所有有效的无穷数值都比+∞小

2、所有有效的无穷数值都比-∞大

3、-∞比+∞小

对于哪些牵涉了NaN的表达式，规则比较简单：

1、任何牵涉了NaN的数值运算的结果是NaN

2、任何有NaN参与的布尔表达式的结果都是false

或许IEEE浮点数标准做出的最有用的假设就是关于除0的时候该如何处理。对于任意一个正实数a，如果运算中涉及到除0的操作，那么有下面的规则：

+a/ +0 = +∞,

−a/ +0 = −∞.

如果程序员利用好IEEE的浮点数标准的话，很多数值运算会变得非常简单。比如，考虑到下面的这样一个表达式：

我们需要从硬件层来思考这样表达式。如果在应用程序中出现了除0的操作，那么应用程序会崩溃，然后如果表达式需要去检查b或者c的值是否是非常小的数值或者是否是0，考虑到IEEE的标准，如果b或者c是0，那么我们直接可以说a的值就是0。另一个非常通用的可以避免特殊情况检查的技术就是善用NaN的布尔属性。我们看看下面这段代码：

这里，函数f可能会返回很多奇怪的值比如∞或者NaN，此时我们看if语句：当a是NaN或者a是-∞的时候，if语句为false，当a是+∞的时候，if语句为true。此时我们再来考虑从函数f返回出来的可能的数值，这里即便没有对一些边际情况进行特殊处理，按照IEEE浮点数标准，这个if语句也是可以正常工作的。如此一来我们就可以看到，IEEE浮点数标准使得程序更加简洁，更加的稳定，并且更加的高效。

1.6 效率

没有什么神奇招式能够使得代码变得更加的高效。通常情况下，我们会通过一些折中的方案来获得性能的提升，并且对于不同的架构来说，这些折中方案的具体执行方法是不一样的（这或许就是每个项目的优化具体手段不一样的原因）。然而对于可预见的未来，对于程序员儿来说一个非常好的启示就是应当在内存访问方式上花更大的力气而不是更关注执行的指令操作的次数。这与二十年前完全相反。这一转变的原因就在于内存的访问速度的提升没有跟上处理器速度提升的节奏。随着这一趋势的发展，尽可能限制访存和保持访存连续对于性能优化的重要性日益增加。

依次使用以下一些方法有助于使得代码跑得更快，这些步骤可以只采纳实际必须的：

1、编码时尽可能简明直接。根据需求直接在运行时计算出某些算法的中间数据而不是把它们存储在什么地方然后读出来。

2、编译程序的时候开启optimized模式

3、使用现存的工具来检查出程序最严重的性能瓶颈在哪

4、检查数据结构以提升局部性，尽可能这些数据单元的大小与目标硬件的cache/page的尺寸相匹配。

5、如果检测出来瓶颈出现在一些数值运算的环节，通过检查编译器编译的汇编代码来查看是哪里造成的性能损失。当你发现了那些损耗比较大的指令的时候，重写那部分源码来解决那些问题。

上面列出来的这些点中，最终要的就是第一条。有很多自称“性能优化”的操作使得代码很难被读懂，但是实际上它们却没有使得代码跑得更快；并且，提前搞这些所谓的性能优化的事情的时间还不如花去修BUG或者增加更多的码更多的功能。然后，你还要小心从一些比较旧的书上流传下来的一些建议，因为一些古老的编程技巧比如通过使用整型来代替浮点数来获得性能提升的方法可能不再能够提升速度，因为现代的CPU处理浮点数运算的速度已经跟处理整形速度不相上下了。最后，你必须要确定的事还有，你需要通过性能分析来确保某种优化对于某个特定的机器或者编译器来说有作用的。

1.7 图形程序的设计与编程

在写图形程序的时候有一些通用的有效策略。本节中，我们会提供一些当你去实现本书中学到的一些图形学方法的时候可能会非常有帮助的建议。

1.7.1 类设计

对于图形程序来说，一个非常关键的部分就是拥有一个良好的类的设计或例程去描述几何实体比如向量和矩阵，同样也可以用来管理图形实体对象比如说RGB颜色和图像。这些例程必须设计的尽可能的干净和高效。一个常见的设计方面的问题就是是否用不同的类来描述位置和位移，因为它们有着不同的操作。举个例子，一个位置被二分之一乘没有什么几何学上的意义，而一个位移则有意义。在这个问题上几乎找不到任何统一的答案，如果在这个问题上往死里抠的话，几乎不能在图形学专家之间取得共识，所以我们先把争议搁置在一边，我们下面列举出来的只是一个参考样本。

这就意味着我们需要写一些基础的类包括：

●vector2. 一个包含x和y分量的2D向量类。这些组成部分应该被存储在一个长度为2的数组里，这样一来这个类就比较容易支持索引操作符的操作了。你应该还为它添加向量的加、减、点积、叉积、标量乘法以及标量除法等操作方法。

●vector3. 一个与vector2类似的3D向量类。

●hvector.四分量齐次向量。（见第7章）

●rgb. 一个存储了三个组成元素的RGB颜色类。你应该同时为它实现RGB的加、减、乘、标量乘法及标量除法操作方法。

●transform.用来表达变换信息的4x4矩阵。你应该为它添加矩阵的乘法操作以及一些用来对位置、方向以及法线向量进行变换的成员函数。如同第6章展示的那样，这些都是不一样的。

●image. 一个有着输出操作函数的二维RGB像素数组。

另外，你可能想去添加一些用于计算间隔，或者基于正交基以及用于坐标系框架的类，这些都取决你自己的想法。

1.7.2 单精度vs双精度

对于现代硬件架构来说，尽可能少的使用内存，并且保持内存访问的连续性是提升效率的关键。这也就意味应该更多的使用单精度的数据，然而为了避免数值计算出现精度问题会而推荐使用双精度的计算。因此，如何权衡依赖于具体的应用程序，但是在你的设计的类应当确定一个默认的精度设定。

1.7.3 调试图形程序

如果你跟周围其他的码农交流一下你就会发现，一个码农越牛B，他越少使用传统的那些调试器。原因之一在于这些调试器在调试简单程序时易用，而调试复杂程序时非常笨拙，另一个原因就是，大部分很难查出来的错误其实是那些概念上的错误，某些错误的东西被实现出来了导致的。如果你先不去排查这样的一些错误的话，那么你就会花费大量的时间去一步一步的把各种各样乱七八糟的变量过一遍。我们这里推荐一些在调试图形程序的时候非常具备实践价值的调试策略。

科学的方法

在图形程序领域有一个相比于传统的调试方法非常有用的方法，这种方法的缺点就是：通常情况下，在你刚入行开始码代码的时候，你会被告知不要用这种方式去进行程序的调试，所以当你使用这种方法去调试图形学程序的时候，可能会看起来有点叛逆。这种方法的做法就是：我们创建一张图像，然后去观察这张图像有什么问题没有。进而我们提出一个引发该问题的假设并且去验证它是否正确。比如说，在一个光线追踪的程序中，我们的画面可能会有很多随机的看起来是暗色的像素。这可能是很多人在写一个光线追踪器的时候会碰到的一个叫做“Shadow Acne”的问题。传统的调试方法此时就不那么管用了，此时，我们必须要意识到阴影的射线们射到了那些被着色的表面上了。我们可能会发现那些比较暗的部分的颜色是环境光的颜色，所以可以推断直接光的部分丢失了。在阴影中，直接光的计算部分会被跳过，所以此时你可以假设那些画面中的暗的点点是因为一部分像素点没有在阴影中却被标记为了在阴影中导致的。为了验证这一想法，我们可以关闭阴影渲染的部分，然后重新编译程序。这将推断出这些是错误的阴影测试导致的，进而我们可以继续进行后面的错误排查工作。这招有时候非常实用的关键原因在于我们不需要找到某个错误的值或者真的去排查出我们的一些概念上的错误，而是基于实验去指导我们改进我们理念上的错误。一般来说，我们只需要做一些简单的实验就可以跟进错误了，并且这样的调试是非常让人享受的。

编码输出调试图像

很多情况下，获取一个图形程序调试信息最简单的方式就是去输出图像本身。如果你想知道计算出每个像素的某个变量在某个步骤的值的话，你只需要临时的对你的程序进行修改，把那个变量的值直接输出到图像中，并且跳过后面的正常情况下需要进行的计算部分。举个例子，如果你怀疑是法线导致了渲染结果出错了，那么你可以把法线向量直接输出到图像中，这样你就会得到一个有颜色的编码了向量的图像，这些就是在你的计算中会使用到的那些法线数据。或者，如果你怀疑某个部分的变量有时候会超出它应有的值的范围，你就在它发生这一意外情况的时候往颜色里面写白色。其他的还有的一些技巧就包括使用显眼的颜色去绘制物体表面的背面，使用物体的ID去标记某个像素是哪个物体，或者根据计算某个像素耗费的运算量去对它进行着色。

使用调试器

尽管如此，仍然会存在一些情况，科学的调试办法看起来会有一些自相矛盾的部分，这时候没有其他的方法来让你观察到底发生了什么错误。因为在图形学程序中，通常会牵涉非常非常多的代码被执行（比如说：每个像素执行一次，或者说每个三角形执行一次），使得一开始就用调试器一步一步的进行调试变得完全不可能。并且，大部分难以重现的BUG只在你的输入变得很复杂的时候会出现。

一个非常有用的方法就是给BUG设置一些“陷阱”。首先你必须保证你的程序的执行是确定的-在单线程中运行并且从固定的几个随机种子中算出随机数。当随机数的种子固定不变，对于找到哪个像素或者三角形在渲染的时候表现出来了一些某一种类型的错误是非常有用的，然后在你觉得不对的代码前面加一些代码，这些代码只有在你觉得会使得渲染结果出错的时候才会被执行。比如说，如果你发现位于（126，247）位置上的像素看起来有问题，那么你就加这么一句类似的代码：

如果你在这句print语句上设置了断点，你将会在真正开始计算你怀疑有问题的那个像素点之前断点到这个地方，然后开始你的调试。有的调试器有“条件断点”的功能，这使得你可以不用加上面那些代码照样可以办到刚才说的这些。

在那些应用程序会崩溃的情况中，传统的调试器还是非常有用的，它能帮你定位到崩溃点。那时候你就要从崩溃点开始查找BUG，这时候你可以通过断言来找到程序哪里出错了。这些断言应该被就那样被放在应用程序中来帮助你定位未来可能出现的同样的错误。再一次这将意味着可以避免使用传统的调试模式，因为传统的调试模式不会让你去在你的程序中添加一些有用的断言。

调试相关的数据可视化

理解你的程序在做什么通常来说是非常困难的，因为在出错之前，它会计算大量的中间结果。这个情况跟测量大量数据的科学实验一样非常的类似，所以有一个相同的解决方案：那就是生成图表来帮助你自己去理解那些数据的含义。比如说，在一个光线追踪器中，你可能会写代码去可视化一个射线的树，这样一来你就可以看到对于某一个像素来说，它是由哪些射线生成的，或者在一个图像的重采样的处理过程中，你可能会生成一张图表来显示出来对于某一个输入来说，所有那些被采样的样本的位置点。虽然你需要花费很多时间来可视化你程序的内部状态，但是同样的，这些工作将会在你进行优化的时候发挥它的价值。

注意事项

这里关于软件工程方面的讨论受到了《Effiective C++》系列书籍、《Extreme Programming movement》以及《The Pactice of Programming》的影响。这里讨论的这些调试经验是建立在跟Steve Parker的相关讨论的基础之上的。

每一年都有很多跟图形学相关的会议，这就包括了ACM SIGGRAPH以及SIGGRAPH Asia，Graphics Interface，the Game Developers Conference（GDC），Eurographics，Pacific Graphics，High Performance Graphics，the Eurographics Symposium on Rendering，以及IEEE VisWeek。你现在就可以通过这些会议的名字在网上找到它们的相关资料。

本章翻译绝大部分参考了知乎的两篇文章，我对其中一些字句进行了修订，原始参考如下：

战火科技-杨振  专栏-图形渲染入门   https://zhuanlan.zhihu.com/p/480142555

0110君（虎书翻译小分队） 专栏-虎书第4版  https://zhuanlan.zhihu.com/p/264790377