GAMES101笔记(2)——Rasterization

课程链接：GAMES101-现代计算机图形学入门-闫令琪
课程讲师：闫令琪
本系列笔记为本人根据学习该门课程的笔记，仅分享出来供大家交流，希望大家多多支持GAMES相关讲座及课程，如涉及侵权请联系我删除：albertlidesign@gmail.com

经过上一节我们将所有的物体都映射到了一个 $[-1,1]^3$ 的立方体里，那么下一步我们该怎么办？下一步就是将这些物体画在屏幕上，这一步就叫做光栅化 (Rasterization)。

Canonical Cube to Screen

屏幕的定义

既然要画在屏幕上就需要把屏幕的概念定义好：

它是一个包含像素 (pixels) 的数组 (array)
数组的尺寸：分辨率 (resolution)，例如 $1920×1080 (1080p)$
屏幕是一个典型的光栅成像设备

Raster在德语里就是screen，光栅化Rasterize == drawing onto the screen

像素pixel是"picture element"的简写，在这里我们定义一个像素是一个颜色均匀的小正方形，它包含 $(red, green, blue)$ 三个值。

屏幕空间

屏幕空间就是在屏幕上建立一个坐标系，约定俗成地，以左下角为原点 $(0,0)$ ，向右为 $X$ ，向上为 $Y$ ，因此任何屏幕上的点都可以用 $(x,y)$ 来表示。

每一个像素的坐标都是用 $(x,y)$ 来表达，这里的 $x$ 和 $y$ 均为整数。例如图中蓝色的像素为 $(2,1)$
如果我们定义屏幕的分辨率为 $width×height$ ，则所有的像素的坐标的范围为从 $(0,0)$ 到 $(width-1,height-1)$
像素 $(x,y)$ 的中心点位于 $(x+0.5,y+0.5)$ 。例如蓝色像素的中心为 $(2.5,1.5)$
整个屏幕覆盖的范围为从 $(0,0)$ 到 $(width,height)$

因此为了完成 $[-1,1]^3$ 的立方体映射到屏幕这一操作，我们需要将物体的 $z$ 坐标移去，将 $xy$ 平面上的 $[-1,1]^2$ 变换到 $[0,width]×[0,height]$ 。我们只需将宽度和高度都除以 $2$ ，然后再将它的中心从 $(0,0)$ 移动到屏幕空间左下角，也就是移动宽度除以 $2$ 和高度除以 $2$ 的距离。视口变换的表达式如下：

$M_{viewport} = \left[\begin{matrix} \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{matrix}\right]$

到这一步时，我们已经得到平面上的图，三维空间中的网格模型经过以上变换，变成了屏幕空间中的多边形，我们需要把这些多边形进一步“打碎”，打成像素，变成每一个像素上的颜色值，这就是我们所说的光栅化。

Triangle Meshes

为什么选用三角形网格？

它是最基本的多边形
任何多边形都可以被拆分成多个三角形

三角形网格的独特性质

三角形一定是平面图形。三点共面
三角形的内外定义清晰。可以通过向量叉积来定义一个点在三角形内还是三角形外
面内插值方便。只要定义三角形三个顶点不同的属性，就可在三角形内部做这个属性的渐变效果，也就是说，通过三角形面内的一个点和其他点的位置关系，可以得到一个插值。（重心坐标插值方法）

通过屏幕上三个顶点坐标，可以知道一个三角形在屏幕中的位置，如左图所示。为了绘制出这个三角形，我们需要判断每个像素的中心点是否在三角形内部，这里介绍一个最简单的方法：采样。

采样

采样就是给定一个连续的函数，在不同的点处求它的函数值。也就是说，采样就是把一个连续的函数离散化的过程。

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

采样是一个非常重要的概念，在图形学里会涉及到各种各样的采样，我们可以采样时间、面积、方向、体积等等。我们这里说的采样，是指利用像素中心对屏幕空间进行采样，也就是说我们需要求出某一个函数在屏幕中不同的像素中心的值。

我们这里的采样就是去判断每一个像素的中心是否在三角形的内部，因此我们可以定义出这个函数：

$inside(tri, x, y) = \begin{cases} 1 \quad Point(x,y) in triangle t \\ 0 \quad Otherwise \end{cases} , x,y\ not\ necessarily\ integers$

Rasterization = Sampling A 2D Indicator Function

我们使用两个for循环来遍历所有的像素，对每一个像素执行采样方法即可完成光栅化的过程：

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);

那么如何定义函数 $inside(tri, x, y)$ 呢？也就是说我们需要去判断一个点是否在一个三角形内。我们可以用向量叉积的方法来判定，例如，如图所示，我们需要判断点 $Q$ 是否在三角形 $(P_0,P_1,P_2)$ 内，我们需要执行如下过程（注意顶点顺序）：

计算 $P_1P_2×P_1P_Q$ ，如果得到的向量的 $z$ 值为正，则 $Q$ 在向量 $P_1P_2$ 的左侧，否则在右侧
计算 $P_0P_1×P_0P_Q$ ，如果得到的向量的 $z$ 值为正，则 $Q$ 在向量 $P_0P_1$ 的左侧，否则在右侧
计算 $P_2P_0×P_2P_Q$ ，如果得到的向量的 $z$ 值为正，则 $Q$ 在向量 $P_2P_0$ 的左侧，否则在右侧

当三个叉积向量全部为正或负（同号）时，该点在三角形内部。

这里可能会有一种情况，刚好点在三角形边界上时该如何判断？要么不做处理，要么特殊处理。即点到底在三角形 $1$ 还是三角形 $2$ 上，可以自己定义标准，可以定义点既在 $1$ 又在 $2$ 上，也可以定义点不在这两个三角形上。

上面我们提到了通过采样来进行光栅化的过程，那么我们想，我们已经写了一个二重循环，也就是说考虑一个三角形的光栅化就需要将所有的像素都跑一遍，其实是没必要。一个三角形其实只能覆盖一个相对较小的区域，比如图中左边第一列根本不在蓝色的区域，就不可能碰到三角形，也就根本不用去考虑这些像素。蓝色的区域我们称为三角形的包围盒（Bounding Box），更严格地说是一个轴向包围盒（Axis Aligned Bounding Box，AABB）。求三角形的包围盒非常简单，只需要使用三个点最小和最大的 $x$ 值和 $y$ 值来构造一个区域。这样只有当这个三角形很窄长并且旋转45度左右的时候，才会用一个很大的Bounding Box来包住

还有一种方法是将三角形覆盖的区域中，每一行都去找它的最左和最右，这样的话一个多余的像素都不会多考虑。

经过以上操作，我们得到了如图所示结果，我们会发现这个结果不太对，因为它有锯齿(Jaggies)，这是因为我们的采样率对信号来说是不够高的，所以产生了走样（Aliasing）。因此我们要使用抗锯齿（也称反走样）技术来进一步优化。

反走样 (Antialiasing)

我们用每一个像素的中心去检测是否在三角形内，然后把对应的像素涂上颜色，我们最后绘制出来的图案就是带有锯齿的图像。事实上我们不希望有锯齿，因此我们需要抗锯齿和反走样。锯齿的学名叫走样（Aliasing），反走样就称为Antialiasing。

采样理论

前面有提到，采样是在图形学中广泛存在的一个做法。光栅化的过程其实就是在屏幕空间离散的点上进行是否在三角形内的采样。对于任何一个我们拍出来的照片，放大后就会发现很多格子，也就是像素，这也是我们表示图像的基本方法。一副照片其实就是所有到达感光元件的光学信息，通过把它离散成图像像素的过程，其实也是采样。采样不光可以发生在不同的位置，也可以发生在不同的时间，视频就是在时间中进行采样。因此采样是广泛存在的，同样，采样所产生的问题也是广泛存在的。

Sampling Artifacts in Computer Graphics

采样所产生的错误（或称瑕疵）称为Artifacts。采样产生的第一个问题就是锯齿问题，如图所示。

然后是摩尔纹问题。如果我们把下左图中的奇数行和奇数列的像素都去掉，然后再重新对在一起，再显示原图大小，就会出现摩尔纹效果。当我们拿手机去拍显示器的屏幕也会看到类似的效果，这些都是采样带来的问题。

接着是车轮效应，当我们顺时针旋转纸片，如图所示，会有些条纹显得像是在逆时针旋转。在生活中也经常看到类似的现象，比如高速行驶的汽车，其轮子看上去在反向旋转，这是因为人眼在时间中的采样跟不上运动速度所造成的。

因为采样所产生的问题有：

锯齿问题 (Jaggies) - sampling in space
摩尔纹问题 (Moire) - undersampling images
车轮效应 (Wagon wheel effect) - sampling in time
Many more...

采样产生问题的本质其实是信号变化过快导致采样速度跟不上。因此我们要通过频率来分析它。

Antialiasing Idea: Blurring (Pre-Filtering) Before Sampling

如何进行反走样，答案是在采样之前先做模糊（或滤波）。之前我们采样会发现，有些点完全在三角形内，有些点完全在三角形外，因此这些点要么是红的要么是白的。

但是如果我们在拿到一个三角形后，先做一个模糊操作，把它变成一个模糊的三角形，然后再去用像素中心点采样，这样就可以解决锯齿问题，得到下图效果。

举个例子，上图中，左图为抗锯齿操作之前，右图为抗锯齿操作之后。但是，先采样再模糊是不行的。下图是效果对比：左图是先采样再模糊，右图是先模糊再走样。先采样再模糊的操作称为Blurred Aliasing，先模糊再采样的操作称为反走样 Antialiasing

那么，为什么采样速度跟不上信号变化的速度就会产生走样？为什么要先做采样再做模糊达不到发走样的效果呢？为了弄清楚这些事我们需要了解频域（Frequency Domain）方面的知识

Frequency Domain

我们来看最简单的波：sines and cosines。通过调整 $x$ 前面的系数，例如 $2\pi x$ 和 $4 \pi x$ ，我们能得到不同的余弦波，它们的不同在于频率不同，我们定义 $cos2\pi fx$ ，其中 $f$ 为频率，因此 $cos4\pi x$ 的频率 $f=2$ ，因此我们可以用频率 $f$ 来定义余弦波的变化有多快。同样道理，我们还可以定义它的周期 $f=\frac{1}{T}$ ，通俗地讲，所谓周期就是每隔多少 $x$ ，函数会重复自己一次，例如 $cos2\pi x$ 每隔 $1$ 会重复一次， $cos4\pi x$ 每隔 $0.5$ 会重复一次。因此周期是频率的倒数。

那么为什么我们要介绍周期和频率呢？因为傅里叶变换（Fourier Transform）会用到它们。微积分里面有一个概念是函数展开，其中一个就是傅里叶级数展开。

傅里叶级数展开就是说，对于任何一个周期函数，都可以把它写成一系列正弦和余弦函数的线性组合以及一个常数项。

这样我们就可以把一个函数描述成很多不同的正弦余弦项的和。这说明傅里叶级数展开和傅里叶变换是紧密相连的。给定任何一个函数，我都可以经过一个复杂的操作变成另外一个函数，也可以把变换后的函数通过逆变换变回原来的函数，这样的操作就称为傅里叶变换和逆傅里叶变换。

不同的函数都有着不同的频率，仔细上图傅里叶级数展开的中 $\omega$ 的系数分别为 $3t,5t,7t,...$ 这些值都代表了不同的频率，也就是说通过傅里叶级数展开可以将任何一个周期性函数分解为不同的频率。所谓傅里叶变换其实就是把函数变成不同的频率的段，并且把这些不同频率的段显示出来。

举个例子，如上图所示，通过傅里叶变换我们得到了这 $5$ 个不同的函数，我们知道这些函数都含有不同的频率，假设我们对这些函数进行一次相同间隔的采样我们会发现如下图所示结果

从 $f_1$ 到 $f_5$ 会发现， $f_5$ 的采样效果非常差。这也就是说通过频率分析，我们可以体会到，对于一个函数来说，它本身有一定的频率，采样也有一定的频率，但是如果我们采样的频率很低而函数本身的频率很高，就会跟不上它的变化，就没有办法将原始的信号拟合出来。

再看一个例子，蓝色线是函数本身，黑色线为采样得到的函数。现在如果我们把黑色线看作是另一函数，我们发现，如果我们用同样的一个采样方法采样两种截然不同的信号，我们会得到完全相同的结果。即采样频率相差很多的蓝色的函数和黑色的函数所得到的结果完全相同。这一现象就称为“走样”。

Filtering

现在我们知道了走样的定义，也知道了傅里叶变换，那么就可以开始真正的分析一些函数倒底拥有怎样的频率。这里有一个重要的概念——滤波（Filtering），它就是把某个特定的频段去除。傅里叶变换可以帮助我们理解这个问题，它可以将函数从实域变到频域。如下图所示，左图是一个人的图像，也就是实域，我们将其作傅里叶变换，得到右图为频域。

那么右边这幅图应该如何理解呢？中心是左边这张图最低频的区域，四周为高频区域，也就是说从中心到四周，其频率会越来越高。其亮度表达了左图在该频域的信息量。这张图就说明左图大多数的信息都是集中在低频上的，高频的信息相对于低频会少很多，实际上自然中所有的图片基本都是这样的。有人可能会问为什么图片中有一个十字，水平一条线、竖直一条线很明显。简单地说，这是因为在分析一个信号时它是一个周期重复的信号，对于没有周期重复的信号的话就将无限多个图像叠放，因为很少有图像左边界和右边界完全一致，不一致的情况下，我们把这个图像的左侧放到它的右侧，就会产生一个极高的高频，傅里叶变换就会产生这两条线，为了分析，我们暂时忽略这两条线。也就是说，傅里叶变换能够让我们看到这个图像在各个不同的频率的样子，我们称之为频谱。

接着，如果我们使用滤波，去掉频域中心的内容，也就是去掉低频的内容，保留高频的区域，然后我们再使用逆傅里叶变换得到实域，就会得到如图所示结果。从图中我们可以看到，高频信息表示的其实就是图像内容上的边界。这样的滤波称为高通滤波（High-pass filter）。那么通常我们所说的边界其实就是指图像上的某一区域的周围发生了剧烈的变换，也就是所谓的边界，比如人的衣服和背景之间的色差，这样的信息就是高频信息，那么如果我们只显示高频的信息，得到的就是图片中各物体的边界。

再反过来，将高频信息全部去除，只保留低频信息，得到如下图所示结果。我们会发现得到了一张相对模糊的图，绝大部分细节被去除了。这里就是应用了低通滤波器（Low-pass filter）。边界被去除了就会变得模糊。

接下来，我们将高频和最低频信息都去除，保留中间频率的信息，得到下图所示结果。我们得到了不是很明显的边界特征，因为最明显的边界特征对应最高的频率。

更多关于这方面的信息可以去了解一门课，叫《数字图像处理》，图形学中就不再过多赘述了。这是一个经典操作，现在更多的操作是通过机器学习来完成的。

Convolution Theorem

我们说滤波其实就是去掉特定频率的信息，从另外一个角度上看，滤波又等于卷积，或者平均，Filtering = Convolution ( = Averaging)。平均的概念比较好理解，低通滤波器就是将图片模糊，也就是一种平均操作。然后卷积是什么呢？

如上图所示，对于一系列信号数组，滤波器就好像一个窗口，它可以左右移动，窗口的大小是3个格子，这其实是要做一个卷积（Convolution）操作。这是在说，在移动这个窗口的时候，窗口三个数所对应的信号的三个数做一个点积操作，如下图所示，最后将结果写回这个格子。对所有格子做这样的操作，就会得到新的数组。注意这里的卷积定义不是数学上的定义，是图形学简化的定义。

卷积理论：实域上如果要对两个信号进行卷积，其实，对应到两个信号各自的频域上，就是两个信号的频域的乘积。在实域上如果是对两个信号进行卷积，那就是频域上对其信号的乘积。通过这个理论我们可以直接对图进行一个卷积操作，也可以将这幅图先用傅里叶变换，变换到频域上，再把卷积的滤波器变到频域上，两者相乘，得到频域上的结果，再把它逆傅里叶变换变回实域，这两个操作是一样的。

我们对图片进行一个平均或者是卷积操作，即对任何一个像素，取它周围 $3×3$ 个像素的平均，那么得到的结果就是一个模糊的图像。我也可以使用傅里叶变换的方法来做这样的操作，最后通过逆傅里叶变换变回这幅图。实域卷积=频域乘积，频域卷积=实域乘积。

再举一个例子，下左图为实域，右图为频域，如果左图中的方形变大了，频域会如何变换呢？

答案如下图所示，变小了。因为我们为了模糊一张图，用了一个 $3×3$ 的卷积操作，如果我们换成一个 $21×21$ 的方形做卷积，那么得到的结果会越来越模糊，也就更接近于低频。如果我们用一个很小的方形做卷积，那么对应频域的范围就会很大，也就能留下更高的频域，最后模糊的效果就会不明显。

从频率的角度看采样

下面我们再从频率的角度来看什么是采样。采样就是在重复频率或者说频域上的内容Sampling = Repeating Frequency Contents。

如上图所示，图 $a$ 为某个连续的函数，其频域为图 $b$ ，假设我们要采样这个函数，就要取一系列离散的点，留下这些离散点的函数值。也就是让函数 $a$ 去乘另外一个函数，这个函数只在一些固定的位置有值，其他地方没有值，也就是图 $c$ ，这样的函数称为冲击函数。我们令 $a$ 函数乘 $c$ 函数，得到的就是图 $e$ 函数，这就是采样。也就是给定一个原始函数 $a$ ，我们乘上一个冲击函数就可以得到采样结果。在频域上，冲击函数的频域还是冲击函数，只不过间隔有所变化。我们记得实域的乘积对应到频域上是卷积，即 $b$ 卷积 $d$ ，最后的结果就是将 $b$ 重复了很多次。那也就是说，采样就是在重复原始信号的频谱。

所以，如果我们采样地不够快，原始信号重复的间隔就会非常小，意味着采样之间的距离很大，采样的越稀疏，频谱就越密集，频谱越密集，采样就越稀疏。如果频域上重复的时候叠在一起了，就发生了走样现象。所谓走样在频率图像上发生了混叠。

图形学中的反走样

增加采样率是终极解决办法，直接更换硬件来提高分辨率，例如用视网膜显示器来看图形，高分辨率意味着采样率高，意味着频谱与频谱之间的搬移间隔大，就不容易出现频谱的混叠。但是这并不是反走样要做的事情，反走样不会增加分辨率。

反走样操作：先模糊再采样。通过前面的讲解，我们知道先模糊再采样这一操作是有意义的。模糊就是用低通滤波将高频信息拿掉，然后再采样。

为什么这样是正确的？我们再看一个例子，一个函数的频谱就是如图所示的梯形，稀疏的采样就会发生频谱的混叠，产生走样。如果我们先做一个模糊，也就是把高频信号砍掉，也就是去掉虚线方块之外的信息，剩下的就是下图的信号。然后再采样，就不会发生混叠了。

在实际的操作中，我们用什么样的方法来对图像进行模糊呢？用一个一定大小的低通滤波器来进行卷积。最简单的块就是一个像素，一个像素就是一个box filter。因此我们的解决方案为：

原本的函数 $f(x,y)$ ，判定了一个三角形要么在三角形里要么在三角形外，这就是一个二值函数，我们用每一个像素对它进行一个卷积操作，也就是求一个平均，然后用平均值的中心采样（其实不需要采样，因为就一个像素对应一个box filter，就只有一个值）

对于任何一个像素，我们都能知道它可能被覆盖，我们对它的覆盖面积求平均，然后根据覆盖得多少赋值。

Antialiasing By Supersampling (MSAA)

那么我们如何把一个像素被三角形覆盖的区域算出来呢？实现并不容易，因此人们研究出一种近似算法，称为Antialiasing By Supersampling (MSAA)，它是一个反走样的近似，并不能严格意义地解决反走样的问题。

算法是将每一个像素划分成许多小像素，每一个小像素有一个中心，我们可以判断这些点在三角形内，再将这些点平均起来，如果点足够多就能得到比较好的结果。其实就是在一个像素内部增加采样点。例如一个像素里，如果 $4$ 个采样点都不在三角形内，就判定它不在三角形内，如果有一个采样点在三角形内，覆盖率就为 $25\%$ ，如果三个点在，覆盖率就为 $75\%$ 。通过这样的方法就能实现抗锯齿的效果。

因此MSAA解决的是对信号的模糊的操作，而下一步采样的操作被隐含在这一步里了。MSAA不是靠提升分辨率和采样率来直接解决走样问题。

通过MSAA，我们得到了一个不错的反走样效果，但是为了引入MSAA，我们牺牲了什么？很显然，我们使用了更多的点来测试是否在三角形内，也就是增大了计算量。因为这些点只是为了检测三角形的覆盖而已，却要付出很多倍的计算量。为了减少计算量，在工业界上不会规则地划分成均匀的 $4$ 个点，而会用一些分布不均的点来使很多样本得到复用。

FXAA和TAA

其他的具有里程碑意义的方法有：FXAA (Fast Approximate AA) 和TAA (Temporal AA)。FXAA是图像的后期处理方法，先把有锯齿的图得到，再通过一种操作把锯齿消掉。但是如果先得到锯齿的图，再做模糊操作是不对的，FXAA是通过图像匹配的方法找到边界然后替换成没有锯齿的边界，效率非常高。TAA方法是最近几年兴起的方法，它可以寻找上一帧的信息，用像素内的一个点没有做MSAA来感知，假如我们看到的是静止的场景，相邻两帧看到的信息一样，那么我们可以用不同位置上的点来感知覆盖信息，那么大家会发现在时间范围内，得到的边界会各不相同。TAA是复用上一帧得到的像素的值，相当于将MSAA的样本分布在时间上，这样就没有引入任何额外的操作，这是一个非常聪明的作法，对于运动物体，我们会在后面的实时光线追踪继续讲解。

超分辨率问题

如果我们有一张 $512×512$ 的图，我们想将其放大至 $1024×1024$ ，但是我们又不想看到锯齿，就也要解决样本不足的问题，因此超分辨率问题和反走样问题是非常相似的。有效的做法是DLSS（Deep Learning Super Sampling），利用深度学习来解决。