Tile型三角形多向并行掃描算法的設(shè)計

樊 萌，蔣 林，楊博文，郭佳樂，田 璞

(1.西安郵電大學(xué) 電子工程學(xué)院，陜西 西安 710121；2.西安科技大學(xué) 集成電路設(shè)計實驗室，陜西 西安 710054)

0 引 言

隨著圖形應(yīng)用的快速發(fā)展，復(fù)雜的三維(3D)圖形應(yīng)用需求與日俱增，圖形處理器(graphic processing unit，GPU)作為顯示系統(tǒng)的核心，以硬件加速的形式實現(xiàn)了3D圖形的繪制，在計算機系統(tǒng)中的作用日益增高[1,2]。光柵化是GPU的關(guān)鍵單元[3,4]，是將幾何圖元轉(zhuǎn)換為片段的重要過程，其掃描填充率的高低直接影響到GPU圖形加速的性能。因此，如何設(shè)計合理的三角形光柵掃描算法，使得硬件電路設(shè)計簡單，掃描填充速度快成為了研究的熱點。

傳統(tǒng)的光柵掃描算法會產(chǎn)生大量無關(guān)像素，文獻[5]介紹的Zigzag掃描算法與文獻[6]介紹的中心線掃描算法都能夠減少對大量多余像素的遍歷，但是通過中心線算法在對三角形進行處理時，會出現(xiàn)中心線偏離三角形的情況，導(dǎo)致掃描行起始點在三角形外，從而增加無效像素的遍歷。文獻[7]介紹的中點遍歷算法將三角形以中間頂點劃分為上下兩部分，通過對上下兩個方向的掃描，可以解決中心線掃描算法中心線偏離的情況。但是以上算法都只能從一個方向?qū)θ切芜M行掃描，并行度低，當(dāng)三角形面積過大時，掃描周期變長，填充效率較低。文獻[8]提出的基于塊的等半空間三角形光柵化將三角形通過包圍盒平分線劃分為上半空間和下半空間兩部分，并且以像素塊為單位,同時從兩個方向?qū)θ切芜M行遍歷，一次可以處理兩個像素塊，提高了掃描效率。但是該算法上半空間和下半空間的交匯點固定為三角形包圍盒的平分線，當(dāng)上半空間和下半空間像素分布相差比較大時，會出現(xiàn)其中一個半空間掃描結(jié)束，另一半空間仍有大部分像素還未掃描的情況，導(dǎo)致長時間的等待問題。因此，算法對三角形遍歷也不能達到最佳效果。

針對現(xiàn)有光柵掃描算法的不足，在適用于分塊式渲染(Tile based rendering，TBR)架構(gòu)的基礎(chǔ)上，提出了一種高效的基于Tile的三角形多向并行掃描算法，并通過專用硬件電路進行設(shè)計實現(xiàn)，該算法的設(shè)計在避免了對無關(guān)像素處理的基礎(chǔ)上，與其它光柵掃描算法相比，并行度更高，可以顯著提高三角形的遍歷速度，對三角形的填充率最大可達到100%，適用于高性能的移動圖形處理器。

1 適用于分塊式渲染的圖形處理器

為了適用于移動GPU低帶寬，低功耗需求，基于Tile的GPU架構(gòu)被廣泛用于移動平臺[9,10],該架構(gòu)通常分為TBR架構(gòu)和分塊式延遲渲染(Tile based deferred rende-ring，TBDR)架構(gòu)。

TBR架構(gòu)將屏幕劃分為若干個很小的Tile，并且對每一個Tile進行光柵化等后續(xù)處理[11,12]。與傳統(tǒng)的渲染架構(gòu)相比，該架構(gòu)可以將整個Tile的幀緩沖區(qū)、深度緩沖區(qū)和模板緩沖區(qū)保存在片上高速緩存中，利用內(nèi)部存儲直接對其進行渲染，從而減少GPU對外部存儲的訪問和內(nèi)存帶寬的消耗。TBR架構(gòu)如圖1所示。

圖1 TBR架構(gòu)

為了在TBR架構(gòu)上進一步降低帶寬的消耗，提出了TBDR渲染架構(gòu)。該架構(gòu)和TBR架構(gòu)原理相似，都是以Tile為單位對三角面進行繪制。但該架構(gòu)對每個光柵化生成的像素都進行深度測試操作，提前剔除掉被遮擋的像素，減少不必要渲染的片段，降低了帶寬的需求[13]。TBDR架構(gòu)如圖2所示。

圖2 TBDR架構(gòu)

2 光柵化掃描算法分析

2.1 邊界函數(shù)算法分析

本文提出的三角形掃描算法基于邊界函數(shù)方程，邊界函數(shù)算法可以有效地對像素點進行判斷，基本思想是通過三角形3條邊的線性函數(shù)確定出屬于三角形內(nèi)部的像素點，判斷過程如下：

假定一個Tile左上方為坐標(biāo)原點，一個三角形由點A(x1，y1)、B(x2，y2)、C(x3，y3)繞逆時針順序組成，通過式(1)計算出P(x，y)點相對于三角形3條邊的邊界方程，并通過Top_left原則[14]判斷出該像素點與三角形的位置關(guān)系

(1)

對式(1)進行推導(dǎo)變形為

(2)

其中

(3)

采用Top_left原則對系數(shù)dx12、dx23、dx31、dy12、dy23、dy31進行約束，得到式(4)

(4)

當(dāng)三角形3條邊的邊界方程值都小于0時，像素點P在三角形內(nèi)部；當(dāng)有其中一條邊的邊界方程值為0，并且同時滿足式(4)時，像素點P在三角形內(nèi)部；若不滿足以上兩種情況，則像素點P在三角形外部。

2.2 三角形光柵化掃描算法分析

通過對邊界函數(shù)算法的分析，在適用于分塊式渲染的GPU架構(gòu)基礎(chǔ)上，提出一種基于Tile的三角形多向并行掃描算法，在不同大小的Tile內(nèi)，從三角形的最大頂點(xmax_block，ymax_block)和最小頂點(xmin_block，ymin_block)開始，將三角形分為上下兩個半空間，以2×2大小的像素塊為單位，分別從下到上和從上到下同時進行左右并行掃描，直到兩個方向的掃描相遇時停止。該算法流程如圖3所示，當(dāng)輸入三角形的3個頂點坐標(biāo)位置信息后，先通過簡單加法器和乘法器對三角形的邊界方程系數(shù)進行計算，以及對三角形最大頂點和最小頂點的計算，記為三角形參數(shù)計算，然后對三角形同時進行上、下半空間掃描處理，采用邊界函數(shù)算法判斷出像素與三角形的位置關(guān)系，并且輸出屬于三角形內(nèi)部的像素點，完成對三角形的掃描遍歷。

圖3 三角形光柵化掃描算法流程

以16×16大小的Tile為例，掃描過程如圖4所示。每個框代表一個2×2像素塊，其中斜線框表示邊緣像素塊，灰色框表示邊界像素塊(邊緣像素塊的一種)，豎線框表示內(nèi)部像素塊，虛線箭頭表示掃描起始塊像素坐標(biāo)，垂直方向箭頭表示當(dāng)前行掃描屬于上半空間還是下半空間，這需要在每一次對當(dāng)前行掃描完成之后通過條件判斷后得到，水平方向箭頭表示對當(dāng)前行進行的左右遍歷。

圖4 三角形光柵化掃描算法

掃描算法的步驟如下：

(1)首先計算對三角形掃描的起始像素塊，根據(jù)輸入的三角形頂點坐標(biāo)信息，分別確定x，y坐標(biāo)的最大值和最小值，利用式(5)計算出三角形的兩個起始像素塊坐標(biāo)(xmax_block，ymax_block)和(xmin_block，ymin_block)，如圖4中虛線箭頭所示

(5)

其中，x(y_max)，x(y_min)分別表示當(dāng)y值最大和最小時x的值。

(2)從兩個當(dāng)前掃描行起始像素塊坐標(biāo)開始同時對上、下半空間進行左右并行掃描，根據(jù)邊界函數(shù)值判斷并輸出屬于三角形內(nèi)部和邊緣像素塊，如圖4中斜線框和豎線框所示，直到遇到位于三角形之外的像素塊時停止，并且記前一個像素塊為邊界像素塊，如圖4中灰色框表示。當(dāng)左右方向掃描都停止時，該行掃描結(jié)束。

(3)計算下一行起始掃描像素塊，開始進行下一行的掃描，下一行水平掃描線的起始塊坐標(biāo)可以通過當(dāng)前水平掃描行的邊界像素塊坐標(biāo)得到，具體做法如式(6)

start_block_x=left_bound+(right_bound-
left_bound)>>1,start_block_y=current_y±2

(6)

其中，start_block_x為下一行水平掃描線的起始塊x坐標(biāo)，start_block_y為下一行水平掃描行的y坐標(biāo)，current_y為當(dāng)前行水平掃描行的y坐標(biāo)，left_bound、right_bound分別為當(dāng)前水平掃描行的左邊界和右邊界。

(4)判斷出下一行是停止掃描還是繼續(xù)掃描，如若是繼續(xù)掃描，判斷出該水平掃描線是屬于上半空間還是下半空間，如若是停止掃描，則三角形遍歷結(jié)束。判斷條件如下：

1)當(dāng)上半空間和下半空間同時完成當(dāng)前水平掃描行時。若滿足top_start_block_y=down_start_block_y，下半空間停止掃描，上半空間完成下一行掃描后三角形遍歷結(jié)束；若滿足top_start_block_y=down_start_block_y+2，停止上半空間和下半空間掃描，三角形遍歷結(jié)束。

2)當(dāng)上半空間正在掃描當(dāng)前行，下半空間開始下一行掃描時，若滿足top_current_y+2=down_start_block_y，上半空間完成當(dāng)前行掃描停止，下半空間完成下一行掃描停止。三角形遍歷結(jié)束。

3)當(dāng)下半空間正在掃描當(dāng)前行，上半空間開始下一行掃描時，若滿足top_start_block_y+2=down_current_y，下半空間完成當(dāng)前行掃描停止，上半空間完成下一行掃描停止。三角形遍歷結(jié)束。

4)若不滿足上述1)，2)，3)條件，從下一行的起始像素塊開始，執(zhí)行步驟(2)。

在上述掃描遍歷方式中，為了得到三角形內(nèi)部的像素塊，需要采用式(2)對每一個像素塊進行邊界方程計算，從而導(dǎo)致大量的乘法操作使得算法計算量大，實現(xiàn)效率低下。因此，在實際電路設(shè)計中，為了簡化電路設(shè)計，加快硬件處理速度，對式(2)再進行推導(dǎo)得到式(7)，從而根據(jù)當(dāng)前像素邊界方程值可直接計算一個2×2像素塊內(nèi)相鄰子像素點的邊界方程值

E(x±Δx,y)=E(x,y)±dy×Δx
E(x,y+Δy)=E(x,y)?dx×Δy
E(x±Δx,y±Δy)=E(x,y)+dy×Δx?dx×Δy
E(x-Δx,y±Δy)=E(x,y)-dy×Δx?dx×Δy

(7)

此時，在一個2×2像素塊內(nèi)，相鄰像素點的步進為1，則Δx和Δy取值為1。

實現(xiàn)該算法的偽代碼如下：

calculate the starting block pixel coorinates(x,y) and edge function values(e1,e2,e3).

determine if the next line scan is the top half space or the down half space.

if(topen==1)//traversing top

while(leften==1 and righten==1)

{

if(e1<0 and e2<0 and e3<0)

rendering this point;

leftx=leftx-2;rightx= rightx+2;

else

y=y+2;

}

if(downen==1) //traversing down, and the same as the top

…

y=y-2;

3 光柵化掃描硬件實現(xiàn)

根據(jù)對光柵化掃描遍歷算法的分析，將其硬件電路實現(xiàn)分為4個模塊：三角形參數(shù)建立模塊，上半空間掃描模塊，下半空間掃描模塊和判斷模塊，硬件結(jié)構(gòu)如圖5所示。

三角形參數(shù)建立模塊主要完成對邊界方程系數(shù)dx12,dy12,dx23,dy23,dx31,dy31,c12,c23,c31以及三角形最大頂點和最小頂點的計算，并將其結(jié)果送入上半空間掃描模塊和下半空間掃描模塊。

上半空間掃描模塊和下半空間掃描模塊分為起始像素塊邊界函數(shù)計算模塊和掃描模塊。起始像素塊邊界函數(shù)計算模塊根據(jù)三角形參數(shù)建立模塊的輸出數(shù)據(jù)或者掃描模塊的輸出數(shù)據(jù)計算出第一行或者下一水平掃描行的起始像素塊的邊界函數(shù)值，并將結(jié)果送入掃描模塊，以判定像素塊相對于三角形的位置。掃描模塊對當(dāng)前水平掃描行進行左右并行掃描，并且根據(jù)式(7)計算出掃描像素點的邊界函數(shù)值，完成對三角形上半空間和下半空間的遍歷，輸出三角形內(nèi)有效像素點，同時將掃描行狀態(tài)送入判斷模塊。

判斷模塊決定三角形的下一行水平掃描線是進行上半空間掃描還是下半空間掃描，或者是停止掃描，并將判斷結(jié)果送入上一模塊。

4 性能分析與FPGA實現(xiàn)

4.1 性能分析

考慮到對于不同的三角形會有不同的繪制效果，為了驗證該算法的適用性，在16×16大小的Tile內(nèi)對等腰三角形、直角三角形、任意銳角三角形、鈍角三角形以及特殊狹長三角形進行了功能驗證，并將電路仿真結(jié)果對三角形進行填充，如圖6所示。

圖5 光柵化掃描硬件結(jié)構(gòu)

圖6 不同三角形的繪制結(jié)果

通過對圖6的分析，該算法可以正確完成對三角形的掃描遍歷過程。對于圖6(e)和圖6(f)中的狹長三角形來說，該算法具有一定的局限性。從圖中可以看出，對狹長三角形的填充會有誤差，造成三角形失真，當(dāng)三角形兩條狹長邊在橫坐標(biāo)或者縱坐標(biāo)跨度越小時，繪制的三角形更接近于一條直線，三角形失真越嚴(yán)重。這是因為當(dāng)兩條狹長邊越接近于一條直線時，兩條邊內(nèi)的像素往往只占半個1×1像素塊，無法得到精確的繪制。要解決這個問題，需要將一個1×1像素塊再進行劃分，假設(shè)對1×1像素塊再進行2×2像素劃分，則繪制的像素個數(shù)會成為原來的4倍，這樣雖然會得到更精準(zhǔn)的狹長三角形，但犧牲了填充率，對于一般三角形而言，會顯著降低對三角形的繪制速率，延長三角形的繪制時間，因而降低在圖形繪制中光柵化的實現(xiàn)效率，并且，在一般高分辨率圖像顯示中，這種誤差并不影響人們的視覺體驗。因此，為了提高三角形的填充率，本文選擇該算法完成對三角形的掃描遍歷。

衡量光柵化效率最重要的性能指標(biāo)是平均每個周期能夠產(chǎn)生多少個有效像素，一般而言，假設(shè)三角形3個頂點坐標(biāo)為A(x1，y1)、B(x2，y2)、C(x3，y3)，則該三角形包含的有效像素個數(shù)可以近似為

count_pixel=area

(8)

其中，area為三角形的面積[15]。當(dāng)產(chǎn)生該三角形內(nèi)的有效像素所花費的時鐘周期個數(shù)為T時，平均每個周期產(chǎn)生的有效像素個數(shù)為

pixel=count_pixel/T

(9)

三角形的掃描填充率為

rate=area/T

(10)

為了測試本文提出掃描算法的實際處理速率，根據(jù)本文所設(shè)計電路的實驗結(jié)果，對不同種類三角形實際填充的像素個數(shù)以及完成對三角形遍歷所使用的時鐘數(shù)進行統(tǒng)計，計算出三角形的掃描填充率。結(jié)果見表1。

從表1可以看出，本文所設(shè)計的算法對直角三角形和等腰三角形的填充率可以達到100%，對鈍角三角形和任意銳角三角形的填充率也達到80%以上。對狹長三角形的填充率卻只有30.16%，這是因為當(dāng)三角形足夠窄時，對三角形的繪制更趨近于一條直線，一行只需遍歷一個像素甚至半個像素，無法發(fā)揮算法的并行優(yōu)勢。但對于大部分三角形來說，該算法能夠有效地提高三角形的填充率。

表1 不同三角形的遍歷結(jié)果

為了能夠更好地說明提出的掃描算法的高效性，將三角形處理過程中一個時鐘節(jié)拍所能夠處理的像素數(shù)目進行統(tǒng)計，與文獻[5]、文獻[1]提出的雙掃描技術(shù)以及文獻[8]提出的掃描算法進行比較，結(jié)果見表2。

表2 不同算法在一個時鐘節(jié)拍處理的像素數(shù)目比較

文獻[5]介紹的Zigzag掃描算法以像素點為單位，從起始像素點開始對三角形進行水平掃描，直到遇到無效像素點，使y坐標(biāo)步進一個單位接著對下一行掃描，如此重復(fù)至最后一行結(jié)束；文獻[1]提出的雙掃描技術(shù)基于bresenham線掃描算法，以像素點為單位，在單掃描技術(shù)的基礎(chǔ)上，使用兩條掃描線，以y軸中間頂點坐標(biāo)為界，從上下兩端對三角形處理，直到三角形分界線時結(jié)束；文獻[8]提出的基于塊的等半空間三角形光柵化掃描算法是以像素塊為單位，將三角形通過包圍盒平分線分為上下兩個半空間，并從上半空間和下半空間同時向平分線掃描，直到包圍盒平分線時停止。在遍歷的過程中，3種算法在水平方向上皆是單向的。因此，從表2可以看出，本文提出的掃描算法最大的優(yōu)勢是可以在同一時刻處理更多的像素，處理速度更快，并行度更高。與文獻[8]相比，該算法可以解決三角形上下半空間長時間的等待問題，并且將像素的處理效率提高2倍。

4.2 FPGA實現(xiàn)

在真實的圖形繪制中，一個Tile內(nèi)可能會處理多個三角形，本文對各種不同單個三角形完成功能驗證后，對一個16×16的Tile內(nèi)的多個三角形同樣進行驗證，并且采用Xilinx公司的ISE開發(fā)環(huán)境進行綜合，使用Xilinx公司的ZYNQ系列芯片XC7Z045-2-FFG900對硬件電路進行FPGA測試，通過Chipscope抓取需要直接觀測的信號。為了驗證FPGA測試的正確性，將抓取到的信號坐標(biāo)通過Matlab仿真軟件進行填充，所得到的結(jié)果如圖7所示。由于該結(jié)果是將小分辨的圖像放大得到的，因此，鋸齒效果明顯，但是這并不影響掃描算法對三角形內(nèi)部像素填充的正確性。

圖7 FPGA測試結(jié)果

由圖7可以看出，本文所設(shè)計的電路能夠正確完成對三角形的掃描遍歷功能，并且由圖可以發(fā)現(xiàn)，當(dāng)不同的三角形共用一條邊時，依然能夠正確完成對三角形的繪制。因此，F(xiàn)PGA測試結(jié)果正確。

在基于Xilinx V6-760 FPGA上對電路進行綜合后，資源占用情況與文獻[1]的兩種算法對比見表3?？梢钥闯?，相比于文獻[1]的兩種算法，本文所設(shè)計的硬件電路Slice Registers資源使用率分別減少了59.6%和25.3%，Slice LUTs資源使用率分別減少了36.1%和12.0%，降低了對資源的使用，更易于硬件的實現(xiàn)。

表3 硬件電路資源使用對比情況

5 結(jié)束語

在基于分塊式渲染架構(gòu)的基礎(chǔ)上，通過對現(xiàn)有光柵化掃描算法的深入分析，針對這些算法所存在的不足和問題，本文提出了更高效的三角形雙向并行掃描算法，并通過專用硬件加速設(shè)計光柵化單元。經(jīng)過實驗分析，與其它現(xiàn)有掃描算法相比，具有更高的并行性，可以在Tile內(nèi)對三角形一次處理16個像素，使得掃描填充率最大可以達到100%。通過在Xilinx公司的ZC706開發(fā)板上進行驗證，可實現(xiàn)三角形的掃描遍歷功能，適用于高性能圖形處理器。