计算机图形学三：光栅化-Rasterization

什么是光栅化？

虎书上的解释：

光栅化是对象顺序图形的中心操作，而光栅化器是任何图形管道的中心。对于输入的每个基元，光栅化器有两个任务：枚举基元覆盖的像素，并在基元上插值，称为属性。这些属性的用途将在后面的示例中明确。光栅化器的输出是一组片段，每个片段对应于基本体覆盖的像素。每个片段“存在”于特定像素处，并携带其自己的一组属性值。

在上述我们针对摄像机及物体进行MVP变化后，物体被呈现在[−1,1]3[-1,1]^3[−1,1]3的标准空间中，之后经过视口变换将之映射到了[0,width]∗[0,height][0,width]*[0,height][0,width]∗[0,height]的屏幕上。那么，屏幕又是怎样将物体正确的展示出来的呢？这就是今天所要介绍的光栅化。

个人理解：MVP变化所关注的是如何将物体的正确二维表示通过转换得到，而光栅化的目的就是将想要展现的物体给真正现实到屏幕上的过程（drawing onto the screen）。

像素和屏幕

在了解屏幕之前，得知道像素是个什么东西。在我们的日常生活中，常常会接触到像素风格东西的存在，如像素风游戏，像素风图像，共有的特点是所要表现的物体及形象是通过一个个颜色不同而内部均匀的像素块堆叠而成的，与真实的形象神似但是并不确切，因为它很“模糊”。

这是百度对像素的解释：像素是指由图像的小方格组成的，这些小方块都有一个明确的位置和被分配的色彩数值，小方格颜色和位置就决定该图像所呈现出来的样子。

而屏幕其实就是像素的二维数组。我们平常所说的分辨率，如1920 * 1080（1080p）、1280 * 720（720p）、2k、4k，就是像素数组的大小。像素点越多，像素数组越大，屏幕分辨率越高。屏幕是典型的光栅显示。

屏幕的像素如何表示呢？

• 每个像素以方块形式呈现，默认长宽均为单位长度，坐标表示为左下角的坐标，故范围为(0,0)(0,0)(0,0)到(width−1,height−1)(width-1,height-1)(width−1,height−1)
• 像素中心点坐标即为像素坐标，数值表示为(x+0.5,y+0.5)(x+0.5,y+0.5)(x+0.5,y+0.5)
• 整个屏幕表示范围为(0,0)(0,0)(0,0)到(width,height)(width,height)(width,height)

直线光栅化（Linear Rasterization）

DDA数值微分算法

DDA算法是一个非常简单直观的算法。

首先当任何一条直线知道任意两点时都可以用 y=kx+by=kx+by=kx+b 来表示，其中 kkk 代表斜率，如果∣k∣<1∣k∣ < 1∣k∣<1，那么它的主要行进方向就是 xxx 轴，即 xxx 轴的变化要比 yyy 轴快；相反如果 ∣k∣>1∣k∣ > 1∣k∣>1 ，那么它的主要行进方向就是 yyy 轴，即 yyy 轴的变化要比 xxx 轴快。如下图所示：

我们分别就图上两种情况进行考虑(假设起点与终点给定)

① 当∣k∣<1∣k∣ < 1∣k∣<1时，从起点开始画起每次 x=x+1x = x+1x=x+1， y=y+ky = y+ky=y+k，并将 yyy 四舍五入，得到新的 x，yx，yx，y 就是像素点应该画的地方
② 当∣k∣>1∣k∣ > 1∣k∣>1时，从起点开始画起每次 y=y+1y = y+1y=y+1， x=x+1kx = x+\frac{1}{k}x=x+k1​，并将 xxx 四舍五入，得到新的x，yx，yx，y 就是像素点应该画的地方

中点Bresenham算法

我们首先规定想要光栅化的线段的起点P0(x0,y0)P_0(x_0,y_0)P0​(x0​,y0​)与终点P1(x1,y1)P_1(x_1,y_1)P1​(x1​,y1​)则该直线方程可以用 y=kx+by = kx + by=kx+b 的形式来表示，定义 f(x,y)=y−kx−bf ( x , y ) = y − k x − bf(x,y)=y−kx−b

中点Bresenham算法的思想其实也比较简单，在这里只给出 0<k<10 < k < 10<k<1的情况，其它情况可以类推，除却起点与终点，我们每次的画点只会考虑右边或者右上的点两种情况(由斜率所决定的)，因此我们只需要在这二者之间做出选择。那么该依据什么进行判断呢，给出如下两种情况：

我们已经成功画出了前三个深色方格之后，所要考虑的便是第三个深色方格右边或者右上的浅色方格，此时我们取这两个浅色方格的中点，如图中圆圈符号所对应的那个点，倘若这个点在直线方程的下面，那么很明显我们应该选择右上的方格。

此时中点位于直线方程的上方，此时选择右边的浅色方格。

至此，如何判断两种方格选择的条件已很明显，就是确定中点与直线的位置关系，这里就可以使用到一开始定义的f(x,y)=y−kx−bf ( x , y ) = y − k x − bf(x,y)=y−kx−b的方程了。显然，当 f(x+1,y+0.5)>0f(x+1,y+0.5) > 0f(x+1,y+0.5)>0的时候中点在直线上方，当f(x+1,y+0.5)<0f(x+1,y+0.5) < 0f(x+1,y+0.5)<0的时候中点在直线下方 。（其中 x+1x+1x+1，y+0.5y+0.5y+0.5是为了表示两个浅色方格的中点，此时 x，yx，yx，y为前一个确定的像素坐标）

伪代码如下：

明显地，some condition是：

该算法仍有优化，在此不做讨论。

三角形光栅化（Triangle Rasterization）

为什么是三角形？

为什么着重讨论三角形光栅化？

• 是最基础的多边形，任意多边形都可以拆分成三角形
• 可以保证在平面
• 三角形内外部定义明确，有利于像素的着色
• 用于在三角形顶点处插值的明确定义方法（重心插值）（ps：这个闫老师没有细说，可以参考这个博主的重心坐标系）

如何光栅化

要想实现三角形光栅化，需要采样（sampling）。

程序语言为：

for(int x = 0 ; x < xmax ; ++x){
	for(int y = 0 ; y < ymax ; ++y){   //遍历每个像素点
		image[x][y] = inside(tri,x+0.5,y+0.5);   //在三角形内部的像素点作为采样对象
	}
}

我们对屏幕中的每一个像素进行采样，如果这个像素点在三角形之中那么这个像素点就应该被采用。那么该如何去判断一个点在不在三角形内部呢，如何实现上述的 inside 函数呢？最经典的方法就是利用叉乘了。

我们从P2P_2P2​按照顺时针顺序来看，直线P2P1P_2P_1P2​P1​与直线P2QP_2QP2​Q的叉乘，利用右手定则，指向屏幕内，说明点 QQQ 在直线P2P1P_2P_1P2​P1​的右侧。同理直线P1P0P_1P_0P1​P0​与直线P1QP_1QP1​Q的叉乘，得点 QQQ 在直线P1P0P_1P_0P1​P0​的右侧，而最后得到点 QQQ 在直线P0P2P_0P_2P0​P2​的左侧。说明点 QQQ 在三角形外部。（当点均在三线一侧时才位于内部）

因此，三角形光栅化只需要遍历每一个点，判断是否位于其内部即可。当然我们还可以进一步的进行优化，因为显然并没有必要去测试屏幕中的每一个点，一个三角形面可能只占屏幕很小的部分，可以利用一个bouding box包围住想要测试的三角形，只对该bounding box内的点进行采样测试，如下图：

光栅化带来的锯齿/走样（Aliasing）

利用上述光栅化，我们可以得到三角形在屏幕上的呈现是这样的：

呃呃，效果一言难尽。经常玩游戏的人应该都知道这种图形的呈现称作锯齿，就是十分的不平整光滑，看得人十分难受。在图形学中，更学术的名称为走样。问题的本质是：采样的频率过低无法跟上图像的频率。大白话就是采样数过少，试想如果像素点足够多，采样数足够大，那么精细度就会越高，一个个的锯齿将会变得十分小至肉眼无法分辨，这样看上去就是平整光滑的了。

下面理解一下锯齿/走样产生的本质：采样的频率过低无法跟上图像的频率。

f1(x)f_1(x)f1​(x)到f5(x)f_5(x)f5​(x)的频率不断增加而采样的频率不变，可见由采样点预估出的曲线越来越失真。

如何抗锯齿/反走样呢？这就是我们接下来要讨论的问题。

如何抗锯齿/反走样？（Antialiasing）

抗锯齿/反走样的基本思路是：模糊

如图示，我们将三角形模糊之后再进行采样，而采样的像素深度同模糊后的图像颜色。

更明显的两个例子：

这边闫老师说了很多拓展知识，例如时域和频域的转换。其中，采样对应的时域像素点的乘积等于图像对应的频域与低频滤波的卷积，二者都可以达到模糊的效果。

总之，解决问题的方法是用有限离散的像素点去逼近连续的三角形。具体工业采用什么方法呢？

超采样反走样(Super Sampling Anti-Aliasing，SSAA)

这是最基本的抗锯齿模式，实现原理是渲染时把画面按照显示器分辨率的若干倍放大，如在1024x768分辨率上开启2xSSAA，GPU会先渲染2048x1536 图像，再“塞进”1024x768的边框里成型，将画面精细度提升一倍，毫无疑问会改善边缘锯齿情况。但是众所周知，高分辨率图形的渲染会极大的消耗GPU运算资源和显存容量及带宽，因此SSAA资源消耗极大，即使是最低的2x也未必就能轻易承受。

举例：此方法无非就是提高分辨率，即增加采样点。将每个像素点细分成了4个采样点：

之后根据每个采样点来进行着色，每有一个采样点被覆盖就着一次色。这样得到了每个采样点的颜色之后，我们讲每个像素点内部所细分的采样点的颜色值全部加起来再求均值，作为该像素点的抗走样之后的颜色值。结果如下：

仔细观察可以发现因为将4个采样点的颜色求均值的之后，靠近三角形边缘的像素点有的变淡了，从宏观角度来看的话，这个锯齿就会变得不那么明显了。玩3A游戏时我们可以发现会有SSAA抗锯齿选项，其下的 ×2 , ×3 , ×4 分别代表的就是4个，9个，16个采样点，显然采样点越多抗锯齿效果越好，但计算负担也会随之增加。

多采样反走样(Multi Sampling Anti-Aliasing，MSAA)

MSAA是SSAA的改进版。SSAA仅仅为了边缘平滑，而不得不重新以数倍的 分辨率渲染整个画面，造成宝贵显卡处理资源的极大浪费，因此MSAA正是为了改善这种情况而生。MSAA实现方式类似于SSAA，不同之处在于MSAA仅仅将3D建模的边缘部分放大处理，而不是整个画面。简单说3D模型是由大量多边形所组成，MSAA仅仅处理模型最外层的多边形，因此显卡的负担大幅减轻。

MSAA虽然趋于易用化，十分流行，但是缺点也很明显。1，如果画面中单位物体较多，需要处理的边缘多边形数量也自然增多，此时MSAA性能也会下降的十分厉害。2，同样倍数的MSAA，理论上边缘平滑效果与SSAA相同，但是由于仅仅处理边缘部分的多边形，因此非边缘部分的纹理锐度远不如SSAA。

同样利用上述的例子说明MSAA与SSAA区别，MSAA仍将像素分为多个采样点，不同的是不再采用每有一个采样点被覆盖就着一次色的，而是统计被覆盖采样点的个数，例如有两个采样点被覆盖，那么只需要用该像素中心计算出来的颜色值乘以50%即可，这样大大减少了计算量。如上述：

深度缓冲（Z-Buffer）

在第二节课堂笔记视图变换中的视口变换模块说过这么一句话：

对于标准立方体[−1,1]3[ − 1 , 1 ]^3[−1,1]3，先不管它的 ZZZ 轴数据（由深度缓冲来处理）

深度缓冲是什么？

接着上文，我们在处理完图形光栅化之后，还要考虑物体先后的关系？这十分重要，更直白的说法是，要搞清楚物体的图层，哪个物体会被哪个物体遮挡，哪个物体会遮挡哪个物体。具体的说每个像素点所对应的可能不止一个三角形面上的点，该选择哪个三角形面上的点来显示呢？

当然是离摄像头最近的像素点显示，这就需要用到深度缓冲。（3D物体的远近通过 ZZZ 轴表示，故又称Z-Buffer）

简单的图示，离摄像机越近的像素点颜色越深。如何实现呢？分为两步：

1. Z-Buffer算法需要为每个像素点维持一个深度数组记为zbuffer，其每个位置初始值置为无穷大（即离摄像机无穷远）。
2. 随后我们遍历每个三角形面上的每一个像素点[x,y]，如果该像素点的深度值z，小于zbuffer[x,y]中的值，则更新zbuffer[x,y]值为该点深度值z，并同时更新该像素点[x,y]的颜色为该三角形面上的该点的颜色。

Initialize depth buffer to ∞
During rasterization:
	for(each triangle T)
		for(each sample(x,y,z) in T)
			if(z < zbuffer[x,y])              //目前为止离摄像机最近的
				framebuffer[x,y] = rgb;       //更新颜色
				zbuffer[x,y] = z;             //更新深度

一个形象的例子：

数字代表深度，越小代表离相机越近，实现像素颜色的更新。