这届图灵奖得主究竟做了什么贡献这篇197

机器之心分析师网络

作者：JoshuaChou

编辑：H4O

时隔32年，计算机图形学领域学者再获图灵奖。获奖者EdwinE.Catmull的研究对计算机图形学领域贡献卓著。仅在年所著的博士论文中，他就提出了两种用于显示弯曲patch的突破性技术。本文将介绍这篇博士论文的贡献。

图灵奖是计算机科学领域的最高荣誉。今年3月，ACM宣布了年的图灵奖得主，EdwinCatmull和PatrickHanrahan凭借对3D计算机图形学的贡献获得此奖项。

本文介绍了EdwinCatmull年发表的博士论文，这篇论文奠定了3D计算机图形学的基础。

这篇论文的研究目标是在一台光栅扫描机器上为曲面或弯曲固体对象创建高质量的计算机生成图像（CGI）。Catmull的工作不仅提高了所显示对象的准确度，还提高了其阴影和纹理的质量。

生成弯曲的图像patch需要的知识包括：1）曲面上的点与显示器上光栅元素之间的对应关系；2）patch的隐藏或不可见部分；3）光栅上应该显示的光强度。

在深入本文内容之前，我们先来了解该领域的一些术语。

光栅扫描设备（或光栅显示器）是一个用于图像捕捉和重建的矩形模式。在光栅扫描器中，图像被细分为多个条（通常是水平方向），这些条被称为扫描线（scanline）。每个条都可以看作一组点，这些点叫做光栅元素（raster-element）。在计算机系统中，每一个扫描线被分成几个离散像素。扫描线通常按顺序进行处理/生成，每个光栅元素都有一个由某些强度值决定的亮度值。取强度值，在光栅显示器上画出相应强度的点，这一过程叫做“显示”（display）。

帧缓存（frame-buffer）是一个内存缓冲区，用来存储显示之前的所有强度值。帧缓存的大小由光栅显示器的分辨率和强度值存储位数来决定。

人们习惯在三维空间中观察和理解对象。而要想在二维平面上显示相同的对象，必须首先将三维对象进行透视变换（perspectivetransformation），这样我们才能把它理解为三维对象。我们将常规的三维空间叫做对象空间（objectspace），经过透视变换的空间叫做图像空间（imagespace）。图像空间也是一个三维的空间，但对象经过了扭曲，使得其在x-y平面上的正交投影可以产生预期的透视图。图像空间的维数保持为3，以保存深度信息。图像空间在x-y平面上的投影被称为“投影图像”（projectedimage），x-y平面与光栅相关的部分称为“屏幕”（screen）。

为了显示弯曲的patch，我们必须定义图像空间与光栅之间的关系，以便将投影图像中的信息转换为光栅中的信息。屏幕被分割为一个个小正方形，即光栅元素方块（rasterelementsquare），每个光栅元素方块都与光栅元素一一对应。下图1显示了不同空间之间的关系，以及图像空间、帧缓存和真实显示结果之间的关系。

图1：上述不同术语之间的关系。

在接下来的内容中，我们首先讨论Catmull工作的基础——细分算法（subdivisionalgorithm），并探讨他为了显示弯曲patch对该算法所做的修改。接下来我们讨论隐藏面（hiddensurface）问题，该问题的挑战在于：任何被观察的对象都应该只显示观察者所能看到的部分。本文将重点讨论Catmull用来解决此问题的两种算法。最后，我们将讨论光栅显示所涉及的多个因素，如强度值、采样所带来的不必要的伪影等，以及Catmull在修改细分算法以减少锯齿（aliasing）方面做出的贡献。

显示弯曲patch的通用算法

细分算法

细分算法构建了patch与光栅元素之间的对应关系。每个光栅元素的中心被表示为一个采样点（samplepoint）。我们将通过图2来讨论这一算法。

图2：（上）：网格状的点为采样点，线代表投影对象的弯曲边缘。回想一下，每个采样点对应一个光栅元素，该元素与一个强度值相关联；（中）：该算法的工作原理是将被对象覆盖的采样点patch分割成更小的子patch，这些子patch覆盖的采样点集更小；（下）：重复该过程，直到每个子patch只覆盖一个采样点。计算每个子patch的强度，并将强度值写入帧缓存的对应元素中。

该算法存在一些问题：

如何终止细分过程？对于那些没有覆盖一个采样点的patch，会发生什么？如果子patch与屏幕的边相交或者不在视线范围内，会怎么样？一个patch要被细分多少次？离散采样会产生什么问题？Catmull在自己的论文中一一解决了这些问题。

1.终止条件

终止条件共有两种。第一种是patch或子patch只覆盖一个采样点。此patch可以通过将其角与直边相连构成一个多边形来得到近似。接下来只需要检查该多边形，确定区域内是否只存在一个采样点即可，如图3所示。

图3：patch的多边形近似。

第二种终止条件是裁剪，即如果一个patch不再出现在屏幕上，则它的细分过程就会终止。也就是说，如果图像空间中的patch投影到x-y平面上后位于屏幕区域之外，或者patch不在视线范围内，则它不会得到显示，也就不需要进一步的细分。

这里需要一种方法来确定patch是否完全在屏幕内/外。对于那些部分位于屏幕之外的patch，通用法则是将其细分成更小的子patch，然后重复以上检查过程。

2.细分数量

patch的细分次数与其在屏幕上的面积成正比。通常来讲，细分次数与patch矩形区域的比例大约是1/3。对于弯曲的patch，这个比例可能更大。

3.采样问题带来挑战

随着采样点的引入，一些问题也随之产生。面积很小的patch可能无法覆盖一个采样点，因此，它的强度值没有分配给任何一个采样点，它就会消失。这个问题可以通过将其强度值分给最近的采样点来解决。

这个细分算法首次应用于双三次patch（bi-cubicpatch），双三次patch适用于大部分应用。Catmull的主要贡献之一就是改进细分算法，使之可以用于其他类型的曲面。

细分三次曲线

Catmull提出了一个新的差分方程，用于确定三次曲线的中心点。中心点是其两个端点的平均值减去修正项。类似的方法可用于确定中心点处的导数。

假设三次曲线f(t)=axt^3+bxt^2+cxt+d。问题是：已知f(t-h)和f(t+h)，确定f(t)。其中f(t+h)=ax(t+h)^3+bx(t+h)^2+cx(t+h)xd，f(t-h)=ax(t-h)^3+bx(t-h)^2+cx(t-h)xd，f(t-h)+f(t+h)可以计算为2xf(t)+2x(h^2x(3x(axt+b)))，则中心点f(t)=(f(t-h)+f(t+h))/2–h^2x(3x(axt+b))。其中f(t)表示三次曲线段，a、b、c、d为描述曲线的标量参数。h是表示与点f之间距离的标量值。

我们可以看到中心点是两个端点的平均值减去修正项。由于f(t-h)和f(t+h)已知，那么唯一要处理的就是修正项h^2x(3x(axt+b))。类似地，我们可以根据(t-h)和(t+h)处的修正项求得t处的修正项。

假设g(t)=h^2x(3x(axt+b))为t处的中心点，g(t-h)=h^2x(3x(ax(t-h)+b))，g(t+h)=h^2x(3x(ax(t+h)+b))，计算g(t-h)+g(t+h)=2xg(t)，得到g(t)=(g(t-h)+g(t+h))/2。将以上计算结合起来，就可以确定中心点f(t)的最终差分方程，即

f(t)=(f(t-h)+f(t+h))/2–(g(t-h)+g(t+h))/2

注意，h可以根据细分程度进行修改。此处不再详述h的详细计算过程，仅提供直观介绍。

h对细分程度的依赖是必要的，因为细分越多，每个patch就越小。因此，中心点t应为两个距离较近的点的平均值。例如，以下（多边形）patch被分割为三个子patch：A、B和C。

要想获得子patchA上方边的中心点（点a）信息，我们需要这条边两个端点(a-h)和(a+h)的信息。要想获得子patchB上方边的中心点（点b）信息，我们需要两个端点(b-h’)和(b+h’)的信息。可以看到hh’，也就是说较小的子patch所需的h参数也更小。

Catmull对此的贡献是，他提出了一种计算曲线中心点的方式，这种方式不受限于多边形的直边。

从应用的角度来看，修改后的细分算法能够帮助我们确定曲线的细分中心点。从数学角度来看，该方法没有使用两个端点的中心点，而是添加了一个额外的修正项，进而得到中心点信息。

该计算过程可以转换为矩阵运算，感兴趣的读者可以查看原论文了解更多细节。

将细分从三次曲线扩展到曲面

对曲线进行细分后，自然而然地，我们需要解决曲面细分问题。三次曲线的每个端点都有值和修正项，而三次patch的每个角都有值和修正项。patch细分需要：

找出patch每条边的中心点。找出patch自身的中心点。简而言之，每条边的中心点可以按照上述章节中介绍的方式进行计算。patch的中心点则需要使用在4条边上找出的4个中心点进行插值。

隐藏面问题

要想创建任意对象的逼真视图，我们必须展示观察者可以看到的线条，忽略他们不可见的线条。对此类表面的识别和移除就是隐藏面问题，或者可见面检测问题。下图4从视觉角度进行了解释：

图4：隐藏面问题。观察者观看的任何对象应仅展示观察者能够看到的部分。从这个角度来说，对象剩余的部分就变得无用了。

Catmull的论文讨论了两种解决方法：Z-buffer算法和修改版的Newell算法。

Z-buffer算法概述

现在，Z-buffer已成为隐藏面检测的常用方法。Z-buffer方法对比投影平面（如映射至屏幕的平面）上每个像素位置的表面深度。通常，用z轴表示深度。根据观察者的方向，该算法使用最大Z值或最小Z值初始化Z-buffer。互不重叠的光栅元素不需要任何对比，可以直接写入帧缓存。

通常，我们假设观察者位于z轴的正轴方向，看向z轴的负轴方向。具备较小z值的对象距离观察者更远，具备较大z值的对象距离观察者较近。当观察者从z轴的负轴看向正轴方向时，情况恰好相反。因此，Z-buffer方法可能取决于观察者的视角方向。

下图5展示了Z-buffer方法，此时观察者位于z轴的负轴方向，看向z轴的正轴。

图5：观察者在z轴负轴看向z轴正轴。深度越小的对象距离越近，并存储在最终Z-buffer中，然后显示在屏幕上。

Z-buffer方法有多项优势。它可以轻松处理隐藏面问题和任意表面的相交。也就是说，能够以任意顺序将表面写入buffer，无需进行额外的处理。该算法的核心概念非常好理解。多边形表面的每个(x,y,z)点对应x-y平面上的正交投影，然后映射至光栅显示器上的点。在光栅显示器的每个点(x,y)处，使用其深度(z-)值对比对象。最后需要注意的是，处理透明表面对Z-buffer而言是个难题。此时，需要使用另一种常见方法——A-buffer。

处理隐藏面问题的其他常见方法还有：

Scanline算法：逐行处理，而不是以多边形或像素为基础进行。Warnock算法：对屏幕执行递归切分，直到所有区域易于计算。该算法多作为其他算法的基础，适合并行执行。画家算法（Painter’salgorithm）：根据深度对场景中的所有多边形进行排序，然后按照从远到近的顺序进行绘画。多用于（简单的）视频游戏中。光线追踪算法：试着反向追踪进入你眼睛的光线，并沿着这个轨迹找到光源。目前，Z-buffer和光线追踪算法较为常用。

修改版Newell算法概述

修改版Newell算法是一种显示多边形的算法，它将多边形以z顺序进行排序，然后基于该顺序绘制多边形并写入帧缓存中。首先绘制距离观察者较远的多边形，后续写入的多边形有可能覆盖buffer中已有的多边形，从而消除模糊的多边形。如果两个多边形相交，或难以按z值排序，则将它们分割为较小的部分，直到能够准确排序。

该算法包含以下步骤：

以z顺序对多边形进行排序；对于每个多边形，检查它是否与其他多边形重叠；查看测试多边形后面有没有其他多边形；如果有，移除其后面的多边形；将重叠的多边形分割为更小的部分，每次分割后均重复以上步骤。Catmull将修改版Newell算法和Z-buffer算法结合起来，处理图像空间中的对象，并将强度值写入buffer。

强度、采样、光栅扫描和锯齿

强度

如前所述，子patch仅覆盖一个采样点时，将强度值分配给该采样点。以下方式可用于获取每个点的强度：

使用曲面的法线来计算强度；定义强度函数来计算强度；基于某幅图映射强度值；针对阴影或透明修改已有强度。下面我们来看这些方法的细节。

1.使用曲面法线

曲面法线常用于计算强度。通常做法是取光向量和法向量的点积。但是，找到法向量并非易事，这也是该方法的难点。

2.使用强度函数

强度函数不应定义为曲面方向的函数，而是压力、应力、高度和密度等的函数。

3.使用映射

照片、绘画或任意图像都可以映射到双变量patch上。该方法尝试对patch上的任意点和图画的强度进行对应。

4.修改强度

强度值写入buffer后，仍有可能被修改，如处理阴影或透明时。例如，需要修改的强度值可能是旧的和新的强度值的凸组合。

其数学形式为：

new_value=modification_value+Tx(old_value–modification_value)=Txold_value+(1-T)xmodification_value

其中T是0和1之间的标量参数。

以上这些方法均在Catmull的论文中有详细讨论，感兴趣的读者可以阅读原论文。

现在，我们已经了解了Catmull的大部分贡献。生成弯曲patch的画面需要了解：(1)曲面上点和显示器光栅元素的对应关系；(2)patch的隐藏面；(3)应在光栅显示器上得到显示的光强度。

Catmull提出了一种新的差分方程来确定三次曲线和双三次patch的中心点，这有助于解决patch的切分问题。

执行该细分算法直到每个子patch覆盖一个光栅元素点(1)。Catmull将Z-buffer算法和修改版Newell算法结合起来解决隐藏面问题(2)。最后，Catmull探讨了多种确定强度值的方法(3)。

在论文的最后部分，Catmull讨论了使用光栅显示器生成的伪影，并提出一些解决该问题的标准方法。

下文将简述锯齿问题。Catmull提出的方法目前已经是信号处理领域的标准做法，下文旨在将信号采样和计算机图形学结合起来。

采样、光栅扫描和锯齿

简而言之，光栅元素（像素）是连续图像的离散样本。采样处理的问题是：要想准确捕捉连续图像的本质，采样的密集度应该是怎样的？此处将对采样和锯齿的关系提供简洁的示例。

假设有一个你想以规律间隔采样的时间信号。这些采样点之间的时间长度可能导致最终采样信号出现显著区别。下图6通过采样正弦波形做出了展示：

图6：（上）样本足够快，重建信号和原始信号具备同样的频率；（下）样本太慢，以至于重建波形的频率比原始信号低很多。这就叫做锯齿。

因此，采样频率必须足够高，以便正确重建信号。在采样理论中，奈氏定理表示，要想准确重建信号，采样率必须是信号最高频率的2倍及以上。此处，不再深入探讨信号处理。

那么，这对计算机图形学有何影响呢？由于图像可以看做是在像素中心处定义的值的强度图，因此它还可以看做是连续函数的点采样，写下像素强度值就像在像素中心处采样该函数一样。

从视觉上来看，锯齿表现为分辨率过低的图像中边的阶梯形状，参见图7：

图7：渲染图像中的锯齿现象。

抗锯齿的目的就是尽量避免锯齿的影响。

当图像经过傅里叶变换后，图像内的尖锐边缘和较小对象通常对应于高频率。而光栅显示器仅能重现低频率。因此，频率的上限取决于光栅显示器的分辨率。在采样过程中，高于光栅显示器可复现范畴的频率将难以分辨，或者说出现锯齿。

抗锯齿算法可分为以下两个类别：

前置滤波（Pre-filtering）：将像素作为区域，基于场景中对象与像素区域的重叠计算像素颜色；后置滤波（Post-filtering）：以较高分辨率渲染场景，将像素值计算为子像素的（加权）平均值。Catmull详细讨论了前置滤波技术。如上所述，在区域采样中，像素强度与每个像素和显示对象的重叠区域成正比。

该论文的最后一项贡献就是支持抗锯齿的细分算法。细分算法分割patch，直到每个子patch仅覆盖一个光栅元素。Catmull修改了该算法，使之支持区域采样。请看以下示例：

每个正方形表示一个光栅元素，横线与纵线的交叉点为顶点。Catmull做出的修改是令每个子patch最多覆盖一个顶点。使用近似该patch的多边形（虚线）来执行区域计算。将该多边形分割为四部分，分别属于四个正方形。然后使用区域平均算法处理每个正方形，以计算新的像素值。

以右上子patch为例。我们可以看到对象位于背景的上方，每个都有自己的强度值。像素包含对象和背景的一部分。最终的像素值是背景和对象强度值的加权平均值。

结语

Catmull在这篇论文中为计算机图形学领域提供了一个流程，用于解决与渲染复杂对象相关的特定研究问题，包括难度很高的曲面渲染问题。

Catmull提出的方法可以计算三次曲线的中心点，进而使得之前仅能处理多边形patch的细分算法也能够切分具备曲线边界的patch。

此外，他还提出了Z-buffering算法，该算法利用图像深度信息确定三维物体在计算机图形学中的二维视图。

最后，他修改了细分算法，使其通过区域采样支持抗锯齿，成为现代计算机图形学领域的突破性发展。

Catmull这篇论文中提到的很多方法现仍广泛应用于视频游戏和动画片。

转载请注明：http://www.abuoumao.com/hytd/3307.html