计算机图形学基础（4）——光栅化

上一篇 文章 我们介绍了矩阵变换在计算机图形学中的应用，包括：视图变换、模型变换、投影变换。此外，我们还详细介绍了投影变换中的正交投影和透视投影，以及屏幕映射过程中的视口变换。

本文，我们来介绍一下计算机图形学中最重要的内容之一——光栅化。

栅格显示

光栅化（Rasterization）中光栅（Raster）一词来源于德语，表示栅格的意思。我们现在用的显示设备基本上都是由像素点阵构成的栅格显示设备。因此，我们很容易理解光栅化的含义，即在栅格显示设备上绘制图形。

这里我们先介绍一下常见的栅格显示设备。

旧式的阴极射线管（Cathode Ray Tube，CRT）电视，它的基本原理是 通过射线管将电子射到屏幕进行逐行扫描，如下图所示。在实际应用中，会借助视觉暂留效应，对屏幕进行 隔行扫描，从而降低扫描的计算量。

现代平板显示器（Flat Panel Displays）中最常用的是液晶显示器（Liquid Crystal Display，LCD），它的基本原理是 通过扭转偏振来阻挡或传输光线，如下图所示。在实际应用中，会使用 帧缓冲（Frame Buffer）来提前缓存画面的帧数据，从而提高显示流畅度。

光栅化

基本单元

光栅化的基本单元是三角形，采用三角形作为基本单元的原因是：

• 三角形是最基本的多边形。
• 三角形具有平面性。
• 三角形可以明确定义内部和外部。我们可以通过向量叉积来判断，详见 计算机图形学基础（1）——线性代数。
• 任意多边形可以拆分成 N 个三角形。

采样绘制

2D 屏幕是一个离散的像素阵列，空间中的三角形则是一个连续的函数。采样绘制的本质则是对一个函数进行离散化。具体的做法是：

• 遍历像素阵列，判断每一个像素阵列是否位于三角形的投射区域内
• 如果是，进行绘制像素；否则，不绘制。

如下所示为采样绘制的伪代码和示意图。注意，像素本身是一个矩形区域，因此判断像素是否在三角形内部时，采用的是像素点的中心作为参照。

bool inside(t, x, y) {
    if point(x, y) in triangle(t) {
        return 1
    } else {
        return 0
    }
}

for (int x = 0; x < xmax; ++x) {
    for (int y = 0; y < ymax; ++y) {
        image[x][y] = inside(tri, x + 0.5, y + 0.5);
    }
}

在绘制三角形时，一般不会对整个屏幕的像素点进行扫描，而是仅仅对三角形的 包围盒（Bounding Box）区域内的像素进行扫描和绘制，从而有效降低算法复杂度。对于一些窄长三角形，甚至可以进一步优化算法，如下图右侧所示。

核心问题

我们观察上述这种简单的采样绘制方式，可以发现一个很明显的问题——锯齿（Jaggies）。这个问题根本上是采样导致的，对于这种现象我们称之为 走样（Aliasing）。走样会带来很多奇怪的现象，比如：锯齿、摩尔纹（Moire Patterns）、车轮效应等，如下图所示。

光栅化要解决的核心问题就是走样问题，即 反走样（Antialiasing）。

解决方法

计算机图形学中解决走样问题的最常用方法是：先模糊，后采样。模糊，从字面上理解就是将图片虚化，从数学上理解则是 滤波，关于滤波，我们将在下一节中进行介绍。

下图所示，为「直接采样」和「先模糊，后采样」的流程对比图。

在具体实践中，通过这种方式能够有效解决光栅化中的锯齿问题，如下所示为反走样前后的效果对比图。

这里，我们可能会产生疑问：

• 出现走样的根本原因是什么？
• 为什么先模糊（滤波）后采样能够实现反走样？

要讲明白这些内容，我们必须要介绍一下采样理论。

采样理论

采样理论是信号系统中非常重要的一个理论，它在数字信号处理、数字通信、图像处理等众多领域都有着广泛的应用。

在实际应用中，我们通过一定的采样率把连续信号转换为离散信号，然后再对离散信号进行处理。处理完后，我们又可以通过一定的重构方法把离散信号转换回连续信号，以便在实际系统中使用。

傅里叶级数

那么如何表示任意一种信号呢？法国数学家傅里叶认为，任何周期函数（信号）都可以用正弦函数和余弦函数构成的无穷级数来表示，如下所示。

对于上图中的信号，使用傅里叶级数展开的表示如下所示。其中，这里 \(t\) 表示时间，\(A\) 表示振幅，\(w\) 表示角频率。

\[\begin{aligned} f(x) = \frac{2Acos(tw)}{\pi} - \frac{2Acos(3tw)}{3\pi} + \frac{2Acos(5tw)}{5\pi} - \frac{2Acos(7tw)}{7\pi} + ... \end{aligned}\]

时域与频域

基于傅里叶级数，我们可以对信号的时域（以时间为横坐标）和频域（以频率为横坐标）进行相互转换：

• 时域转换成频域：采用 傅里叶变换（Fourier Transform）
• 频域转换成时域：采用 逆傅里叶变换（Inverse Fourier Transform）

走样原理

了解了信号的时域和频域之后，我们再来介绍走样的原理。

理想情况下，对一个连续信号进行采样后得到的离散信号，应该能够近似重构原始信号。然而，当采样频率低于原始信号的频率时，就会很容易出现走样的问题。换句话说，就是采样得到的离散信号无法近似重构原始信号。

下图所示，我们列举了几种信号，信号频率依次从高到低，我们使用相同的频率对这些信号进行采样。很显然，我们对低频信号进行采样时，由于采样频率大于信号频率，得到的离散信号可以近似重构原始信号；但是，我们对高频信号采样时，由于采样频率小于信号频率，得到的离散信号则无法近似重构原始信号。

因此走样的根本原因就是 采样频率小于信号频率。

滤波

由于滤波在反走样中起到了重要作用，因此我们简单介绍一下图像处理中滤波。

如下图所示，通过傅里叶变换将左侧的像素空间（空间域）变为右侧的频谱（频域）。对于二维信号，其频谱的表示如下：

• 高频部分代表细节、边缘、噪声
• 低频占据绝大多数能量，其中直流分量（零频）能量占比最大
• 频率分部具有中心对称性

下面，我们来介绍一下几种常见的滤波。

高通滤波

高通滤波（High-pass filter），保留高频信号。在图像中，轮廓的边缘会发生剧烈变化，属于高频信号。经过高通滤波后，图像只会保留一些轮廓信息，如下图所示。

低通滤波

低通滤波（Low-pass filter），保留低频信号。在图像中，颜色变化平缓的区域属于低频信号。经过低通滤波后，图像会抹去轮廓信息，如下图所示。模糊处理基于低通滤波实现的。

带通滤波

带通滤波（Band-pass filter），顾名思义，只保留一部分频率范围内的信号。对图像滤波后的效果取决于带通滤波所选择的频率范围。下图所示，为两种不同频率范围的带通滤波。

卷积

那么如何实现滤波呢？卷积（Convolution）就是实现滤波的主要数学工具和底层原理。滤波器的基本原理是 响应函数与输入信号进行卷积运算，因此滤波器也可以称为 卷积核。

如下所示，是卷积的数学定义，两个函数的 \(f\) 和 \(g\) 卷积 \(f * g(n)\)。

\[\begin{aligned} 连续形式：& (f * g)(n) = \int_{-\infty}^{\infty}f(\tau)g(n-\tau)d\tau \\ 离散形式：& (f * g)(n) = \sum_{-\infty}^{\infty}f(\tau)g(n-\tau) \end{aligned}\]

观察 \(f(\tau)\) 和 \(g(n-\tau)\) 的关系，可以发现是对 g 函数进行了「翻转」，这就是「卷」的来源。同时，对两个函数 f 和 g 进行积分，这就是「积」的来源。

卷积本身是一个很难解释的数学定义，如果你想深入理解卷积，这里推荐一篇知乎高赞回答——传送门。简而言之，两个函数的卷积，会先将一个函数翻转，然后进行滑动叠加。本质上可以将卷积理解成加权平均。

下图所示，是对图像进行滤波（卷积）的过程，实现模糊处理。基于傅里叶变换，我们可以实现时域（空间域）与频域之间的相互转换。时域（空间域）上对两个信号进行卷积，等同于频域上对两个信号的频率进行乘积。

反走样原理

在「走样原理」一节中，我们提到了走样的根本原因是 采样频率小于信号频率。在不提高采样频率的前提下，通过 先滤波，后采样 的方式可以实现反走样，这里的底层逻辑又是什么呢？

简单的理解就是，滤波（低通滤波，即模糊处理）会过滤掉信号中大于采样频率的信号分量。滤波后，剩余的信号分量的频率满足 采样频率 >= 信号频率 的条件，因此实现了反走样。

实现反走样的方法主要就是围绕两个角度来实现：

• 提高采样频率。如：超采样技术（Supersampling）、多重采样抗锯齿（MSAA）、超分辨率
• 过滤高频信号。如：先模糊后采样（Pre-Filter）

遮挡与可见

上述内容介绍了光栅化一个三角形的场景，以及其会遇到的问题——走样。下面，我们来介绍光栅化多个三角形会遇到的问题——遮挡与可见问题。

在 3D 空间中，三角形之间存在着前后遮挡关系，那么三角形绘制的先后顺序应该是什么样的呢？

画家算法

对此，我们先介绍一个经常被提到的算法：画家算法（Painter's Algorithm）。

画家算法，顾名思义，按照画家绘画时的先后顺序来执行，远的物体先绘制，进的物体后绘制，如下图所示。

虽然画家算法适用于绝大多数场景，但是在某些场景下它仍然无法解决可见性问题。如下图所示，三个相互嵌套的三角形，使用画家算法则无法对三角形进行排序，因此无法准确实现光栅化。

深度缓冲算法

那么上述问题该如何解决呢？于是出现了 深度缓冲算法（Z-Buffer Algorithm），其基本原理是：

• 光栅化采用两个缓冲区
  • 原有的 帧缓冲区（Frame Buffer）存储每个像素颜色值
  • 附加的 深度缓冲区（Z-Buffer）存储每个像素深度值
• 深度缓冲区存储每个像素当前的 最小深度值（Z-Value）

如下所示，为深度缓冲算法的伪代码实现。注意：我们会初始化深度值为无穷大。

for (each triangle T) {
    for (each sample (x, y, z) in T) {
        if (z < zbuffer[x, y]) {            // 处理深度更小的采样点
            framebuffer[x, y] = rgb;        // 更新颜色值
            zbuffer[x, y] = z;              // 更新深度值
        }
    }
}

下图所示，使用深度缓冲算法光栅化两个三角形的示意图。当光栅化红色三角形时，我们遍历红色三角形的每一个像素的深度值，并与当前深度值进行比较。由于当前深度值均为无穷大，所以红色三角形的每一个像素都可以绘制。当光栅化蓝色三角形时，同样会遍历蓝色三角形每一个像素的深度值，并与当前深度值变换，深度值大于当前深度值，则不绘制；否则，绘制并更新当前深度值。

注意，这里的深度值比较取决于坐标系是如何建立的。按照我们之前的介绍，相机是沿着 -Z 轴方向观测，因此深度越大，则 Z 值越小。

总结

本文，我们主要介绍了光栅化技术。首先介绍了光栅化的含义以及栅格设备。其次，我们介绍了光栅化的基本单元——三角形。

在绘制单个三角形时，我们会遇到走样问题。对此我们介绍了反走样的两种方法：提高采样频率、过滤信号频率。我们着重介绍了后者，先滤波（模糊）后采样，并介绍了其中涉及的原理。

在绘制多个三角形时，我们会遇到遮挡问题。对此我们介绍了两种算法：画家算法、深度缓冲算法。

后续，我们还会继续介绍计算机图形学的其他内容，敬请期待吧~

参考

1. 《GAMES 101》
2. 如何通俗易懂地解释卷积
3. 傅里叶变换与图像的频域处理
4. 采样定理