Rasterization（光栅化）

Rasterization（光栅化）

笔记来源：GAMES101-现代计算机图形学入门-闫令琪
上一篇我们了解了MVP变换

1.Raster image

光栅化是计算出每一个三角形顶点及其内部点显示在屏幕上的位置，然后三点之间填充颜色，画出三角形，在这个基础上再绘制光影特效之类的–引用自如何通俗地解释光线追踪技术和光栅化？

经过MVP变换，得到二维画面/图形，接下来将此画面用像素“打碎/分割”就是光栅化（德语Raster意思是Screen、Rasterize意思是drawing onto the screen）

2.Raster Displays

Oscilloscope（示波器）

Cathode Ray Tube（阴极射线管）

显存

LCD（Liquid Crystal Display）液晶显示

LED（Light Emitting Diode）发光二极管阵列

Electrophoretic（Electronic Ink）Display

3.Rasterization：Drawing to Raster Displays

如何在成像设备上画东西？将图形用像素描述
下图中老虎由四边形组成（Polygon Meshes）

下图球体由三角形组成（Triangle Meshes）

为什么选取三角形来构图？
三角形是最基础的多边形，多边形可以切分成三角形
三角形沿对角线对折三角形内部仍为一个平面，而多边形沿对角线对折则多边形内部不再是一个平面
三角形内部外部定义清晰，可用叉积判断某点在三角形内还是外
三角形的三个顶点属性定义好，则三角形内部点属性可以借助三个点进行插值

4.Sampling

像素（确切地说是像素中心点）与三角形的位置关系
通过采样（sampling）来离散化函数

判断是否像素中心点在三角形内部


函数返回代表该像素（实则用像素中心判断）在三角形内部，否则在外部
1×1大小的像素，其中心(0.5,0.5)
遍历屏幕上所有像素，遍历时使用inside函数判断像素中心是否在三角形内部，若在内部则为采样点

inside具体如何实现？利用叉积判断
详见本人博客：Review of Linear Algebra

三个向量收尾相接
$\overrightarrow{P_1{P}_2}\times \overrightarrow{P_{1}Q}$可以知道Q点在$\overrightarrow{P_1{P}_2}$左侧
$\overrightarrow{P_2{P}_0}\times \overrightarrow{P_{2}Q}$可以知道Q点在$\overrightarrow{P_2{P}_0}$右侧
$\overrightarrow{P_0{P}_1}\times \overrightarrow{P_{0}Q}$可以知道Q点在$\overrightarrow{P_0{P}_1}$左侧
三个结果不一致，所有Q在三角形外部

如果采样点同时在两个三角形重合边上，要么不处理，要么自行定义
OpenGL、DirectX 有特殊规定

光栅化的加速方法
其实无需遍历屏幕上所有像素，我们用一个Bounding Box把三角形包围起来，在此范围内进行遍历

找到三角形在每一行上的最左侧像素和最右侧像素，而后进行遍历
这种方法适用于窄长且有旋转角度的三角形

5.Rasterization on Real Displays

6.Aliasing（走样）

对屏幕上处于三角形内部的像素中心点进行采样

采样后像素中心所在像素上色后，由于像素是方块状的，出现了锯齿

理想三角形为

7.Antialiasing（反走样）

Why undersampling introduces aliasing？
Why pre-filtering then sampling can do antialiasing？

7.1 Sampling Artifacts（Error/Mistakes/Inaccuracies）

Jaggies（锯齿）

Moire Pattern（摩尔纹）
如果去除奇数列和行会出现摩尔纹

Wagon Wheel Effect
肉眼看着有的顺时针有的逆时针

Photograph（照片）在本质上是到达感光元件的信息
Video（视频）在本质上是时间维度上的采样
以上为提到的是采样中可能出现的错误
锯齿、摩尔纹不同位置采样出现的问题（照片中）
车轮效应时间采样上出现的问题（视频中）
走样问题的本质
signals are changing too fast（high frequency），but sampled too slowly
信号变化太快（频率太高）以至于采样速度跟不上，也就是说信号变化速度大于采样速度

7.2 Aliasing Idea

Blurring（Pre-Filtering）before sampling（采样之前进行模糊处理或者说滤波处理）

之前直接对屏幕中处于三角形内部的像素进行采样，如果某像素的中心点落在三角形内部则就把所在像素上色为纯色

先对原图形（信号）进行滤波，随后对模糊处理过的三角形在屏幕中进行采样

接下来我们需要进行模糊处理（滤波、卷积）

7.3 Filtering then Sampling

7.3.1 Filtering

图像与波的关系
详见本人博客：傅里叶变换与图像处理


一张灰度图像可以由许多个波叠加而成
低频部分（波峰波谷稀疏）是决定整个图像的大致走向，即轮廓，因为低频波代表着像素值的变化平缓
高频部分（波峰波谷密集）是负责填充细节，因为高频波代表着像素值的快速变化

详见本人博客：傅利叶变换在图像处理的应用

将图像函数化，随后对函数进行傅利叶展开，可以得到各种较为简单的函数（频率不同）这些简单函数叠加得到该图像。
Fourier Transform Decomposes a signal into frequencies
傅利叶变换和逆傅利叶变换


对这些简单函数进行采样
高频函数（图像中的细节部分）变化快，如果采用频率跟不上其图像细节变化，就会出现图像走样

对高频函数和低频函数如果采样频率相同就会出现走样问题，因为对高频函数（图像细节）对应的图像变化快，采样频率低的话就跟不上图像变化的速度了。正确做法应该是对高频函数的采样频率应该高于低频函数的采样频率，也就是针对频率不同的函数，采样频率也应该不同

（1）角度一

角度一：滤波（Filtering）本质上就是去除掉某一种频率的波（函数）
傅里叶变换可以将一幅图像从时域变到频域
详见本人博客：傅利叶变换在图像处理的应用

中心低频，外围高频

低通滤波器（去掉高频部分，留下低频部分）
低频部分（波峰波谷稀疏）是决定整个图像的大致走向，即轮廓，因为低频波代表着像素值的变化平缓

高频滤波器（去掉低频部分，留下高频部分）
高频部分（波峰波谷密集）是负责填充细节，因为高频波代表着像素值的快速变化（如边界处）

过滤掉高频和一部分低频

（2）角度二

角度二：滤波（Filtering）就是进行卷积（Convolution）（=Averaging）操作，卷积核充当滤波器功能，不同卷积核具有不同作用。，卷积核相当于一个“透镜”，通过该透镜可以提取出原图像中符合该透镜特征的内容，在原图像素与卷积核的卷积过程中，卷积核内的值相当于权重，若权重为非零值，则在与原图像对应相乘过程中强化了与卷积核相似的特征，也就提取出了原图像中与卷积核相似的特征，若权重为零值，则忽略原图中该部分的特征。

详见本人博客：如何理解卷积(Convolution)？
详见本人博客：卷积神经网络底层原理

图像中的卷积操作：对应值相乘后相加

某种卷积核有模糊（Blurr）的作用

Convolution in spatial domain is equal to multiplication in the frequency domain，vice versa
时域上的卷积操作等价于频域上的乘法操作

如何对图像进行模糊操作？
选择1：空间域上直接进行卷积得到模糊图像
选择2：图像函数进行傅利叶变换到频域上，卷积核进行傅里叶变换到频域上，两者结果相乘，相乘结果进行逆傅利叶变换，得到最终模糊图像

1/9是对卷积核进行归一化处理，若不归一化处理，以下图中卷积核为例，像素对应相乘后相加后，像素值变大了，也就是图像变亮了，为了防止其变亮，对该卷积核进行了归一化处理

7.3.2 Sampling

Sampling = Repeating frequency contents。
时域上的卷积等价于频域上的乘法
反之亦然，时域上的乘积等价于频域上的卷积
冲激函数可用于对连续信号进行线性表达（冲激函数有采样功能）

把冲激函数频域图像左右置换（操作类似下图）

冲激函数反向后滑动过程中与信号频域图像依次相乘

频率角度来看走样
采样时间间隔小，也就是采样频率大，采样结果越稠密（dense）可能出现如下图的频谱混叠（走样）
采样时间间隔大，也就是采样频率小，采样结果越稀疏（sparse）
下图中纵轴为振幅，横轴为频率

综上：如何反走样？
选择一：提高采样率，但一个屏幕的分辨率是确定的，采样率就确定，只能通过更换更高分辨率的平面解决此问题。
高分辨率像素小（“像素块”就多）意味着光栅化同一个三角形时相比低分辨率的屏幕其采样率就高（落在三角形内的“像素块”多），也就是频谱的间隔大
选择二：先模糊（滤波或卷积）后采样

通过模糊把容易发生频谱混叠的部分“砍掉”，然后进行采样，就不会出现频谱混叠（走样）了

7.4 Antialiasing by supersampling（MSAA）

将一个像素划分为多个小像素


假设每个像素划分为4个小像素

如下图中用橙色圈住的这个像素，4个小像素中有3个小像素在三角形中，占比3/4也就是75%，那该像素为纯红色的75%



左侧为含锯齿的图像，右侧为通过MSAA抗锯齿的图像

MSAA的代价：由于对每一个像素进行了划分，所以在判断像素是否在三角形内部是计算量提高了数倍
其他抗锯齿方法
FXAA（Fast Approximate AA）
TAA（Temporal AA）
DLSS（Deep Learning Super Sampling）将画面拉伸放大，但细节会缺失，通过DL补上细节