# Rasterization（光栅化）

# Triangles - Fundamental Shape Primitives

三角形是最最基础的多边形，任何其他的多边形都可以拆成三角形。三角形还有一些独特的性质。例如，三角形永远都在一个平面内；三角形的内外定义的很清楚，可以用向量的叉积来判断一个点是不是在三角形内；根据重心坐标我们很容易进行插值。

接下来我们要做的就是判断一个像素和三角形之间的位置关系。

# A Simple Approach: Sampling（采样）

采样就是把一个函数离散化的过程。

判断一个点是否在三角形内，我们只需要按照一个循环的顺序依次与该点形成的向量做叉乘即可，如果该点在三角形的里面，那么最后结果的向量的方向都应该是一致的。

实际上，并不用检查屏幕上所有的像素区域，我们把上面蓝色区域的部分叫做包围盒。用这个轴向的包围盒（AABB）检查三角形覆盖的区域即可。

这里我们会发现我们实际光栅化后得到的三角形是存在锯齿的。为什么会出现锯齿，是因为像素本身有一定的大小，并且我们的采样率对于这个信号来讲是不够高的，从而产生了信号的走样问题。

那么抗锯齿（反走样）就是我们接下来要做的事情。

# Sampling Artifacts in Computer Graphics（采样的一些问题）

走样产生的原因：采样的速度跟不上信号变换的速度就会发生走样。

# Blurring (Pre-Filtering) Before Sampling（先模糊再采样）

可以看到，先模糊再采样的方法还是不错的。

但是先采样再模糊的结果就不尽人意了。

# Frequency Domain（频域）

傅里叶级数展开：任何一个周期函数，都可以把它写成一系列正弦和余弦函数它们的线性组合以及一个常数项。

通过傅里叶级数展开，我们可以发现：任何一个函数都可以把它分成不同的频率（tw，3tw，5tw，7tw...）上式 f (x) 便被分解成了频率从低到高进行表示。

傅里叶变换要做的事情便是把函数变成不同频率的段并且把这些不同频率的段给显示出来。

这张图我们可以看出：高频的信号需要更加密集的采样才能保证信号不失真。

关于走样的正规定义：同样的一个采样方法采样两张不同频率的函数，得出来的结果却是相同的，我们无法区分它，这便是” 走样 “。

# Filtering（滤波）= Getting rid of certain frequency contents

由前面的知识我们可以知道，傅里叶变换可以把函数从时域变到频域，于是我们可以把左边这张图（时域）变换成右边这张图（频域），值得注意的是，虽然左边这张图本身并不具备任何时间上的信息，但是我们认为它空间上不同的位置也算是它的时域。

如何理解频域图？我们把中心定义成最低频的区域，向外则是高频的区域，从中心向外的频率会越来越高；在不同频率的位置上，它到底有多少信息，我们通过亮度来表示。

（为什么右边这张图有很明显的两条直线？这个原因是我们在分析一个信号的时候，我们会认为他是一个周期性重复的信号，那么对于不周期性重复的信号我们该怎么办？这个时候会认为这张图在水平和竖直方向上不断重复，因为图与图之间的边界上会发生剧烈的信号变化）

将上面这张图进行高通滤波之后我们只剩下了高频的信息，而这些高频的信号表示图像的边界。但是为什么？为什么高频的信号就表示了图像的边界呢？可以这样理解：在图像的边界处，信号的变化往往非常大，可能一侧是衣服，而另一侧却是背景，而这个信号发生的剧烈变化就是信号所蕴含的高频的信息。

通过低通滤波我们发现，确实图像的边界不再那么明显了。

到此为止，通过频域上的分析我们把不同的频率和信号的变化就建立起这样一种联系了。这是一种经典的图像处理方式，多说一句，现在更多的图像操作是通过机器学习来进行的。

# Filtering（滤波 - 从另外一个角度分析）= Convolution（卷积）（= Averaging）

关于卷积，一个简化的定义是，将滤波器所形成的窗口在信号上移动，并将原始信号上的值和滤波器做一个加权平均，最后便会得到一个新的信号序列。

卷积定理：时域上我如果想对两个信号做一个卷积，如果对应到两个信号实际的频域上，

是它们两个之间的乘积；反之，如果是在时域上的乘积，那么就是频域上的卷积。

当我们把左边时域上的一个小盒子变到右边频域上时，如果我们把小盒子变大，会发现对应在频域上反而变小了。也就是说，如果我们用一个大的 box 进行滤波，留下的更多的就是低频信号，图像会变的更模糊；反之，如果我们用一个小的 box 进行滤波，那么一些高频信号并没有被过滤掉，图像相对来说就会清晰一些。

# Sampling（采样）= Repeating Frequency Contents（重复频域上的内容）

从上面的图我们会发现，采样实际上是在复制频域上的频谱。

那么为什么会产生走样现象呢？是因为采样的不同时间的间隔会引起频谱以不同的间隔进行移动。如果采样的频率不够快，就会导致频谱复制粘贴的间隔会比较小，以至于它们重叠在了一起，在这种情况下，我们就称之为走样。

# Antialiasing（反走样）

如何减缓走样现象？

• 增加采样频率
• 先模糊再采样

先做模糊实际上就对应了上面频谱的显示。这时，我们发现频谱之间的混叠就没有了。

在这里，我们把像素内部的值根据三角形的覆盖面积给平均起来了，这就是我们所说的卷积操作。

# Antialiasing By Supersampling（MASS）

超采样认为一个像素被划分为了好多个小的像素，然后判断这些点是不是在三角形的内部，然后我们再把这些点给平均起来，就达到了对三角形覆盖区域的一个近似。

# Visibility/occlusion

画家在作画时，会先将远处的物体画出来，再来画近处的物体。我们借用画家算法的思想，先画立方体后面的面，再以左下右上的顺序画出周围的面，再画出最前面的这个面，我们便能得到立方体正确的显示结果。但侧边的四个面我们随便改一下顺序，又会发现结果不对，也就是说，定义这个深度有一定的难度。

但是面对上图这种情况，无论我们以怎样的顺序去画，画家算法都不能得到正确的结果。

由于对空间中的三角形不好排列它们的顺序，于是就想到了对每个像素进行 z 值的排列，每个像素只记录它表示的几何的最浅的深度（也就是离我们最近的那个距离）。为了完成这个深度缓存，我们会渲染这个成品的图，也就是我们要的这个图像，然后在生成这个图像的同时，我们也会生成另外的图像，这个图像只存任何像素它所看到的几何物体的最浅的深度的信息，我们把这个图叫做深度图或者深度缓存。

在这个地方，为了方便理解，我们认为 z 值永远是正值。

这个算法具体要怎么做呢？首先我们认为这个深度缓存中记录的所有像素它们一开始记录的距离都是无限远的。对于任意一个三角形，我们都可以把它光栅化成不同的像素，所以我们就可以找到任意一个三角形覆盖的任意一个像素，这就是两个 for 循环的意思。然后将新的三角形的深度和深度缓存之前的深度进行比较，并进行相应的更新。

对于画家算法，我们有 n 个三角形，把这些三角形排序一遍要花 O (NlogN) 的时间，而对于 Z-Buffer 算法来说，我们只需要 O (N) 的时间复杂度即可对深度进行排序（更准确的说，只是在记录当前深度的最小值）。利用深度缓存我们和三角形的渲染顺序是没有关系的。只要能够维护深度缓存中的内容即可，这里我们假设永远都不会有两个三角形对应像素的深度值相同。很多时候我们都是用浮点数来表示一个值的，而浮点型和浮点型判断相同是非常困难的事情，通过计算而得到的浮点数存在浮点数精度丢失的问题，但确实有时会出现两个深度值相同的情况，这种情况如何处理，这里暂时不做详细说明。

这里再多说一句，为了做反走样我们会用到 MSAA 的技术，在一个像素内取很多的采样点，对于不同的采样点来说如果我们要应用深度缓存，那么我们就需要对每一个采样点记录一下它所能看到的深度信息，这个时候用 Z-Buffer 就要考虑对每一个采样点记录深度信息。