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

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

0 引 言

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

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

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

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

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

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

圖1 TBR架構(gòu)

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

圖2 TBDR架構(gòu)

2 光柵化掃描算法分析

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

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

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

(1)

對(duì)式(1)進(jìn)行推導(dǎo)變形為

(2)

其中

(3)

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

(4)

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

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

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

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

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

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

掃描算法的步驟如下：

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

(5)

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

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

(3)計(jì)算下一行起始掃描像素塊，開始進(jìn)行下一行的掃描，下一行水平掃描線的起始?jí)K坐標(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為下一行水平掃描線的起始?jí)Kx坐標(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)上半空間和下半空間同時(shí)完成當(dāng)前水平掃描行時(shí)。若滿足top_start_block_y=down_start_block_y，下半空間停止掃描，上半空間完成下一行掃描后三角形遍歷結(jié)束；若滿足top_start_block_y=down_start_block_y+2，停止上半空間和下半空間掃描，三角形遍歷結(jié)束。

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

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

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

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

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)

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

實(shí)現(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 光柵化掃描硬件實(shí)現(xiàn)

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

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

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

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

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

4.1 性能分析

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

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

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

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

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

count_pixel=area

(8)

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

pixel=count_pixel/T

(9)

三角形的掃描填充率為

rate=area/T

(10)

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

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

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

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

表2 不同算法在一個(gè)時(shí)鐘節(jié)拍處理的像素?cái)?shù)目比較

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

4.2 FPGA實(shí)現(xiàn)

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

圖7 FPGA測(cè)試結(jié)果

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

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

表3 硬件電路資源使用對(duì)比情況

5 結(jié)束語

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