吳玉培，王斌

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都　610065）

基于GPU的實(shí)時(shí)抗鋸齒算法

吳玉培，王斌

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

0　引言

隨著3D技術(shù)的不斷發(fā)展，抗鋸齒技術(shù)已經(jīng)廣泛應(yīng)用于虛擬現(xiàn)實(shí)、3D電影、3D游戲、飛行模擬以及其他場(chǎng)景渲染中。目前的抗鋸齒技術(shù)主要分為兩個(gè)方向：基于硬件的混合權(quán)重顏色采樣和基于顏色或距離差異的像素邊界采樣?；谟布夹g(shù)的增加分辨率和采樣頻率的算法，開(kāi)銷(xiāo)代價(jià)不僅很大，并且?guī)l率低.基于距離差異的像素邊界算法，還存在對(duì)于因不同材質(zhì)引起差異的像素邊界無(wú)法區(qū)分，導(dǎo)致某些邊界缺失，繼而出現(xiàn)失真的問(wèn)題。由于以往的基于像素顏色差異的圖像邊界算法，基本上都是采用“前處理”的思想，所以非常依賴(lài)于渲染管道。本文提出了一種基于GPU的抗鋸齒算法，完全運(yùn)行于GPU，可以高效地整合在實(shí)時(shí)圖形渲染管線內(nèi)，提升實(shí)時(shí)渲染的圖形質(zhì)量。

1　相關(guān)工作

近年來(lái)隨著GPU計(jì)算能力和存儲(chǔ)能力的提升，于是開(kāi)始探索利用GUP的可編程性來(lái)進(jìn)行圖像的抗鋸齒算法。由于圖像內(nèi)部邊緣像素之間的顏色不連續(xù)變化導(dǎo)致了絕大部分鋸齒現(xiàn)象，因此為了能夠設(shè)計(jì)出一種基于GPU的可以和延遲渲染算法共同工作的抗鋸齒算法，Shishkovtsov[1]計(jì)了一種以圖像內(nèi)邊緣檢測(cè)操作為核心的局部混合抗鋸齒算法。Keller提出了一種基于比較相關(guān)距離的抗鋸齒技術(shù)[2]，主要原理是按照預(yù)定義的距離相關(guān)性規(guī)則采樣像素，根據(jù)權(quán)重進(jìn)行像素顏色值混合，計(jì)算當(dāng)前像素新的顏色值，渲染場(chǎng)景。Malan[3]提出一種基于物體的幾何描述進(jìn)行抗鋸齒操作的算法，此算法消耗內(nèi)存，并且計(jì)算量大，該算法適用于高端的GPU，無(wú)法在中低端GPU以及游戲機(jī)平臺(tái)上應(yīng)用。

2　算法概述

本算法是基于GPU實(shí)現(xiàn)的實(shí)時(shí)抗鋸齒算法，算法的主要思想有三個(gè)步驟：

（1）搜索圖像內(nèi)像素間的不連續(xù)性

（2）尋找預(yù)先定義的幾何模式

（3）在預(yù)先定義幾何模式的鄰域像素計(jì)混合顏色權(quán)重，然后利用權(quán)重計(jì)算最終顏色

圖1（a）是一個(gè)7×7的黑白圖像，為了方便描述算法，縱坐標(biāo)用數(shù)字表示，橫坐標(biāo)用字母表示定義一個(gè)像素的相應(yīng)的邊，字母1、r、t和b分別代表了左、右、上和下四個(gè)方向，例如像素a7的右側(cè)邊用a7r表示，依此類(lèi)推。圖中定義了三種幾何模式：L（綠色），Z（紅色），U（黃色）這三種幾何模式。例如{a3t，b3t，b3r}就屬于L形模式.圖1（a）中像素c3和像素c4會(huì)出現(xiàn)鋸齒，為了消除鋸齒，需要重新計(jì)算像素c3的顏色。

圖1　計(jì)算混合權(quán)重

使用本算法處理圖1（a），依次執(zhí)行三個(gè)步驟：

第一步，遍歷圖像的所有的像素，判斷目標(biāo)像素與所有的相鄰像素的特征數(shù)值的差異，當(dāng)數(shù)值差異超過(guò)了一定的閾值以后，即認(rèn)為圖像在該像素處發(fā)生不連續(xù)性，該像素被一條輪廓邊覆蓋，成為邊界像素.假設(shè)c3像素為目標(biāo)像素，向左端搜索找到像素b3，向右端搜索找到像素e4，這樣就構(gòu)成邊界線{c3b，d3b，e3b}是連續(xù)的，稱(chēng)為主要邊，像素c3被圖中的藍(lán)色線所覆蓋。

第二步，在連續(xù)邊界線兩段尋找與它正交方向上的像素邊，然后判斷連續(xù)邊與正交邊，構(gòu)成的邊界輪廓屬于哪種預(yù)定義的模式.對(duì)于連續(xù)邊界線{c3b，d3b，e3b在向兩段尋找正交的邊時(shí)，找到與其正交的兩條邊b3r 和e4r，稱(chēng)為次要邊，就可以判斷邊界輪廓{b3r，c3b，d3b，e3b，e4r}屬于Z（紅色）形模式。

第三步，計(jì)算模式周?chē)袼氐幕旌蠙?quán)重，然后計(jì)算目標(biāo)像素的顏色。圖1（b）是圖1（a）中的一部分，假設(shè)目標(biāo)像素為c3，經(jīng)過(guò)前兩步，邊AB，BG和GC構(gòu)成Z形模式，為了計(jì)算分割邊（DF）覆蓋像素的混合權(quán)重，連接AB邊中點(diǎn)D和GC邊的中點(diǎn)F，像素c3，d3被邊DF分割成梯形。計(jì)算三角形DBE內(nèi)的梯形面積，把這個(gè)面積作為混合權(quán)重，來(lái)計(jì)算對(duì)應(yīng)像素的新顏色，見(jiàn)公式（1）。

Cnew是像素的新顏色值，Cold是原像素的顏色值，Coppsite是分割線另外一側(cè)像素的顏色，a是位于主要邊上梯形的面積，即計(jì)算顏色的混合權(quán)重。黑色顏色值為0，白色顏色值為1。圖1（c）是經(jīng)過(guò)算法三步處理之后的圖像。

3　算法實(shí)現(xiàn)

通常情況為了尋找圖像中像素之間的不連續(xù)性，可以利用相鄰像素間的顏色差異.對(duì)于顏色信息，一般采用RGB格式，在本算法中，將顏色數(shù)值通過(guò)CIEXYZ[4]格式轉(zhuǎn)化為亮度值，見(jiàn)公式（2），利用相鄰像素間的亮度差異來(lái)判讀連續(xù)性。

對(duì)于判斷像素之間差異是否滿(mǎn)足邊界像素差異的閾值，用公式（3-1）計(jì)算相應(yīng)的亮度值標(biāo)記為L(zhǎng)l，Lr，Lt，Lb。目標(biāo)像素的亮度值標(biāo)記為L(zhǎng)，然后根據(jù)公式（3）依次與四個(gè)相鄰亮度值比較。

Lx表示相鄰像素的亮度值，e是布爾變量，e為1表示和相鄰像素不連續(xù)，否則與相鄰像素連續(xù).這樣對(duì)每個(gè)像素比較，就可以得到四個(gè)布爾值，用一張紋理EdgeInfoTex保存每個(gè)像素的比較結(jié)果。

在計(jì)算出場(chǎng)景所有邊緣像素的混合權(quán)重，并存在紋理BlendWeightTex，該紋理對(duì)應(yīng)位置的每一個(gè)像素相對(duì)于它的左右上下相鄰像素的混合權(quán)重。在算法的最后一步，使用這張包含了混合權(quán)重信息的紋理來(lái)獲取最終的顏色。計(jì)算最終顏色見(jiàn)公式（4）：

Cfinal是最終的顏色值，Wl是目標(biāo)像素左鄰像素的混合權(quán)值，Cl是目標(biāo)像素左鄰像素的原始顏色值，Wr是目標(biāo)像素右鄰像素的混合權(quán)值，Cr是目標(biāo)像素右鄰像素的原始顏色值，Wt是目標(biāo)像素上鄰像素的混合權(quán)值，Ct是目標(biāo)像素上鄰像素的原始顏色值，Wb是目標(biāo)像素下鄰像素的混合權(quán)值，Cb是目標(biāo)像素下鄰像素的原始顏色值?；旌蠙?quán)重只需要在紋理BlendWiehtTex查找即可。

4　結(jié)果分析

4.1實(shí)驗(yàn)平臺(tái)

處理器：Intel Pentium 2 CPU G620@2.60GHz雙核；內(nèi)存：4.0GB；顯卡：NVIDIA GeForce GT 440；顯示器分辨率：1440×900；操作系統(tǒng)：Windows 7（32位）。

4.2實(shí)驗(yàn)結(jié)果

本文提出的基于GPU的實(shí)時(shí)抗鋸齒算法，在實(shí)時(shí)性和抗鋸齒效果上都取得良好的效果。下表1測(cè)試本算法在不同分辨率下每秒的幀頻率，與NVIDIA自帶的FXAA[5-6]在采樣為2X下進(jìn)行對(duì)比。

表1　分辨率和幀頻率對(duì)比表

表1可以看出，本算法的幀率，滿(mǎn)足場(chǎng)景實(shí)時(shí)渲染需求。表中測(cè)的幀率，不僅與分辨率有關(guān)，也與渲染場(chǎng)景的復(fù)雜度有關(guān)。

為了驗(yàn)證本算法的實(shí)際效果，選取了多個(gè)場(chǎng)景進(jìn)行驗(yàn)證，分別測(cè)試了不使用抗鋸齒算法、FXAA算法和本算法時(shí)場(chǎng)景的繪制圖像的質(zhì)量，如圖2所示.圖2（a）是沒(méi)有經(jīng)過(guò)抗。

鋸齒算法處理的原圖，圖2（b）分別是圖2（a）經(jīng)過(guò)FXAA算法處理之后的圖，圖2（c）分別是圖2（a）經(jīng)過(guò)本算法處理之后的圖。圖2（c）和圖2（b）對(duì)比可以得出，本算對(duì)鋸齒的處理效果非常明顯，平滑也很顯著，特別是對(duì)圖2（b）右邊圖中線和木板邊緣的處理，幾乎沒(méi)有鋸齒。對(duì)比本算法抗鋸齒處理后的圖2（c）效果與FXAA處理的圖2（b）效果，左圖處理效果沒(méi)有差別，但是中間和右邊圖的對(duì)比可以發(fā)現(xiàn)，本算法對(duì)鋸齒邊緣處理更平滑。

圖2　原始圖、FXAA和本算法效果對(duì)比

5　結(jié)語(yǔ)

本文提出了一種基于GPU的實(shí)時(shí)抗鋸齒算法，算法檢測(cè)圖像中不連續(xù)變化的邊緣像素，識(shí)別出邊緣像素所在的分割邊的形狀，屬于哪種預(yù)定義的幾何模式。然后利用分割邊的相關(guān)信息來(lái)檢索匹配預(yù)先計(jì)算好的像素混合權(quán)重信息，再計(jì)算最終顏色，使得在這些邊緣區(qū)域的像素可以有更為平滑的過(guò)度。本算法屬于后處理算法，獨(dú)立于渲染管線，完全運(yùn)行于GPU，可以高效地整合在實(shí)時(shí)渲染管線內(nèi)，提升實(shí)時(shí)渲染的速度和圖形的質(zhì)量。

[1]Shishkovtsov O.Deferred shading in STALKER GPU Gems2[C]，2005：143-545.

[2]Iourchak，Yangjc，Pomianowskia.A Directionally Adaptive Edge Anti-Aliasing Filter[J].In High Performance Graphics 2009，ACM，New York，USA，2009：127-133.

[3]J.Jimenez，D.Gutierrez，J.Yang，A.Reshetov，P.Demoreuille，T.Berghoff，C.Perthuis，H.Yu，M.McGuire，T.Lottes，H.Malan，E.Persson，D.Andreev，T.Sousa.Filtering Approaches for Real-Time Anti-Aliasing[C].ACM SIGGRAPH Courses，2011.

[4]T.Smith，J.Guild，The CIE Colorimetric Standards and their Use[J].Transactions of the Optical Society，1931，33（3）：73-134.

[5]Atwood，Jeff.Fast Approximate Anti-Aliasing.Coding Horror.Retrieved September 30，2012.

[6]Wang，James.FXAA:Anti-Aliasing at Warp Speed.NVIDIA.Retrieved January 3，2013.

Anti-Aliasing;GPU;Geometric Morphology;Parallel Processing;3D Scene Model

Real-Time Anti-Aliasing Algorithm Based on GPU

WU Yu-pei，WANG Bin
（College of Computer Science，Sichuan University，Chengdu 610065）

1007-1423（2016）03-0054-04

10.3969/j.issn.1007-1423.2016.03.013

吳玉培（1990-），男，河南鄧州人，碩士研究生，研究方向?yàn)橛?jì)算機(jī)圖形圖像處理、計(jì)算機(jī)圖形學(xué)、虛擬現(xiàn)實(shí)

2015-12-01

2016-01-10

隨著現(xiàn)代計(jì)算機(jī)圖形圖像技術(shù)的發(fā)展，目前的抗鋸齒技術(shù)存在幀頻率低、消耗內(nèi)存大、對(duì)硬件要求高、算法不穩(wěn)定、圖像失真等問(wèn)題.針對(duì)以上問(wèn)題，提出基于GPU的實(shí)時(shí)抗鋸齒算法，是根據(jù)幾何形態(tài)學(xué)圖像分析方法來(lái)區(qū)分像素邊界，然后計(jì)算像素顏色的混合權(quán)重，最后對(duì)模型進(jìn)行渲染，不僅可以用于前處理，而且可以用于后處理，完全獨(dú)立于渲染管線，可以有效地解決多物體復(fù)雜三維場(chǎng)景下的鋸齒失真問(wèn)題，而且不會(huì)對(duì)系統(tǒng)造成太大的負(fù)擔(dān)，是一種既快速又健壯的抗鋸齒算法。

抗鋸齒；GPU；幾何形態(tài)學(xué)；并行處理；三維場(chǎng)景

王斌（1989-），男，湖北襄陽(yáng)人，碩士研究生，CCF會(huì)員，研究方向?yàn)橛?jì)算機(jī)圖形圖像處理、計(jì)算機(jī)圖形學(xué)、虛擬現(xiàn)實(shí)

Along with the development of modern computer graphics technology,the existing anti-aliasing technology suffers with many problems, such as low frame frequency,consuming large memory,high requirements for hardware,unstable algorithm and distortion of the image.In order to solve these problems,proposes a new real-time anti-aliasing technology based on GPU.It distinguishes pixel boundary depending on the geometric morphology image analysis,then calculates blending weight,finally renders the model.It is not only suitable for preprocessing but post-processing,and completely independent of rendering pipeline.It can effectively solve the distortion under the complex 3D scene model and cost less resources of the system.It is a fast and robust anti-aliasing algorithm.