基于GPU的實時抗鋸齒算法

吳玉培，王斌

（四川大學計算機學院，成都　610065）

基于GPU的實時抗鋸齒算法

吳玉培，王斌

（四川大學計算機學院，成都610065）

0　引言

隨著3D技術的不斷發展，抗鋸齒技術已經廣泛應用于虛擬現實、3D電影、3D游戲、飛行模擬以及其他場景渲染中。目前的抗鋸齒技術主要分為兩個方向：基于硬件的混合權重顏色采樣和基于顏色或距離差異的像素邊界采樣。基于硬件技術的增加分辨率和采樣頻率的算法，開銷代價不僅很大，并且幀頻率低.基于距離差異的像素邊界算法，還存在對于因不同材質引起差異的像素邊界無法區分，導致某些邊界缺失，繼而出現失真的問題。由于以往的基于像素顏色差異的圖像邊界算法，基本上都是采用“前處理”的思想，所以非常依賴于渲染管道。本文提出了一種基于GPU的抗鋸齒算法，完全運行于GPU，可以高效地整合在實時圖形渲染管線內，提升實時渲染的圖形質量。

1　相關工作

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

2　算法概述

本算法是基于GPU實現的實時抗鋸齒算法，算法的主要思想有三個步驟：

（1）搜索圖像內像素間的不連續性

（2）尋找預先定義的幾何模式

（3）在預先定義幾何模式的鄰域像素計混合顏色權重，然后利用權重計算最終顏色

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

圖1　計算混合權重

使用本算法處理圖1（a），依次執行三個步驟：

第一步，遍歷圖像的所有的像素，判斷目標像素與所有的相鄰像素的特征數值的差異，當數值差異超過了一定的閾值以后，即認為圖像在該像素處發生不連續性，該像素被一條輪廓邊覆蓋，成為邊界像素.假設c3像素為目標像素，向左端搜索找到像素b3，向右端搜索找到像素e4，這樣就構成邊界線{c3b，d3b，e3b}是連續的，稱為主要邊，像素c3被圖中的藍色線所覆蓋。

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

第三步，計算模式周圍像素的混合權重，然后計算目標像素的顏色。圖1（b）是圖1（a）中的一部分，假設目標像素為c3，經過前兩步，邊AB，BG和GC構成Z形模式，為了計算分割邊（DF）覆蓋像素的混合權重，連接AB邊中點D和GC邊的中點F，像素c3，d3被邊DF分割成梯形。計算三角形DBE內的梯形面積，把這個面積作為混合權重，來計算對應像素的新顏色，見公式（1）。

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

3　算法實現

通常情況為了尋找圖像中像素之間的不連續性，可以利用相鄰像素間的顏色差異.對于顏色信息，一般采用RGB格式，在本算法中，將顏色數值通過CIEXYZ[4]格式轉化為亮度值，見公式（2），利用相鄰像素間的亮度差異來判讀連續性。

對于判斷像素之間差異是否滿足邊界像素差異的閾值，用公式（3-1）計算相應的亮度值標記為Ll，Lr，Lt，Lb。目標像素的亮度值標記為L，然后根據公式（3）依次與四個相鄰亮度值比較。

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

在計算出場景所有邊緣像素的混合權重，并存在紋理BlendWeightTex，該紋理對應位置的每一個像素相對于它的左右上下相鄰像素的混合權重。在算法的最后一步，使用這張包含了混合權重信息的紋理來獲取最終的顏色。計算最終顏色見公式（4）：

Cfinal是最終的顏色值，Wl是目標像素左鄰像素的混合權值，Cl是目標像素左鄰像素的原始顏色值，Wr是目標像素右鄰像素的混合權值，Cr是目標像素右鄰像素的原始顏色值，Wt是目標像素上鄰像素的混合權值，Ct是目標像素上鄰像素的原始顏色值，Wb是目標像素下鄰像素的混合權值，Cb是目標像素下鄰像素的原始顏色值。混合權重只需要在紋理BlendWiehtTex查找即可。

4　結果分析

4.1實驗平臺

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

4.2實驗結果

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

表1　分辨率和幀頻率對比表

表1可以看出，本算法的幀率，滿足場景實時渲染需求。表中測的幀率，不僅與分辨率有關，也與渲染場景的復雜度有關。

為了驗證本算法的實際效果，選取了多個場景進行驗證，分別測試了不使用抗鋸齒算法、FXAA算法和本算法時場景的繪制圖像的質量，如圖2所示.圖2（a）是沒有經過抗。

鋸齒算法處理的原圖，圖2（b）分別是圖2（a）經過FXAA算法處理之后的圖，圖2（c）分別是圖2（a）經過本算法處理之后的圖。圖2（c）和圖2（b）對比可以得出，本算對鋸齒的處理效果非常明顯，平滑也很顯著，特別是對圖2（b）右邊圖中線和木板邊緣的處理，幾乎沒有鋸齒。對比本算法抗鋸齒處理后的圖2（c）效果與FXAA處理的圖2（b）效果，左圖處理效果沒有差別，但是中間和右邊圖的對比可以發現，本算法對鋸齒邊緣處理更平滑。

圖2　原始圖、FXAA和本算法效果對比

5　結語

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

[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-），男，河南鄧州人，碩士研究生，研究方向為計算機圖形圖像處理、計算機圖形學、虛擬現實

2015-12-01

2016-01-10

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

抗鋸齒；GPU；幾何形態學；并行處理；三維場景

王斌（1989-），男，湖北襄陽人，碩士研究生，CCF會員，研究方向為計算機圖形圖像處理、計算機圖形學、虛擬現實

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.