三角形的光柵化與反走樣算法

杜慧敏， 郝 哲， 王鵬超， 曹廣界， 杜琴琴， 丁家隆

(1.西安郵電大學 電子工程學院， 陜西 西安 710121； 2.西安郵電大學 計算機學院， 陜西 西安 710121)

三角形的光柵化與反走樣算法

杜慧敏1， 郝 哲2， 王鵬超1， 曹廣界1， 杜琴琴2， 丁家隆1

(1.西安郵電大學 電子工程學院， 陜西 西安 710121； 2.西安郵電大學 計算機學院， 陜西 西安 710121)

針對三角形的光柵化技術，提出一種基于邊函數(shù)的三角形超采樣反走樣算法。根據(jù)三維平面方程的思想，推導出基于二維平面的屬性平面方程的屬性插值算法，結(jié)合基于Bresenham邊步進三角形光柵化算法，對起始基點和反走樣點的屬性做了修正。實驗結(jié)果表明，該算法最大工作頻率可達到230.631MHz，提高了光柵化的速度。

三角形；光柵化；反走樣；屬性平面方程

圖形處理器[1](Graphics Processing Unit，GPU)的硬件架構(gòu)經(jīng)過了五代發(fā)展變革，圖元光柵化始終是圖形處理過程中最重要的處理單元，直接決定著圖形的繪制效果和渲染質(zhì)量。光柵化是由頂點的幾何數(shù)據(jù)和像素數(shù)據(jù)定義成的基本圖元轉(zhuǎn)化成與像素點對應的片元。三角形是圖元光柵化中最基本的圖元，其光柵化過程包含三角形的參數(shù)建立、屬性平面方程的建立、邊方程的建立和光柵化控制，整個過程包含了大量的算數(shù)運算和復雜的狀態(tài)控制，這已經(jīng)成為GPU性能的瓶頸。

隨著圖形渲染模型中每個片元屬性值的不斷增多，要提高圖片顯示質(zhì)量，就需要在光柵化過程中對非毗鄰邊進行反走樣，以此處理更多的運算單元和更大的存儲開銷。對于采用電池供電的高端移動通訊設備，低功耗、高性能的三角形光柵化反走樣算法就需要研究[2-3]。

三角形光柵化現(xiàn)有的方法[4-5],仍然需要處理大量的像素點,同時也需要大量的計算。如果使用軟件來處理三角形光柵化,會造成CPU的大量開銷和資源利用率的降低。

本文擬在三角形構(gòu)成的圖形中，通過分析基于邊函數(shù)的三角形光柵化算法，提出一種基于邊函數(shù)的三角形超采樣反走樣算法。通過推導基于二維平面的屬性平面方程的屬性插值算法，結(jié)合基于Bresenham邊步進三角形光柵化算法[6]，對起始基點和反走樣點的屬性做了修正。并通過硬件來驗證此算法的可行性。

1 三角形光柵化與反走樣算法

將三角形的三個頂點按照y坐標值的大小，由小到大分別記作A,B,C，當有一條邊水平時(兩個點的y坐標相等)，水平邊上兩個點的順序任意，如圖 1 所示。定義AC邊為引導邊，AB邊為第一跟隨邊，BC為第二跟隨邊。 位于引導邊與跟隨邊之間的水平線定義為跨度[7]。

圖1 三角形的邊的定義說明

1.1 屬性平面方程

現(xiàn)代的圖形渲染模型中，每個片元附有更多的屬性，比如光照的各種顏色、紋理坐標、權(quán)重、法向量等。每個片元的各個屬性值根據(jù)三角形各頂點的屬性值進行插值計算。其根據(jù)平面方程來推導出屬性插值的一般算法。

在三角形的一般方程[8]

ax+by+cz+d=0

(1)

中得知方程系數(shù)的值，便可求出這個平面內(nèi)任一點(x，y)的z值。可以將頂點的各個標量屬性參數(shù)(包括顏色，紋理坐標，法向量等)統(tǒng)一設為字母s，和式(1)中的z類似，同樣可以得到屬性平面方程[9]

ax+by+cs+d=0。

(2)

1.1.1 屬性平面方程的求解

由式(2)可以推出屬性s的函數(shù)表達式

s(x,y)=Ax+By+C。

(3)

根據(jù)圖1中三個點的信息A(xA,yA,sA),B(xB,yB,sB)和C(xC,yC,sC)可以求出系數(shù)

a=(yB-yC)(sA-sC)-(yA-yC)(sB-sC),

(4)

b=(xA-xC)(sB-sC)-(xB-xC)(sA-sC),

(5)

-c=area=(yB-yC)(xA-xC)-(xB-xC)(yA-yC),

(6)

其中系數(shù)area就是三角形的有向面積[10]，如圖2所示。當area>0時，引導邊位于左側(cè)，B點位于右側(cè)，三角形ABC是逆時針方向(ccw)；當area<0時，引導邊位于左側(cè)，B點位于右側(cè)，三角形ABC是順時針方向(ckw);當area=0時，三角形ABC的面積為零，三角形退化為一條直線或一個點，此時三角形不需要光柵化。

圖2 三角形的有向面積

由式(4)(5)(6)可得出A和B的表達式

A=T1(sA-sC)-T2(sB-sC),B=T3(sB-sC)-T4(sA-sC),

其中T1，T2，T3，T4是只與點的坐標有關的參數(shù)

對同一三角形的屬性s，計算屬性平面方程系數(shù)時Ti(i=1,2,3,4)值相同，因此只需計算(sB-sC)和(sA-sC)，從而在硬件電路中減小功耗。

1.1.2 屬性函數(shù)的應用

由式(3)可知，在圖3中三角形ABC中，基點O(xO,yO,sO)有

sO=s(xO,yO)=AxO+ByO+C,

(7)

那么對于三角形所在平面內(nèi)的任意一點P(xP,yP,sP)有

sP=s(xP,yP)=Axp+Byp+C。

(8)

解式(7)和式(8)可得

sP=s(xP,yP)=s(xO,yO)+A(xP-xO)+B(yP-yO)=sO+AΔxOP+BΔyOP,

(9)

即在已知三角形所在平面內(nèi)的任一基點的屬性值和該屬性的屬性平面方程，就可以求出該平面內(nèi)所有點的該屬性值。

圖3 點與三角形矢量邊的位置關系

采取自底向頂，子引導邊向跟隨邊的掃描順序進行掃描，一般選取A為基點。因此其他各點的屬性s為

s=sA+AΔx+BΔy。

(10)

1.2 基于邊方程的多采樣反走樣算法

邊函數(shù)可以計算出像素相對于邊的位置，對于一個逆時針排列的三角面來說，判斷一個點是否在三角面以內(nèi)，可以計算出該點對三條邊的邊界函數(shù)

lAB=(x-xA)(yB-yA)-(y-yA)(xB-xA)=a0x+b0y+c0,lBC=(x-xB)(yC-yB)-(y-yB)(xC-xB)=a1x+b1y+c1,lCA=(x-xC)(yA-yC)-(y-yC)(xA-xC)=a2x+b2y+c2。

(11)

若式(11)的計算結(jié)果均為正，則點S在三角形內(nèi)部，否則點S在三角形外部。

一個三角形，若能清楚地判斷任意點相對于每一條邊的位置，就能夠判斷出該點的位置。同時使用邊函數(shù)就意味著從一個像素點被掃描到，到判斷出它的位置的時間是固定的。這有利于掃描像素點以流水或并行的方式進行處理。

由上述可知，將一個像素劃分成多個亞像素，通過依次判斷落在三角形內(nèi)部的亞像素個數(shù)來決定該像素點的覆蓋率和渲染強度。如圖4所示，將一個像素分為16個亞像素，并根據(jù)上述算法描繪出該算法下反走樣三角形。

(a) 像素劃分

(b) 未啟用反走樣

(c) 啟用反走樣

2 光柵化的參數(shù)屬性初始化與修正

實際的光柵顯示系統(tǒng)中，像素是由具有一定物理大小的方塊組成，每個像素對應一個整數(shù)坐標。而在光柵化過程中使用的窗口坐標是一個定點小數(shù)。因此，應該以像素中心點所對應的屬性值作為這個像素點的屬性。

2.1 起始迭代參數(shù)修正

在三角形掃描時，需要引導邊和跟隨邊一起步進，且兩條邊的決策參數(shù)iter_frac的初始值應該修正為圖5(a)中的dxr和dxl。

2.2 起始基點的修正

由于整個掃描過程都是整數(shù)迭代進行的，式(10)中的Δx和Δy都是整數(shù)，因此只需要保證sA是A點所在像素的中心位置的屬性值，那么迭代過程中所有像素點的屬性值都是該像素中心點的屬性值。如圖5(a)所示，根據(jù)式(10)對A點進行屬性修正后得到圖5(b)，則

sO=sA+Adx+Bdy。

(a) 掃描的參數(shù)屬性初始化

(b) 掃描的參數(shù)屬性修正

圖5

2.3 反走樣點的屬性修正

反走樣像素點只有部分位于三角形內(nèi)部，該像素點屬性值不應該再像完整像素那樣以像素中心點P的屬性值作為該像素點的屬性值。根據(jù)像素被覆蓋的區(qū)域，確定出該像素區(qū)域被覆蓋區(qū)的幾何中心點的屬性值作為該點的屬性值。如圖6所示，被覆蓋區(qū)域的幾何中心應該為O點，因此通過式(10)對該像素點的屬性進行修正，以O點的屬性值作為該像素點的屬性值。

圖6 三角形光柵化與反走樣整體結(jié)構(gòu)

3 硬件電路設計

三角形圖元光柵化與反走樣硬件設計結(jié)構(gòu)如圖7所示，在三角形掃描轉(zhuǎn)換整體結(jié)構(gòu)中，按照流水線計算順序可以分為3部分，包括三角形參數(shù)建立、屬性參數(shù)初始化和掃描插值模塊。

圖7 三角形光柵化與反走樣總體結(jié)構(gòu)

在圖 7 中三角形參數(shù)建立單元采用固定功能實現(xiàn)方式。每18個周期可以完成一個三角形光柵化過程所需參數(shù)的計算，該模塊包含算法中公共部分的計算。屬性參數(shù)的初始化部分包括透視修正、屬性差值參數(shù)的建立和屬性值初始化3個小單元，此處是一個6級的流水線，負責對所有的片斷屬性值進行初始化和修正計算。掃描插值模塊包括掃描控制、垂直步進掃描、水平步進掃描和反走樣處理幾個單元。如圖8所示，是實現(xiàn)光柵化與反走樣過程的控制電路結(jié)構(gòu)。其通過雙軌握手協(xié)議控制垂直步進模塊、反走樣模塊與水平跨度模塊之間的工作。

根據(jù)三角形面積的大小掃描時間不定，可以在這些單元的處理過程中都采用流水線的設計方式。掃描峰值時像素生成速率可以達到1個周期出一個像素。

圖8 掃描轉(zhuǎn)換的控制電路結(jié)構(gòu)

4 結(jié)果驗證

為了驗證算法的正確性，采用Verilog_HDL完成RTL級的電路設計，使用Xilinx(Virtex6-760)開發(fā)系統(tǒng)，對所設計的三角形光柵化硬件電路進行了FPGA驗證。結(jié)果表明，該算法設計占用了FPGA芯片Virtex6-760：1.79%的資源，最大工作頻率為230.631MHz，像素填充速率峰值可達一個像素每時鐘周期。

如圖9所示是一個兔子，一個沒有對基點和反走樣點進行屬性修正的繪制結(jié)果，可以看出在耳朵和曲率比較大的部分有明顯的鋸齒，并且整個兔子看起來不平滑。

圖9 沒有經(jīng)過修正的兔子

圖10是經(jīng)過對基點和反走樣點進行屬性修正的繪制結(jié)果，可以看出這個兔子比沒有經(jīng)過修正的兔子繪制效果更好。對比可見，屬性修正是很有必要的，對于提高圖形渲染質(zhì)量也有很大提高。

圖10 經(jīng)過修正的兔子

圖11是繪制的不啟用反走樣和啟用反走樣情況下星狀圖。其中左圖沒有反走樣處理，右圖經(jīng)過反走樣處理。從圖中可以看出，沒用反走樣處理的測試結(jié)果在邊界的地方有明顯的鋸齒走樣，而經(jīng)過反走樣處理的測試經(jīng)過則比較平滑，看起來更加舒服。

圖11 非反走樣和反走樣的星狀

5 結(jié)束語

通過分析基于邊函數(shù)的三角形光柵化算法，提出基于邊函數(shù)的三角形超采樣反走樣算法。根據(jù)三維平面方程的思想，推導了基于二維平面的屬性平面方程的屬性插值算法。結(jié)合基于Bresenham邊步進三角形光柵化算法，對起始基點和反走樣點的屬性做了修正。總結(jié)了整個光柵化過程中公共參數(shù)的計算部分，設計出基于硬件資源最大共享化思想和流水線的設計結(jié)構(gòu)。FPGA驗證結(jié)果表明，該算法能夠準確地完成三角形的光柵化。該算法的電路設計很適合集成到移動設備的GPU系統(tǒng)中。

[1] 韓俊剛,劉有耀,張曉.圖形處理器的歷史現(xiàn)狀和發(fā)展趨勢[J].西安郵電學院學報,2011,16(3):61-64.

[2] 楊國東.嵌入式圖像處理器的研究與實現(xiàn)[D].濟南：山東大學,2010：8-66.

[3] 田譯,張駿,許宏杰,等.圖形處理器低功耗設計技術研究[J].計算機科學,2013,40(6A):10-216.

[4] Garachorloo N.Gupta S,Sproull R F,et al.A Characterization of ten Rasterization Techniques[C]//Proc.of the 16th Annual Conference on Computer Graphics and Interactive Techniques .New York ,USA:ACM Press，1989:355-368.

[5] Kaufman A. Rendering, Visualization.Rasterization Hardware[M],NewYork,USA:Springer-Verlag,1993,(6):16-18.

[6] Gaol,Ford.Lumban.Bresenham algorithm implementation and analysis in raster shape[J].IEEE Journal of Computers (Finland) ,2013(1):69-78.

[7] 張鵬,王良.嵌入式圖像系統(tǒng)的改進Bresenham反走樣算法的應用[J]. 電子設計工程, 2011(4):117-119.

[8] 黃瑞.實時嵌入式圖形系統(tǒng)中的三角形光柵化研究與設計[D].上海：上海交通大學,2008：7-12.

[9] 李玉云.面向移動設備的光柵化處理器的研究與設計[D].合肥：中國科學技術大學,2010：8-10.

[10] 吳躍生,李詠秋.關于逆順三角形有向面積的一個定理及其推論[J].贛南師范學院學報,2010,6(3):31-34.

[11] Chih-Hao Sun,You-Ming Tsao,Ka-Hang Lok et..al.Universal rasterizer with edge equation and tile-scal triangletraversal algorithm for graphics processing unis[J].ICME,2009(6):1358-1361.

[責任編輯:祝劍]

Triangle rasterization and anti-aliasing algorithms

DU Huimin1, HAO Zhe2, WANG Pengchao1,CAO Guangjie1, DU Qinqin2, DING Jialong1

(1. School of Electronic Engineering ,Xi’an University of Posts and Telecommunications,Xi’an 710121,China；2. School of Computer Science, Xi’an University of Posts and Telecommunications,Xi’an 710121,China)

In order to solve the existing problems of the traditional triangular rasterizer technology in a graphics processing unit (GPU), a triangle super sampling aliasing algorithm based on boundary function is proposed. Based on the three-dimensional plane equation, the attribute interpolation algorithm based on the two-dimensional planar plane equation is deduced. By combining stepping triangle rasterization algorithms based on Bresenham edge, some corrections are made in the starting point and anti-aliasing some properties. Experiment results show that the speed of the rasterizer can be improved and the algorithm can achieve maximum working frequency of 230.631 MHz by using the FPGA chip Virtex6-760 authentication.

triangle, rasterization, anti-aliasing, attribute plane equation

2015-01-20

國家自然科學基金資助項目(90607008，60976020)；陜西省政府基金資助項目(2011k06-47)；西安市科技發(fā)展計劃資助項目(CXY1440(10))

杜慧敏(1966-)，女，博士，教授，從事集成電路設計、計算機體系結(jié)構(gòu)研究。E-mail:228660529@qq.com 郝哲(1987-)，女，碩士，研究方向為計算機體系結(jié)構(gòu)與VLSI。E-mail:648325913@qq.com

10.13682/j.issn.2095-6533.2015.03.005

TP399

A

2095-6533(2015)03-0033-06