空间中的立体图形在经过MVP和视口变换屏幕空间中描述的一堆三角形,如图中的老虎，可以看到屏幕上有各种多边形，但这样还不够，还需要进一步将三角形打散成像素点，告诉成像设备每个像素的值应该是什么，raster在德语中就是屏幕的意思，变成动词，就是“把东西画在屏幕上”即rasterization:Drawing to Raster Display
光栅化是将屏幕空间中的连续几何图元转换为离散像素覆盖结果的过程，如下图
为什么选择三角形？
- 最基础的多边形 Most basic polygon
- 所有的多边形都可以拆成三角形 Break up other polygons
- 拥有独特的性质 Unique properties
- 除非折成两个三角形，否则永远是一个面 Guaranteed to be planar
- 三角形的内外很明确 Well-defined interior
- 有在三角形顶点处插值的明确方法（重心插值） Well-defined method for interpolating values at vertices over triangle (barycentric interpolation)
下一步需要将三角形光栅化，采样是实现光栅化的简单的一种方式：
从本质上看，光栅化可以理解为对屏幕空间中的二维覆盖指示函数进行采样：若图元覆盖该位置则取 1，否则取 0
采样 Sampling
- 在一个函数上求不同位置处对应的值分别是多少，这个过程就是采样 Evaluating a function at a point is sampling.
- 采样是一个将函数离散化的过程 We can discretize a function by sampling.
for (int x = 0; x < xmax; ++x)
output[x] = f(x);三角形采样
Rasterization = Sampling A 2D Indicator Function
定义一个二进制函数inside(t,x,y)其作用是输入屏幕空间中的任意一个点Point(x,y)，判断这个点是否在三角形内部，如果在三角形内返回1，不在则返回0
- 如果一个点恰巧在三角形的边界，要么不处理，要么特殊处理，图形API中一般有着严格规定
优化采样逻辑
但为了一小块三角形就对函数进行采样从而对屏幕空间上所有点进行计算真的有必要吗？
AABB包围盒
根据三角形三个顶点的位置确定一个包围盒，只对AABB包围盒(Axis-Aligned Bounding Box)内的像素点进行采样
逐行检测
方法对瘦长且旋转放置的三角形较为合适
采样 Sampling
采样在图形学中很常见 Sampling is Ubiquitous in Computer Graphics
- 光栅化 = 采样二维平面上的点 Rasterization = Sample 2D Positions
- 摄影 = 采样感光元件上的信息(将光学信息离散为图像上的像素) Photograph = Sample Image Sensor Plane
- 视频 = 在时间时间中的采样 Sample Time
采样造成的失真现象 Sampling Artifacts (Errors / Mistakes / Inaccuracies) in Computer Graphics
由于采样率对于信号频率来说不够高
（准确的说是要无失真地重建信号，其采样频率必须大于信号最高频率的两倍）
孤立边界的高频 → 锯齿 Jaggies(Staircase Pattern)-sampling in space
重复纹理的高频（尤其缩小） → 摩尔纹 Moiré Patterns in Imaging：左图跳过奇数行和奇数列后得到右图
- 车轮效应 Wagon Wheel Illusion (False Motion)-sampling in time
- 对高速旋转的物体采样可能出现视觉上倒转的现象
- 失真的原因 ：信号变化太快而采样太慢
抗锯齿/走样的原理分析 Antialiased
频域和时域
傅里叶变换可以把信号从时域转化到频域，因为从时域或空间域的角度看，该信号是由多种频率不同的正弦波的叠加，而从频域角度看，该信号的频谱却如此的简单，这便于我们的观测和计算
傅立叶级数展开：
任何一个周期函数都可以写成一系列正弦和余弦函数和一个常数项的和，这些正弦波和余弦波有着各自的频率，A是振幅。
空间域/时域和频域可以通过傅里叶变换和逆傅里叶变换相互转换 Fourier Transform Decomposes A Signal Into Frequencies
时域解释采样稀疏造成走样 Aliases
函数本身有一个频率，采样也应该有一个频率，由下图可知我们可以用高频率的采样频率恢复出高频率的函数，因此采样的频率相较于信号的频率来说过小，还原出的函数就会不准确，丢失很多原信息
可以看到由于采样频率过低导致两个不同频率信号的采样结果是完全相同的
在给定的采样率下无法区分两个频率，这种现象成为”走样“ Two frequencies that are indistinguishable at a given sampling rate are called “aliases”
滤波（去掉特定频率的信息） Filtering (Getting rid of certain frequency contents)
用傅里叶变换把一张图从时域转换到频域的结果如下：
- 上面的变换是把一段信号变换成很多个频率不同(从上到下频率递增)的波表示。
- 这里是把一个图片变换成一个频率不同(从内而外频率递增)图形表示。
在图像处理中，频率是指图像中像素值变化的速度或图案变化的速率，它衡量的是单位空间内亮度变化的程度
从中间向外频率不断变高，在不同频率的位置上有多少信息，用亮度表示。此例中中心亮度很高可以看出信息主要集中在低频，高频信息相比低频信息少了很多，事实上对自然的图片来说大部分都是如此
水平和竖直分割线产生原因：
分析信号时默认信号是周期性重复信号，但对于不重复周期信号比如比如图片，我们就认为到右边界之后重复左边界的内容（如果时函数就进行左延拓和右延拓）。就好比水平和竖直方向都重复放置了很多图片。而很少有图片左边界与有边界是一致的，这就导致在图片右到左的过程中，在这条边界上会发生剧烈的信号变化，也就会产生一个及其高的高频，这就是做傅里叶变换会看到两条线
把声音波形文件切一刀，比如之前完全静音，突然间有声音，就会有一声嚓的噪声。 做过剪辑的人应该都有这个体会。 现在想来，这段极短的阶跃如果编辑傅立叶变换的话，囊括了非常宽的频域，所以这也是变成噪声的原因吧……
其实这里我有一个疑问，很明显这是一个极坐标 / 复平面的坐标空间，那么亮度表示信号的振幅（强度），r – 距原点的距离表示频率的高低，由低到高，那这个图里的角度代表什么信息？
可以发现高频信号表示了图像的边界，图像信息变化快的地方频率就高，比如团的边界，纹理，褶皱。只留下低频信息
所以去掉高频可以图像的边界就变得模糊了
图中的水波纹是由于不完美的低通滤波造成的，可知内部细节越多，频率就越应该保留低频部分。
中通滤波器保留的是图像中间的部分
卷积 Convolution
- 时域的卷积等于频域的乘积，频域的卷积等于时域的乘积（两者具有对偶关系） Convolution in the spatial domain is equal to multiplication in the frequency domain, and vice versa
通过卷积定理实现对图像的处理
- 方法一：
- 在时域空间域中通过卷积过滤 Filter by convolution in the spatial domain
- 方法二：
频域解释采样稀疏造成走样
采样就是在重复原始信号频谱内容，即，在时域上进行采样 等价于 在频域上进行周期延拓 Sampling = Repeating Frequency Contents
从频率的角度上，采样如果较为稀疏，在该信号的频谱重复时会发生混叠，就会发生走样现象
采样定理，如果采样频率 fs（其倒数为采样周期 T）大于信号中的最高频率成分的两倍（即 fs>2B，其中 B是信号的带宽），则原始信号的信息可以从其采样值中完全恢复
如何减少反走样现象
- 方法一：增加采样率 ncrease sampling rate
本质上增加了采样时频谱中副本之间的距离 Essentially increasing the distance between replicas in the Fourier domain（f = 2Π /T，T越小，f不就越大）
使用更高分辨率的显示器、传感器、更高规格的帧缓冲区 Higher resolution displays, sensors, framebuffers…
但是：成本非常高，可能需要非常高的分辨率 But: costly & may need very high resolution
- 方法二：反走样 Antialiasing
在采样重复频谱前使其中的副本内容”更窄“，即在采样前滤除高频信息 Making Fourier contents “narrower” before repeating, i.e. Filtering out high frequencies before sampling
反走样具体的方法
- 先模糊后采样 Pre-Filtering Before Sampling
- 最简单可以使用一个像素大小的低通滤波器用于求该像素内的平均 Antialiasing By Averaging Values in Pixel Area
- 在光栅化一个三角形时，一个像素区域内的平均值等于该三角形在该区域的覆盖率
但如何知道有颜色部分到底占有像素的百分比呢？
超采样抗锯齿(Super Sample Anti-aliasing, SSAA)
一种很笨的方法是超采样抗锯齿(Super Sample Anti-aliasing, SSAA) ，它使用比正常分辨率更高的分辨率（即超采样）来渲染场景，当图像输出在帧缓冲中更新时，分辨率会被下采样至正常的分辨率。这些额外的分辨率会被用来防止锯齿边缘的产生。虽然它确实能够解决走样的问题，但是性能消耗成倍增加。 肯定不可取
多重采样抗锯齿(Multisample Anti-aliasing, MSAA)
我们认为把一个像素可以再细分为很多个次像素，给每个像素增加采样点（MSAA绝对不是增加分辨率来解决走样问题，增加采样点的目的只是为了算覆盖率）
判断这些小像素是否在三角形内，然后再把判断的结果进行平均，就能得到一个近似结果。
若一个像素被覆盖n个子采样点，则该像素 覆盖率 为(n/4)x100%
覆盖率计算完毕则得到每个像素被三角形覆盖的百分比， 到这里只是模糊操作完毕
模糊后再进行采样(采样每个像素的颜色) 像素的颜色=覆盖率x三角形颜色
其他方法：
- No Free lunch
- FXAA（Fast Approximate AA），生成有锯齿的图片之后，对锯齿进行处理，替换成没有锯齿的边界
- TAA（Temporal AA），将上一帧感知到的结果应用到当前帧，相当于把MSAA对应的这些样本分布在时间上，并且在当前帧没有引入任何额外的操作
- DLSS 是利用AI 深度学习技术，把低分辨率的画面 “脑补” 并放大成高分辨率画面，从而在几乎不损失画质的前提下，大幅提升游戏帧数（FPS）。
可见度/遮挡 Visibility / occlusion
画家算法 Painter’s Algorithm
- 由远到近绘制物体，先绘制完远处物体接着再绘制近处的物体覆盖掉之前的物体 Inspired by how painters paint, paint from back to front, overwrite in the framebuffer
- 一定程度上可行，排序n个三角形的时间复杂度为O(nlogn) 基于比较的排序最快就是这个复杂度 Requires sorting in depth O(nlogn) for n triangles)
- 有互相遮挡关系时，无法定义物体间的深度关系，画家算法无法解决 Can have unresolvable depth orde
深度缓冲 Z-Buffer
- 存储当前每个采样点（像素）的距离相机最近距离的深度信息 Store current min. z-value for each sample (pixel)
- 每个像素最后输出的颜色信息储存为帧缓冲，深度信息储存为深度缓冲 Frame buffer stores color values, depth buffer (z-buffer) stores depth
深度缓冲的算法 Z-Buffer Algorithm
注意：之前视图转换时相机是朝Z的负方向看的，以下为了简化，深度值z永远是正的，越小表示越近，越大表示越远
将深度缓冲中全部每个像素（采样点）的深度值初始化为无限远，在每个三角形光栅化时，将它的每个像素的深度值和深度缓冲进行比较，如果该像素的深度值小于深度缓冲，则更新深度缓冲，否则舍弃
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- 排序n个三角形的时间复杂度为 for n triangles (assuming constant coverage)
- 三角形的进入深度缓冲的顺序和结果无关
- 深度缓冲算法是一个最重要的算法，在几乎所有的GPU硬件中都有应用 Most important visibility algorithm, implemented in hardware for all GPUs
- Z-Buffer不能处理透明物体，透明物体需要特殊处理
Reference：
