3.5.1 形态反走样

SSAA和MSAA都是在一个像素正方形区域内使用多个采样点（sub sample），每个子采样点形成的区域称为一个子像素（subpixel），如图（1）所示，最后再使用某种过滤器对像素中心位置周围的子像素进行过滤，例如一个盒式过滤器（box filter）就是求这些子像素颜色的平均值。

图（1）：传统的全屏反走样技术对一个像素使用多个子采样点，通过以某种过滤方式计算这些子像素点的权重（例如面积覆盖率，距离等）来实现全屏反走样

如果每个子像素具有不同的颜色值，这称为具有子像素特征（subpixel feature），则SSAA能够比较准确地反应这种子像素特征，如图（1）(a)所示；然而，如果不考虑子像素特征，即每个像素只有一个颜色值，那么子像素的作用仅是用来计算该像素的覆盖率，这正是MSAA的思路，如图（1）(b)的思路。

通常人眼对于物体形状以及颜色变化（color variation）最敏感，而在渲染结果中这种变化通常来源于几何体的轮廓（silhouette），要么是深度不连续（depth discontinuities），或者是不同物体之间颜色不连续（color discontinuities），所以即使不具备子像素特征，MSAA在游戏中运用仍然非常广泛。由于MSAA不适用于延迟渲染，如果我们能够以一种低成本的方式计算出这些轮廓上像素的覆盖率，那么我们就可以做到和MSAA类似的品质。

形态反走样[a:MorphologicalAntialiasing]（morphological anti-aliasing，MLAA）正是基于这样的思路，它的核心算法是找出物体的轮廓信息，并利用这些轮廓信息（而不是使用更多的采样点）计算出处于轮廓上像素的覆盖率，然后使用一个后期处理（post-processing）阶段对轮廓上的像素与相邻像素的颜色进行混合。

MLAA基本算法的过程主要包括三个步骤，这里首先简要介绍这三个步骤，后面要讨论的MLAA的一些变体基本上也是按照这三个步骤来进行的，只是每个步骤内部可能使用不同的方法。这三个步骤分别是：

1. 根据一定的像素属性（如颜色，深度，法线，几何体ID等）找出图像中不连续的像素，并标记出这些像素中的哪些边处于轮廓边缘，这称为边缘检测（edge detecting），如图（2）(a)中的绿色线段。
2. 利用这些边缘线段的几何特征计算每个像素与周围邻近用来进行混合的像素的权重值（即是面积覆盖率），如图（2）(c)所示。
3. 对周围邻近的像素按照混合权重进行混合计算求出轮廓上像素的颜色值，如图（2）(c)所示。

图（2）：MLAA算法首先根据一定的标准标注出图像中不连续的边，并对其划分为L，U以及Z三种类型，然后针对这三种类型的线段连接成分段线性（piecewise-linear）的线段，这些线段将边缘部分的像素分割成两个梯形，其梯形的面积分别代表周围邻近的像素颜色进行混合的权重

由于MLAA是通过后期处理的方式来实现反走样的，所以它的输入就是光栅化渲染的一张屏幕分辨率大小的图像，如图（2）(a)所示，在这个图像中，几何体边缘部分的像素完全按照其像素中心位置是否被一个几何体覆盖来对其进行着色计算的，它是一个走样的图像（aliased image）。

MLAA拿到图像后第一步需要做的事情是边缘检测，一个图像中的边缘可以通过多种类型的属性来判断，例如相邻像素深度，颜色，法线或者材质等的不连续。通常使用颜色变化来判断边缘，因为通常具有相似颜色的像素更容易聚集在一起，一些实现也使用亮度来计算边缘。

当我们选定了边缘检测的标准之后，边缘检测可以通过遍历图像中的每两个相邻的列和行的像素，并比较相邻像素的值来判断它们的邻边是否处于边缘，如图（2）(a)中的绿色线段。因为一条直线段可能包括多个像素的边，所以接下来我们需要找到每条直线段的起点和终点，如图（2）(a)所示，由于这些终点的线段与该计算的直线段是交叉垂直的，所以起点和终点线段又称为交叉边缘（crossing edges）。

这些边缘线段可以被划分为三种类型：L，Z以及U型，如图（3）所示，每种类型的交叉边缘只包含一个像素的长度，非交叉边缘可以具有任意长度。当这些类型被划分之后，直接连接每个类型的交叉边缘的中点就构成一条轮廓线（silhouette），如图（2）(c)中蓝色的线段，它是一个Z-形状交叉边缘的中点链接起来的线段。

图（3）：MLAA中的边缘线段被划分为三种类型，每种类型的最短边只包含一个像素的长度

当轮廓线段被连接起来以后，它们将轮廓上的像素分割成两个梯形，其每个梯形的面积就代表了该像素与附近像素的颜色用来进行混合计算的权重，我们可以根据边缘线段中$d_{\rm left}+d_{\rm right}$的长度，如图（2）(c)所示，以及宽度（一个像素的大小）来计算每个梯形的面积。如图（2）(d)所示，$c_{old}$轮廓上像素原来的颜色，$c_{opp}$代表邻近像素的颜色，$a$代表轮廓上的像素的混合权重，则该轮廓上像素的新的颜色值为：

$$c_{new}=(1-a)\cdot c_{old}+a\cdot c_{opp}$$

（式1）

以上内容讨论了形态反走样方法的基本思路，然而我们并没有说明具体的算法内容，这是因为原始的MLAA算法是针对基于CPU的光线追踪渲染器实现的，现代实时渲染程序主要是面向GPU的，所以我们将在后面的内容详细讨论一个基于GPU的实现方案，即SMAA。

MLAA算法各个阶段的视觉效果如图（4）所示，它是一种非常高效的反走样技术，在不需要多重采样或超采样的基础下，几乎可以达到4倍于MSAA的效果。并且MLAA是一种后处理算法，它可以被很灵活地加入到任何渲染器而不需要对应的渲染管线做出修改。自从MLAA被提出之后，由于其高效的性能引起了大量的兴趣，在随后的几年大量的MLAA变体算法被提出，例如SRAA[a:SubpixelReconstructionAntialiasingforDeferredShading]，FXAA[a:FXAA]等， 读者可以阅读[a:FilteringApproachesforReal-TimeAnti-Aliasing]了解更多详细内容

图（4）：左上为MLAA算法输入走样的原图，右上首先根据某种标准计算像素边缘线段，然后根据这些边缘线段连接成左下图对应的轮廓线段，这些轮廓线段将边缘的像素切割成两个梯形，每个梯形的面积则用来表示周围相邻像素用来进行混合计算的权重，最终MLAA计算的结构如右下图

然而，MLAA的主要缺点是不能处理子像素级的特性，任何小于一个像素的几何体（例如超薄表面，文字等）将不能被有效地处理，由于采样的不足，高光和着色走样也不容易处理；另外，MLAA原始算法主要设计为处理贴近水平或垂直的轮廓，它几乎忽略掉了对角线轮廓，因为对角线轮廓需要考虑更多的像素，而MLAA仅考虑轮廓线上的像素的混合。下面我们将介绍这些变体中由Jimenez等提出的SMAA算法，SMAA是基于GPU实现的，它包含了针对GPU硬件的一些优化，从功能和性能上都具有较大的提升。

子像素形态反走样

子像素形态反走样（subpixel morphological anti-aliasing，SMAA）[a:SMAA:EnhancedSubpixelMorphologicalAntialiasing]是基于Jimenez等于2011年实现的MLAA[a:PracticalMorphologicalAnti-Aliasing]变体的增强算法，本节将放在一起讨论它们。此外，SMAA还包括对于时间反走样的优化，我们将把这部分内容放入到下一节当中，SMAA还被集成到了CryEngine 3[a:Anti-AliasingMethodsinCryENGINE3]当中，读者还可以获取全部SMAA实现的源代码（可从以下网站获得：http://iryoku.com/smaa/）。

SMAA和MLAA算法使用相似的步骤，但是每个步骤内部使用的方法是完全不同的。SMAA算法包含三个渲染通道（pass）：

• 第一通道：首先边缘被检测出来，这些边缘被存储到一个边缘纹理（edges texture）中，如图（5）(d)所示，纹理中的颜色表示每个边缘在像素中（即上，下，左和右）的位置：绿色像素的边缘在其像素顶部，红色像素的边缘在左边，黄色像素同时在以上两个方向拥有边缘（出于性能考虑，这里仅存储顶部和左边的边缘，因为其他两边的边缘能够从旁边邻近的像素推导出来。）。此外，在此通道，边缘像素的模板值被记录，以便后续的通道仅处理轮廓上的像素。
• 第二通道：计算每个轮廓上像素的混合权重，如图（5）(e)所示。为了计算该权重值，首先找出每条经过该像素左边和顶部边缘线段的模式，如图（5）(b)所示，然后计算出该像素距离这些模式线段交叉边缘的距离，然后这两个距离值作为纹理坐标到一个预计算的纹理中进行采样，这个预计算的纹理是根据线段模式计算出来的权重分布值，如图（5）(c)所示。
• 第三通道：根据上一步的权重值从周围的四个像素中取出颜色值进行混合计算，计算结果如图（5）(f)所示。

图（5）：MLAA概述： (a)输入的走样的图像，其中红色线段表示轮廓边缘，绿色部分表示覆盖面积，并标注了L，U和Z三种线段模式；(b)原始MLAA算法中预定义的线段模式；(c) Jimenez等MLAA变体中预计算的面积纹理；(d)检测出的边缘； (e)计算出的面积覆盖率；(f) 最终混合结果

以下分别详述每个渲染通道内的一些关键处理，SMAA算法的较大特点是充分利用了GPU纹理过滤的功能以大大减少了一些迭代，循环的操作，这些技巧对于着色器编程有非常大的借鉴作用。

边缘检测

为了进行边缘检测，首先要选择用于相邻像素边缘比较的量，例如RGB颜色，亮度，深度，法线，几何体ID等，SMAA选择使用亮度（luminance，L）值来进行边缘检测，每个像素的亮度值可以根据CIE XYZ标准计算而得：

$$L=0.2126\cdot R+0.7152\cdot G+0.0722\cdot B$$

（式2）

当边缘比较参数选择之后，由于SMAA是基于GPU中实现的，它在像素（或计算）着色器中，对每个像素比较它与左边和上边的像素的亮度值，这个比较基于一个阈值（threshold），即两个相邻像素之间的亮度差值的绝对值必须大于该阈值，比较的结果是一个枚举值，这两个枚举值被存储在图（5）(d)中的纹理中，该纹理是一个2通道的RG纹理，分别对应上边和左边是否处在边缘。

当直接以上述方法独立地进行两个像素的比较时，相邻多个（2个以上）线段的渐进变化（一个线段模式）很容易被拆分成多个独立的线段模式，如图（6）左边小图所示，一个跨多个线段的Z型模式被拆分成多个模式，这导致图（6）上中小图那样不正确的结果，而我们想要图（6）上右小图这样的结果。

图（6）：仅对本地的像素边缘进行测试可能导致过多的边缘线段而使得结果不正确，SMAA使用一种适应性双阈值的技术，通过比较相邻像素的边缘来决定是否需要保存当前像素的边缘，这样使得较长的轮廓线上的颜色过度更平滑

SMAA采用一种适应性双阈值（adaptive double threshold）的策略来克服这种问题，这种策略的思路如图（6）下左所示，其中灰色的点表示当前处理的像素点，黄色表示当前像素点可能的左边边缘，蓝色表示相邻像素的边缘。首先计算出所有蓝色边缘中亮度差值并取最大值$c_{\max}$，然后根据$c_{2l}>0.5\cdot c_{\max}$是否为true决定左边缘$c_l$是否存在。用同样的思路计算图（6）下中的上边缘。然而实践中，由于计算所有边缘涉及大量的内存占用和读取，实际的算法仅选择一部分进行比较，如图（6）下右所示。

最终的算法如下：首先计算出$e_l=|L-L_l|>T$，这里$e_l$表示边缘是否应该激活的枚举值，$L$和$L_l$分别为当前和相邻左边像素的亮度值，$T$为给定的阈值（通常在0.02到0.2之间），然后通过如下式决定边缘是否应该保留：

$$\begin{aligned} c_{\max}&=\max(c_t,c_r,c_b,c_l,c_{2l})\\ e^{'}_l&=e_l\wedge c_l>0.5\cdot c_{\max} \end{aligned}$$

（式3）

这里$c_t,c_r,c_b,c_l,c_{2l}$分别为如图（6）下右对应边的亮度差值，${e}^{'}_l$表示当前像素的左边缘是否应该激活，对应的上边缘为${e}^{'}_t$。

计算权重值

当边缘被标记出来后，混合权重（blending weights）的计算包括三个步骤：首先找出每个像素中心距离其所在形状两端的距离，如图（2）(b)以及其中的$d_{\rm left}$和$d_{\rm right}$距离；然后，需要找出该像素所在形状的交叉边缘，并连接两个交叉边缘中点构成一条轮廓线，如图（2）(c)；最后，根据这条轮廓线计算该像素的混合权重，如图（2）(d)所示。

SMAA第一个通道输出的是一种包含边缘信息的纹理，其中纹理中每个像素的值要么为1（处于边缘），要么为0（非边缘像素），如图（5）(d)所示，因此求一个边缘像素到其所在边缘形状的两端交叉边缘的距离最简单的方法，就是每次向两个方向遍历，直到遇到边缘纹理中像素的值为0。

为了加速距离的计算，SMAA算法利用硬件支持的纹理过滤功能，每次遍历向前步进2个像素单位，如图（7）所示。图中带颜色的小圆点表示边缘纹理上值为1的像素，五角星代表当前需要计算到交叉边缘距离的像素，菱形表示对边缘纹理进行采样的位置，可以看出它的步进为2个像素单位。

图（7）：SMAA算法利用硬件双线性插值功能每次步进2个像素单位计算距离，它不但减少了计算量，也减少了内存读取操作以及相应的带宽占用

由于边缘纹理上每个像素只有0和1两个值，它们均表示每个像素其中心坐标位置的值，因此从每两个相邻像素重叠的位置（菱形的地方）对边缘纹理进行采样，使用双线性插值的过滤方式将得到三种结果：

• 0.0 表示两个像素均不包含边缘。
• 0.5 表示其中一个像素包含边缘。
• 1.0 表示两个像素均包含边缘。

当某次采样的值为0.5时即停止步进，它表示下一个像素不包含边缘信息，如图（7）中的黑色的菱形位置。使用这种方法比直接对每个相邻像素进行判定要节省一半以上的计算量，同时它也减少了内存读取，节省了带宽占用。

以上是[a:PracticalMorphologicalAnti-Aliasing]中采样的方法，尽管上述方法比较有效，然而却不够精确，由于它每次迭代仅在相邻两个像素的左边缘进行比较，容易忽略掉轮廓形状另一边的左边缘，例如图（8）左下图所示，当前迭代对$b_1$和$b_2$两个像素的左边缘进行比较，但是它却忽略了$b_2$上面像素的左边缘，也就是蓝色线段，该蓝色线段本来应该导致迭代停止，因为蓝色线段就已经是交叉边缘。

图（8）：SMAA算法使用双线性插值过滤方法，一次对4个像素进行过滤，它能够非常准确地找到交叉边缘。

所以我们不仅需要对像素步进方向的像素左边缘进行比较，还需要对边缘形状另一边的左边缘进行判断。双线性插值本身是可以对周围的4个值进行插值的，但是由于我们将$y$轴与其中两个像素处于同一直线，导致$y$轴方向其他两个值的贡献为0，读者可以回头参照图[ref f:intro-BilinearInterpolation]中的双线性插值方法。所以[a:SMAA:EnhancedSubpixelMorphologicalAntialiasing]将采样点移到了4个边缘纹理中像素的中间部分，使得它可以取到各个点的插值，这样就可以考虑到上边像素的边缘分布，如图（8）右下图中黄色的采样位置，它可以同时收集$b_1,b_2,b_3,b_4$的边缘信息。

这里对纹理坐标使用了一个$(-0.25,-0.125)$的偏移，需要注意的是，edgesTex是一个RG类型的纹理，它的R用来存储每个像素的左边缘，而G用来存储上边缘，这两个分量都会被执行双线性插值采样，所以采样结果$e$是一个矢量。这里如果$e.r$为0表示$b_1,b_2,b_3,b_4$四个像素都没有左边缘，即是没有交叉边缘，所以迭代可以继续；$e.g>0.8281$用来保证$b_1,b_2$的上边缘始终存在的，否则一定应该有交叉边缘的出现。

当找到当前边缘形状两边的结束位置之后，我们还需要找到具体的交叉边缘的位置，同样使用和距离计算一样的双线性插值可以避免多次纹理读取。但是这里有一个小技巧，这里不光是需要知道哪条边是交叉边缘，为了避免条件语句的比较，这里直接将它们的返回值编码为一个特定的值，然后用这些值代表的顺序生成后面使用的面积纹理，面积纹理如图（4）(c)所示，我们在后面将会介绍。

图（9）：4种可能的右交叉边缘，使用一个（0.0，-0.25）偏移之后对边缘纹理进行采样，得到图中对应的返回结果被用于后面的面积纹理查询。

这里对像素使用一个$(0.0，-0.25)$的偏移后再对边缘纹理进行双线性插值采样，得到如图（9）中的4个返回值，这4个值乘以4之后变成0，1，3，4四个值作为后续计算的一个索引值，避免了着色器中的条件判断。

现在我们有了每个像素到两个交叉边缘的距离，以及每个交叉边缘的类型，剩下的就是利用这些值来计算边缘像素的覆盖面积。首先我们需要将交叉边缘的中点连接起来，然后计算每个像素内梯形的面积，由于每个像素涉及大量的计算（例如还要梯形与像素交叉的点，然后进行面积计算），所以SMAA仍然将这些计算逻辑保存在一个面积纹理中。

图（10）：面积纹理是由25个$9\times 9$的子纹理组成的纹理，每个子纹理的坐标表示像素离两个交叉边缘的距离，这样通过预计算的面积查询，节省了着色器中复杂面积的实时计算

面积纹理（area texture）是由25个$9\times 9$的子纹理（subtexture）组成的纹理，如图（10）所示，每个子纹理表示一个边缘形状类型，每个形状类型可以由2个0到4的索引值查询，这些索引值即是前面交叉边缘求得的数值，其中索引值2是不存在（思考交叉边缘的双线性插值采样的返回值不可能是0.5）。每个子像素采样的纹理坐标为每个像素距离两个交叉边缘的距离，这里的最大值9是一个优化选项，它表示前面的距离计算的迭代最大次数为9，当然也可以根据需要采样不同的值，但是必须和这里子纹理的分辨率保持一致。

Jimenez的SMAA算法是一种非常高效的反走样技术，它被用于大量的大型游戏及游戏引擎当中，其中的一些着色器编程方法和思路尤其值得学习，这也是CPU编程和GPU编程的不同的地方，其也是本节花这么多篇幅介绍的原因。SMAA[a:SMAA:EnhancedSubpixelMorphologicalAntialiasing}还包括其他一些进一步的优化，以及与MSAA的整合，限于篇幅，这里将这些有趣的内容留给读者去研究。