2.光栅化
2.光栅化
鲸拓工作室本系列的主要目的是复盘并总结计算机图形学这个学科常用算法与原理，会从基本的数学理论讲起，同时会附带部分算法的代码实现，由浅入深，只需初中的数学基础就行。主要参考了GAMES101-现代计算机图形学入门这门课（具体引用见文章末尾），同时附加上自己的理解。有兴趣的也可直接看视频。
光栅化
光栅化的过程就是把模型渲染在屏幕上的过程。
这里我们先定义什么是屏幕，屏幕就是一个二维数组，数组里的每一个元素都代表一个像素点，一个像素能表示一种颜色，在一般情况下一个像素在同一时间只能发出一种颜色（有些屏幕可以发出多种）
屏幕中的每一个像素点我们都用整数坐标进行表示，最大最小值与分辨率相对应，考虑到每个像素都有一定的面积，我们定义(x+0.5,y+0.5)为该(x,y)像素的中心，如图中黑圈所示。
直线光栅化
DDA数值微分算法
首先当任何一条直线知道任意两点时都可以用
我们分别就图上两种情况进行考虑(假设起点与终点给定(确定了直线方程)，就像图中一样)
- 当
时，从起点开始画起每次x = x+1， y = y+k, 并将y四舍五入，得到新的x，y就是像素点应该画的地方 - 当
时，从起点开始画起每次y = y+1， x = x+1/k, 并将x四舍五入，得到新的x，y就是像素点应该画的地方
中点Bresenham算法
我们首先规定想要光栅化的线段的起点
中点Bresenham算法的思想其实也比较简单，我们在这里只给出0 < k < 1的情况，其它情况可以类推，除却起点与终点，我们每次的画点只会考虑右边或者右上的点两种情况(由斜率所决定的)，因此我们只需要在这二者之间做出选择。那么该依据什么进行判断呢，给出如下两种情况
第一：我们已经成功画出了前三个蓝色方格之后，所要考虑的便是第三个蓝色方格右边或者右上的橙色方格，此时我们取这两个橙色方格的中点，如图中圆圈符号所对应的那个点，倘若这个点在直线方程的下面，那么很明显我们应该选择右上的方格。
第二种情况：
此时中点位于直线方程的上方，此时选择右边的橙色方格。
至此，如何判断两种方格选择的条件已很明显，就是确定中点与直线的位置关系，这里就可以使用到一开始定义的
显然，当
三角形光栅化
这里我们需要知道，数字世界几乎所有的模型都是由三角形组成的，数以万计的三角形组成了一个模型，一个个模型又组成了游戏世界。
那么为什么要选择三角形，而不是别的什么几何体呢？
- 它简单，三角形是构成几何中拥有边数最少的图形
- 能够保证三角形上的所有点都在同一个平面
- 并且很容易判定一个点是否在三角形内部
那我们怎样将三角形渲染在屏幕上呢？
这里用到了采样的方法，遍历屏幕上的各个像素点，如果该点在三角形内，则显示，否则不显示。这里复习一下判断一个点是否在三角形内部的方法：
好了，经过一遍采样之后，我们已经知道结果了
这里需要补充一句：如果像素点正好在三角形的边上，该怎么处理？这种情况发生的概率相当小，如果遇到了，随便怎么处理都行，忽略或者算作三角形内都可以。
当然，这样采样还是过于暴力，我们可以优化一下，不选择采样全部的点，而是只采样三角形附近的点，如下图所示
我们只需要采样蓝色区域内的点就可以了，因为蓝色之外的点必然不可能在三角形内。当然也有一些其他的优化方法，比如只找最左或者最右等等，这里不过多赘述。
好了，确定了像素点之后，我们需要将其展示在屏幕上
很明显，这并不是我们想要的结果。三角形周围出现了很明显的锯齿，用这种办法去渲染其他模型也会出现类似的情况
这个问题其实有一个很简单的优化方法，那就是先模糊，再采样
那么为啥模糊之后效果会好些呢？能不能先采样再模糊呢？想要探究这些问题，就得了解锯齿到底是啥，接着学下去吧
走样与反走样
走样
锯齿其实是一种走样，说通俗点就是屏幕分辨率太低，像素太少，图形过于精细，无法用这么少的像素表达出图形本身的样子。换成数学一点的语言就是：信号变化太快而采样太慢。（懵逼也不要紧，看几个例子）
我们可以理解，视频就是在短时间内告诉播放图片，这本质上就是对时间进行采样，如果我们把这些图片拼接在一起，就会是这样，能看出运动员各个动作之间的间隔。
我们的显示屏有时候为了提高刷新率，会隔行显示，也就是只显示奇数行或者偶数行的像素，把其他的像素忽略，或者是重叠显示等等，这样做就能提高一倍的性能，并且显示效果也不会相差太多。但这也会导致“摩尔纹”，也就是下图这样的效果
我们的人眼也是一样，如果把一个格子的图片旋转起来，我们就会看到它似乎变成了一个车轮在转动。
这三种走样本质上都是一样的，就是上面提到的：信号变化太快而采样太慢
虽然这样说很有道理，但是缺少了数学表达，我们来加点数学元素进来（别慌，不难）。我们都知道频率，频率等于周期的倒数，同时对于图像信号而言，我们认为两个像素间的颜色变化大则代表频率高，反之则是频率低。
注意上图的三角函数，有一个叫傅里叶的人说，任意的图形都可以用这些三角函数表示，他提出的公式，叫傅里叶级数展开，如下所示（不用记，看看就行）
他还搞了个傅里叶变换，这个变换很有用，它可以将时域转换成频域。可以简单的理解一下，时域就是信号在不同时间的状态。频域就是用三角函数表示的东西，能在不同的频率下观察信号，它重点关注频率的变化。当然，这些公式知道干什么的就行，不用记。
了解这个东西干嘛的呢？它可以帮助我们更好的了解走样是怎么回事。
看上面的图片，我们能发现：频率慢的信号和我们的采样恢复结果基本一致，但是频率高的信号就不行了，就出现了严重的走样现象。所以说，两种不同频率采样出来的结果无法区分就是走样
滤波
上面说到，一个时域或空间域上连续重复的信号可以通过傅里叶变换变到频域上。而图像本身就属于空间域上的一种信号，因此我们也可以通过傅里叶变换使其变成频域的表现形式。如下图，左边是一张图像，右边是傅里叶变换后的频谱。
对于右图的解读：图像中心代表着低频率区域，越往外频率越高，图像周围即是高频率区域。同时亮度越亮，说明该频率的信息越多，例如图中中心最亮，往外越来越暗，说明原始图像中低频信息最多，高频信息偏少。而关于图像的频率信息也就是像素间颜色变化，颜色变化越大则频率越高。同时我们也可以通过逆傅里叶变化，将右图变回左图。
接着我们将对这个图片进行几个经典的滤波操作。首先是高通滤波，高通的意思就是高频可以通过，也就是过滤掉低频的信号。如下图，我们去掉低频信号后得到如下图像。
有高通滤波自然也有低通滤波，即过滤掉高频的信号，如下图，图像变得模糊了，因为原本清晰的边界都被过滤掉了。
还有带通滤波，允许特定频段的波通过。例如下两图
采样
接着我们再说说采样，采样是一个冲激函数（别深究），每一次冲激就代表采样一次，那么采样后的结果在这里我们就可以理解成这两个函数相乘所得到的结果。
如图，a函数代表信号，c函数为冲激函数代表采样，两个相乘得到e函数，即采样结果，也就是信号上各个点的结果。上述就是在时域上的采样原理。
那么采样在频域上是一个怎么样的过程呢？我们知道一个信号可以通过傅里叶变换变到频率上，如下图
a是我们时域上的信号，b是我们频域上的信号。上面说到频域其实是在频率上观察信号，因此b中的坐标系的横轴代表着频率，同时越往外代表频率越高。从b中我们可以看出，信号a大部分还是低频的信号（信号大部分都集中在原点附近）。
接着我们的冲击函数同样可以做一个傅里叶变换，得到的截图如下，c为我们的冲激函数，d为该函数的频谱。（具体为什么变成这样我们这里暂时不做过多的推理）
从中可以看出，将冲激函数傅里叶变换后以及还是冲激函数，只不过间隔发生了变化。
最后我们类比时域上采样的过程，对频域进行采样，过程如下。
你会发现我们在时域上是做乘积，而频域上是卷积。这背后的数学原理我们暂不深究，只需要知道，在频域上，采样就是重复原始信号的频谱就可以了。
从前面我们知道采样是根据冲击函数的频谱间隔在重复信号的频谱，那么就会存着这么一个问题，冲击函数的间隔小于频谱的大小，如下图：
可以发现，这种情况就会造成一部分的频谱重叠，这就是我们所谓的走样现象。因此在频域角度上，走样就是频谱重复时发生了混合。而重叠的这部分就是我们的高频信号，因为前面b中我们可以看出，一个信号的频谱图外面代表着高频信号，而重叠部分就是外面的这部分。
反走样
那么解决方法是什么呢？最简单的自然是增加频谱中冲激函数的间隔，使其避免重叠现象。通过前面的学习，我们知道采样频率越高，即时域上的冲激函数间隔越小，走样越少，因此我们也可推出，冲激函数在时域间隔越小，在频域上则间隔越大。
当然了，增加采样频率是最容易理解的解决办法，但并不是最简单的，因为例如一个固定分辨率的屏幕，我们没法更改他的分辨率，即采样频率。那么应该怎么做呢？此时我们可以去除掉这些会被重叠的信号，如下图：
我们把原始信号的频谱的两头（即高频信号）去掉，然后依旧按原来的间隔排列，就会发现重叠的部分消失了。
这也就解释了为什么前面所说的先做模糊操作再采样可以实现反走样，**因为模糊操作等于做了个低通滤波，即去掉了高频的信号，减少了信号重叠的情况。**同时先采样在模糊的话，在频域上，采样后频谱已经混叠了，此时再去掉高频信号，等于是把混叠后的结果去掉两端（并不是每一段去掉两端），所以是错误的。
超采样(MSAA)
除了先模糊后采样之外，我们还有一些别的抗锯齿方法，比如超采样。它的思想也很简单，就是多做一些采样，只要我们屏幕像素有足够多的采样点，那么就可能覆盖到所有的原始像素。然后我们只需要知道这些采样点分别与三角形的位置关系即可。具体流程如下图
虽然效果还挺不错的，但是代价也很明显，它的计算量增加了很多。因此为了更好的性能同时能够实现反走样，也对MSAA进行了很多的优化。例如增加的采样点并不是均匀分布的，而是按照一定的规则摆放，或者有些采样点能够被复用等等。
除了MSAA外，现代图形学还有各种各样的反走样操作，其中最具代表性的就是FXAA和TAA
FXAA
先得到带有锯齿的图，然后通过一些图像匹配的方法找到这些锯齿边界，然后将这些边界换成没有锯齿的边界，属于图像的后期处理。
时间抗锯齿TAA
将采样点从单帧分布到多个帧上，使得每一帧并不需要多次采样增加计算量。
深度缓存
通过上面的光栅化，我们就可以将所有的三角形渲染到屏幕上了。但是似乎还有一个问题亟待解决，那就是模型与模型之间似乎很有可能存在遮挡关系。例如背着书包的人，正面看去书包和人是重叠的。并且对于单个三维物体而言，不同的面也是存在重叠关系的，例如书包的背面和正面。换句话说，所有要绘制的三角形，它们可能存在着重叠的关系，对于这些重叠的三角形，我们应该把谁显示在像素上？不绕弯子了，其实这里我们用到了深度缓存，还记得我们再视口变换里没有用到的Z值吗，这里就派上用场了。
那么什么是深度缓存呢，字面意思上似乎是把深度值缓存起来，实际上也确实是这样，但是这里的深度不再是每个三角形的深度，而是针对每个像素来处理。例如下图：
假设图中的小红块代表着一个像素，那么在这个像素中，R的深度肯定是小于P的深度的，我们假设在这个像素中R的深度为0.3，P的深度为0.5，然后我们会有个值用来存储这个像素对应的深度信息（默认值设为正无穷）。
此时我们就不用管绘制顺序了，例如：
- 先绘制P，绘制到该像素时，先对比P在该像素的深度（0.5）和已存入的深度的大小（由于之前没有存过所以是默认值），0.5<正无穷，因此这个像素显示P的颜色，并存入深度值0.5。
- 然后我们绘制R，对比R在该像素的深度（0.3）和已存入的深度的大小（0.5）,0.3<0.5，更新像素颜色，显示R的颜色，并更新深度值为0.3。
反之亦然，我们先绘制R，0.3<正无穷，显示R的颜色，存入0.3。然后绘制P，0.5>0.3，因为深度更大的不用显示，因此就不用管了。
在深度缓存算法中，我们会有两个buffer，如下：
- frame buffer：用来存储每个像素的颜色值
- z-buffer（depth buffer）：用来存储每个像素所对应的深度值，只保存值最小的那一个，默认值为正无穷。
对于深度缓存算法，其时间复杂度为 O(n)，因为它并不是一个排序操作（排序的时间复杂度最小也是 O(nlogn)），它仅仅只是求一个最小值，而不需要知道除了最小值外其他值的顺序如何。
了解了这些后，我们看下面这个例子就很清楚了：
图中每个格子代表一个像素，先后光栅化了一红一蓝两个三角形，根据不同的深度值得到的最终结果。
因为两个buffer的大小都是像素在屏幕上的宽和高的数量，因此这两个buffer我们都可以得到一幅图像，例如下图：
frame buffer对应的自然就是最终渲染出来的图像，而depth buffer对应的图像我们称之为深度图。
在深度图中越黑的代表越近，因为越近就是深度越小，即越接近于0，而在RGB颜色中，0即代表着黑色。反之越远，即深度越接近于1，即白色。这样就很容易看懂右边这幅深度图了。
虽然深度缓存看起来很美好，但是其实还有两个小问题：
- 虽然我们深度值是浮点型，但是还是可能存在相等的情况，那么若碰见深度值相同的情况，该如何显示？这里就需要我们特殊处理了。玩游戏中常见的闪烁效果可能就是这种情况所导致的。
- 对于带有透明度的物体，深度缓存的方法是无法处理的。
