Games101(2)-光栅化与着色

光栅化Rasterization

首先考虑之前在变换章节我们完成的事情。在MVP变换中，我们经过Model，View的变换，将照相机放置在了标准位置，并将对应的Model坐标也进行转换；再通过Projection变换，将所有的Model坐标都映射到了一个标准立方体中，即\([-1, 1]^3\)中。而下一步，就需要将标准立方体的信息绘制在图像上，或者说绘制在显示器屏幕上。而光栅化(Rasterization)指的就是将模型绘制在屏幕上的过程。在德语中，Raster表示的就是screen屏幕的意思，因此动词化的Rasterize，就表示绘制到屏幕上这一操作。

在具体介绍光栅化之前，我们首先需要明确一些概念。

在计算机图形学中，3D模型通常都是由数量众多的三角形组成的。通常来说，要描述一个3D模型，我们会提供一系列三维的坐标，同时提供三角形信息，具体来说就是描述所有的哪三个点会构成三角形。使用三角形来描述3D模型是有很多好处的，包括但不限于三角形足够简单；三角形可以保证是一个平面；同时三角形有很好的方式来进行插值计算（利用重心坐标）。

而屏幕通常会被看成是一个二维矩阵，矩阵中的每个元素是一个像素pixel，每个像素是一个单色的小矩形，具有RGB等色彩信息。这个矩阵的大小就是常说的分辨率。我们一般会将像素看成是屏幕上的一个点，当然实际上，每个像素都会占用一定面积，并不是真实的点，一个像素代表一个矩形区域，它的值就是这一块矩形区域属性的平均值。在屏幕坐标系下，利用一个二维坐标(x, y)，我们就可以确定一个像素的位置，而这个像素的中心点实际上是(x+0.5, y+0.5)。其中，屏幕坐标系原点的位置的指定是一个习惯问题，多指定为左上位置。

假设屏幕宽度有width个像素, 高度有height个像素。如果先不考虑z轴的话，那么将标准立方体中的xy范围\([-1,1]^2\)映射到屏幕尺寸\([0,\text{width}] \times [0, \text{height}]\)，实际上就是执行了一个缩放操作，其中缩放矩阵为:(注意这里还是3DModel坐标系中的变换，与屏幕坐标系无关，只是使用到了屏幕的宽度和高度) \[ \mathbf{M}_{viewport} = \begin{pmatrix} width/2 & 0 & 0 & width/2 \\ 0 & height/2 & 0 & height/2 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{pmatrix} \]

不要将3D Model的坐标系和屏幕坐标系混淆，二者并没有直接的联系。

三角形光栅化

由于3D模型最终是有三角形构成的，因此我们考虑基础的三角形光栅化。考虑我们现在具备的条件，我们有一个三角形在\([0,\text{width}] \times [0, \text{height}]\)连续空间中的表示，需要将其绘制在屏幕上，简单来说，就是决定哪些像素需要被绘制上颜色。

一种简单的考虑方式是判断每个像素的中心点和三角形的位置关系，如果像素中心点在三角形内，那么就将其绘制在屏幕上，否则不进行绘制。而在之前在线性代数基础中，我们已经简单介绍了如何利用叉乘来判断一个点是否在三角形内，实际上这也就是三角形光栅化的核心。整体的逻辑可以用下面的伪代码来表示：

# image表示屏幕像素数组
# inside函数用于判断(x,y)是否在三角形t中
int inside(t, x, y) {
    if (Point(x, y) in triangle t) {
        return 1
    } else {
        return 0
    }
}

# 循环处理每个像素
for(int x=0; x < width; x++) {
    for(int y=0; y < height; y++) {
        image[x][y] = inside(tri, x+0.5, y+0.5);
    }
}

当然实际上，我们可以一定程度上减少循环次数。如果我们知道了一个三角形的三个顶点，那么很容易计算出一个小于屏幕范围的BoundingBox，然后只需要遍历BoundingBox中的像素即可。

走样分析

使用上面的操作，我们可以将一个三角形绘制在屏幕上，但是我们会发现实际表示出来的效果非常不真实，带有非常明显的锯齿，这点在分辨率低的情况下尤为明显。我们称这种现象为走样。当我们提高分辨率之后，锯齿问题可以得到一定程度的缓解，但是这没有解决走样问题。

走样问题的解决被成为反走样，反走样应该在同等分辨率的条件下进行解决。一种解决方案是先对三角形进行模糊，然后再进行光栅化。这里我们对于每个像素只进行一次判断，即使用中心点坐标是否在三角形内，来代表整个像素。另一种可以一定程度增加真实性的操作是超采样，对像素区域内进行多次采样，每次采样得到的坐标都进行是否在三角形内部的判断，最终整个像素的表示就是这些采样的综合。注意第二种方法并没有提高分辨率，最终得到的像素个数依然没有改变。

对于走样和反走样的分析，可以从采样理论方面进行分析，具体指的是频域和时域的分析。出现走样的原因是采样频率过低，也叫做欠采样，简单说明一下就是信号变化很快，但是我们采样的频率跟不上信号变化的频率。欠采样可能导致的问题包括锯齿，摩尔纹和马车轮效应等。

深度缓存

通过上面的分析，我们现在已经可以将空间中的一个三角形给绘制在屏幕上了，下一步就是将这个过程推广到空间中所有的三角形上。对多个三角形进行光栅化，必然会出现可见性和遮挡的问题。光栅化的结果应当和现实生活中的场景类似，当出现遮挡时，则是离照相机远的被遮挡，离得近的能够显示出来。

一种很简单的处理方式是画家算法，这种算法总是先绘制远的物体，然后再绘制近的物体。在整个过程中，新绘制的物体如果与已绘制的物体有重叠部分，新的结果总会覆盖旧的结果。这种方式非常简单，但是会出现非常多的冗余计算。并且画家算法无法解决物体之间相互交错的情况，因为无法完全分出哪个物体在前，哪个物体在后。

在图形学中，通常使用深度缓存Z-Buffer的算法来处理这类问题。具体来说，当我们需要光栅化得到一幅图的时候，底层实际上维护了两个数组，分别是frame buffer和depth buffer(z-buffer)，分别称为渲染图和深度图。它们分别存储了每个像素的RGB值和每个像素的最小深度值，即空间中的Z值。深度图的维护也非常简单，首先将depth buffer中的每个像素值深度初始化为无穷，然后遍历每个三角形，根据三角形采样点的Z值来判断是否更新frame buffer和depth buffer。伪代码如下。这里需要注意的是，我们始终认为深度是一个非负数，如果在空间中的实际坐标为负，则取它的绝对值。这种处理方式可以统一不同坐标系定义之间的差别，使得算法无需进行符号操作。

for (each triangle T) {
    for (each sample (x, y, z) in T) {
        if (z < depth_buffer[x, y]) {
            frame_buffer[x, y] = rgb; // update color
            depth_buffer[x, y] = z; // update depth
        } else {
            pass; // do nothing
        }
    }
}

如果我们将深度图进行可视化，可以得到一张灰度图，每个像素记录其最浅的深度。在这张灰度图中，离照相机近的物体会显得更黑，颜色更深。因为深度值小，转化为灰度值，越小越黑。

Z-Buffer算法的复杂度为\(O(n)\)，因为它只需要对所有的三角形遍历一遍即可。并且Z-Buffer算法具有顺序无关性，这就使得该算法可以并行完成，例如使用GPU来进行加速。但是Z-Buffer也有一些缺点，例如无法处理透明物体等。

着色Shading

通过光栅化，我们可以将模型绘制在屏幕上，但是得到的效果非常不真实。在图形学中，Shading着色指的是根据不同物体的材质和光照进行不同效果呈现的过程，经过shading操作之后，物体会显得更加真实。

Blinn-Phong着色模型

Blinn-Phong着色模型是一个简单的着色模型。它是一个经验模型，虽然不完全符合真实生活中的光照现象，但是能够在一定程度上进行模拟。该着色模型将光线分为三类，分别是高光(Specular Highlights)、漫反射(Diffuse Reflection)和环境光照(Ambient Lighting)，三类光照分别使用不同的计算方式。

首先考虑shading作用在某个点的过程，这个点我们称为shading point。在该点上具有如下相关属性：

• 向量v为viewer direction，是从shading point指向观察点位的单位向量
• 向量n为surface normal，是shading point所在位置的法向量
• 向量l为Light direction，是从shading point指向光源的单位向量
• 还有一些材质本身的性质，包括颜色，光泽度等属性

漫反射

首先考虑三种光照类型中的漫反射。在漫反射的条件下，如果一束光打在物体的某个点上，光线会均匀地反射到各个不同的方向，也就是说观察者不管从什么角度进行观察，表面的颜色都是一样的。但是同样的光如果以不同的角度照在同样的表面上，得到的明暗程度是不一样的，因为物体单位面积吸收光的多少是不同的，因此能反射出去的也有所不同，如图所示：

一般认为只有当入射光线与shading point所在平面垂直的时候，该点才能完整地接受所有光的能量。Lambert余弦定律定向地描述了这种情况，它通过光线方向和法线方向来计算一个shading point的亮度，即接受到的光线能量与光线的角度有关，这里可以通过光线方向和法线方向点乘得到cos来表征角度。

接下来考虑有到底有多少光到达了shading point，考虑光从光源向外辐射的过程，这个过程可以看作是无数个球壳叠加。由于球的表面积计算公式是平方项的，同时结合能量守恒，因此光源处的光强度与半径为r处的光强度成平方反比的关系。

结合上面的分析，我们可以得到Blinn-Phong着色模型中漫反射光照强度的计算公式。

其中：

• \(k_d\)是一个与shading point所在位置的材质有关的系数，用于表征该物体吸收能量的能力。该系数为1表示物体材质完全不吸收能量，具有最大的亮度；该系数为0则表示全部吸收，那么看到该点就是黑色
• \(I\)为定义的光源处的光强，\(r\)为光源到shading point的距离
• \(\mathbf{n} \cdot \mathbf{l}\)得到的结果就是\(\cos{\theta}\)，结合Lambert余弦定律来估计shading point吸收了多少能量。这里使用与0进行max取值的原因是如果点乘的结果为负数，则表示\(\theta\)大于九十度，对应实际情况是光从物体下面打到物体表面。在只考虑反射的条件下，这种情况没有任何意义，因此使用max将大于90度的光进行排除
• 漫反射与观测的角度没有关系，这是由漫反射基本原理决定的：在其余条件相同的情况下，人在不同方向看到的漫反射光是完全一样的。因此这里并不会涉及观测方向\(\mathbf{v}\)的参与

高光

接下来考虑三种光照类型中的高光。高光可以理解为是到达shading point之后通过直接镜面反射进入人眼中的光照，如图所示。其中\(\mathbf{R}\)表示镜面反射出射光的方向。

通过直觉考虑，该shading point反射的高光强度应当与出射方向\(\mathbf{R}\)和观察方向\(\mathbf{v}\)之间的夹角有关，夹角越小，光强度越高。我们通过镜面反射定律计算出\(\mathbf{R}\)，然后再计算\(\mathbf{R}\)与\(\mathbf{v}\)之间的夹角来得出最终的光强。这的确是一种计算方式，但是可能会遇到比较复杂的运算。Blinn-Phong着色模型则采用了一种半程向量的思想，得出高光强度的计算方式：

其中：

• \(\mathbf{h}\)被称为半程向量，它是\(\mathbf{v}\)和\(\mathbf{l}\)之间角平分线方向上的单位向量。相比于上面的夹角，半程向量计算方式非常简单。半程向量与法线方向之间形成一个夹角\(\alpha\)，Blinn-Phong的思想就是用这个夹角来近似表示出射方向\(\mathbf{R}\)与视线方向\(\mathbf{v}\)之间的夹角
• \(k_s\)是镜面反射系数，同样与该点所在位置的材质有关
• 注意到这里有一个指数\(p\)的存在，这个指数实际上是用来控制高光衰减速率的值。指数越大，高光衰减越快，即高光范围越小，只有在很小的范围内才能看到高光

环境光照

最后考虑三种光照类型中的环境光照。对于环境光，Blinn-Phong着色模型做了一个非常大胆的简化，即认为无论在哪个点，环境光照的强度都是一样的，即公式中的\(I_a\)。而公式中的\(k_a\)则与该点所在位置的材质有关。

最终总结一下，Blinn-Phong着色模型对一个shading point的光照计算如下： \[ \begin{aligned} L &= L_s + L_d + L_a \\ L_s &= k_s(I/r^2)\max{(0, \mathbf{n}\cdot\mathbf{h})^p} \\ L_d &= k_d(I/r^2) \max{(0, \mathbf{n} \cdot \mathbf{l})} \\ L_a &= k_aI_a \end{aligned} \]

着色频率

通过Blinn-Phong着色模型，我们可以计算出在某个shading point上的光照强度。而着色频率Shading Frequencies描述地则是我们如何将Shading应用在模型上。常见的策略有三种，分别是Flat Shading逐平面着色、Gouraud Shading逐顶点着色以及Phone Shading逐像素着色。

Flat Shading逐平面着色以Model的面为着色单位，对于每个三角形，使用叉积计算出每个三角形的法线，之后可以根据着色模型进行计算，将结果赋予整个面。

Gouraud Shading逐顶点着色则是以Model的各个顶点为着色单位，对于每个顶点首先计算出该顶点的法线，然后进行一次着色，而三个顶点构成的三角形的着色结果则可以通过插值方法得到。其中顶点法线的计算方式可以通过各面平均完成。具体来说，将顶点所关联的各个面法线进行简单或者加权平均，最后进行归一化，就可以得到顶点的法线。

Phone Shading逐像素着色则是以像素为着色单位。对于每个像素，首先求出对应的法线方向，然后进行着色。像素的法线方向可以通过插值完成，首先得到对应三角形三个顶点的法线方向，然后通过插值得到像素的法线方向。

通常情况下，逐像素着色能够得到比较好的效果，但是相应的计算复杂度也更高。不过这也不是一定的，当模型面数逐渐增加，也可以选择相对简单的着色模型，此时仍然能够得到较好的效果。

纹理映射Texture Mapping

纹理图

到目前为止，我们讨论的模型都是一些简单的三维物体，这里的简单体现在物体各个位置上的属性我们简单地认为是相同的。纹理映射Texture Mapping实际上解决的就是如何在物体不同位置上定义不同的属性。通过纹理，我们可以定义物体上不同位置的属性，即前面公式中出现的\(k\)。这样在进行着色的时候，不同位置得到的效果也不同，更接近现实世界中的情况。

任何一个三维物体的表面都是二维的，并且我们通常只考虑物体表面点的属性，因此如果将物体的表面展开成一张二维的图，就可以得到一张纹理图。通常会在纹理图上使用纹理坐标系uv，并且3D模型中的每一个顶点，都可以对应纹理坐标系上的一个uv坐标，这样通过查询的方式可以直接得到对应的属性，这也就是纹理映射中映射的来源。当然这种映射并不是严格限定为一一映射，不同的顶点可以对应到同一个uv坐标，即不同位置可以映射为相同的纹理。

引入纹理映射，我们就解决了模型三角形每个顶点上的属性定义问题。这张图实际上在进行美术建模的时候，就已经同步完成了，此时就已经为模型的每个顶点分配了uv信息。而对于三角形内部的属性，则可以利用插值的方式进行平滑的过渡。

问题分析

虽然我们现在有了一张纹理图，可以提供不同位置的属性信息，但是这张图不总是能和最终的分辨率对应。例如当纹理图的精细程度无法跟上分辨率的时候，就会出现下面最左边这种类似马赛克的情况。

我们首先定义一个概念为texel(纹理元素、纹素)，它可以理解为在纹理图中的一个像素。

考虑现在需要查询得到一个点的纹理，但是由于分辨率高，但是纹理图又不够精细，这就导致在查询uv的时候可能得到一个非整数的值。也就是想要查询的点落在了uv的一些非整数点上。如果此时直接采用最近查询的方式返回纹理值，那么就会出现第一幅图那种马赛克的情况。

此时可以考虑使用插值来解决这样的问题。例如对于这个点，我们再考虑它周围的四个点，进行纹理的插值，具体插值方式这里不进行展开。Bilinear Interpolation双线性插值得到的就是第二幅图的情况，可以看到效果明显更加优秀。或者可以进一步使用Bicubic方式，取邻近的16个texel，每次对四个进行双线性插值。

上面描述的纹理不够精细的时候会产生的问题。另一方面，在一些情况下，如果纹理过于精细，也会产生一些问题。例如下面的图，在近处出现了锯齿，在远处出现了摩尔纹的现象。

出现这种现象的原因也可以解释，由于纹理图比较精细，可能一个像素就覆盖了多个texel。

超采样SuperSampling可以在一定程度上解决这种问题，对每个像素进行超采样，然后将得到的纹理结果进行平均。这样确实可以一定程度缓解，但是代价是昂贵的计算量。不过我们可以从这种方式中得到启发。在目前的uv查询方式中，我们都是通过点进行查询的，如果对应一个范围，则通过采样后平均来解决。那么有没有一种方式，可以直接范围查询得到平均值，而不需要进行采样。Mipmap就是基于这种思想来解决问题的。

对于一张纹理图，我们可以首先对其进行Mipmap的计算，即逐步降低纹理图的精度，得到不同精度下的纹理图，最终可以构成一种类似图像金字塔的结构。相比于原来的只存放一张纹理图，Mipmap额外存放了其他多级的结果。不过由于每层除以4的存储容量，实际多出来的只是原先\(1/3\)的存储量。

有了预先处理的纹理图像金字塔之后，就可以执行范围查询了。对于一个像素点，我们可以根据该点覆盖纹理图的区域计算出对应匹配的层级，如果该层级为整数，就可以直接在对应的层级中进行查询，如果层级为非整数，则可以在前后两个层级之间查询之后进行插值处理，这样可以得到一个过渡平滑的处理结果，这里不进行细节的描述。

这种方式相当于提前算出了一系列特定区域的平均，之后将一般的区域近似到这些特定区域上，最后直接做查询。

当然Mipmap方法也存在一些缺点。首先Mipmap只支持正方形的范围查询，并且在处理过程中的很多地方存在近似，因此与真实的效果还是有所差距，可能会出现过渡模糊(OverBlur)的情况。但是相比于最初的结果，效果已经得到较大改善，并且没有带来很高的额外开销。

在此基础上，还有各向异性过滤(Remap)和EWA过滤，这两种方式对Mipmap进行改进，前者增加了在横纵两个方向的计算，允许我们对一个矩形区域进行范围查询；后者使用多个圆形来覆盖拟合不规则的形状，代价是带来多次查询。

纹理的高级应用

在现代GPU中，我们可以将纹理理解为一张图，或者说是一块内存，并且我们可以对这块内存进行范围查询。纹理提供的是一种机制，即将图像映射到物体表面。经典的纹理映射完成的就是将纹理图的内容映射到物体表面。

事实证明，一旦将图像映射到物体表面的机制存在，纹理映射还能做远远不止创造表面细节的事情，比如创造阴影和反射、提供照明、甚至可以定义出物体的形状。在复杂的交互程序中，纹理被用来存储各种数据，这些数据甚至与图片无关!

纹理还有许多高级应用，例如可以用纹理来记录环境光照。环境光照可以记录在球面上，将其展开后得到记录环境光照信息的纹理图。使用球面记录信息，在展开之后会导致扭曲的效果，Cube Map是其中一种改进方式。它采用球形的外接立方体来记录光照信息，最终展开成一个六面的正方体展开图。这种处理方式不会有扭曲的现象，不过代价是坐标映射的计算方式会相对复杂。

使用纹理，还可以影响shading的结果，达到欺骗人眼的效果。例如通过法线贴图，我们可以定义一个复杂的纹理，但是不需要改变Model的几何信息，即不会带来更多的三角形增加模型的复杂度。在法线贴图中，我们定义每个顶点法线的扰动情况，之后在进行shading的时候，结合记录的法线扰动情况，重新计算该点的法线，从而影响shading的结果。或者使用位移贴图，直接定义每个顶点的扰动位置，进而影响shading结果。

纹理还可以用来记录一些事先计算好的信息，在需要使用的时候直接进行查询使用，以此来增加渲染的速度。

图形管线Graphics Pipeline

至此，我们已经基本了解整个图形管线的流程，即如何将3D场景变换到二维屏幕上的一张图。

1. 首先通过MVP变换，将3D空间中的顶点变换到屏幕中(Vertex Processing)
2. 然后构成对应的三角形(Triangle Processing)
3. 通过光栅化得到对应的像素点表示，此时三角形都被离散化成为了一堆像素点(Rasterization)
4. 通过着色shading，深度测试等等操作，得到最终的Image

现代的图形管线通常已经被整合在了硬件当中，例如GPU等。在这个渲染管线中，有某个特定部分是可编程等，这个部分被称为着色器Shader。着色器工作在图形渲染管线等某个特定部分，接收某种输入并执行得到对应的输出。着色器分为顶点着色器和片段着色器，它们工作在渲染管线的不同位置。顶点着色器(Vertex Shader)作用在Vertex Processing。该着色器接受一个单独的3D顶点作为输入，输出则是2D坐标。除了完成MVP变换，我们还可以增加一些自定义的操作。片段着色器(Fragment Shader)作用在Fragment Processing。该着色器主要完成的是为每个三角形中的每个像素进行着色。

重心坐标

在前面我们多次提到插值，插值可以让我们得到一个平滑的结果。前面提到的许多操作，都是在三角形的顶点上完成的，而插值允许我们得到三角形内部任意点的平滑结果。并且得益于重心坐标，这种插值的计算也非常方便。

重心坐标是定义在三角形平面上的一个坐标系，假设三角形的三个点分别为\(A,B,C\)，那么任意一个点都可以使用这个三个点坐标的线性组合来表示，即: \[ (x,y) = \alpha A + \beta B + \gamma C, \text{其中，}\alpha + \beta + \gamma = 1 \] 后面的约束条件是为了保证所求的点在在三角形平面内。

实际上，重心坐标的三个值与对应三角形面积有密不可分的关系，实际上如果要用重心坐标来表示三角形的重心，那么得到的应该是\((1/3, 1/3, 1/3)\)。

如果已知一个点的实际xy坐标，那么可以通过下面的方式计算出对应的重心坐标：

需要注意的是，空间维度变换并不能保证重心坐标不变，因此三维空间的属性需要在三维空间中进行插值。

Shadow Mapping

前面我们提到shading着色，它完成的只是对某个shading point的处理，使用的只有单个点的相关性质(属性k、法线、光照方向等)，并不会考虑其他点对它的影响，即shading实际上不能做出阴影的效果。接下来则介绍一个可以在光栅化中处理阴影的方式，称为Shadow Mapping。

需要指出的是，Shadow Mapping是一个在图像空间中的算法(Image-Space Algorithm)，它并不需要场景的几何信息。另一方面，Shadow Mapping只能处理点光源，只能构造硬阴影，具有明显的阴影边界。

阴影的产生与光源有关。来自光源的光线，如果照射到不透明物体上，被该物体遮挡的地方，由于光线无法到达，于是会产生阴影。从这个原因出发，似乎阴影的构造一定需要几何结构的参与，但是Shadow Mapping的思想来自于观察到的另一个现象。假设在点光源的位置有一个照相机，从这个位置向物体看，可以得到一张深度图，也就是哪些像素能够被看到；同样从实际的观察位置看，也可以得到从该点到光源的深度。如果某个地方可以通过实际观察位置看到，但是无法通过点光源的位置看到，那么这个位置就应该出现阴影。或者换一种说法，没有阴影的地方必须能够同时从实际观察位置和点光源位置看到。

Shadow Mapping的实际做法也确实是这样。首先从点光源看向场景，记录看到的每个点的深度，可以得到一张深度图；之后从实际观察位置出发，再次看向场景。对于每个看到的点，可以将其投影回从光源观察时所成的像上，此时也有一个深度信息。如果从光源到该点的深度与从实际观察位置看到的该点到光源的深度相同，那么说明这个位置没有阴影。于是通过两次不同方向的计算，可以得到一张Shadow Map阴影图，它表示的就是在哪个位置上有阴影。这张阴影图也是一张图，它的分辨率则影响整体的阴影质量。

Shadow Mapping具有不错的效果，但是也存在一些问题。首先是上面提到的只能处理点光源，无法形成软阴影；其次在Shadow Mapping的过程中会涉及到浮点数的比较，因此会存在数值精度的问题，现有的算法都是在一定程度上缓解效果，无法从本质上解决数值精度的问题。

参考文章

1. Lecture 05 Rasterization 1 (Triangles) bilibili
2. 计算机图形学入门(四): 图形渲染管线 - 掘金
3. 08_Shading2(Shading,Pipeline and Texture Mapping)