光栅化与深度缓存 agile Posted on Oct 2 2021 优秀博文 > 本文由 [简悦 SimpRead](http://ksria.com/simpread/) 转码， 原文地址 [zhuanlan.zhihu.com](https://zhuanlan.zhihu.com/p/363245957) 光栅与光栅化 ------ **光栅**（Raster）在德语中就是屏幕的意思，**光栅化**（Rasterize）就是把东西画在屏幕上的过程。也就是说如果我们要把摄像机所看见的三维场景最终呈现到我们的屏幕上，就需要光栅化这个过程，它也是图形学中一个重要的知识点。 屏幕（Screen） ---------- 在图形学中，我们把屏幕抽象为一个**二维数组**，数组中的每个元素称之为**像素**（pixel，picture element 的缩写）。这个数组的大小，就是屏幕的**分辨率**（Resolution），例如我们常说的屏幕分辨率为 1920*1080，就是说有这么些个像素。 而像素等于是屏幕中的一个最小单位，我们可以把它理解为一个个小方块，像素内的颜色可以用 rgba 来定义，一个像素（小方块）内只存在一种颜色（注：我们这里只是对像素的一个最简单理解，实际上随着硬件的发展，不同的屏幕上的像素本身也可能是各式各样的）。 屏幕是一个典型的**光栅成像设备**（Raster display）。其他光栅设备还有： * 示波器（Oscilloscope） * 阴极射线管（Cathode Ray Tube，早期的显示器） * 液晶显示器（Liquid Crystal Display，LCD，利用了光的波动性，液晶的扭曲） * 发光二极管（Light Emitting Diode，LED） * 墨水屏（Electrophoretic Display，刷新率很低） ### 定义屏幕空间 定义屏幕空间相当于在屏幕上建立一个坐标系，这里我们以屏幕的左下角为原点，向右为 x 轴方向，向上是 y 轴方向（注，定义的方法有很多种，例如我们也可以左上角为原点，在后续的操作中遵循自己的定义即可）。  前面说到屏幕是有一个个像素所组成的，例如我们像素的二维数组为 w*h，那么就表示在 x 轴方向有 w 列，在 y 轴方向有 h 行。这里我们设每个像素的大小为 1*1，那么整个屏幕的大小即为 w*h。如上图，一个个小方块即代表一个像素。 这样我们就可以通过坐标的方式来定义每个像素的位置了，即 (x, y)，可以当做是图中每个小方块左下角点的坐标。例如坐标(0, 0) 就表示屏幕最左下角的那个像素，由于坐标从 0 开始，因此最右上角的那个像素坐标为(w-1, h-1)。 此外我们说过像素是一个个小方块，那么自然有它的中点（即图中小方块中间的点），因此像素 (x, y) 的中点即为(x+0.5, y+0.5)。 视口变换（Viewport Transform） ------------------------ 上一篇我们讲到了[视图变换与投影变换](https://zhuanlan.zhihu.com/p/362713511)，它可以把我们摄像机看到的物体全部压缩成一个标准立方体。而要把标准立方体里的内容显示到屏幕上，自然首先要把它变换成和屏幕空间一样的大小，这个变换我们称之为视口变换。 根据前面的定义，我们设屏幕空间大小为 w*h，那么该变换我们主要分为如下两步： 1. 将 x 轴和 y 轴长度为 2 的标准立方体缩放为 x 轴和 y 轴长度分别为 w 和 h 长方体。 2. 将该立方体从原点平移到  注：此处我们先不考虑 z 轴的变换，后续会有它的作用。 这个变换矩阵很简单，就不过多推导了，其结果如下： >  Mesh 与三角形 --------- 在上面视口变换后，我们的标准立方体虽然变成了一个 xy 方向和屏幕一样大的立方体，但是空间中依旧还是我们的三维物体，例如人，建筑，植物等。前面我们知道屏幕是由一个个像素组成的，也就是说我们通过屏幕看见的二维画面其实都是由无数个像素构成的。因此接下来我们要做的就是**把空间中的那些三维物体全部打散成像素，而这个过程，我们就可以称之为光栅化**。 想要把三维物体都变成像素，那么首先我们要了解这些三维物体到底是什么。 在生活中我们知道，不管是相机拍照还是人眼看，我们仅仅只能看见物体的表面，因此我们要显示在屏幕上的，也仅仅是这些三维物体的表面。 而对于表面，我们可以把它理解成由多个不同平面所组成，例如长方体即是六个长方形所组成的。在图形学中，我们需要把表面分解成无数个不同的小**三角形**（Triangle），这些三角形像网一样编织在一起，就可以形成任何我们想要的三维物体表面，这些由三角形所构成的表面我们称之为 **Mesh**。一些物体表面分解可见下面几个示意图：  为什么选择三角形呢？因为它的优点如下： * 三角形是最基础的多边形，任何其他不同的多边形都可以拆成若干个三角形。 * 我们可以通过向量的叉积来判断一个点是在三角形内或者外，但是对于有凹凸的多边形不行，这块内容可见[向量运算与应用](https://zhuanlan.zhihu.com/p/362035810)。 * 我们可以给定三个顶点不同的属性，在三角形内做出渐变效果，即可根据插值算出三角形内任意一点的属性，这块内容可见[重心坐标](https://zhuanlan.zhihu.com/p/361943207)。 单个三角形光栅化 -------- 通过上面的解释，我们又把问题进行了简单化，也就是把三维物体光栅化即是把无数个三角形进行光栅化。那么同样由繁化简，我们先来看看如何把空间中的一个的三角形进行光栅化，如下图，背景中的黑色实线所围成的小格子即是我们的像素，灰色虚线为辅助线，方便看像素的中心点：  注：图中我们可以看见显示的是一个二维空间中的三角形，我们可以理解为把三维空间中的三角形投影到了 xy 屏幕上，因为**光栅化是在 MVP 变换后做的**，视图变换后，摄像机看向 - z 轴，投影变换后，无论是正交投影的长方体还是透视投影的视锥体都变成标准立方体，因此只需要无视 z 轴的值即可。 首先可以肯定的是，光栅化后，肯定不是像上图那样的显示了。因为前面我们说过一个像素中只会存在一个颜色，而上图明显不符合这个要求，例如我们看下标为 (1, 2) 的像素点，里面只有一部分是红色的。那么这个像素到底应该是没有颜色还是全部红色呢？ 在图形学中，我们定义若一个像素的中心点在三角形的内部，那么这个像素就属于该三角形。例如例子中下标为 (1, 2) 的像素点，我们可以从图中明确的看出其中心点在三角形内部，那么这个像素就应该全部显示红色。 当然了，我们肯定不可能通过肉眼来观察是否在三角形内部，因此光栅化过程中很重要的一步便是：**判断像素的中心点与三角形的内外关系**。这里也就体现了使用三角形的好处，因为前面我们说了使用叉积的方法可以判断点和三角形的内外关系。那么我们就可以定义一个函数用来判断，如下： ``` bool isInside(t, x, y){} ``` 函数体内即使用叉积来判断（具体怎么实现这里就不写了），若在三角形内则返回 true，不在则返回 false。输入的参数 t 代表三角形的信息集合（三个顶点的 x，y 信息），输入的参数 x 和 y 即点的位置信息。 假设我们点正好在三角形的边上，那么我们应该如何考虑，到底是算还是不算在三角形内部呢。至于这个问题，就全看使用者自己的定义了，我们可以定义算在也可以不算（像在 OpenGL 里还有更严格的定义方式），后续的操作只需要遵从自己的定义即可。在本章中，我们认为这种情况不在三角形内。 知道了屏幕中任何一个点和三角形的关系后，我们只需要遍历屏幕中每个像素的中心点，带入 isInside 函数中，即可知道哪些像素属于在这个三角形内部的。其中遍历屏幕中每个像素的中心点的操作，我们称之为**采样**。 前面我们说了屏幕是由 width * height 个像素点组成的，那么即可得到下面代码： ``` for(int x = 0; x < width; x++){ for(int y = 0; y < height; y++){ pixel[x][y] = isInside(t, x + 0.5, y + 0.5);//前面提到像素中心点是像素坐标x,y的值+0.5 } } ``` 这样我们就可以知道在三角形内的所有像素了，如下图，顶点标记黑色的即为在三角形内的顶点。  **思考**：如果我们修改下上面的代码，改成如下，那是做了什么事情？ ``` for(int x = 0; x < width; x++){ for(int y = 0; y < height; y++){ pixel1[x][y] = isInside(t, x + 0.25, y + 0.25); pixel2[x][y] = isInside(t, x + 0.25, y + 0.75); pixel3[x][y] = isInside(t, x + 0.75, y + 0.25); pixel4[x][y] = isInside(t, x + 0.75, y + 0.75); } } ``` 其实很简单，做的就不再是采样每个像素的中心点，而是讲一个像素分成了如下图的四块，然后采样每个像素这四块的中心点。  上诉就是 MSAA 的核心思想，在[采样、走样和反走样](https://zhuanlan.zhihu.com/p/363284887)中会介绍到。 ### Bounding Box 在上面的过程中，我们判断一个三角形就需要采样屏幕中所有的像素中心点，若是整个 mesh 所有的三角形，那么这个计算量就变得非常的庞大。并且实际上有些三角形可能非常的小，就占了几个像素，那么这种做法就会造成很大的性能消耗。 因此我们可以使用 Bounding Box 来缩小我们的采样范围。例如下图，可能在三角形内的像素肯定是在蓝色区域的范围内，而这个蓝色区域我们就称之为 Bounding Box。也可称之为轴向的包围盒，即 Aixe align bounding box，也就是常说的 AABB。  因此，给定三角形的三个顶点，我们只需要求出三个顶点的在 x 轴的最大最小值，在 y 轴的最大最小值，即可定义出一个 Bounding Box，然后只需要在这个 Bounding Box 中进行采样即可，大大减少了计算量。 ``` for(int x = xmin; x < xmax; x++){ for(int y = ymin; y < ymax; y++){ pixel[x][y] = isInside(t, x + 0.5, y + 0.5); } } ``` 但是还有些特殊的情况，导致三角形本身依旧不大，但是 Bounding Box 特别大，例如下图这种情况：  针对这种情况，我们也可做特殊处理，例如**每行做一个 Bounding Box**，然后从左到右遍历，如下。  至于怎么判断每行的 Bounding Box 的左右边界，以及怎么判断这个三角形属于这种特殊情况，个人的思路（对不对么，我也不知道）是： 1. 从图中我们可以看出只有在三角形瘦长且倾斜的时候会导致这样的情况发生，那么我们需要去判断一个三角形是否瘦长且倾斜？其实并不需要这么麻烦，我们只需要计算三角形的面积  与其所占的 Bounding Box 的面积  的占比即可，因为需要特殊处理情况，肯定是  特别小的情况（可以假设小于 0.3 需要特殊处理）。 2.  的面积很好求，宽乘高即可。  面积我们可以使用**海伦公式**，因为我们知道三角形的三个顶点位置，也就可以求出三条边的边长，通过海伦公式即可求出三角形的面积。设三条边的边长分别为 a，b，c，则  其中 p 为半周长，即  。 3. 接着就是怎么逐行定义 Bounding Box，因为是逐行的所以每行的 Bounding Box 的 ymin 和 ymax 很清楚的可以知道，问题就在于 xmin 和 xmax 的值了。 4. 我们来单独看下某一行，如下图：  想要确定改行的 Bounding Box 宽度，我们只需要求出图中标记的四个点的 x 值（y 值已经可以确定），然后求出最大和最小的 x 即可。 从图中我们可以看出，这四个点分别在三角形的某两条边上。（若是像上图中的最下面一行的特殊情况，看着只有三个点，我们可以想象成最下面的那个点是两个点重叠即可）那么我们就要确定这两条边是三角形的哪两条边。由于四个点的 y 值是确定的（该行的 ymin 和 ymax），那么肯定是一个 y 值大于 ymin 和 ymax 的顶点和 y 值小于 ymin 和 ymax 的顶点的连线。（不可能三角形三个顶点都大于或都小于 ymin 和 ymax） 确定了四个点所在的两条边之后，我们的问题就等于变成了求直线上的一点，知道了直线的两个顶点的值，和直线中一点的 y 值，可以很轻松的求出该点的 x 的值。例如上图中标记的左下角点，其 y 值为 ymin，设其所在边的两个顶点分别为 (x1, y1) 和 (x2, y2) ，其中 x1<x2，y1<ymin<y2，那么 该点的 x 值为：  ，其他点的值同理。 ### 结果 通过上面的知识，我们可以找到屏幕中在三角形内部的像素，接着我们对这些像素进行着色，就可得到如下结果  上图也就是我们单个三角形进行光栅化后的结果，也就是屏幕中真正显示的样子。 很显然，这个效果看着和原本的三角形差距很大，三角形的边缘处都是凹凸不平的，也就是所谓的**锯齿**。因此我们要通过**抗锯齿**，使其看起来更像三角形一些。 所有物体光栅化 ------- 前面我们说的是一个三角光栅化，那么对于空间中所有的物体，也就是所有的 mesh 光栅化，即把这些所有的三角形遍历一下即可。通过一个个三角形光栅化，我们就可以将视口变换后的整个空间绘制到屏幕上了。 那么有个问题，我们知道我们看向不同的物体的时候，它们之间可能存在前后**重叠 / 遮挡**的关系，例如背着书包的人，正面看去书包和人是重叠的。并且对于单个三维物体而言，不同的面也是存在重叠关系的，例如书包的背面和正面。换句话说，所有要绘制的三角形，它们可能存在着重叠的关系，对于这些重叠的三角形，我们应该把谁显示在像素上？ 深度 -- 物体能够重叠，说明他们间存在着前后关系。对于空间中物体的前后位置，更专业的术语称之为**深度**，我们用 **z** 表示，**范围为 0.00 ~ 1.00**。z 值越大，即深度越深，代表离摄像机越远。（注意这个 z 值和坐标系的 z 值不一样，若按坐标系的话，因为视图变换后摄像机看向 - z，也就是说 z 越小，离得越远） 有关深度计算更详细的内容参考： [王江荣：【Unity】深度图（Depth Texture）的简单介绍](https://zhuanlan.zhihu.com/p/389971233) 画家算法（Painter's Algorithm） ------------------------- 在生活中，我们知道当两个物体发生重叠，我们只能看到离我们更近的那个物体。同样的，对于摄像机而言，我们也只显示深度更小的那一个。 这样我们是不是只需要求出所有要光栅化的三角形的深度，然后将它们按**深度排序**，从深度深的三角形开始光栅化即可呢？ 对于上面的操作，我们称之为画家算法，因为要按深度排序，因此对于 n 个三角形，时间复杂度为 O(nlogn) 。看着似乎是可行的，例如我们先光栅化背包背面的三角形（深度高）显示在像素上，然后光栅化正面的三角形（深度低），这样像素上就会覆盖了原本背面的颜色，没有什么问题。 但是如果是下面这两种种情况呢？ 情况 1：如下图，两个面的 z 值相同，即深度相同，那么为什么我们看见的重叠部分是红色在后白色在前呢？  情况 2：如下图，三个三角形是互相重叠的关系，无论是 P-R-Q 还是 Q-R-P 等顺序去光栅化，都不能达到我们图中的效果。  上面的例子都说明画家算法在一些特殊的情况是不可行的。 深度缓存（Z-Buffer） -------------- 前面的例子推翻了我们依照每个三角形的深度做光栅化的操作，因此为了解决类似上面这也的问题，图形学中引入了一个新的算法，叫深度缓存。 什么是深度缓存呢，字面意思上似乎是把深度值缓存起来，实际上也确实是这样，但是这里的深度不再是每个三角形的深度，而是针对每个像素来处理。例如下图：  依旧是之前的例子，假设图中的小红块代表着一个像素，那么在这个像素中，R 的深度肯定是小于 P 的深度的，我们假设在这个像素中 R 的深度为 0.3，P 的深度为 0.5，然后我们会有个值用来存储这个像素对应的深度信息（默认值设为正无穷）。 此时我们就**不用管绘制顺序**了，例如： 1. 先绘制 P，绘制到该像素时，先对比 P 在该像素的深度（0.5）和已存入的深度的大小（由于之前没有存过所以是默认值），0.5 < 正无穷，因此这个像素显示 P 的颜色，并存入深度值 0.5。 2. 然后我们绘制 R，对比 R 在该像素的深度（0.3）和已存入的深度的大小（0.5）,0.3<0.5，更新像素颜色，显示 R 的颜色，并更新深度值为 0.3。 反之亦然，我们先绘制 R，0.3 <正无穷，显示 R 的颜色，存入 0.3。然后绘制 P，0.5>0.3，因为深度更大的不用显示，因此就不用管了。这样就可以解决我们上面提到的画家算法没法解决的问题了。 对于上面的情况 1 也是一样的，例如下图中，依旧以红色为像素块，那么在该像素中白色的深度是小于红色的，因此显示白色。  可见两者的区别在于： * 画家算法中，一个三角形只有一个深度值，及其重心点的深度。 * 深度缓存算法中，一个三角形根据它所占用的像素，拥有多个深度值，每个像素对应一个深度。 因此在深度缓存算法中，我们会有两个 buffer，如下： * frame buffer：用来存储每个像素的颜色值 * z-buffer（depth buffer）：用来存储每个像素所对应的深度值，只保存值最小的那一个，默认值为正无穷。 深度算法简单的逻辑代码如下： ``` float[,] frameBuffer = new float[width, height];//存储每个像素的最终颜色 float[,] zBuffer = new float[width, height];//存储每个像素的深度值 for (int x = 0; x < width; x++) { for (int y = 0; y < height; y++) { //设默认值为正无穷 zBuffer[x, y] = float.PositiveInfinity; } } //遍历所有三角形 foreach (Triangle t in allTriangle) { //光栅化每个三角形 for (int x = xmin; x < xmax; x++) { for (int y = ymin; y < ymax; y++) { //如果该像素在该三角形里 if (isInside(t, x + 0.5, y + 0.5)) { //比较该三角形在这个像素的深度和已经保存了的深度 if (t.z < zBuffer[x, y]) { //如果新的深度值更小，则更新颜色和深度值 frameBuffer[x, y] = t.color; zBuffer[x, y] = t.z; } else ;//反之不用任何操作 } } } } ``` 对于深度缓存算法，其时间复杂度为 O(n)，因为它并不是一个排序操作（排序的时间复杂度最小也是 O(nlogn)），它仅仅只是求一个最小值，而不需要知道除了最小值外其他值的顺序如何。 了解了这些后，我们看下面这个例子就很清楚了：  图中每个格子代表一个像素，先后光栅化了一红一蓝两个三角形，根据不同的深度值得到的最终结果。 ### 深度图 因为两个 buffer 的大小都是像素在屏幕上的宽和高的数量，因此这两个 buffer 我们都可以得到一幅图像，例如下图：  frame buffer 对应的自然就是最终渲染出来的图像，而 depth buffer 对应的图像我们称之为深度图。 在深度图中越黑的代表越近，因为越近就是深度越小，即越接近于 0，而在 RGB 颜色中，0 即代表着黑色。反之越远，即深度越接近于 1，即白色。这样就很容易看懂右边这幅深度图了。 ### 其他一些问题 问题一，虽然我们深度值是浮点型，但是还是可能存在相等的情况，那么若碰见深度值相同的情况，该如何显示？这里就需要我们特殊处理了。玩游戏中常见的闪烁效果可能就是这种情况所导致的。 问题二，对于带有透明度的物体，深度缓存的方法是无法处理的。 贝塞尔曲线与曲面（Bezier Curve and Surface）的详细介绍与代码实现 光栅化过程中的采样与反走样（MSAA），频域与滤波