樊養(yǎng)余，胡斯強，郭 哲，張妍典，王 毅

（西北工業(yè)大學(xué)電子信息學(xué)院，陜西西安710072）

邊緣優(yōu)化的幾何體信息反走樣

樊養(yǎng)余，胡斯強，郭 哲，張妍典，王 毅

（西北工業(yè)大學(xué)電子信息學(xué)院，陜西西安710072）

基于幾何體信息的反走樣方法由于利用幾何體的頂點信息進(jìn)行邊緣檢測，會存在將內(nèi)部邊緣檢測出來的情況，從而造成不必要的反走樣，增加了資源消耗。針對這一問題，本文提出了一種基于邊緣優(yōu)化的幾何體信息反走樣算法。首先對幾何體進(jìn)行預(yù)處理，利用多邊形法線信息與攝像機的位置關(guān)系檢測出邊緣；然后使用延期著色技術(shù)將場景渲染到紋理中，在屏幕空間根據(jù)邊緣信息確定混合朝向及覆蓋率；最后結(jié)合覆蓋率與邊緣相鄰像素進(jìn)行混合。實驗結(jié)果表明：提出的算法在保留原幾何體后處理式反走樣方法效率的同時，有效減少了不必要的反走樣，邊緣檢測時間相比基于幾何體信息的反走樣方法平均縮短了22．55％。在場景復(fù)雜度提升時能有效減少邊緣提取時長，滿足實時性的要求。

反走樣；邊緣檢測；后處理；延期著色；覆蓋率；像素混合；幾何體預(yù)處理

圖形的走樣在很大程度上會影響圖形的質(zhì)量，進(jìn)而影響人的辨別及視覺感受。因此，在圖形領(lǐng)域反走樣一直是研究的熱點。反走樣的基本原理是將圖像邊緣的像素點與其周圍的像素按某種方式進(jìn)行混合，以此來消除邊緣的鋸齒，它是以模糊邊緣為代價的。在圖形學(xué)中，反走樣方法大致可以分為兩種，分別是提高采樣率［2］和基于屏幕空間的后處理式方法［3］。提高采樣率的方法通過增加采樣點數(shù)來實現(xiàn)反走樣，增加的采樣點數(shù)越多，反走樣的效果越好。目前，顯卡提供的硬件反走樣，例如多重采樣反走樣（multi-sampling anti-aliasing，MSAA）就屬于這種方法，它實現(xiàn)起來比較容易，可以有效解決圖像走樣的問題，但是這種方式對硬件的要求比較高，消耗的資源多。后處理式方法的基本思路是先正常的將目標(biāo)場景渲染到紋理當(dāng)中，然后對紋理進(jìn)行邊緣檢測采集出圖像的邊緣，最后對邊緣像素做一定的平滑處理，以此來減少邊緣像素的鋸齒現(xiàn)象。

因后處理式反走樣方式的優(yōu)勢，近年出現(xiàn)了許多類似的方法，在2009年，Reshetov提出了基于形態(tài)學(xué)的反走樣方法［4］，這種方法不受場景復(fù)雜度的限制，處理速度快，可用來取代硬件反走樣。FXAA［5］（fast approximate anti-aliasing）是Lottes在2001年提出的，該算法快速、高效，但會將紋理高光部分檢測為邊緣，適用范圍有限。McGuire和Luebke提出的sub-pixel reconstruction anti-aliasing［6］方法將單個像素著色與亞像素可見性結(jié)合以創(chuàng)建反走樣圖像，其反走樣效果接近超采樣反走樣方法。GPAA［3］（geometric postprocess anti-aliasing）由Persson在2011年提出，該方法利用渲染引擎提供的幾何體信息進(jìn)行反走樣，邊緣平滑效果好，是反走樣方法中邊緣平滑最精確的方法。然而，該方法存在一個較大的缺點，一些內(nèi)部邊緣被視為邊緣處理，增加了額外的邊緣存儲消耗，不利于場景的擴(kuò)展。針對這一問題，通過利用面法線與虛擬攝像機的位置關(guān)系找出背向視點的不可見邊緣，從而對邊緣檢測的過程進(jìn)行改進(jìn)。在場景復(fù)雜度提高且硬件條件有限的情況下，有利于縮短邊緣提取用時，平滑邊緣鋸齒并提高顯示實時性。

1 基于幾何體信息的反走樣

針對幾何體信息的反走樣算法的缺點，提出的基于邊緣優(yōu)化的幾何體信息反走樣算法能很較好的解決這一問題，該算法的主要思路是:假設(shè)場景中存在走樣的現(xiàn)象，首先對幾何體模型進(jìn)行處理，檢測出其走樣的邊緣。在此過程中，利用多邊形法線與視點的位置信息判斷出多邊形的可見性進(jìn)而判斷出邊緣是否需要進(jìn)行反走樣處理，將需要反走樣處理的邊緣頂點保存在頂點緩存中。然后結(jié)合延遲光照算法對目標(biāo)場景進(jìn)行光照處理并將后臺緩存保存在紋理當(dāng)中。最后將檢測到的邊緣以畫線的形式繪制出來，每一個渲染出的邊緣像素點都會與之前保存的紋理中相應(yīng)的像素點混合。

1．1 邊緣優(yōu)化

邊緣優(yōu)化的邊緣檢測過程是基于物體空間［7］，即利用三維模型的幾何信息獲取物體的輪廓線，主要包含兩類邊緣的檢測，一個是物體與背景分離的輪廓邊緣，另一個是相鄰多邊形形成的公共邊，即褶皺［8］。

1．1．1 輪廓邊緣的檢測

輪廓邊緣是物體表面的前向面與后向面的分界線，它是與視點相關(guān)的［9］。輪廓檢測最直接的方法是遍歷物體的所有邊，然后依據(jù)物體面法線計算出邊緣。假設(shè)多邊形模型為O，視線方向為V，Ei為多邊形的邊Ei∈O，P1（Ei）和P2（Ei）表示公共邊為Ei的兩個多邊形，Nj（Ei）代表Pj（Ei）的法線。多邊形的可見性可由以下公式得出［12］

式（1）表示多邊形的法線與視線反向，多邊形朝向視點，它是可見的；式（2）表示多邊形背向視點，它是不可見的。借助以上兩個多邊形可見性判別公式可以導(dǎo)出輪廓邊緣的一般公式:

式中:N1，N2是邊Ei相鄰兩個多邊形的法線，通過遍歷Ei（i=1，2，…，n），可以查找出物體的輪廓邊緣。此外，還可根據(jù)不可見邊緣的相鄰兩個多邊形都背向視點來判斷它的可見性。

1．1．2 褶皺的檢測

褶皺是指兩個相鄰面的公共邊，根據(jù)兩個面形成的二面角的大小，可以將其分為脊（Ridge line）或者谷（Valley line），兩種類型的邊都是獨立于視點的［10］。褶皺的檢測類似于輪廓邊緣的檢測，但其可以不用視點信息。若P1（Ei）和P2（Ei）是邊Ei的兩個相鄰面，它們的法線分別是N1（Ei）和N2（Ei），則Ei為褶皺的條件是:

式中:N1（Ei），N2（Ei）都是歸一化的法線，Threshold為閾值，它是二面角的余弦值，若邊Ei的兩個相鄰面平行，則相鄰面的法線也平行，此時Threshold可取0．99，由此可以判斷邊緣當(dāng)中不是褶皺的邊。

1．2 延遲光照渲染場景

延遲著色［11］是利用幾何體緩存器（G-Buffer）實現(xiàn)的高級圖形學(xué)技術(shù)，它可以用來實現(xiàn)多光源的延期光照計算。延期光照［12］借助G-Buffer將傳統(tǒng)的光照計算轉(zhuǎn)移到了光柵化階段之后，G-Buffer只保存屏幕空間每個像素的法線、深度值、顏色值等等，利用它作為后續(xù)處理的輸入，從而不再需要原先幾何體的信息，在很大程度上減少了光照計算的復(fù)雜度。

延期光照計算大致可以分為兩個階段:幾何階段和光照處理階段［12］。幾何階段需要對場景中的幾何數(shù)據(jù)進(jìn)行處理，主要是坐標(biāo)變換，還需要將頂點位置信息、法線及紋理坐標(biāo)等填充到G-Buffer中，為后續(xù)光照計算做好準(zhǔn)備。

光照處理階段利用幾何階段保存在G-Buffer中的法線、位置、漫反射信息以及光源的位置信息作為輸入，在片段著色器中實現(xiàn)Phong光照模型的計算，最后輸出像素的顏色值。

1．3 幾何體邊緣反走樣

在進(jìn)行反走樣之前，先要按照渲染的一般流程對目標(biāo)場景進(jìn)行渲染，并將渲染好的后臺緩存保存在一個紋理當(dāng)中，以便后期的混合平滑操作。反走樣的過程如圖1。

圖中較寬的深色斜線是幾何體的邊緣，淺灰色和深灰色的部分代表兩個圖元，黑色的箭頭表示混合的方向及要混合的像素點，方塊中的圓圈代表像素中心，黑色虛線是用來表明像素在邊緣直線上的值，后面可以用來計算覆蓋率coverage。

圖1 采樣方向及覆蓋率計算示意圖Fig．1 Calculation of sampling direction and coverage

1．3．1 確定邊緣朝向

在平滑邊緣之前首先要確定邊緣在屏幕空間的主要方向，判斷邊緣這條線是大致水平或是垂直。例如，圖1中的邊緣可認(rèn)為是大致水平的，此時應(yīng)該混合其上面或者下面的相鄰像素點?；旌系姆较蛉Q于邊緣在像素中心的哪一側(cè)。對于邊緣在像素中心上的點應(yīng)該向上采樣，否則向下采樣。另外，對于垂直的邊緣，其混合左邊或者右邊相鄰的像素點。

假設(shè)需反走樣的邊緣為Ei（Ei∈O），邊的兩個頂點分別為三維向量，記做:position0和position1。在處理邊緣的頂點著色器中利用式（5）先將物理空間的頂點乘以裁剪矩陣Viewproj轉(zhuǎn)換至裁剪空間，然后再轉(zhuǎn)換至以像素為單位的屏幕空間中。因硬件對于直線和多邊形的光柵化方式并不完全相同，導(dǎo)致對于位于兩個相同頂點之間的直線和多邊形邊，其像素的深度值并不相同，在顯示時會產(chǎn)生閃爍的感覺［13］。為了避免這種問題，可以在屏幕空間對邊緣做一定的偏移:

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

式中:二維向量p0為pos0在屏幕空間的坐標(biāo)，它加上了一個偏移量bias，同理可求出pos1在屏幕空間的位置p1。

邊緣直線在屏幕空間的向量dir=p1-p0，通過二維向量dir可判斷邊緣是大致水平或是垂直。在屏幕空間，如果邊緣兩個頂點投影至水平方向的距離大于投影至垂直方向的距離，則邊緣為大致水平的，否則為垂直的。即｜dir．x｜＞｜dir．y｜時，邊緣為水平，否則為垂直。

1．3．2 采樣方向及覆蓋率計算

在確定好邊緣的朝向之后，可以用直線的數(shù)學(xué)公式表示邊緣，水平情況用y=kx+b表示，垂直情況下用x=ky+bx表示，k為直線的斜率。現(xiàn)考慮水平情形，在片段著色器利用直線公式可以求出像素點到直線的垂直距離（即圖1中像素中心到虛線的距離）dis=k·xp+b-yp，xp和yp為屏幕空間的像素坐標(biāo)。dis≥0時，像素點在直線上方，采樣方向朝下，否則像素點在直線下方，采樣方向朝上。垂直邊緣的情況類似，只是采樣方向變?yōu)槌蠡蛘叱摇Ｆ沃髦?，覆蓋率coverage依據(jù)像素到該邊緣的距離來計算，其公式為

coverage作為邊緣像素點與相鄰像素點的混合權(quán)重。如果邊緣穿過像素中心，則dis=0且coverage= 0．5，意味著邊緣所處像素與其相鄰像素應(yīng)均勻混合；若邊緣處于像素的邊界，則dis=0且coverage= 0．5，表明相鄰像素不參與最后的反走樣混合。

1．3．3 邊緣平滑反走樣

邊緣的平滑是通過顏色混合實現(xiàn)的，它把覆蓋率當(dāng)成混合的權(quán)重然后將邊緣所處的當(dāng)前像素與相鄰像素進(jìn)行混合，混合的數(shù)學(xué)表達(dá)式如下:

式中:Colorfrgb表示最終混合的顏色值，Ccrgb表示當(dāng)前像素的顏色值，Cnrgb代表相鄰像素的顏色值?；旌系男Ч鐖D2所示。

圖2 顏色混合前后對比圖Fig．2 Comparison map before and after color blending

2 算法實現(xiàn)

邊緣優(yōu)化的幾何體信息反走樣算法的具體實施步驟如下:

1）設(shè)置顯示分辨率的大小為m×n，這也是保存后臺緩存紋理的大小。

2）載入多邊形模型數(shù)據(jù)，進(jìn)行邊緣檢測提取，提取出的邊緣頂點保存在頂點緩存中。

3）渲染目標(biāo)場景，并將后臺緩存保存到紋理當(dāng)中。

4）對渲染好的場景進(jìn)行延期光照處理，給場景添加光照。

5）對頂點緩存中的頂點以畫線的方式進(jìn)行繪制，計算出采樣方向及混合權(quán)重，最后以紋理濾波的方式對邊緣像素進(jìn)行混合平滑。

6）渲染到屏幕，顯示輸出。

在5）中，邊緣像素與相鄰像素混合的操作是通過簡單的紋理坐標(biāo)偏移與紋理濾波實現(xiàn)的?；旌掀交僮鞯膫未a如下:

如果coverage＞0

｛

偏移方向off=（dis＞=0）？1:-1；

如果邊緣為水平情況

offset．y=off；

否則為垂直情況

offset．x=off；

｝

Sample（Filter，（Pos．xy+coverage?offset．xy）?

PixelSize）；

上面的偽代碼中濾波的對象是先前保存好的紋理，偏移方向off為1主要是使紋理坐標(biāo)朝下或朝右偏移，off為-1使紋理坐標(biāo)朝上或朝左偏移。偏移量取決于混合權(quán)重和像素的大小。coverage的取值范圍應(yīng)為0～0．5，若取值超過0．5取1，當(dāng)邊緣穿過像素中心時，依據(jù)式（8），會出現(xiàn)混合時只取邊緣相鄰像素的情況，不符合混合的要求。

3 實驗結(jié)果

3．1 實驗數(shù)據(jù)說明

算法驗證在配置為Core 2．6GHz CPU，NVIDIA GeForce GT425顯卡的計算機上進(jìn)行，用微軟公司的DirectX10軟件開發(fā)包實現(xiàn)了基于幾何體信息的反走樣以及基于邊緣優(yōu)化的幾何體信息反走樣算法。實驗采用立方體模型以及建模得到的某型號飛機的機翼、機輪蓋和座艙蓋模型，利用以上的模型數(shù)據(jù)分別測試了兩種反走樣算法的平滑處理效果和邊緣檢測時間。

3．2 反走樣算法實驗對比結(jié)果

在反走樣算法實驗部分，分別對實驗數(shù)據(jù)，采用基于幾何體信息的反走樣方法和所提出的邊緣優(yōu)化的反走樣方法進(jìn)行處理。圖3～6分別給出了立方體、機翼、機輪蓋和座艙蓋模型對兩種方法的實驗結(jié)果。

從實驗結(jié)果可以看出，邊緣優(yōu)化的反走樣方法可以精準(zhǔn)的檢測出走樣的邊緣，適用的邊緣角度范圍廣，無論邊緣是處于水平，豎直或是其他的狀態(tài)，都能很好的被檢測出來，而且平滑的效果比較明顯。

圖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 邊緣檢測時間對比結(jié)果

對四種不同的數(shù)據(jù)模型，分別給出兩種反走樣算法的邊緣檢測時間。

從表1可知，基于邊緣優(yōu)化的幾何體信息反走樣的邊緣提取用時相對較短，在場景復(fù)雜度提升時能有效的減少邊緣提取用時，能滿足實時性的要求。

表1 邊緣檢測時間對比結(jié)果Table 1 Edge detection time comparison results

4 結(jié)論

本文針對基于幾何體信息的反走樣方法邊緣檢測的時長問題，提出了一種邊緣優(yōu)化的幾何體信息反走樣算法:

1）經(jīng)實驗驗證，邊緣優(yōu)化的反走樣算法能有效的檢測出需要反走樣的邊緣，其邊緣檢測的時間效率相對于基于幾何體信息的反走樣方法有了大幅度提升且邊緣平滑效果明顯。

2）在場景復(fù)雜度較高，尤其是多邊形數(shù)量增多的情況下，能有效地減少邊緣提取用時，提高顯示的實時性。

3）幾何體信息的反走樣方法依賴于線的光柵化，當(dāng)多邊形小到一定程度時會影響線框的渲染速度，因此邊緣優(yōu)化的反走樣算法適用于對模型精細(xì)度要求不高的場景。

［1］馬志強，王莉莉，張鑫維，等．基于圖像空間的三維動態(tài)場景遠(yuǎn)程可視化方法［J］．計算機研究與發(fā)展，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］朱曉臨，陳嫚，李雪艷，等．結(jié)合形態(tài)學(xué)變形蟲和復(fù)合顏色空間的彩色圖像邊緣檢測模型［J］．計算機輔助設(shè)計與圖形學(xué)學(xué)報，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

樊養(yǎng)余，胡斯強，郭哲，等．邊緣優(yōu)化的幾何體信息反走樣［J］．哈爾濱工程大學(xué)學(xué)報，2016，37（12）:1734-1738．

2015-10-13．

2016-09-28．

國家自然科學(xué)基金項目（61402371，61461025）；陜西省自然科學(xué)基金項目（2013JQ8039，2015JM6317）；中央高?；究蒲袠I(yè)務(wù)費專項資項目（3102014JCQ01060）．

樊養(yǎng)余（1960-），男，教授，博士生導(dǎo)師；

郭哲（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．