图形的走样在很大程度上会影响图形的质量，进而影响人的辨别及视觉感受。因此，在图形领域反走样一直是研究的热点。反走样的基本原理是将图像边缘的像素点与其周围的像素按某种方式进行混合，以此来消除边缘的锯齿，它是以模糊边缘为代价的。在图形学中，反走样方法大致可以分为两种，分别是提高采样率^[2]和基于屏幕空间的后处理式方法^[3]。提高采样率的方法通过增加采样点数来实现反走样，增加的采样点数越多，反走样的效果越好。目前，显卡提供的硬件反走样，例如多重采样反走样(multi-sampling anti-aliasing,MSAA)就属于这种方法，它实现起来比较容易，可以有效解决图像走样的问题，但是这种方式对硬件的要求比较高，消耗的资源多。后处理式方法的基本思路是先正常的将目标场景渲染到纹理当中，然后对纹理进行边缘检测采集出图像的边缘，最后对边缘像素做一定的平滑处理，以此来减少边缘像素的锯齿现象。

因后处理式反走样方式的优势，近年出现了许多类似的方法，在2009年，Reshetov提出了基于形态学的反走样方法^[4]，这种方法不受场景复杂度的限制，处理速度快，可用来取代硬件反走样。 FXAA^[5](fast approximate anti-aliasing)是Lottes在2001年提出的，该算法快速、高效，但会将纹理高光部分检测为边缘，适用范围有限。McGuire和Luebke提出的sub-pixel reconstruction anti-aliasing^[6]方法将单个像素着色与亚像素可见性结合以创建反走样图像，其反走样效果接近超采样反走样方法。GPAA^[3](geometric postprocess anti-aliasing)由Persson在2011年提出，该方法利用渲染引擎提供的几何体信息进行反走样，边缘平滑效果好，是反走样方法中边缘平滑最精确的方法。然而，该方法存在一个较大的缺点，一些内部边缘被视为边缘处理，增加了额外的边缘存储消耗，不利于场景的扩展。针对这一问题，通过利用面法线与虚拟摄像机的位置关系找出背向视点的不可见边缘，从而对边缘检测的过程进行改进。在场景复杂度提高且硬件条件有限的情况下，有利于缩短边缘提取用时，平滑边缘锯齿并提高显示实时性。

1 基于几何体信息的反走样

针对几何体信息的反走样算法的缺点，提出的基于边缘优化的几何体信息反走样算法能很较好的解决这一问题，该算法的主要思路是：假设场景中存在走样的现象，首先对几何体模型进行处理，检测出其走样的边缘。在此过程中，利用多边形法线与视点的位置信息判断出多边形的可见性进而判断出边缘是否需要进行反走样处理，将需要反走样处理的边缘顶点保存在顶点缓存中。然后结合延迟光照算法对目标场景进行光照处理并将后台缓存保存在纹理当中。最后将检测到的边缘以画线的形式绘制出来，每一个渲染出的边缘像素点都会与之前保存的纹理中相应的像素点混合。

1.1 边缘优化

边缘优化的边缘检测过程是基于物体空间^[7]，即利用三维模型的几何信息获取物体的轮廓线，主要包含两类边缘的检测，一个是物体与背景分离的轮廓边缘，另一个是相邻多边形形成的公共边，即褶皱^[8]。

1.1.1 轮廓边缘的检测

轮廓边缘是物体表面的前向面与后向面的分界线，它是与视点相关的^[9]。轮廓检测最直接的方法是遍历物体的所有边，然后依据物体面法线计算出边缘。假设多边形模型为O，视线方向为V，E_i为多边形的边E_i∈O，P₁(E_i)和P₂(E_i)表示公共边为E_i的两个多边形，N_j(E_i)代表P_j(E_i)的法线。多边形的可见性可由以下公式得出^[12]

${N_j}({E_i}),V < 0$

(1)

${N_j}({E_i}),V > 0$

(2)

式(1)表示多边形的法线与视线反向，多边形朝向视点，它是可见的；式(2)表示多边形背向视点，它是不可见的。借助以上两个多边形可见性判别公式可以导出轮廓边缘的一般公式：

${N_1}({E_i}),V\cdot{N_2}({E_i}),V \le 0$

(3)

式中:N₁，N₂是边E_i相邻两个多边形的法线，通过遍历E_i(i=1,2，…，n)，可以查找出物体的轮廓边缘。此外，还可根据不可见边缘的相邻两个多边形都背向视点来判断它的可见性。

1.1.2 褶皱的检测

褶皱是指两个相邻面的公共边，根据两个面形成的二面角的大小，可以将其分为脊(Ridge line)或者谷(Valley line)，两种类型的边都是独立于视点的^[10]。褶皱的检测类似于轮廓边缘的检测，但其可以不用视点信息。若P₁(E_i)和P₂(E_i)是边E_i的两个相邻面，它们的法线分别是N₁(E_i)和N₂(E_i)，则E_i为褶皱的条件是：

${N_1}({E_i}),{N_2}({E_i}) > Threshold$

(4)

式中:N₁(E_i)，N₂(E_i)都是归一化的法线，Threshold为阈值，它是二面角的余弦值，若边E_i的两个相邻面平行，则相邻面的法线也平行，此时Threshold可取0.99，由此可以判断边缘当中不是褶皱的边。

1.2 延迟光照渲染场景

延迟着色^[11]是利用几何体缓存器(G-Buffer)实现的高级图形学技术，它可以用来实现多光源的延期光照计算。延期光照^[12]借助G-Buffer将传统的光照计算转移到了光栅化阶段之后，G-Buffer只保存屏幕空间每个像素的法线、深度值、颜色值等等，利用它作为后续处理的输入，从而不再需要原先几何体的信息，在很大程度上减少了光照计算的复杂度。

延期光照计算大致可以分为两个阶段：几何阶段和光照处理阶段^[12]。几何阶段需要对场景中的几何数据进行处理，主要是坐标变换，还需要将顶点位置信息、法线及纹理坐标等填充到G-Buffer中，为后续光照计算做好准备。

光照处理阶段利用几何阶段保存在G-Buffer中的法线、位置、漫反射信息以及光源的位置信息作为输入，在片段着色器中实现Phong光照模型的计算，最后输出像素的颜色值。

1.3 几何体边缘反走样

在进行反走样之前，先要按照渲染的一般流程对目标场景进行渲染，并将渲染好的后台缓存保存在一个纹理当中，以便后期的混合平滑操作。反走样的过程如图 1。

图中较宽的深色斜线是几何体的边缘，浅灰色和深灰色的部分代表两个图元，黑色的箭头表示混合的方向及要混合的像素点，方块中的圆圈代表像素中心，黑色虚线是用来表明像素在边缘直线上的值，后面可以用来计算覆盖率coverage。

1.3.1 确定边缘朝向

在平滑边缘之前首先要确定边缘在屏幕空间的主要方向，判断边缘这条线是大致水平或是垂直。例如，图 1中的边缘可认为是大致水平的，此时应该混合其上面或者下面的相邻像素点。混合的方向取决于边缘在像素中心的哪一侧。对于边缘在像素中心上的点应该向上采样，否则向下采样。 另外，对于垂直的边缘，其混合左边或者右边相邻的像素点。

假设需反走样的边缘为E_i(E_i∈O)，边的两个顶点分别为三维向量，记做：position₀和position₁。 在处理边缘的顶点着色器中利用式(5)先将物理空间的顶点乘以裁剪矩阵Viewproj转换至裁剪空间，然后再转换至以像素为单位的屏幕空间中。因硬件对于直线和多边形的光栅化方式并不完全相同，导致对于位于两个相同顶点之间的直线和多边形边，其像素的深度值并不相同,在显示时会产生闪烁的感觉^[13]。为了避免这种问题，可以在屏幕空间对边缘做一定的偏移：

$\left\{ \matrix{ po{s_0} = Viewproj\cdot(positio{n_0},1) \hfill \cr po{s_1} = Viewproj\cdot(positio{n_1},1) \hfill \cr} \right.$

(5)

式中：pos₀和pos₁都是裁剪空间的四维向量。

${p_0} = (po{s_0}.xy/po{s_0}.w) \times bias.xy + bias.zw$

(6)

式中：二维向量p₀为pos₀在屏幕空间的坐标，它加上了一个偏移量bias，同理可求出pos₁在屏幕空间的位置p₁。

边缘直线在屏幕空间的向量dir=p₁-p₀，通过二维向量dir可判断边缘是大致水平或是垂直。在屏幕空间，如果边缘两个顶点投影至水平方向的距离大于投影至垂直方向的距离，则边缘为大致水平的，否则为垂直的。即|dir.x|>|dir.y|时，边缘为水平，否则为垂直。

1.3.2 采样方向及覆盖率计算

在确定好边缘的朝向之后，可以用直线的数学公式表示边缘，水平情况用y=kx+b表示，垂直情况下用x=ky+bx表示，k为直线的斜率。现考虑水平情形，在片段着色器利用直线公式可以求出像素点到直线的垂直距离(即图 1中像素中心到虚线的距离)dis=k·x_p+b-y_p，x_p和y_p为屏幕空间的像素坐标。dis≥0时，像素点在直线上方，采样方向朝下，否则像素点在直线下方，采样方向朝上。垂直边缘的情况类似，只是采样方向变为朝左或者朝右。片段着色器中，覆盖率coverage依据像素到该边缘的距离来计算，其公式为

$coverage = 0.5|dis|$

(7)

coverage作为边缘像素点与相邻像素点的混合权重。如果边缘穿过像素中心，则dis=0且coverage=0.5，意味着边缘所处像素与其相邻像素应均匀混合；若边缘处于像素的边界，则dis=0且coverage=0.5，表明相邻像素不参与最后的反走样混合。

1.3.3 边缘平滑反走样

边缘的平滑是通过颜色混合实现的，它把覆盖率当成混合的权重然后将边缘所处的当前像素与相邻像素进行混合，混合的数学表达式如下：

$Colo{r_{frgb}} = {C_{crgb}} \cdot (1coverage) + {C_{nrgb}} \bullet coverage$

(8)

式中：Color_frgb表示最终混合的颜色值，C_crgb表示当前像素的颜色值，C_nrgb代表相邻像素的颜色值。混合的效果如图 2所示。

2 算法实现

边缘优化的几何体信息反走样算法的具体实施步骤如下：

1) 设置显示分辨率的大小为m×n，这也是保存后台缓存纹理的大小。

2) 载入多边形模型数据，进行边缘检测提取，提取出的边缘顶点保存在顶点缓存中。

3) 渲染目标场景，并将后台缓存保存到纹理当中。

4) 对渲染好的场景进行延期光照处理，给场景添加光照。

5) 对顶点缓存中的顶点以画线的方式进行绘制，计算出采样方向及混合权重，最后以纹理滤波的方式对边缘像素进行混合平滑。

6) 渲染到屏幕，显示输出。

在5)中，边缘像素与相邻像素混合的操作是通过简单的纹理坐标偏移与纹理滤波实现的。 混合平滑操作的伪代码如下：

如果coverage > 0

{

偏移方向 off = (dis>= 0)? 1 : -1;

如果边缘为水平情况

offset. y = off;

否则为垂直情况

offset. x = off;

}

Sample(Filter,(Pos. xy + coverage * offset. xy) * PixelSize);

上面的伪代码中滤波的对象是先前保存好的纹理，偏移方向off为1主要是使纹理坐标朝下或朝右偏移，off为-1使纹理坐标朝上或朝左偏移。 偏移量取决于混合权重和像素的大小。coverage的取值范围应为0~0.5，若取值超过0. 5取1，当边缘穿过像素中心时，依据式(8)，会出现混合时只取边缘相邻像素的情况，不符合混合的要求。

3 实验结果 3.1 实验数据说明

算法验证在配置为Core 2.6GHz CPU，NVIDIA GeForce GT425显卡的计算机上进行，用微软公司的DirectX10软件开发包实现了基于几何体信息的反走样以及基于边缘优化的几何体信息反走样算法。实验采用立方体模型以及建模得到的某型号飞机的机翼、机轮盖和座舱盖模型，利用以上的模型数据分别测试了两种反走样算法的平滑处理效果和边缘检测时间。

3.2 反走样算法实验对比结果

在反走样算法实验部分，分别对实验数据，采用基于几何体信息的反走样方法和所提出的边缘优化的反走样方法进行处理。图 3~6分别给出了立方体、机翼、机轮盖和座舱盖模型对两种方法的实验结果。

从实验结果可以看出，边缘优化的反走样方法可以精准的检测出走样的边缘，适用的边缘角度范围广，无论边缘是处于水平，竖直或是其他的状态，都能很好的被检测出来，而且平滑的效果比较明显。

3.3 边缘检测时间对比结果

对四种不同的数据模型，分别给出两种反走样算法的边缘检测时间。

从表 1可知，基于边缘优化的几何体信息反走样的边缘提取用时相对较短，在场景复杂度提升时能有效的减少边缘提取用时，能满足实时性的要求。

4 结论

本文针对基于几何体信息的反走样方法边缘检测的时长问题，提出了一种边缘优化的几何体信息反走样算法:

1) 经实验验证，边缘优化的反走样算法能有效的检测出需要反走样的边缘，其边缘检测的时间效率相对于基于几何体信息的反走样方法有了大幅度提升且边缘平滑效果明显。

2) 在场景复杂度较高，尤其是多边形数量增多的情况下，能有效地减少边缘提取用时，提高显示的实时性。

3) 几何体信息的反走样方法依赖于线的光栅化，当多边形小到一定程度时会影响线框的渲染速度，因此边缘优化的反走样算法适用于对模型精细度要求不高的场景。