2020/05/14 16:43

Joshua Chou作者H4O编辑

这届图灵奖得主究竟做了什么贡献？这篇1974年的博士论文给了我们答案

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

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

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

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

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

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

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

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

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

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

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

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

显示弯曲 patch 的通用算法

细分算法

细分算法构建了 patch 与光栅元素之间的对应关系。每个光栅元素的中心被表示为一个采样点（sample point）。我们将通过图 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-cubic patch），双三次 patch 适用于大部分应用。Catmull 的主要贡献之一就是改进细分算法，使之可以用于其他类型的曲面。

细分三次曲线

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

假设三次曲线 f(t) = a x t^3 + b x t^2 + c x t +d。问题是：已知 f(t-h) 和 f(t+h)，确定 f(t)。
其中 f(t+h) = a x (t+h)^3 + b x (t+h)^2 + c x (t+h) x d，f(t-h) = a x (t-h)^3 + b x (t-h)^2 + c x (t-h) x d，
f(t-h) + f(t+h) 可以计算为 2 x f(t) + 2 x (h^2 x ( 3 x (a x t +b) ) )，
则中心点 f(t) = ( f(t-h) + f(t+h) )/ 2 – h^2 x ( 3 x (a x t +b) )。

其中 f(t) 表示三次曲线段，a、b、c、d 为描述曲线的标量参数。h 是表示与点 f 之间距离的标量值。

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

假设 g(t) = h^2 x ( 3 x (a x t +b) ) 为 t 处的中心点，
g(t-h) = h^2 x ( 3 x (a x (t-h) +b) )，g(t+h) = h^2 x ( 3 x (a x (t+h) +b) )，
计算 g(t-h) + g(t+h) = 2 x g(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。

要想获得子 patch A 上方边的中心点（点 a）信息，我们需要这条边两个端点 (a-h) 和 (a+h) 的信息。要想获得子 patch B 上方边的中心点（点 b）信息，我们需要两个端点 (b-h’) 和 (b+h’) 的信息。可以看到 h > h’，也就是说较小的子 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’s algorithm）：根据深度对场景中的所有多边形进行排序，然后按照从远到近的顺序进行绘画。多用于（简单的）视频游戏中。
光线追踪算法：试着反向追踪进入你眼睛的光线，并沿着这个轨迹找到光源。

目前，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 + T x ( old_value – modification_value ) = T x old_value + (1-T) x modification_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 这篇论文中提到的很多方法现仍广泛应用于视频游戏和动画片。

关于机器之心全球分析师网络 Synced Global Analyst Network

机器之心全球分析师网络是由机器之心发起的全球性人工智能专业知识共享网络。在过去的四年里，已有数百名来自全球各地的 AI 领域专业学生学者、工程专家、业务专家，利用自己的学业工作之余的闲暇时间，通过线上分享、专栏解读、知识库构建、报告发布、评测及项目咨询等形式与全球 AI 社区共享自己的研究思路、工程经验及行业洞察等专业知识，并从中获得了自身的能力成长、经验积累及职业发展。

理论图灵奖Edwin Catmull博士论文计算机图形学