3. 光栅化

做完变换操作，也就相当于将位置摆好，角度选好了，那么下一步就是要将物体画到屏幕上，也就是将其转化为 2 维的。所谓的光栅化，要做的工作就是将物体画到屏幕上

1. 屏幕和像素

1.1 屏幕

1. 屏幕是一种典型的光栅成像设备，由一组像素阵列组成
2. 像素的多少也就代表了分辨率

1.2 像素: 简单理解

1. 像素是屏幕上最小的单位，一个像素就是具有均匀颜色的一个小方块
2. 所谓均匀的颜色中，每种颜色都是由 $($红，绿，蓝$)$ 三原色混合组成的

1.3 屏幕空间: 为屏幕建系

1. 以左下角为原点，向右为 $x$ 正向，向上为 $y$ 正向
2. 约定: 像素在屏幕中的索引从 $0$ 开始
3. 坐标为 $\left(x,y\right)$ 的像素，其像素中心在 $\left(x+0.5,y+0.5\right)$ 上

2. 光栅化

2.1 将规范立方体转化到屏幕上

变换过程

以转换立方体的 $xoy$ 平面到屏幕上为例

1. 忽略 $z$ 轴
2. 将 [ − 1 , 1 ] 2 \left[-1, 1\right]^2 [−1,1]2 平面拉扯到 $\left[0,width\right]\times \left[0,height\right]$ 平面
   • 这里确实是 $\left[0,width\right]\times \left[0,height\right]$ 而非 $\left[0,width-1\right]\times \left[0,height-1\right]$
   • 因为像素的坐标和屏幕还是不太一样，右上角像素的中心是 $\left(width-1+0.5,height-1+0.5\right)$，因此屏幕的右上角就是在此基础上各再加 $0.5$，即 $\left(width,height\right)$ 了

变换矩阵

通过一个变换矩阵 M v i e w p o r t \mathbf{M}_{viewport} Mviewport​ 可以完成上述变换，该变换称为 视口变换
M v i e w p o r t = ( w i d t h 2 0 0 w i d t h 2 0 h e i g h t 2 0 h e i g h t 2 0 0 1 0 0 0 0 1 ) \mathbf{M}_{viewport}=\left( \begin{array}{cccc} \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{array} \right) Mviewport​= ​2width​000​02height​00​0010​2width​2height​01​ ​
注意到，该变换先将立方体的 $xoy$ 平面 缩放 到屏幕大小，再将原点 平移 到屏幕中心

2.2 将图打散成像素

具体地说，这才是真正的光栅化，在这一步，我们将空间中的三角形打散成像素，绘制到上一步准备好的图片中。如果说 2.1 是准备图片，绘制框架，那么这一步就更类似于上色

2.2.1 三角形

1. 三角形是最基本的多边形
2. 三角形有许多良好性质
   • 其他所有多边形都可以被拆分为三角形
   • 三角形的内部始终是平面的
   • 三角形的内和外定义得很清楚
   • 只要定义三角形三个顶点，就可以根据和这三个点的位置关系将三角形内任何一点的属性拆出来，从而得到逐渐的变化，即，在三角形内部如何 插值

2.2.2 画一个三角形

首先给出示意图

1. 完全在三角形内部的像素 $⟶$ 直接画 (在上图中就是画成红色)
2. 部分在三角形内部，部分在外部的像素 $⟶$ 根据该像素的中心点与三角形的位置关系来决定
   • 利用像素中心对屏幕空间进行 采样

2.2.3 采样: 将连续函数离散化的过程

$inside$ 函数: 用于判断一个点是否在三角形内部
i n s i d e ( t , x , y ) = { 1 , p o i n t ( x , y ) i n t r i a n g l e t 0 , o t h e r w i s e inside\left(t,x,y\right)= \begin{cases} 1, &point\ \left(x,y\right)\ in\ triangle\ t \\ 0, &otherwise \end{cases} inside(t,x,y)={1,0,​point (x,y) in triangle totherwise​
在屏幕空间中采样 $inside$ 函数可以表现为下图

用代码写出该采样过程如下，即，分别检查每个像素中心是否在三角形内部

for(int x = 0; x < xmax; ++x)for(int y = 0; y < ymax; ++y)image[x][y] = inside(t, x + 0.5, y + 0.5);

$inside$ 函数 的实现: 向量和线性代数 中叉乘的用途 2 就给出了判定一个点是否在三角形内部的方法。特别的，如果一个像素中心在三角形的边上，那么该点是否属于三角形内部，则自行决定！

包围盒: 在之前的采样过程中，需要遍历屏幕中的每一个像素点，但如下图所示，其实白色部分的像素点必定是在三角形外的，不必处理。因此，为了提升效率，可以只处理 包围盒 范围 (下图蓝色正方形部分)，具体要确定包围核可按如下方式

1. 已知三个点 p 1 ( x 1 , y 1 ) p_1\left(x_1,y_1\right) p1​(x1​,y1​)， p 2 ( x 2 , y 2 ) p_2\left(x_2,y_2\right) p2​(x2​,y2​)， p 3 ( x 3 , y 3 ) p_3\left(x_3,y_3\right) p3​(x3​,y3​)
2. 可以分别对 $x$ 和 $y$ 取最小和最大值，从而得到一个矩形包围核的范围如下
   • [ min ⁡ ( x 1 , x 2 , x 3 ) , max ⁡ ( x 1 , x 2 , x 3 ) ] × [ min ⁡ ( y 1 , y 2 , y 3 ) , max ⁡ ( y 1 , y 2 , y 3 ) ] \left[\min\left(x_1,x_2,x_3\right),\max\left(x_1,x_2,x_3\right)\right]\times\left[\min\left(y_1,y_2,y_3\right),\max\left(y_1,y_2,y_3\right)\right] [min(x1​,x2​,x3​),max(x1​,x2​,x3​)]×[min(y1​,y2​,y3​),max(y1​,y2​,y3​)]

这就是一种对光栅化进行加速的方式

其他加速: 如下图所示，对每一行寻找三角形的最左和最右，实现不检查任何一个额外的像素

1. 该方法适用于窄长且斜着放的三角形 (这种三角形占据很少的像素点，却需要一个很大的包围盒)
   

3. 抗锯齿$/$反走样

根据前述的算法进行采样后绘制出的三角形如下图，可以看到它和想要的三角形之间还有很大的差距，这是因为

1. 像素本身有一定的大小
2. 采样不够多

产生的这种现象叫做 锯齿，也称为 走样，显然，锯齿对最终的效果影响很大，因此我们还需要继续处理锯齿问题
事实上采样会产生一系列的问题，除了锯齿之外，还有摩尔纹，车轮效应等，这些问题产生的本质原因都是信号 (函数) 变化太快，采样的速度跟不上

在采样之前先做 模糊 再采样似乎可以有所改善，值得注意的是，顺序很重要，如果先采样再模糊，就并不能起到应有的效果

3.1 采样理论

3.1.1 频域

对于正弦 $\sin 2\pi fx$ 和余弦 $\cos 2\pi fx$，通过调整系数 $f$ 就可以得到许多不同的正弦波和余弦波，这里 f = 1 T f=\frac{1}{T} f=T1​，被称为频率，它是周期 $T$ 的倒数

傅里叶级数展开告诉我们，任何的函数都可以有正弦波和余弦波的线性组合得到，正如下图所示。傅里叶级数展开和傅里叶变换紧密相关，任何一个函数都可以经过傅里叶变换变成另一个函数，然后通过其逆变换再变回来

对于一个函数 $f\left(x\right)$，通过如下变换，可以将其变为函数 $F\left(\omega \right)$
F ( ω ) = ∫ − ∞ ∞ f ( x ) e − 2 π i ω x d x F\left(\omega\right)=\int_{-\infty}^\infty f\left(x\right)e^{-2\pi i\omega x}dx F(ω)=∫−∞∞​f(x)e−2πiωxdx
而函数 $F\left(\omega \right)$ 经过以下逆变换又可以变回函数 $f\left(x\right)$
f ( x ) = ∫ − ∞ ∞ F ( ω ) e 2 π i ω x d ω f\left(x\right)=\int_{-\infty}^\infty F\left(\omega\right)e^{2\pi i\omega x}d\omega f(x)=∫−∞∞​F(ω)e2πiωxdω
其中
e i x = cos ⁡ x + i sin ⁡ x e^{ix}=\cos x+i\sin x eix=cosx+isinx
不同的频率 $f$ 可以产生不同的正弦和余弦函数，而任何函数可以由许多正弦和余弦函数线性组合而成，也就是说，任何函数都可以分解成不同的频率，频率越高的函数，采样的频率也需要越高，如下图所示，对于高频率的函数，如果采样频率太低，那么恢复出的函数可能还原来的函数大相径庭

3.1.2 走样

所谓走样，指的就是同样的采样方法，采样两种不同频率的函数，而我们无法区分这两个函数
如下图所示，有两个函数，分别用黑色和蓝色的线条表示，白色的圆点代表我们的采样，显然，这两个不同的函数采样的结果将会是一模一样的，这就是一个走样的例子！

3.1.3 滤波

滤波，指的就是去掉一系列的频率

傅里叶变换可以帮助我们理解频率的分布，如下图所示，我们对左边的图片做傅里叶变换，将其变换到频域上。右边的图中，越靠近图片中心的部分，代表的频率越低，越靠近边缘的部分，频率越高；越亮则代表该部分频率的信息越多，越暗则代表该部分频率的信息越少。因此，通过傅里叶变换，我们就可以知道，左边的图片中绝大部分的信息都是低频的，高频的信息很少。

值得注意的是，右图中水平和竖直方向各有两条杠，这是因为分析信号时，认为信号是周期性重复的，对于不周期性重复的信号就认为到了右边界后就重复左边界的内容，类比到下图，就相当于图片在水平方向和竖直方向上被叠了很多个，在边界交错的地方就会产生高频信号，这就是杠的由来。它并不影响我们此时的分析，忽略即可

滤波: 去掉低频信号，称为 高通滤波

通过滤波，将低频信号抹去，再通过逆傅里叶变换将其变回到图片，就可以得到下图，可以发现，高频信息代表的其实是图像内容中边界的部分。因为边界的部分，通常代表着内容变化很大，所以高频信息对应于它也很合理

滤波: 去掉高频信号，称为 低通滤波

显然，边界的部分变得模糊了

滤波: 去掉高频信号和低频信号，留下频率处于中间部分的信息

剩下的是一些不太那么明显的边界特征

滤波 $=$ 卷积，简单说，滤波起到的效果，就相当于卷积过程中的卷积核，事实上，滤波器就是一个有归一化的卷积核，用小的核，则代表留下尽可能多的频率 (留下的频域范围大，大小频率都留下)，用大的核，则只能留下更低的频率，使结果更模糊

1. 时域上对两个信号的卷积 $⟺$ 频域上对两个信号的乘积
2. 时域上对两个信号的乘积 $⟺$ 频域上对两个信号的卷积

这也就是，为什么可以通过快速傅里叶变换来加速多项式乘法的原因！

3.1.4 采样: 重复频域上的内容

如下图所示，图片 $c$ 中的冲击函数作用于图片 $a$ 中的函数，得到图片 $e$ 中的采样结果，右边则是对应的频域，左边是乘积，则右边是卷积，可以看到，采样表现在频域上，就是对原始内容频谱的重复

走样产生的原因

1. 采样率不足会导致原始信号频谱的复制粘贴的间隔变得非常小，这就导致，原始的信号和粘贴的信号重叠在一起了，这就是走样的原因
2. 时域和频域有着一些相反关系
   • 时域采样越密集，频率粘贴频谱越稀疏 (间隔越大)
   • 时域采样越稀疏，频率粘贴频谱越密集 (间隔越小)

3.2 反走样

1. 一些解决走样的方法
   • 增加采样率
   • 真的做反走样: 先做模糊，再采样

先模糊在采样在频域上的表现如下图所示，即，先把高频信号拿掉，再采样

2. 如何进行模糊？
   • 用一个一定大小的低通滤波器对它进行卷积即可
   • 具体实现: 对每一个像素进行卷积，求一个平均即可，实现上也就是根据覆盖面积 $/$ 像素面积来处理

3.2.1 模糊的具体实现: MSAA

这是一种近似的方法，通过超采样来实现反走样，这里的超采样只是为了近似像素点中的覆盖率，而非增加了采样率

1. 将一个像素划分为很多个小的像素
2. 判断这些小的像素中心是否在三角形内
3. 求平均

下图中，每个像素被分为 4 个小像素，MSAA 带来的开销就是增大了计算量，需要进行更多的判断！

3.2.2 其余反走样方法

这些方法不一定用模糊操作了

1. FXAA: 先得到一个有锯齿的图，找到锯齿，再把锯齿部分换掉
2. TAA: 复用上一帧的信息，对同一个像素点，上一帧和这一帧分别采用像素中不同的位置来计算，起到近似效果 (类似于把 MSAA 的小像素中心分布在时间上)

4. 遮挡与可见性

空间中有很多三角形，需要考虑它们的遮挡关系，使得绘制出来后，近的三角形总是盖住远的三角形，这就是遮挡。

4.1 画家算法

4.1.1 算法

1. 先画远处的东西
2. 再画近处的东西，近的东西会覆盖远的东西

4.1.2 不足

1. 正确性
   考虑空间中的一个正方体，根据画家算法，前面和后面的两个面的远近是显然的，但中间四个面的远近是一样，这四个面绘制的顺序不同，就会影响最终的结果
   • 左 $\to$ 下 $\to$ 右 $\to$ 上: 正确的
   • 右 $\to$ 上 $\to$ 左 $\to$ 下: 错误的
2. 需要将所有组件的深度进行排序，排序需要 $\mathcal{O}\left(n\log n\right)$ 的时间复杂度
3. 深度本身难以判断，因为有可能是互相遮挡的，根本无法排序出谁前谁后，正如下图所示，此时根本无法应用画家算法

4.2 Z-Buffer 算法

4.2.1 思想

1. 不对组件的深度进行排序，而是按像素的深度进行排序，每个像素永远只记录最浅的那个深度
2. 同时生成 frame buffer 和 depth buffer
   • frame buffer: 存储最终的结果 (像素对应的值)
   • depth buffer (z-buffer): 只存每个像素对应的最浅的深度的信息 (像素对应的深度的值)

下图中左边是 frame buffer，右边是 depth buffer，深度缓存中越近颜色越深 (值更小)，越远颜色越浅 (值更大)

注意: 为了简化，假设 $z$ 总是正的，近的更小，远的更大

4.2.2 算法

算法用伪代码描述如下

Initialize depth buffer to \infty
During rasterization:for(each triangle T)for(each sample (x,y,z) in T)if(z < zbuffer[x,y])			// closet sample so farframebuffer[x,y] = rgb;		// update colorzbuffer[x,y] = z;			// update depthelse;							// do nothing

1. 初始化 depth buffer 矩阵的所有值均为 $\infty$
2. 遍历每个组件 (三角形) 中的每个点，对其进行如下操作
   • 如果该组件中的这一点的 $z$ 更大，则更新 frame buffer 和 depth buffer 矩阵
   • 否则，什么也不做

Z-Buffer 算法的一个实例如下

4.2.3 讨论

1. 显然，只需要依次处理掉每个三角形就行，假设每个三角形的大小都一样大，面积为一个常数 $c$，则时间复杂度为 $\mathcal{O}\left(cn\right)=\mathcal{O}\left(n\right)$
2. 由于深度是一个浮点型的值，所以很难出现两个三角形的深度一样，但如果真的深度一样，取哪个三角形在此像素的颜色呢？在此不多做讨论！
3. 考虑到反走样的 MSAA 是对每个小像素中心做处理，因此如果考虑使用 MASS 进行反走样，则 Z-Buffer 算法则需要对每个小像素中心记录深度

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！