GAMES101学习笔记（三）：Rasterization 光栅化（三角形的离散化、抗锯齿、深度测试）

课程资源：GAMES101-现代计算机图形学入门-闫令琪

Lec5 ~ Lec6 学习笔记：
Lecture 05 ：Rasterization 1 (Triangles) ——光栅化（三角形的离散化）
Lecture 06 ：Rasterization 2 (Antialiasing and Z-Buffering) ——光栅化（抗锯齿和深度测试）

视口变换 Viewport

在变换的章节，我们了解了MVP变换(即Model、View、Projection Transformation)，也可以称为观测(Viewing)矩阵变换；
也了解了通过投影变换将三维空间中的物体投影到二维平面：

• 正交投影：忽略深度信息，相当于将相机放在无限远
• 透视投影：考虑相机位置，近大远小

下一步，我们将通过视口变换(Viewport Transformation)将投影变换出来的结果显示在屏幕上。


这将产生3个问题：

• 何为屏幕？
  图形学中，认为屏幕是一个二维数组，数组的每一个元素为一个像素。
  这个数组的大小即为分辨率，例如1280*720，表示这个屏幕的分辨率为720p。
  屏幕是一种典型的光栅成像设备。
• 何为光栅？
  Raster即德语中的屏幕。
  Rasterize光栅化的过程就是将东西画在屏幕上的过程。
• 何为像素？
  在这门课中我们暂时认为像素是一个小方块，内部的颜色是一个混合的颜色，颜色值用RGB表示。

通常我们将屏幕左下角设定为屏幕空间原点(0, 0)
屏幕空间坐标为整数，范围从(0, 0)到(width-1, height-1)
像素(x, y)中心在(x+0.5, y+0.5)

然后我们暂时忽略Z坐标，通过视口变换矩阵转换到屏幕空间坐标。
视口变换后，我们要把这些多边形显示在光栅显示设备上。

常见的光栅显示设备：

• 示波器Oscilloscope （阴极射线管CRT, Cathode Ray Tube）
• LCD显示器（Liquid Crystal Display，液晶显示器）
• LED显示器（Light-Emitting Diode，发光二极管）
• OLED显示器（Organic Light-Emitting Diode，有机发光二极管）
• Electrophoretic（Electronic ink）Display

三角形网格 Triangle Mesh

Triangle - Fundamental Shape Primitives
为什么三角形是最基础的图元：

• 三角形最基础的多边形（most basic polygon），其他多边形都可以分解为多个三角形。
• 三点共面 Guaranteed to be planar
• 三角形的内外定义清晰，可以用叉乘判断内外 Well-defined interior
• 三角形内可以定义明确的插值方法 Well-defined method for interpolating values at vertices over triangle（barycentric interpolation）

通过判断像素的中心点和三角形的位置关系，可以实现最简单的光栅化。

采样 Sampling

采样就是将一个函数 离散化 的过程。

通过对像素中心是否在三角形内进行采样，我们就可以对三角形进行光栅化。
如何判断像素中心和三角形的位置关系？通过叉积

对于边界上的点，我们不做处理。实际上我们定义一个标准，统一处理就好。
我们也没有必要采样所有像素，可以定义Bounding Box在小范围采样。（除此之外也有多种加速采样的方法

轴向包围盒AABB，Axis-aligned bounding box

以上只是最简单的一种光栅化的理论，实际屏幕的光栅化要复杂的多。
但GAMES101中我们还是认为每个像素是一个简单的颜色均匀的小方块。

走样/反走样 Aliasing/Antialiasing

我们对三角形的采样与原三角形的显示效果有较大的差异
具体来说，边缘多了很多锯齿Jaggie现象，这种现象的学名叫做走样（Aliasing）
解决这种现象的过程就叫做反走样，也叫做抗锯齿（Antialiasing）
在了解反走样之前，我们要重新认识一下 采样 的理论

Sampling is Ubiquitous in Computer Graphics

采样在计算机图形学中应用的非常普遍。

• 光栅化即对二维点的采样（Rasterization = Sample 2D Positions）
• 摄影即对相机传感器感光元件的采样（Photograph = Sample Image Sensor Plane）
• 视频或动画即对时间的采样（Video = Sample time）

Sampling Artifacts(Errors/Mistakes/Inaccuracier) in Computer Graphics

采样广泛存在，采样产生的问题/瑕疵同样广泛存在

• 锯齿/走样
• 摩尔纹 Moire Patterns in Imaging
  跳过奇/偶数行和列产生的问题
• 车轮错觉 Wagon Wheel Illusion
  人眼在时间上的采样跟不上运动速度

产生这些问题的本质：
信号变换速度太快，但采样速度太慢。
Signals are changing too fast (high frequency), but sampled too slowly.

我们先介绍一个反走样的解决方法，再详细探究其原理：

先对图像做模糊(blur / pre-filter)，再对模糊后的图像采样。
顺序不能反，采样之后再模糊并不能起到反走样的作用。

采样频率、空间域与频率域

傅里叶级数展开：任何一个周期函数，都可以写成正弦函数和余弦函数的组合

信号处理中：

• 时间域（Time Domain）是描述数学函数或物理信号对时间的关系。是真实世界，是唯一实际存在的域。
• 频率域（Frequency Domain）是描述信号在频率方面特性时用到的一种坐标系。它不是真实的，而是一个数学构造。

图像处理中：

• 空间域（Spatial Domain）即图像空间，以图像左上为原点，横为y竖为x的二维平面。
• 变换域/频率域（Transform/Frequency domain）通过各种数学变换（如傅里叶变换、离散余弦变换、小波变换等）将图像从空间域转换到频率域或其他变换域。在变换域中，图像的特征以频率的形式表示，这使得某些类型的处理（如去除噪声、增强特定频率成分）变得更加高效和直观‌。例如，通过傅里叶变换将图像转换到频率域进行滤波处理后，再转换回空间域，可以得到滤波后的图像‌。

通过傅里叶变换可以图像从空间域转换到频率域。
在相同的采样频率下，我们可以看到信号频率越高，频域中高频信号丢失的现象越严重

上文提到反走样的一个方法是模糊，也就是滤波Filtering。如何在频域理解滤波？
想要详细深入了解各种滤波的细节，需要移步数字图像处理相关课程。
不过在现代项目中，图像处理一般都由深度学习来完成了。

一个方面：
Filtering = Getting rid of certain frequency contents
滤波就是去掉一部分频率信息

另一个方面：
Filtering = Convolution（= Averaging）
滤波即卷积，也即平均

Convolution Theorem
卷积定理
Convolution in the spatial domain is equal to multiplication in the frequency domain, and vice versa.
空域/时域上的卷积 相当于 频域中的乘积；频域上的乘积 也相当于 空域/时域上的卷积。

用更大的卷积核只能留下更小的频率

深入理解采样、走样、反走样

采样 = 重复一个原始信号的频谱

如下图现象，我们可以从另一个层面定义走样：
同样的采样方法，采样不同的两种函数，我们无法区分它，这种现象叫做走样。

关于计算机图形学中的走样现象
光栅化的图形显示器用离散量来表示连续量，因为其中采样的频率并不满足Nyquist采样定理引起的信息失真，是形成图片具有锯齿状或者阶梯状的主要原因，为了消除走样而产生的技术被称为反走样技术。
如上图，黑色低频信号和蓝色高频信号得到一致的采样点，蓝色信号采样不足时，就会可能和黑色信号一样，造成严重走样现象。

香农采样定理，又称奈奎斯特采样定理，是信息论，特别是通讯与信号处理学科中的一个重要基本结论。
Nyquist采样定理：为了不失真地恢复模拟信号，采样频率应该大于模拟信号频谱中最高频率的2倍。

走样 = 频域上是出现了频谱的混叠
采样不够快，f就越小，频谱在复制粘贴的时候发成了重叠，导致走样的问题

时域上的走样失真，在频域上是出现了频谱的混叠；而图形学上的渲染，实际上是对连续函数(图像中的几何关系，着色参数，以及着色方程等)在空间内进行离散的采样，而这个函数包含的频率范围是无限的，意味着不论用多大的采样频率都无法完美恢复原始信号(图形分辨率有限)，所以会造成频谱的混叠，形成走样。这个无法避免，所以在图形渲染中能做的是利用各种技术去减轻走样。

回到我们一开始说的反走样方法：先做模糊（滤波），再进行采样。

• 反走样/抗锯齿操作流程：（消除混叠）
  • 滤波/模糊，砍掉高频信号
  • 再以稀疏的采样率采样
• 如何重新理解滤波/模糊操作？
  模糊操作 = 用低通滤波器做卷积
• 如何在采样时处理模糊？
  超采样MSAA(MultiSampling Anti-Aliasing)
  对每个像素，根据三角形覆盖面积重新计算灰度均值。

反走样总结

总的来说，造成图形学上的走样原因包括两种：

• 几何走样：在图形渲染管线的光栅化过程中，对连续图元进行采样得到离散的片元的过程，也就是几何走样产生的过程。理想的几何图形中的点线是没有宽度的，而光栅化后在显示器上的像素点有了大小，出现阶梯和边缘锯齿状的现象。
• 着色走样：发生在对渲染方程的采样不足，比如纹理映射过程中，是从纹理坐标映射到多边形或者曲面上，再映射到屏幕。从纹理的单个纹素对应到屏幕上时，引起的放大缩小，纹素的多余或者缺少，会造成走样着色时在空间变化较快的高频部分采样不足也会形成走样，形成图像闪烁或者噪点（高光部分的噪点）。

图形学中的走样包括 几何走样 和 着色走样，这些走样引起的锯齿和闪烁现象对图形的显示质量有很大的影响，给人观感不佳，这与人们对高质量和高真实感图像的追求相悖，所以高效高性能的反走样算法也一直是计算机图形学的研究与应用热点之一。

相对来说人眼对几何走样的敏感度更高，所以一般提到反走样技术也大多是几何方面的反走样，但随着硬件的发展和人们对画质要求的提高，也有许多算法用于解决着色反走样，两类算法的解决思路也往往差别很大。

在反走样算法的发展过程中出现了不同形式的算法，并且近年来随着深度学习的发展，也助推了反走样算法的研究。

• 基于超采样的方法(SSAA、MSAA 等)
• 基于形态学的方法(MLAA、SMAA、FXAA 等)
• 基于时间的方法(TAA 等)

超分辨率 / 超采样 Super resolution / Super sampling

• 从低分辨率到高分辨率
• 需要解决样本不足的问题
• 解决方案：DLSS（Deep Learning Super Sampling）
  即由AI预测样本不足的部分

深度测试 Depth testing

复杂三维物体在光栅化的过程中，还要解决一个复杂问题：

• Visibility / occlusion
  可见性 / 遮挡问题

画家算法 Painter’s Algorithm
根据绘画的逻辑，先画远处的物体，再画近处的物体，近处物体可以遮挡住远处物体。
简单场景中，画家算法可以根据正确的排序画出正确的场景。
但在复杂场景下，例如循环遮挡的环状场景下，画家算法就无法画出正确的场景。

实际计算机图形学中的解决方法是引入深度缓存Z-buffer

渲染每帧图像时，同时生成深度图。深度值存储在每个片段里面（作为片段的z值），当片段想要输出它的颜色时，我们会将它的深度值和z缓冲进行比较，如果当前的片段在其它片段之后，它将会被丢弃，否则将会覆盖。

对N个三角形，Z-buffer算法复杂度是O(n)。它不涉及排序，只保存最小的深度值。

Z-buffer算法的结果与三角形进入顺序无关。

这个过程称为深度测试(Depth Testing)

Z缓冲无法处理透明物体