光栅化

发表于 更新于 分类于 阅读次数： Waline： 阅读次数： 本文字数： 3k 阅读时长 ≈ 11 分钟
光栅图形学

我们已经通过 MVP 变换将要显示到屏幕上的物体变换到 \(\left[-1, 1\right]^3\) 的立方体中，接下来要将 \(\left[-1, 1\right]^3\) 的立方体中的物体绘制到屏幕上。首先定义屏幕（screen）：

  1. 屏幕是像素（pixels）的数组；
  2. 分辨率（resolution）是屏幕像素数组的尺寸；
  3. 屏幕是光栅成像设备。

光栅化指的是将物体绘制到屏幕上。像素是具有统一颜色的小方块，是由不同颜色组合而成的（例如 RGB）。

屏幕空间

Img

我们认为屏幕左下角为原点，向右为 \(x\) 轴，向上为 \(y\) 轴。建立平面直角坐标系。屏幕空间满足以下几点：

  1. 像素坐标 \(\left(x, y\right)\) 为整数；
  2. 像素坐标覆盖范围为 \(\left(0, 0\right)\) 到 \(\left(\text{width} - 1, \text{height} - 1\right)\)；
  3. 坐标为 \(\left(x, y\right)\) 的像素的中心点的坐标为：\(\left(x+0.5,y+0.5\right)\)；
  4. 整个屏幕的覆盖范围为：\(\left(0,0\right)\) 到 \(\left(\text{width},\text{height}\right)\).

在这里，我们先忽略 \(z\) 坐标，只考虑 \(x\) 和 \(y\) 坐标。我们需要将 \(\left[-1,1\right]\) 变换到 \(\left[0,\text{width}\right] \times \left[0, \text{height}\right]\)，称之为视口变换，变换矩阵为： \[ M_{viewport} = \begin{bmatrix} \frac{width}{2} & 0 & 0 & \frac{width}{2} \\ 0 & \frac{height}{2} & 0 & \frac{height}{2} \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix} \]

三角形的光栅化

对于一个 3 维图形我们可以用三角形去表示一个一个小面。使用三角形的主要原因是：

  1. 三角形是最基本的多边形；
  2. 任何多边形都可以拆分成三角形；
  3. 空间内任何三个点的连线一定是平面；
  4. 三角形有清晰的内部和外部定义；
  5. 三角形只要定义顶点的属性就可以计算三角形内部点的渐变关系（三角形的内部插值）。

对于一个三角形，如何映射在像素空间上问题，可以转换成判断一个像素和三角形的位置关系。最简单的方法就是进行采样（Sampling）。采样就是连续函数的离散化过程。下面的代码就是对函数 \(f(x)\) 进行采样：

1
2
for (int x = 0; x < xmax; ++x)
    output[x] = f(x);

采样是图形学中的一个核心思想，我们可以对时间（time）、面积（area）、方向（direction）、体积（volume）等进行采样。

对于给定的三角形，定义一个函数，来判断某个坐标是否在三角形内部，函数定义如下： \[ \text { inside }(t, x, y)=\left\{\begin{array}{lc} 1 & \text { point }(x, y) \text { in triangle } t \\ 0 & \text { otherwise } \end{array}\right. \] 那么对三角形采样的代码如下所示：

1
2
3
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);

注意：判断某个像素是否在三角形内部实际上是判断像素的中心是否在三角形内部。

Img

判断某个像素是否在三角形内部，可以使用叉乘。对于三角形边界上的点，这里不做处理。

为了能够更快速的遍历像素点，我们可以用以下方法：

  • 使用包围盒（Bounding box），只对三角形最大的包围正方形区进行遍历。但是不适用于窄长的三角形。
  • 找到每一行三角形包围住最左和最右边的点进行遍历。

反走样

光栅化的三角形可能会生成大量的据此，此时我们需要一些方式来消除锯齿。

瑕疵

在采样的过程中，我们会产生许多的锯齿。这些锯齿的学名就叫做走样（Alias）。之所以会产生走样的原因是因为信号的变化速度比较快（高频信号），但是我们的采样比较慢（低频采样）。常见的走样分为以下几种：

  • 锯齿：空间上采样产生的走样；
  • 摩尔纹：空间上下采样产生的走样；
  • 车轮效应：时间上采样产生的走样。

这些我们也称为采样的瑕疵（Artifacts）。

走样产生的原因

傅立叶变换

任何一个信号都可以表示为一些正弦波和余弦波以及常数的线性表示，我们称之为傅立叶展开。而傅立叶变换指的是将一个时域上的信号转换到频域的过程。

走样和滤波

走样更为学术的定义是两个不同频率的信号在使用相同采样的方法后产生的结果无法进行区分。

Img

图中的红色信号和蓝色信号是两个频率不一样的信号，绿色虚线处是采样点，我们发现两个不同频率的信号在同一个采样方式下结果相同，这就产生了走样。

滤波（Filter）是把特定频率的波过滤掉。如果仅保留高频信息，那么这称为高通滤波；如果仅保留低频信息称为低通滤波；如果既删除高频信息，还删除低频信息，只保留中频信息称为带通滤波。

Img

对一个图片进行傅立叶变换后，得到的是上图右图的样子。中心代表了低频信息，边缘代表了高频信息，亮度代表对应频率的能量。对于图片而言，一般低频信息更加的丰富，而高频信息比较少。高频信息一般代表边缘信息，因为边缘信息频率比较高；低频信息是图片模糊后的结果，频率变化小。

卷积和卷积定律

滤波可以看作卷积操作，也可以看作平均操作。卷积（Convolution）操作是用一个卷积核在信号上不断地滑动，每一次卷积操作的结果是卷积核和对应位置信号乘积的和，可以看作一次加权平均的过程。

卷积定律：时域上的卷积等于频域上的乘积，频域上的乘积等于等于频域上的卷积。

Box Filter

Box Filter 是一个格式如下的滤波器： \[ \frac{1}{n^2} X^{n\times n} \] 其中，\(X\) 是一个全 \(1\) 矩阵。这个卷积核对临近的 \(n \times n\) 的像素做平均。\(n\) 越大，滤波器得到的频率范围越低。下图是一个 \(3 \times 3\) 的 Box Filter.

Img

深入了解采样

采样我们可以认为是一个连续函数乘以一系列的脉冲函数的结果。根据卷积定律我们知道，这相当于连续函数的傅立叶变换和脉冲函数傅立叶变换的卷积。脉冲函数的傅立叶变换还是脉冲函数。卷积的结果是信号的频谱在不断地重复。

Img

当采样率不足时会使得频谱之间的间隔太小，导致频谱间产生重叠，这些重叠就是走样。

频谱重叠示意图

这也就解释了为什么使用高通滤波器可以帮助我们减少走样。这是因为使用高通滤波器只保留更窄的频率范围，可以减少频谱的重叠。

反走样的方法

目前常用的反走样方法有两种：

  • 提高采样率（分辨率）。这是从物理层面上提高采样率来减少走样的方式，但是不够实用；
  • 采用低通滤波器先进行模糊操作，再进行采样的操作。如下图所示：
  • 超采样（Supersampling）。
Img

超采样

在实际的操作中，我们使用 MSAA（Multi-Sampling Antialiasing）的方式来近似进行反走样的操作，具体的步骤如下：

  1. 把每一个像素点拆分成 \(n \times n\) 的小像素点；
  2. 对每一个小像素点判断该点是否在图形中；
  3. 每一个像素点的结果都是这些小像素点的平均结果。
Img Img Img

MSAA 仅仅指的是模糊的过程，并不包含采样的过程。这样的方法虽然简单，效果好，但是会增加计算量。在工业界中，一般会采用更为有效的方式拆分采样点，甚至会复用采样点以达到更好的效果。

除此之外，目前业界还有一些其他的方式进行反走样：

  • FXAA（Fast approximate AA）是通过后期处理的方式处理锯齿。先得到已经有锯齿的图像，找到边界后替换成没有锯齿的边界；
  • TAA（Temporal AA）是通过抖动的方式进行多次采样，将多个帧合成就相当于多次采样。

超分辨率：将一个分辨率较小的图片还原成分辨率较大的图片。和反走样虽然意义不同，但是任务类似。对于超分辨率问题，最重要的是猜测缺失像素的内容，比较适合使用神经网络进行预测，即所谓的 DLSS（Deep-learning Super Sampling）。

可见性与遮挡性（Visibility And Occlusion）

当有多个三角形需要光栅化时，我们需要正确处理三角形的前后关系，以保证前面的三角形会正确地遮挡后面的三角形。

画家算法（Painter’s Algorithm）

画家算法是通过模拟油画家的作画方式来进行渲染。油画家们在画油画时，会先画处于远处的物体，然后再画处于近处的物体，这样处于近处的物体就会遮挡处于远处的物体。类似的，在光栅化三角形时，先光栅化处于远处的三角形，再光栅化处于近处的三角形。这个算法需要先将所有的三角形按照深度（即 \(z\) 坐标）进行排序，假设有 \(n\) 个三角形，排序算法的复杂度为 \(\Omicron\left(n \log n\right)\)。这个算法存在以下几个问题：

  1. 算法复杂度较高；
  2. 有时候不好确定各个三角形的远近，甚至会出现下图所示的情况。
遮挡成环的情况

Z-Buffer

深度缓存（Z-Bufer）算法是处理远近的终极算法。

深度缓存会记录每个像素最小的深度值，会生成深度缓存（Depth buffer）和颜色缓存（Frame buffer）遍历所以三角形上的点，对于任意一个像素，我们记录下这个像素上深度最小的深度信息和颜色信息（假设深度是正数）。Z-Buffer 算法的描述如下：

1
2
3
4
5
6
7
8
9
10
for (each triangle T) {
    for (each sample(x, y, z) in T) {
        if (z < zbuffer[x, y]) {	// closest sample so far
            framebuffer[x, y] = rgb;	// update color
            zbuffer[x, y] = z;	// update depth
        } else {
            // do nothing, this sample is occluded
        }
    }
}

使用深度缓存生成的深度缓存图和颜色缓存图如下所示：

Img

深度缓存技术的时间复杂度是 \(\Omicron \left(n\right)\)。这并不是一个排序算法，因此复杂度比排序算法要小。如果 MASS 中需要深度缓存技术，需要对每一个采样点应用 Z-Buffer 算法。