樊养余，胡斯强，郭 哲，张妍典，王 毅

（西北工业大学电子信息学院，陕西西安710072）

边缘优化的几何体信息反走样

樊养余，胡斯强，郭 哲，张妍典，王 毅

（西北工业大学电子信息学院，陕西西安710072）

基于几何体信息的反走样方法由于利用几何体的顶点信息进行边缘检测，会存在将内部边缘检测出来的情况，从而造成不必要的反走样，增加了资源消耗。针对这一问题，本文提出了一种基于边缘优化的几何体信息反走样算法。首先对几何体进行预处理，利用多边形法线信息与摄像机的位置关系检测出边缘；然后使用延期着色技术将场景渲染到纹理中，在屏幕空间根据边缘信息确定混合朝向及覆盖率；最后结合覆盖率与边缘相邻像素进行混合。实验结果表明：提出的算法在保留原几何体后处理式反走样方法效率的同时，有效减少了不必要的反走样，边缘检测时间相比基于几何体信息的反走样方法平均缩短了22．55％。在场景复杂度提升时能有效减少边缘提取时长，满足实时性的要求。

反走样；边缘检测；后处理；延期着色；覆盖率；像素混合；几何体预处理

图形的走样在很大程度上会影响图形的质量，进而影响人的辨别及视觉感受。因此，在图形领域反走样一直是研究的热点。反走样的基本原理是将图像边缘的像素点与其周围的像素按某种方式进行混合，以此来消除边缘的锯齿，它是以模糊边缘为代价的。在图形学中，反走样方法大致可以分为两种，分别是提高采样率［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，Ei为多边形的边Ei∈O，P1（Ei）和P2（Ei）表示公共边为Ei的两个多边形，Nj（Ei）代表Pj（Ei）的法线。多边形的可见性可由以下公式得出［12］

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

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

1．1．2 褶皱的检测

褶皱是指两个相邻面的公共边，根据两个面形成的二面角的大小，可以将其分为脊（Ridge line）或者谷（Valley line），两种类型的边都是独立于视点的［10］。褶皱的检测类似于轮廓边缘的检测，但其可以不用视点信息。若P1（Ei）和P2（Ei）是边Ei的两个相邻面，它们的法线分别是N1（Ei）和N2（Ei），则Ei为褶皱的条件是:

式中:N1（Ei），N2（Ei）都是归一化的法线，Threshold为阈值，它是二面角的余弦值，若边Ei的两个相邻面平行，则相邻面的法线也平行，此时Threshold可取0．99，由此可以判断边缘当中不是褶皱的边。

1．2 延迟光照渲染场景

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

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

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

1．3 几何体边缘反走样

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

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

图1 采样方向及覆盖率计算示意图Fig．1 Calculation of sampling direction and coverage

1．3．1 确定边缘朝向

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

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

式中:pos0和pos1都是裁剪空间的四维向量。

式中:二维向量p0为pos0在屏幕空间的坐标，它加上了一个偏移量bias，同理可求出pos1在屏幕空间的位置p1。

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

1．3．2 采样方向及覆盖率计算

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

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

1．3．3 边缘平滑反走样

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

式中:Colorfrgb表示最终混合的颜色值，Ccrgb表示当前像素的颜色值，Cnrgb代表相邻像素的颜色值。混合的效果如图2所示。

图2 颜色混合前后对比图Fig．2 Comparison map before and after color blending

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 立方体反走样效果对比Fig．3 The cube anti-aliasing effect comparison

图4 机轮盖反走样效果对比Fig．4 The wheel cover anti-aliasing effect comparison

图5 机翼反走样效果对比Fig．5 The wing anti-aliasing effect comparison

图6 座舱盖反走样效果对比Fig．6 The cockpit cover anti-aliasing effect comparison

3．3 边缘检测时间对比结果

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

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

表1 边缘检测时间对比结果Table 1 Edge detection time comparison results

4 结论

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

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

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

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

［1］马志强，王莉莉，张鑫维，等．基于图像空间的三维动态场景远程可视化方法［J］．计算机研究与发展，2014，51（11）:2559-2572．MA Zhiqiang，WANG Lili，ZHANG Xinwei，et al．Remote visualization for 3D dynamic scene based on image space［J］．Journal of computer research and development，2014，51（11）:2559-2572．

［2］IOURCHA K，YANG J C，POMIANOWKI A．A directionally adaptive edge anti-aliasing filter［C］／／Proceedings of the Conference on High Performance Graphics．New York，USA，2009:127-133．

［3］ENGEL W．GPU Pro3:Advanced rendering techniques［M］．3rd ed．Boca Raton:CRC Press，2011:71-76．

［4］RESHETOV A．Morphological antialiasing［C］／／Proceedings of the Conference on High Performance Graphics．New York，USA，2009:109-116．

［5］LOTTES T．Fast approximate anti-aliasing［EB／OL］．（2001-08-23）［2015-09-15］．http:／／developer．download．nvidia．com／assets／gamedev／files／sdk／11／FXAA_WhitePaper．pdf．

［6］CHAJDAS M G，MCGUIRE M，LUEBKE D．Subpixel reconstruction antialiasing for deferred shading［C］／／Proceeding of Symposium on Interactive 3D Graphics and Games．New York，USA，2011:15-22．

［7］GUERREIRO R F C，AGUIAR P M Q．Extraction of line segments in cluttered images via multiscale edges［C］／／Proceeding of the 20th IEEE International Conference on Image Processing．Melbourne，Australia，2013:3045-3048．

［8］朱晓临，陈嫚，李雪艳，等．结合形态学变形虫和复合颜色空间的彩色图像边缘检测模型［J］．计算机辅助设计与图形学学报，2014，26（7）:1060-1066．ZHU Xiaolin，CHEN Man，LI Xueyan，et al．A color image edge detection model with morphological amoebas and two kinds of color spaces［J］．Journal of computer-aided design＆computer graphics，2014，26（7）:1060-1066．

［9］YANG Linjie，LIU Jianzhuang，TANG Xiaoou．Complex 3D general object reconstruction from line drawings［C］／／Proceeding of the IEEE International Conference on Computer Vision．Sydney，Australia，2013:1433-1440．

［10］CHARI V，AGRAWAL A，TAGUCHI Y，et al．Convex bricks:a new primitive for visual hull modeling and reconstruction［C］／／Proceeding of the IEEE International Conference on Robotics and Automation．Minnesota，USA，2012:770-777．

［11］PETRESCU A L，MOLDOVEANU F，ASAVEI V，et al．Virtual deferred rendering［C］／／Proceeding of the 20th International Conference on Control Systems and Computer Science．Bucharest，Romania，2015:373-378．

［12］CHEN Xiaowu，JIN Xin，WU Hongyu，et al．Learning templates for artistic portrait lighting analysis［J］．IEEE transactions on image processing，2015，24（2）:608-618．

［13］HSIAO S F，LI Shangyu，TSAO K H．Low-power and highperformance design of OpenGL ES 2．0 graphics processing unit for mobile applications［C］／／Proceeding of IEEE International Conference on Digital Signal Processing．Singapore，2015:110-114．

Geometric information anti-aliasing algorithm with edge optimization

FAN Yangyu，HU Siqiang，GUO Zhe，ZHANG Yandian，WANG Yi
（School of Electronics and Information，Northwestern Polytechnical University，Xi′an 710072，China）

Geometric post-processing anti-aliasing uses geometric vertex information to detect edges．However，it may detect some internal edges that are needlessly anti-aliased，resulting in extra resource consumption．To solve this problem，this paper presents a geometric information anti-aliasing algorithm based on edge optimization．First，the geometry was preprocessed to detect the edges using polygon normals and the camera position．Second，the target scene was rendered to a texture using the deferred shading technology．Then，the blending direction and coverage on the screen were computed according to the detected edges．Finally，the edges were blended by combining the neighboring pixels with coverage．Experimental results show that the proposed algorithm can effectively eliminate unnecessary anti-aliasing edges while retaining the quality of the original geometry；the average edge detection time reduced by 22．55％compared with the original anti-aliasing method based on geometry information．When the scene complexity increases，this algorithm can effectively reduce the time for edge extraction and meet real-time requirements．

anti-aliasing；edge detection；post-processing；deferred shading；coverage；pixel blend；geometry preprocessing

10．11990／jheu．201510022

http：／／www．cnki．net／kcms／detail／23．1390．u．20160928．0936．030．html

TP391．9

A

1006-7043（2016）12-1734-05

樊养余，胡斯强，郭哲，等．边缘优化的几何体信息反走样［J］．哈尔滨工程大学学报，2016，37（12）:1734-1738．

2015-10-13．

2016-09-28．

国家自然科学基金项目（61402371，61461025）；陕西省自然科学基金项目（2013JQ8039，2015JM6317）；中央高校基本科研业务费专项资项目（3102014JCQ01060）．

樊养余（1960-），男，教授，博士生导师；

郭哲（1984-），女，讲师．

郭哲，E-mail:guozhe＠nwpu．edu．cn．

FAN Yangyu，HU Siqiang，GUO Zhe，et al．Geometric information anti-aliasing algorithm with edge optimization［J］．Journal of Harbin Engineering University，2016，37（12）:1734-1738．