本节说明

严格来说，GAMES101课程中视口变换实际上是光栅化部分的内容，但是为了变换部分梳理的完整性和便于把握从场景模型到屏幕空间的完整变换过程，本系列将其放在变换部分进行梳理，具体参见GAMES101知识梳理：变换。GAMES101课程中与视口变换一同说明的屏幕空间定义相关内容本文不再赘述。

本部分内容涉及了一部分信号与系统(Signals and Systems)、数字信号处理(Digital Signal Processing, DSP)学科中的内容，限于篇幅此部分并不会进行详细说明，如需了解更加具体的内容可参考文末Further Reading部分中的书籍。

Rasterization-光栅化

Raster Display-光栅显示设备

示波器，阴极射线管(CRT)，LCD，LED，电子墨水屏，…

显示的图像实际上就是内存中的一块区域，我们需要显示的图像/像素信息会存储在被称为帧缓冲区Frame Buffer的地方。

三角形的光栅化

选择三角形作为基础图元的原因:

  • 三角形最基本的多边形
    • 任何多边形都可以拆分成三角形
  • 三角形必定是一个平面
  • 三角形内外的定义很清晰
  • 三角形内部的点易于插值

Sampling-采样

由于一个像素的内部不会有颜色变化，因此判断每个像素应该被绘制成什么颜色需要先判断每个像素(的中心点)与三角形的位置关系。一个最简单的方法就是通过采样。在光栅化中，是用像素中心对屏幕空间进行采样，也就是对于每个像素中心算得其值。
三角形采样

采样的具体做法

对于每个像素中心，判断其是否在三角形内部。
通过如下图所示的inside函数
Inside函数
Rasterization = Sampling A 2D Indicator Function
采样过程伪代码

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函数的实现

三次叉乘同号，即点在三角形三边的同侧则其只可能在三角形内部。
此处的叉乘无所谓顺序。

注：边界情况在图形学中要么不做处理，要么特殊处理（如OpenGl定义上边与左边上的点为内部点，右边与下边为外部点）。

使用包围盒加速

采样时无需遍历整个屏幕空间，使用包围盒(Bounding Box)可节省开销。在包围三角的轴对齐包围盒(AABB)内部遍历即可。

对三角形三个顶点坐标的X,Y分量都取最小值、最大值，得到xmin,xmax,ymin,ymaxx_{min},x_{max},y_{min},y_{max}。
包围盒区域为[(xmin,ymin),(xmax,ymax)][(x_{min},y_{min}),(x_{max},y_{max})]。
AABB

其他加速方法

Incremental Triangle Traversal
对三角形覆盖区域每一行找最左和最右像素，这样不会多考虑任何一个无需绘制的像素。
Faster
这种方法比较适合光栅化窄长且斜在屏幕空间的三角形，因为此时其包围盒覆盖了很多无需考虑的像素，而三角形实际上并未覆盖很多。

关于像素的补充

实际屏幕上的一个像素并不是一整个小方块显示一个均匀的颜色，而是由几个不同颜色的子像素构成，可以是RGB，RGBW，…，甚至也可以不以单个像素为单位排列，而是遵循一定规则排列整个空间，且在概率上保证任意圈出的一块区域中RGB的密度相等（想象一下高中化学中硅的晶体结构，很相似）。
机圈很常见的俗称周冬雨排列、三星钻排等等，其实说的都是像素排列。
Pixels
此部分仅作了解，在GAMES101课程中，我们仍把每个像素认为是一个内部颜色均匀的小方块。

Digital Signal Processing-数字信号处理

**Fourier Expansion-傅里叶级数展开

f(x)=a0/2+∑n=1∞(ancos⁡nx+bnsin⁡nx),x∈[−π，π]f(x)=a_0/2+\sum_{n=1}^\infty(a_n\cos{nx}+b_n\sin{nx}), x\in[-\pi，\pi]

其中，

{a0=1/π∫−ππf(x)dxan=1/π∫−ππf(x)cos⁡nxdxbn=1/π∫−ππf(x)sin⁡nxdx\begin{dcases} \small a_0=1/\pi\int_{-\pi}^\pi f(x)\mathrm{d}x \\ \\ \small a_n=1/\pi\int_{-\pi}^\pi f(x)\cos{nx}\mathrm{d}x \\ \\ \small b_n=1/\pi\int_{-\pi}^\pi f(x)\sin{nx}\mathrm{d}x \\ \end{dcases}

Fourier Transform-傅里叶变换

f(x)⇒F(ω)=∫−∞∞f(x)e−2πiωxdx⇒F(ω)Spatial Domain⇒Fourier Transform⇒⇐Inverse Transform⇐Frequency Domainf(x)⇐f(x)=∫−∞∞F(ω)e2πiωxdω⇐F(ω) f(x) \rArr F(\omega)=\int_{-\infty}^\infty f(x)e^{-2\pi i\omega x}\mathrm{d}x \rArr F(\omega) \\ {} \\ \normalsize{ \colorbox{Lavender}{\textcolor{black}{Spatial Domain}} } \footnotesize{ { \rArr \colorbox{orange}{Fourier Transform} \rArr }\atop { \lArr \colorbox{orange}{Inverse Transform} \lArr } } \normalsize{ \colorbox{Lavender}{\textcolor{black}{Frequency Domain}} } \\ {} \\ f(x) \lArr f(x)=\int_{-\infty}^\infty F(\omega)e^{2\pi i\omega x}\mathrm{d}\omega \lArr F(\omega)

计算机中存储的是离散的值，因此无法直接使用上述傅里叶变换的公式进行时域频域的相互变换。实际应用中常使用，离散傅里叶变换(Discrete Fourier Transform, DFT)、快速傅里叶变换(Fast Fourier Transform, FFT)等方法。

Nyquist’s Theorem-奈奎斯特采样定理

产生走样的原因通俗来说是采样频率过低，跟不上信号的频率。

准确的描述需要用到采样定理，或称奈奎斯特采样定理。简单来说，就是采样频率大于信号最高频率的2倍时，采样信号才能无失真地恢复原信号。其中，信号最高频率2倍的频率被称为奈奎斯特频率，该频率对应的时间间隔称为奈奎斯特间隔。

Filtering-滤波

滤波就是从信号中滤除一系列特定的频率分量。
滤波器通常可分为低通(Low-pass)、高通(High-pass)、带通(Band-pass)、带阻(Band-stop)四种。

同样地，由于计算机使用离散的值，通常使用的滤波器也是数字滤波器而非模拟滤波器。

图像经过傅里叶变换的频域图像如下
FT
图像中像素信息剧烈变化的部分为高频（如边界位置），变化较缓的部分为低频。

对图像施加高通滤波器，滤除低频保留高频，则只显示边界
hpf

对图像施加低通滤波器，滤除高频保留低频，则边界被模糊
lpf

Convolution-卷积

卷积在CV、机器学习中非常常见，对于CG来说我们暂且不需要了解特别深入，看明白闫老师在课上说的卷积核如何在图像中移动、计算即可，这里不再具体说明。

关于卷积的明确定义与解释可参考Further Reading中《信号与系统》一书

Convolution Theorem-卷积定理

时域卷积定理——两个信号时域的卷积对应这两信个号频域的乘积。
频域卷积定理——两个信号时域的乘积对应这两个信号频域的卷积除以2π2\pi。

Antialiasing-反走样

Aliasing-走样

我们通过光栅化方法将中心在三角形内部的像素涂成对应颜色后，可以看见三角形边缘会出现锯齿(Jaggie)。
Jaggies
锯齿就是一种常见的走样(Aliasing)。

走样产生的根本原因就是采样，因为采样导致的一切不准确/有瑕疵的结果在图形学上称为Sampling Artifacts。除了锯齿，常见的Sampling Artifacts还有摩尔纹(Moiré Patterns)、车轮效应(Wagon Wheel Illusion)…

反走样方法

增加采样率（分辨率）固然可以减少我们看到的走样，但是这并不是对于同一个显示设备而言的，而且得加钱…这不是反走样要做的事情，反走样关注于在同样的显示设备、同样的物理限制下获得更好的显示效果。

先模糊再采样

BlurringBeforeSampling
此处模糊本质上就是使用一个低通滤波器对信号进行卷积，将信号频率过高而导致其不满足奈奎斯特定理的频率分量滤除。滤波后的信号在当前采样频率下是符合奈奎斯特采样定理的，因此对于滤波后的信号而言，采样不会带来Sampling Artifacts。

需要特别注意的是，滤波与采样的顺序不可颠倒。在数字信号处理中，采样相当于将信号的频谱以采样频率为周期进行周期性延拓。对于不满足奈奎斯特采样定理的信号，先进行采样会导致周期信延拓后的频谱产生混叠，导致信号产生错误，这种混叠造成的错误是滤波无法消除的。而先滤波后采样的信号，其频谱周期性延拓后不会产生混叠。可以简单理解为先滤波后采样只是去除了采样后会失真的信息，但是先采样后滤波会导致信息错误且无法完全去除这种错误。
MixFreq

如下图所示，先采样后滤波导致图像既有锯齿又模糊，而先滤波后采样的效果很好。
FilterAndSample

MSAA-多重采样反走样

多重采样反走样(Multi-Sampling Anti-Aliasing, MSAA, 游戏中常称作多重采样抗锯齿)，是一种超采样(Supersampling)方法，这种方法用更多的采样点来进行反走样，这是一种对反走样的近似方法。

把硬件意义上的一个像素拆分成n×nn \times n个子像素，对每个子像素使用前文所述的inside函数进行判断。
以2×22 \times 2为例
MSAA_1
若一个物理硬件意义上的像素拆分成的四个子像素中有一个在三角形内部，则该物理像素内的覆盖率为25%；若有两个子像素在三角形内部，则覆盖率为50%，以此类推。这一步完成的是模糊，采样后结果如下图
MSAA_2

如今，游戏中实际使用的MSAA往往不是均匀拆分成正方形，而是使用了更加不规则的分布，同时子像素在计算时也被更多地复用，这就是为什么在游戏中我们开启4×\timesMSAA时不会出现帧数下降到原来的1/4的情况。

其他反走样方法

  • 快速近似抗锯齿(Fast Approximate Anti-Aliasing, FXAA)
  • 时间性抗锯齿(Temporal Anti-Aliasing, TAA)
  • …
  • Super Resolution-超级分辨率
    • DLSS(Deep Learning Super Sampling)
  • …

Visibility & Occlusion-可见性与遮挡

Painter’s Algorithm-画家算法

从远到近绘制，像画油画一样，这样就能形成近处物体在前远处物体在后的遮挡关系。

画家算法的最大问题是，对于距离相近的物体绘制的先后顺序不同可能会导致结果不同、出现错误，而对于互有部分遮挡的多个物体，画家算法则完全无法解决，如下图
Painter

在三角形覆盖有限个像素的前提下，使用快速排序的画家算法绘制nn个三角形，其复杂度为O(nlog⁡n)O(n\log{n})。

Z-Buffer/Depth Buffer-深度缓冲

Z-buffer的基本思想

  • 存储每个像素绘制的采样点当前的最小深度（Z值）
  • 需要一个额外的缓冲区用于深度信息的存储
    • Frame Buffer存储像素颜色信息
    • Depth Buffer(Z-Buffer)存储深度信息，与Frame Buffer同步生成

注：此处我们认为z值小的物体近，z值大的物体远，深度缓冲区中记录的z值永远为正值，而非直接记录坐标值。不要因为先前定义相机朝向-Z而搞反了。

深度缓冲区在作业1的框架中已经出现在光栅化器类里面，但是未使用。关于作业1框架的分析可参考GAMES101作业1：旋转与投影

Z-BufferExample

Z-Buffer算法流程

for (each triangle T)
{
    for (each sample(x, y, z) in T)
    {
        if(z < zbuffer[x, y])         //closest sample
        {
            framebuffer[x, y] = rgb;  //update color
            zbuffer[x, y] = z;        //update depth
        }
        //else do nothing, this sample is occluded
    }
}

Z-Buffer中各像素的初始z值为无限大。对于当前绘制的三角形，遍历其覆盖的像素，如果像素的z值比当前记录的z值小，则更新记录该像素z值的最小值，并且更新对应的framebuffer中记录的颜色；如果z值比当前记录的大，说明当前三角形在这个像素上被先前绘制的其他三角形遮挡，因此无需操作。

Z-Buffer原理的示意图如下
Z-BufferPic

在三角形覆盖有限个像素的前提下，使用Z-Buffer算法绘制nn个三角形，其复杂度为O(n)O(n)。

注：Z-Buffer算法假设不会出现两个三角形在同一个像素位置具有同样深度。

至此，我们已经能将一个3D变换到屏幕空间，并且正确判断各物体的遮挡关系了。
但是要计算出每个像素颜色具体应该是什么值，我们还需要使用着色相关的知识。

Further Reading

数字信号处理(第四版), John G.Proakis, Dimitris G.Manolakis. 方艳梅, 刘永清 等译。
信号与系统（第二版）, Alan V. Oppenheim, Alan S. Willsky, S. Hamid Nawab. 刘树棠 译。