王媛媛，韓俊剛，蔣 林，張 娜

（西安郵電大學(xué)a.電子工程學(xué)院；b.計算機(jī)學(xué)院；c.研究生部，陜西 西安 710061）

點光柵化及反走樣算法的研究與實現(xiàn)

王媛媛a，韓俊剛b，蔣 林c，張 娜a

（西安郵電大學(xué)a.電子工程學(xué)院；b.計算機(jī)學(xué)院；c.研究生部，陜西 西安 710061）

圖形處理器流水線中經(jīng)典的點生成算法和點反走樣算法便于實現(xiàn)，但采樣點測試的計算量大并且存在冗余測試，為此提出了多采樣掃描轉(zhuǎn)換算法。該算法將多采樣集中在邊界片元，同時，利用點區(qū)別于其他圖元的對稱特性，減少了采樣點的冗余測試，提高了多采樣時掃描轉(zhuǎn)換的性能。試驗結(jié)果表明：文中算法在較小代價下達(dá)到了同樣的反走樣性能。

點圖元；光柵化；反走樣；圖形處理器

0 引言

圖形處理器［1］（GPU）不僅是處理大量圖形計算的專用處理器，而且還可以在圖形處理之外的領(lǐng)域進(jìn)行通用計算。它采用流水線結(jié)實現(xiàn)圖形的定位（形狀、位置的確定）、著色和光柵化操作。GPU流水線［2］包括：命令處理、幾何變換、圖元裝配、投影變換、齊次化、視窗變換、掃描轉(zhuǎn)換（圖元光柵化和反走樣）和消隱等單元。圖形處理器的硬件架構(gòu)經(jīng)過5代發(fā)展變革［3－5］，圖元光柵化始終是圖形處理過程中最重要的處理單元，直接決定著圖形的繪制效果和渲染質(zhì)量。點圖元是圖元光柵化中最基本的圖元之一，其繪制質(zhì)量和速度直接影響GPU的性能。但由于點在光柵圖形顯示器的對應(yīng)圖形是由一系列相同亮度的像素組成，因此，繪制點時會出現(xiàn)鋸齒狀，這種用離散量表示連續(xù)量引起的失真稱為走樣［6］。消除這種走樣現(xiàn)象的技術(shù)就叫做反走樣。本文對點的光柵化和反走樣的算法進(jìn)行了研究，并用軟硬件實現(xiàn)，其正確性已在實際應(yīng)用中得到驗證。

1 點光柵化以及反走樣原理與逐點生成算法

1.1 未啟用反走樣下點光柵化

屏幕上所繪制的各種寬度的點所包含的像素集合取決于是否啟用了反走樣功能。如果反走樣功能被禁用（默認(rèn)情況），帶小數(shù)點的寬度值將四舍五入為整型值，在屏幕上所繪制的是其正方形像素區(qū)域。

圖1為未啟用反走樣時點圖元的光柵化，如圖1所示，像素的中心點位于圖1a中的黑點位置（x，y），點的大小被定義為6.5 pixel，在未啟用反走樣的情況下，根據(jù)點的大小投影到屏幕上的掃描區(qū)域如圖1a所示。從左下點起，根據(jù)從下向上，自左向右的掃描順序，依次掃描得到如圖1b所示的正方形繪制結(jié)果［7－8］。

1.2 啟用反走樣的點光柵化

如果啟用了反走樣功能，屏幕上繪制的就是一個圓形的像素區(qū)域。在啟用了反走樣功能情況下，用戶使用OpenGL命令設(shè)置反走樣的質(zhì)量要求，根據(jù)反走樣質(zhì)量要求選擇不同的采樣頻率。根據(jù)多重采樣的方法對點圓求面圓各個像素所覆蓋的亞像素，作為像素亮度大小。

首先，根據(jù)點的坐標(biāo)確定出所要繪制的面圓的中心位置c；然后根據(jù)點的大小確定出反走樣點的半徑r，也就是確定采樣圓域；再按照點的位置與大小計算出來點的正方形掃描區(qū)域，對正方形區(qū)域內(nèi)的每個像素點，按照自下向上，由左到右的掃描順序，判斷每個像素中落在以c為中心，以r為半徑的圓內(nèi)的亞像素點的個數(shù)，來確定該像素的顏色強(qiáng)度。

圖1 未啟用反走樣時點圖元的光柵化

圖2為反走樣時點圖元的光柵化，按照這種算法，以點的大小為6.25 pixel為例，如圖2所示，圖2a中的方框為掃描范圍；以c為中心，以r為半徑的圓域為采樣范圍。圖2b是基于整像素采樣的結(jié)果，由圖2b可以看出：在邊沿部分有明顯的鋸齒狀走樣現(xiàn)象。圖2c為按照多重采樣算法的渲染結(jié)果，由圖2c可以看出：采用這種算法掃描出來的點在邊界有明顯的過度，很好地滿足了反走樣效果［7－8］。

圖2 反走樣時點圖元的光柵化

2 點光柵化以及反走樣改進(jìn)算法

2.1 點反走樣的改進(jìn)算法－邊界點特性

點逐像素生成反走樣算法便于實現(xiàn)多采樣［9］，但采樣點測試的計算量大并且存在冗余測試。為了解決這個問題，新算法建立圖元的邊界盒，將所有的覆蓋測試限于邊界盒中。由于在圖元的邊界處進(jìn)行掃描轉(zhuǎn)換時產(chǎn)生鋸齒，而在圖元內(nèi)部的片元不會產(chǎn)生這種走樣，所以本文的多采樣只在圖元的邊界處附近進(jìn)行采樣，為此提出“邊界片元”［10］的概念。本文整合“邊界片元”的特性，提出了“反走樣邊界點”的概念，由“反走樣邊界點”來確定3種不同片元，這種根據(jù)像素位于不同象限，用兩個點來確定“邊界片元“的方法節(jié)省了判定時間和運算效率。規(guī)則1～規(guī)則4闡述了對不同片元的判定和處理方法。

規(guī)則1：算法針對像素位于象限的不同，確定像素兩個“反走樣邊界點”?！胺醋邩舆吔琰c”定義為一個像素中離圓心最近的點和離圓心最遠(yuǎn)的點。當(dāng)像素位于Ⅰ、Ⅲ象限時邊界點為像素的左下角和右上角，當(dāng)像素位于Ⅱ、Ⅳ象限時邊界點為像素的右下角和左上角。新算法根據(jù)邊界點在圓內(nèi)和圓外的不同情況來確定此像素是外部片元、“邊界片元”或者內(nèi)部片元。內(nèi)部片元指與圖元重疊面積等于1片元面積的片元；“邊界片元”指與圖元重疊面積大于0的非內(nèi)部片元；外部片元指與圖元重疊面積等于0的片元，如圖3所示。

規(guī)則2：片元的“反走樣邊界點”都在圖元內(nèi)部，則此片元是內(nèi)部片元；片元的“反走樣邊界點”一個在圖元內(nèi)部，一個在圖元外部，則此片元是“邊界片元”；片元的“反走樣邊界點”都在圖元外部，則此片元是外部片元。

規(guī)則3：內(nèi)部片元所有屬性按片元屬性賦值，alpha值為1；外部片元不定義此片元；“邊界片元”按照多采樣的方式進(jìn)行反走樣處理。

規(guī)則4：每個像素的子像素按照從下到上，從左到右的順序掃描，某子像素距離圓心的距離平方是：

原算法每個子像素都需要代入式（1），此種情況下浪費乘法器效率。若子像素遞進(jìn)大小為q，則考慮x遞增q后，距離平方記為SDX1：

同理遞減以及y方向亦可獲得。

對于每個像素2×q×x，q×q，2×q×y值固定，即每個子像素的x、y增量都相同，每個像素只需5次乘法。Y軸增加量y_delta＝2×q×y＋q×q，X軸增加量x_delta＝2×q×x＋q×q。

根據(jù)以上規(guī)則，可將算法定義如下：

算法1，以第1象限的1／4圓為例：

輸入，點大小、點屬性

輸出，構(gòu)成點的各個像素和它的屬性

步驟1：點的坐標(biāo)確定出所要繪制的點圓的中心位置c，然后根據(jù)點的大小確定出反走樣點的半徑r，也就是確定采樣圓域。

步驟2：按照點的位置與大小計算出來點的正方形掃描區(qū)，將點圓的中心和掃描區(qū)平移置坐標(biāo)原點。

步驟3：從掃描區(qū)域的右上角開始按“反走樣邊界點”，水平從右到左對1／4點圓進(jìn)行掃描，直到掃描到內(nèi)部片元截止。對外部片元不處理，對邊界片元按規(guī)則4進(jìn)行各個子像素的掃描。當(dāng)掃描到內(nèi)部片元時，此內(nèi)部片元到Y(jié)軸的剩余片元都按內(nèi)部片元處理。

步驟4：片元垂直坐標(biāo)位于零點時，掃完此行截止。

圖3 圖元分類表示

2.2 點反走樣的改進(jìn)算法－點圖元對稱性質(zhì)

3種基本圖元點、直線、三角形中，點相對直線、三角形來說有很好的對稱性質(zhì)，所以點的對稱生成要比直線、三角形更有效。本文探討不同坐標(biāo)、不同半徑情況下點的繪制，點坐標(biāo)不同時點分布圖見圖4。通過比較，提出更節(jié)省資源的點繪制方法。

規(guī)則5：點的中心坐標(biāo)分為X軸、Y軸兩個方向，若X軸坐標(biāo)在整數(shù)點位置上，點所占像素以圓心的X坐標(biāo)軸為軸左右對稱（如圖4a所示）；同理若Y軸位于整數(shù)點位置上，點所占像素以圓心的Y坐標(biāo)軸為軸上下對稱（如圖4a所示）；若X軸坐標(biāo)在像素中點位置上（坐標(biāo)分?jǐn)?shù)為5），點所占像素以圓心所占像素為豎軸左右對稱（如圖4b所示）；同理若Y軸在像素中點位置上，點所占像素以圓心所占像素以橫軸上下對稱（如圖4b所示）；其余情況下不存在像素對稱畫法。

根據(jù)規(guī)則3中點所占像素的對稱性，可將算法分情況改進(jìn)為：

情況1：X軸、Y軸坐標(biāo)均在整數(shù)點位置，點圓關(guān)于圓心對稱，僅需畫1／4圓，其他3／4圓關(guān)于相應(yīng)軸復(fù)制；掃描范圍為｝，此像素按X軸和Y軸均對稱復(fù)制3次。按下面存儲

PutPixel（x，y，color.a.）；

PutPixel（x_another，y，color.a.）；PutPixel（x，y_another，color.a.）；

PutPixel（x_another，y_another，color.a.）。

圖4 點坐標(biāo)不同時點分布圖

情況2：一個點中心坐標(biāo)位于整數(shù)點，一個位于像素中點，掃描范圍為｛ixLeft＝＜x＜xCenter，iyBottom＝＜y＜yCenter｝，僅需畫1／4圓，位于像素中點的1／2行（列）像素關(guān)于Y軸左右（X軸上下）復(fù)制，其他像素按情況1所述方法復(fù)制到另外3個坐標(biāo)系。

情況3：點中心坐標(biāo)的一個坐標(biāo)位于整數(shù)點，一個既不位于整數(shù)點也不位于像素中點，則需畫1／2圓，掃描范圍為｛ixLeft＝＜x＜xCenter，iyBottom＝＜y＜iyTop｝或｛ixLeft＝＜x＜ixRight，iyBottom＝＜y＜yCenter｝，像素關(guān)于X軸或Y軸對稱復(fù)制。

情況4：點中心坐標(biāo)的一個坐標(biāo)位于像素中點，一個既不位于整數(shù)點也不位于像素中點，則需畫1／2圓，掃描范圍為｛ixLeft＝＜x＜xCenter，iyBottom＝＜y＜iyTop｝或｛ixLeft＝＜x＜ixRight，iyBottom＝＜y＜yCenter｝，除位于中點的一行或一列像素不復(fù)制外，其他像素關(guān)于X軸或Y軸對稱復(fù)制。

情況5：兩個坐標(biāo)位置均不位于整數(shù)點也不位于像素中點，則掃描范圍為｛ixLeft＝＜x＜ixRight，iyBottom＝＜y＜iyTop｝，不需復(fù)制，逐點掃描。

2.3 算法比較

傳統(tǒng)的多采樣方法將采樣點逐個代入邊界條件中進(jìn)行采樣測試，完全沒有考慮圖元對片元的覆蓋情況。當(dāng)圖元與片元的重疊面積很小時，這種方法的計算效率很低，且這種情況隨著采樣點數(shù)目的增加會變得更為嚴(yán)重。本文算法區(qū)分各個片元，對3種不同片元采用不同的處理方法，僅對圖元的邊界片元進(jìn)行多采樣，可以有效地減少冗余測試，對外部片元采用不存儲的策略，節(jié)省了存儲器效率。

傳統(tǒng)逐點生成算法是將每個采樣點的坐標(biāo)值代入點圓的參數(shù)方程中，根據(jù)求得的結(jié)果判斷圖元是否覆蓋該采樣點。本文算法將乘法運算用迭代來實現(xiàn)節(jié)省乘法器效率，同時利用不同片元的特性來減少單個片元的運算次數(shù)。表1中所示設(shè)定每個片元采樣率為4×4，對兩種算法中不同片元進(jìn)行了運算比較，從中可以看出3種不同片元中運算次數(shù)均有減少。

表1 3種片元運算次數(shù)比較

本文算法利用圓的對稱性，將圓的對稱情況分為5種，針對5種情況有不同的處理，可以減少采樣點數(shù)，提高算法效率。同時根據(jù)每掃描行僅需判斷一個內(nèi)部片元的特性來減少采樣點個數(shù)。外部片元與需判斷的內(nèi)部片元的有效子像素個數(shù)為2，每個邊界片元有效子像素為4×4。表2對5種不同情況下的點進(jìn)行了有效子像素數(shù)目測試，從表2中可以看出：5種不同情況下有效子像素減少率分別為90.4%、87.7%、75.7%、77.9%和51.8%，減少的趨勢是很大的，采樣效率明顯得到提高。

表2 采樣測試的子像素數(shù)目比較

3 點光柵化以及反走樣的軟硬件實現(xiàn)

3.1 點光柵化與反走樣的軟件實現(xiàn)

采用MFC軟件平臺，利用流水線方式，實現(xiàn)點掃描與反走樣。圖5為軟件實現(xiàn)結(jié)果圖，分別為OpenGL實現(xiàn)點掃描（見圖5a）、OpenGL實現(xiàn)點反走樣（見圖5b）、算法實現(xiàn)點掃描（見圖5c），算法實現(xiàn)點反走樣（速度快）（見圖5d）、算法實現(xiàn)點反走樣（速度慢）（見圖5e）；結(jié)果表明本文算法與OpenGL實現(xiàn)算法實現(xiàn)效果相同。

圖5 軟件實現(xiàn)結(jié)果圖

3.2 點光柵化與反走樣的硬件實現(xiàn)

圖6為硬件電路的整體設(shè)計，如圖6所示，硬件電路模塊可劃分為如下模塊：數(shù)據(jù)接收模塊、光柵化模塊、反走樣模塊、RAM寫控制模塊、雙口RAM模塊。其中，數(shù)據(jù)接收模塊用于從外部接收點的所有相關(guān)信息，將除了坐標(biāo)信息和alpha信息以外的其他信息存儲于內(nèi)部RAM中；并判斷是否反走樣將坐標(biāo)信息和alpha傳給反走樣模塊或光柵化模塊。光柵化模塊，未啟用反走樣的情況下根據(jù)點的坐標(biāo)大小確定掃描范圍，按照從左到右，從下到上掃描，產(chǎn)生各個像素的坐標(biāo)。反走樣模塊包括反走樣數(shù)據(jù)處理模塊和覆蓋率模塊。掃描模塊主要確定掃描范圍，且根據(jù)覆蓋率產(chǎn)生各個新的alpha值，并將像素信息輸出；覆蓋率模塊根據(jù)speed信號判斷覆蓋率計算劃分子像素個數(shù)，統(tǒng)計在圓內(nèi)子像素個數(shù)占總的子像素的比率即可。RAM寫控制模塊，通過此模塊控制3個模塊有序的向RAM內(nèi)寫數(shù)據(jù)。雙口RAM模塊，用于存儲點的各個像素信息。

圖6 硬件電路的整體設(shè)計

4 結(jié)論

本文首先對現(xiàn)有一些繪制點的算法進(jìn)行了分析及總結(jié)，然后基于減少冗余點測試和點的對稱性提出了新的點繪制算法，此算法對各個片元和各種不同的點采用了不同的處理方法，在較小的代價下實現(xiàn)了點的掃描和反走樣，且本算法適合于硬件實現(xiàn)。FPGA驗證結(jié)果表明：本設(shè)計能夠?qū)崟r準(zhǔn)確地完成點的光柵化。綜合結(jié)果顯示：該設(shè)計很適合集成到移動設(shè)備的GPU系統(tǒng)中。進(jìn)一步工作是對各個片元進(jìn)行自適應(yīng)多采樣處理，通過增減各級處理單元來平衡流水線中各級并行度，進(jìn)一步提高系統(tǒng)的性能。

［1］ 韓俊剛，蔣林，杜慧敏，等.一種圖形加速器和著色器的體系結(jié)構(gòu)［J］.計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2010（3）：363－372.

［2］ Angel E.Interactive Computer Graphics：A Top-Down Approach Using OpenGL［M］.5 ed.Boston：Addison Wesley，2008.

［3］ Harris M.Mapping Computational Concepts to GPUs［C］／／Los Angeles：Annual Conference Series，ACM SIGGRAPH. 2005.

［4］ 張浩，李利軍，林嵐，等.GPU的通用計算應(yīng)用研究［J］.計算機(jī)與數(shù)字工程，2005，33（12）：60－61.

［5］ 丁鵬，陳利學(xué)，龔捷，等.GPU通用計算研究［J］.計算機(jī)與現(xiàn)代化，2010（1）：12－15.

［6］ Zhang J X，Luo L，Jiang F.Rendering Optimization to Rich Media Scenes on Mobile Devices［J］.Journal of Computer-Aided Design＆Computer Graphics，2010，22（8）：1272－1278.

［7］ Dave S，Mason W，Jackie N，et al.Opengl編程指南［M］.北京：機(jī)械工業(yè)出版社，2008：26－35.

［8］ Richard S，Wright J，Benjamin L.OpenGL超級寶典［M］.4版.北京：人民郵電出版社，2005：8.

［9］ Schwarz M，Stamminger M.Multisampled Antialiasing of Per-pixel Geometry［C］.Proceedings of Eurographics.2009：21－24.

［10］ 韓俊剛，殷誠信，曹小鵬.自適應(yīng)多采樣掃描轉(zhuǎn)換算法［J］.計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2012，24（4）：451－458.

TP302

A

1672－6871（2014）04－0043－06

國家自然科學(xué)基金重點項目（61136002）

王媛媛（1986－），女，河南洛陽人，碩士生；韓俊剛（1943－），男，吉林長春人，教授，博士生導(dǎo)師，主要研究方向為專用集成電路設(shè)計和圖形學(xué).

2012－06－03