Computer Graphics note(3):视图变换 & 光栅化

一.前提

Games101 Lecture5-6-7
在M(模型)V(视图)P(投影)变换之后，得到$[-1,1]^3$[−1,1]3，接下来就是将其映射到屏幕空间上去。
M变换：https://blog.csdn.net/Enterprise_/article/details/106880754
VP变换：https://blog.csdn.net/Enterprise_/article/details/106934622

二.屏幕

在图形学中，屏幕被认为是一个二维数组，其元素是$pixel$pixel(像素)，数组的大小叫做$resolution$resolution(分辨率)，同时屏幕也是一种典型的光栅化图形设备。光栅化(Rasterization):把三维空间的几何形体显示在屏幕(光栅化设备)上。

三.屏幕空间(Screen Space)

屏幕空间相当于在屏幕(高为$height$height,宽为$width$width)上建立一个坐标系，其原点在屏幕的左下角,如下图所示:

前提规定：像素的坐标$(x,y)$(x,y)是整数值，并且$(x,y)\in[width-1,height-1]$(x,y)∈[width−1,height−1],像素中心在$(x+0.5,y+0.5)$(x+0.5,y+0.5)，屏幕空间覆盖范围为$(0,0)->(width,height)$(0,0)−>(width,height)。

四.视口变换(映射$([-1,1]^3$([−1,1]3)

想要将该立方体映射到屏幕上，需要暂时忽略其$Z$Z坐标($Z$Z不变)，这样就变成了$[-1,1]^2$[−1,1]2,将其缩放(对$x,y$x,y进行缩放)到$[0,width]$[0,width]X$[0,height]$[0,height]。并且由于原来的立方体中心在原点，现在需要将其平移到屏幕空间的中心$(\frac{width}{2},\frac{height}{2})$(2width​,2height​)上。此处的变换被称为视口变换(Viewprot transform)，其变换矩阵$M_{viewport}$Mviewport​如下所示：
$M_{viewport}=\begin{bmatrix} \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{bmatrix}$Mviewport​=⎣⎢⎢⎡​2width​000​02height​00​0010​2width​2height​01​⎦⎥⎥⎤​

五.光栅化

至此，经过了MVP和视口变换之后，三维空间的几何形体就被映射到了屏幕空间里，想要得到图像，需要用这些信息进行光栅化，将其变成像素。
光栅化过程中绘制的基本图元是三角形，因为其内外定义良好，是最基础的多边形。

1.傅里叶变换

这里需要知道关于频域(Frequency Domain)的东西来辅助理解，我们需要用到傅里叶分析，也就是傅里叶级数(Fourier Serie)和傅里叶变换(Fourier Transformation)。两者关系如下图：

简单来说，傅里叶级数是个时域里周期连续，频域里非周期离散的函数；而傅里叶变换是将时域(spatial domain)里非周期连续信号转换为频域(frequency domain)里非周期连续的信号。
举个例子，对于下面这个式子:

对其作傅里叶变换，然后将不同频率的段显示出来，再对其进行同样的采样重建，结果如下图所示：

2.滤波(Filtering)

滤波是把特定频率的内容去除。下图左图为原图像，右图为傅里叶变换之后的频谱。定义右边图的中心为低频区域，往外频率越高，不同频率区域所包含的信息通过其亮度来表示。图像的频率信息可以理解为图像相邻像素间色彩的变化，可见该图大部分都是低频信息，少部分高频信息。分析信号时一般认为其为周期重复信号，对于不重复的，如下图进行连续平铺，即连续同样的图片连载一起，这样在边界处就会出现十字线(信号剧烈变换)。

(1)高通滤波

假如把去除低频信号后，再逆傅里叶变换，就可以看到高频信息表示图像内容的边界(信号剧烈变换)。这样的滤波称为高通滤波(High-pass filter)。如下图从右到左。

(2)低通滤波

低通滤波(Low-pass filter)只留下低频信息。高频代表边界，去除之后边界就变得模糊了。

(3)带通滤波

上面两图都是去除高频和低频信息，但是中间的频率确实一个可选范围，所以当范围往外扩大的时候，其结果就会偏向高通滤波。

3.卷积(Convolution)

(1)定义(Filtering = Convolution(= Averaging)

**图形学上简化的卷积操作(简化定义，非数学定义)，是将滤波器(卷积核)在信号上进行移动，两者重复位置进行点乘，结果写回其中心(新的信号)。**如下图所示。

(2)Convolution Theorem(卷积定理)

时域(spatial domian)里两个信号的卷积等于两个信号频域的乘积，反过来，时域上的乘积等于频域上的卷积。

也就是说，以下两者等价(时域卷积=频域乘积)，例子如下图：

1. 对一幅图可以先通过滤波器在时域上进行卷积
2. 可以先把这幅图先通过傅里叶变换变到频域上，再把滤波器(卷积核)也变换到频域上，两者相乘后逆傅里叶变换到时域上

其中所用的滤波器(卷积核)(如下图)有归一化操作((乘以$\frac{1}{9}$91​))，因为需要保证变换前后的图像亮度不变。这样的滤波器为低通滤波器，其当大小越大时结果越模糊。

4.光栅化基本方式–采样(Sampling)

(1)例子(辅助理解)

此处的采样是指用像素的中心来对屏幕空间进行采样。
比如将像素中心套用到判断函数上，得到每个像素中心在屏幕空间上的对应值(用于判断是否在三角形内)，假设函数如下：
$insidde(triangle,x,y)=\begin{cases} 1,in \\0, not&in \end{cases}$insidde(triangle,x,y)={1,in0,not​in​
然后对屏幕上像素判断，如下图示例：

对于$inside$inside函数可以用叉积的正负号来进行判断，三边按顺序与点进行判断，符号不变则点在三角形内，反之不在。对于点在边界上的情况，自行决定。

对于像素检查不需要检查的所有像素，只需要检查包围盒$(Bounding Box)$(BoundingBox)里的像素即可，包围盒范围可由三角形顶点信息得到，如下图所示:

假设每个像素是个颜色均匀的小方块(暂时定义)，那么光栅化之后如下图所示，有明显的走样(Aliase)现象(锯齿)：

(2)Sampling = Repeating Frequcncy Contents

采样实际就是在重复频率(频域)上的内容。如下图(来源：https://www.researchgate.net/figure/The-evolution-of-sampling-theorem-a-The-time-domain-of-the-band-limited-signal-and-b_fig5_301556095)

假设其中$a$a为原函数(时域信号)，$b$b为其经过傅里叶变换后在频域上的结果。如果要对$a$a进行采样(得到原信号上离散的点)的话，则用另一个函数(冲激函数)$c$c乘以$a$a得到离散的值(如$e$e所示,即采样结果)。此时考虑卷积定理，时域乘积=频域卷积，即$ac$ac在时域上的乘积等于$bd$bd($ac$ac在频域上的结果)在频域上的卷积。所以从结果上看，采样就是在重复原始信号的频谱。

5.Aliase(走样)

采样会产生Artifacts(瑕疵),比如锯齿(在空间中采样)，摩尔纹(Moiré Patterns)(在空间中采样)，Wagon Wheel Illusion(对时间采样，人眼对时间的采样低于运动的速度)。

(1)产生原因 & 定义

Aliasing Artifacts产生的本质原因是信号(函数)变换过快(高频率)，但是采样速度跟不上。从上可以知道高频率必须用更快的采样方法，否则重建效果是非常差的。所以走样为对两个频率截然不同的信号当采用同样的采样方法，否则得到的结果却无法区分。

在频谱上表现为原信号和搬移信号发生混叠现象。如下图所示，当采样率越低时(时域上采样点之间的间隔越大)，在频谱上就表现为信号之间的间隔就越小，发生混叠现象即为走样。

(2)反走样

从走样的原因出发，理论上只要提高采样率，就能解决走样的问题，但是受物理限制(比如高分辨率显示器)。

反走样的方法:Blurring(Pre-Filtering)Before Sampling，也就是在采样之前先对三角形滤波(模糊)，注意其边界像素取中间值，如下图所示：

例子如下：

值得一提的是如果先采样再模糊的话也是走样，不是反走样，如下图：

这里的反走样实际就是使用了低通滤波，也就是说对一个信号去除高频信息后再采样。用上面讲采样时的采用例子，在频谱上表现如下：

上面说过，走样是原信号和搬移信号发生混叠现象，而低通滤波(上图中的虚线矩形)去除高频信号后再采样后，就没有混叠了，即反走样。

6.三角形反走样操作

至此，想要对三角形反走样，就要先对三角形覆盖的像素区域进行模糊操作，这里只需要使用卷积(平均)操作。但是实际操作并不适用，因为覆盖区域不好计算。使用其他方法来模拟，比如MSAA(Multi-Sampling Anti-Aliasing)，需要明确的是MSAA模拟的是反走样的第一步，即模糊(滤波)的过程。

(1)MSAA(Multi-Sampling AA)(光栅化阶段)（通过Supersampling来计算三角形的覆盖率）

Supersampling，首先将一个像素划分(划分方法多样，上图中的网格划分只是一种划分方法)称为更多个更小的"像素"，并认为每个小的"像素"(次像素，采样点)有其中心，再判断其是否在三角形内，然后对结果进行平均。这样就三角形对原像素覆盖区域的近似，很明显，划分越多结果越准确。从这里会发现MSAA导致计算量倍增，其大小和划分结果有关，但是实际工作中会因为划分结果的不同以及相邻像素对次像素的复用使得计算量不会增加太多。

举个例子，如下图，先划分每个像素为2x2:

然后对每个像素进行判断，比如左上角第一个像素，四个小"像素"都没有被三角形覆盖，则认为原像素不在三角形内；而三角形上部的一个像素，有3个小"像素"被覆盖，1个没有，覆盖率为$75\%$75%，则认为原像素在三角形内，如下：

全部都判断完之后，结果如下：

其最后结果如下，每个像素变成了颜色平均的，数值为覆盖率。至此走样的第一步(模糊操作)就完成了，MSAA只针对第一步。之后再进行采样即可。

(2)其他方案FXAA& TAA& Super resolution/super sampling

FXAA(Fast Approximate AA) 和采样无关，属于图像的后期处理技术，对于有锯齿的图像，通过图像匹配找到锯齿部分，然后替换成没有锯齿的图像。

TAA(Temporal AA) 的思想是复用上一帧像素的结果，对于静止图像而言，相当于把MSAA对应的Sample分布到时间轴上，并且对于当前这一帧而言不引入其他操作。

Super resolution(超分辨率)/Super Sample(超采样)，将低分辨率图像"恢复"成高分辨图像，这个和抗锯齿本质是一样的，解决的是Sample不足的问题。方法有DLSS(Deep Learning Super Sampling)，将缺失的像素"猜测"出来。

7.深度测试算法(Z-Buffer,像素内)

当有多个不同的三角形，距离相机位置，三角形之间存在遮挡问题。解决方法有Painter’s Algorithm，即绘画顺序从后往前，这样就能解决遮挡问题，应用到光栅化上，也就是先处理距离观测点远的对象，但是深度(距离观测点的距离)难以定义。比如下图存在互相遮挡：

这就需要Z-Buffer算法来解决，其思想是当考虑到对于三角形的相对深度不好排序时，转而对像素进行排序，在每个像素内记录该像素所表示的几何物体的最浅的深度(距离观测点最近的距离)。当和MSAA结合时，就应该对每个采样点进行Z-Buffer。

在具体实现的时候，同步生成成品图像信息和深度图(深度缓存)，深度图只存每个像素所表示的几何物体的最浅的深度信息。前者存储在$frame$frame $buffer$buffer(存颜色值)中，后者存储在$depth$depth $buffer$buffer(存深度信息)中。

在之前的视图变换中提到过，相机(观测点)是看向$-Z$−Z方向的，所以物体越远其$Z$Z值越小(负数)。但是考虑深度测试，为了方便，认为此时的$Z$Z值是距离相机的距离(正数)，距离近深度浅(深度越小，替换成颜色值，也就越黑)，反之深度大。

Z-Buffer示例图如下：

(1)Z-Buffer伪码

Initialize depth buffer to ∞
During rasterization:
	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

Z-Buffer复杂度是$O(n)$O(n)，因为这里没有对三角形进行排序(与顺序无关)，只是求每个像素看到的最小深度值。

Z-Buffer算法伪码如上，首先是初始化，接着在光栅化阶段，对每个三角形(与顺序无关)进行光栅化，得到三角形覆盖的每一个像素。比较每个像素当前所记录的深度$zbuffer[x,y]$zbuffer[x,y]和新三角形对应的深度$z$z，如果当前的深度更大，说明距离更远，新三角形会将其覆盖，则进行更新，反之则什么也不做。例子如下，两个三角形互相遮挡，(可以想象紫色的三角形是个倾斜(远离相机方向)的三角形)：