杜慧敏,張英杰,王一鳴

(西安郵電大學 電子工程學院，陜西，西安 710121)

現(xiàn)代圖形處理器(graphics processing unit，GPU)已具有高度的并行計算能力和極高的傳輸帶寬，從單純的圖形渲染加速器發(fā)展為通用的高性能并行計算芯片[1]，廣泛地應用在游戲、虛擬現(xiàn)實、科學計算、人工智能、機器人等眾多領域[2]。

目前高性能GPU通常采用統(tǒng)一渲染架構(gòu)實現(xiàn)基于瓦片渲染(tile based rendering,TBR)管線[3]。統(tǒng)一架構(gòu)GPU由若干個結(jié)構(gòu)相同的處理器實現(xiàn)頂點處理和片元處理功能，根據(jù)渲染場景的特點，將處理器分配給頂點著色和片元著色，高效地完成場景渲染，保證渲染管線上各個單元負載平衡[4]。與傳統(tǒng)立即渲染(immediate mode rendering,IMR)不同的是，采用TBR方式的GPU在圖元裝配之后將渲染場景劃分為多個相同大小的瓦片，每次僅渲染一個瓦片，每個瓦片渲染時所需要的全部數(shù)據(jù)都放在片內(nèi)存儲，有效地減少了帶寬需求，極大地降低了功耗。幾何流水線是GPU中重要的組成部分，基于TBR方式的GPU中幾何流水線功能包括圖元裝配、裁剪和剔除以及多邊形鏈表的建立等[5]。文獻[6]提出了一種基于計算著色器的視見體剔除算法，雖然提高了視見體剔除的效率，但是算法計算量較大。文獻[7]雖然設計了一種高能效和高靈活性的背面剔除算法，但是需要大量的矩陣運算。文獻[8]對常見的裁剪算法包圍盒算法進行改進，提高了裁剪效率，但是卻沒有針對特殊位置的小三角形進行處理。

總體而言，現(xiàn)有的研究或者計算量較大不利于硬件實現(xiàn)，或者為了簡化計算忽略了某些信息影響渲染效果。為了兼顧硬件實現(xiàn)的便利性和渲染效果，擬在TBR架構(gòu)常用的幾種幾何流水線關算法的基礎上，優(yōu)化視見體剔除與背面剔除算法，在裁剪過程選取包圍盒算法，針對特殊位置的小三角形進行處理，加入多重采樣算法和邊函數(shù)算法，避免小三角形丟失，優(yōu)化“瓦片”(Tile)切割，加入分層概念，選擇合適的層級等方式以在簡化計算便于硬件實現(xiàn)的同時提高渲染效果。

1 幾何流水線中的常用算法

在TBR架構(gòu)的嵌入式GPU中，圖形處理過程分為幾何處理過程和像素處理過程，常用的的幾何流水線包括圖元裝配、視見體剔除、背面剔除、裁剪、Tile切割與鏈表建立等操作。幾何流水線結(jié)構(gòu)如圖1所示。其中，幾何流水線位于圖1中虛線框內(nèi)，是幾何處理過程的一部分。圖元裝配操作將頂點數(shù)據(jù)裝配成不同類型的圖元。視見體剔除操作剔除位于視見體外的圖元。背面剔除操作剔除不可見的背面圖元。裁剪操作剔除位于裁剪平面外的圖元。Tile切割操作將屏幕劃分多個Tile并產(chǎn)生鏈表。

圖1 幾何流水線結(jié)構(gòu)

1.1 背面剔除與視見體剔除算法

在計算機圖形學中，定義一個三維多邊形時，需要同時定義正面和背面。對于觀察者來說，幾何圖形的背面通常是不可見的。通常情況下，在光柵化前將背面剔除會增加渲染效率。文獻[9]提出了四叉樹的背面剔除算法，該算法計算每個節(jié)點的法向量，并根據(jù)節(jié)點到觀察者的向量和法向量的內(nèi)積進行判斷是否需要背面剔除。文獻[10]在經(jīng)典背面剔除算法基礎上提出一種新算法，忽略頂點坐標的z分量，并且為減輕計算負擔加入位置判定條件，該算法對硬件資源和處理效率有所優(yōu)化。

進行背面剔除的前提是確定正反面，可以通過對圖元指定確定的索引順序，再根據(jù)右手定則來判定這個面是向外還是向內(nèi)。背面剔除算法通常根據(jù)三角形頂點的索引順序來定義正反面。假定對著觀察者的面為正面，其法向量指向觀察者，背面則定義法向量背離觀察者的面。設定法向量與觀察者的夾角為θ，如果法向量與觀察者的夾角-90°≤θ≤90°，則為正面，若夾角不在此范圍內(nèi)，就可以確定當前面為背面。

視見體剔除算法的目的一般是剔除所有頂點都不在視見體內(nèi)的三維圖元[11]。三維圖元的所有頂點坐標都需要與指定視見體的6個側(cè)面進行比較，假設當前有N個圖元，需要18×N次比較計算才能得到剔除結(jié)果，每次比較計算過程都會產(chǎn)生單精度浮點中間變量，共占用32×18×N個比特的存儲量。通常這樣的遍歷的方法計算量比較大[12]。

1.2 裁剪算法

C-S(Cohen-Sutherland)算法是經(jīng)典的線段裁剪算法之一。它基于區(qū)域編碼技術，通過對裁剪線段頂點的區(qū)域編碼進行邏輯運算，判斷頂點與矩形裁剪窗口的位置關系，進而對線段執(zhí)行剔除或保留操作[13]。文獻[14]對C-S算法提出改進，增加了頂點編碼判別條件以減少交點計算。

S-H(Sutherland-Hodgman)算法是一種針對多邊形的裁剪算法。它基于裁剪窗口的每條邊界逐個對多邊形進行裁剪[15]。為減少S-H算法的冗余計算，文獻[16]對S-H算法進行改進，在循環(huán)中加入判別條件，達到條件時跳出循環(huán)，并用Matlab軟件對改進后的算法進行驗證。文獻[17]提出了基于S-H算法的優(yōu)化算法，在引入入點和出點概念的基礎上，對裁剪后保留的部分進行標記，在裁剪過程中將入點和出點按多邊形方向排列，最后將其連接得到封閉多邊形。

包圍盒算法是一種先將圖形包裹在規(guī)則簡單的封閉空間內(nèi)再進行裁剪的算法[18]。文獻[19]針對三維線段的包圍盒改進算法，構(gòu)建了由12個45°平面組成的包圍盒，同時將三維線段投影到二維平面后進行二次編碼，利用編碼分區(qū)完成幾何變換，提高了裁剪效率。文獻[20]提出了基于八叉樹的包圍盒算法，該算法將每個節(jié)點劃分8個子節(jié)點后進行八叉樹的遍歷，當節(jié)點不在包圍盒內(nèi)則所有子節(jié)點無需遍歷就可判斷為不可見。

1.3 Tile-Based渲染結(jié)構(gòu)

由于受到帶寬、功耗等限制，嵌入式GPU一般采用TBR架構(gòu)渲染場景。與立即渲染不同的是，TBR在圖元裝配之后將渲染場景劃分為多個相同大小的Tile。

Tile劃分示意圖如圖2所示。圖2中的有效區(qū)域被劃分成多個固定大小且相互不重疊的塊，一個塊稱為一個Tile。通過將屏幕分成多個小塊，一次只渲染一個小塊中的數(shù)據(jù)，渲染完成后再寫入GPU外部的存儲器當中，這樣就減少了讀寫存儲器的頻率，進而減少了功耗并降低了對存儲器帶寬的需求。

圖2 Tile劃分示意圖

2 算法設計

2.1 視見體剔除算法

為了適合硬件實現(xiàn)，本文視見體剔除算法包括如下3個步驟。

步驟1將三維圖元與z方向上的近裁剪平面和遠裁剪平面進行比較，若圖元的所有頂點坐標的z分量不在遠近裁剪平面之間，則確定該圖元需要被剔除，否則執(zhí)行步驟2操作。

步驟2將三維圖元正投影到二維平面，頂點坐標的x，y分量不會改變，投影前頂點坐標V與投影后頂點坐標V′的矩陣形式變換關系為

其中：xV、yV、zV分別表示頂點V坐標的x、y、z軸分量；wV表示頂點V變換后的z軸分量。

步驟3將正投影后形成的二維圖元的頂點坐標的x和y分量與視見體的左裁剪平面、右裁剪平面、上裁剪平面和下裁剪平面進行比較，剔除掉完全位于視見體在xoy平面上投影窗口外側(cè)的圖元，其它圖元保留。

相較于遍歷的方法，所提算法可以先通過z方向的比較剔除掉部分不可見圖元，無需再進行的比較，從而減輕了計算負擔。與傳統(tǒng)的視見體剔除算法相比較，提出的算法的主要優(yōu)點是所使用的存儲空間較少。若三維圖元的所有坐標的z分量位于視見體遠近裁剪平面之外，則N個圖元只需要6N次比較就可以得到剔除結(jié)果，此外，只需要存儲剔除標志位而并非邊界值，故中間變量只需要1 bits，共占用1×6×N比特的存儲。事實上，并非所有的三維圖元都由算法中的步驟1剔除，從而導致比較次數(shù)最多不會超過傳統(tǒng)算法的比較次數(shù)為18×N，但中間存儲卻僅占用18×Nbits存儲空間。

2.2 背面剔除算法

2.2.1 算法優(yōu)化原理

背面剔除的目的是根據(jù)用戶的設置，剔除不可見的三角形。如果直接用經(jīng)典的背面剔除算法去剔除背面，首先需要計算法向量，接著計算三角形與觀察者之間的方向向量，最后還需要計算二者點積，算法實現(xiàn)的復雜度較高。事實上，只要通過計算法向量就可以判定三角形是否被剔除。

兩個向量與構(gòu)成一個平面，其叉乘為法向量。定義指向觀察者的法向量為正，背離觀察者的法向量為負，則根據(jù)法向量的指向，即可判定當前處理的三角形是正面還是背面。利用OpenGL ES(openGL for embedded systems)指定順時針或逆時針為正面圖元，同時指定剔除正面或背面圖元，三角形剔除判斷規(guī)則如表1所示。

表1 三角形剔除判斷規(guī)則

2.2.2 算法優(yōu)化實現(xiàn)

在幾何處理階段，頂點采用單精度浮點數(shù)表示。如果能判定輸入的三角形3個頂點之間的位置關系，就可以判定大部分三角形應該被丟棄還是保留。基于此考慮，提出使用查找表法進行判定。

3個點之間是否構(gòu)成一個三角形的關系，以及構(gòu)成什么三角形關系總共有4種情形：1)3個點不構(gòu)成三角形；2)3個點構(gòu)成順時針三角形；3)3個點構(gòu)成逆時針三角形；4)無法確定3個點是否可以構(gòu)成三角形。

查找表的原理為，對于一個二維三角形圖元，窮舉三角形3個頂點的x和y坐標分量數(shù)值之間的大小比較關系，將這些關系一一列舉便組織成一張查找表。利用查找表可以判定輸入的3個頂點是否構(gòu)成三角形。如果不能構(gòu)成三角形，則刪除這3個頂點；如果能構(gòu)成三角形，則根據(jù)軟件設置剔除正面或者背面。當丟棄剔除面時，無論是逆時針還是順時針，都無須計算三角形面積。對于無法確定是否構(gòu)成三角形的3個頂點，也就無法判斷其對應正面或背面圖元。此時，需要進一步通過矩陣運算三角形的面積數(shù)值，已決定是否需要剔除。

可以看出，使用查找表，能夠剔除不需要計算三角形面積的情況，只有無法判定的情況和保留的情況下，才需要再進一步通過矩陣運算三角形的面積數(shù)值，這種操作方式能夠減少計算量，從而降低功耗。

2.3 小三角形的實現(xiàn)

2.3.1 小三角形與多重采樣

在圖形學中，每個像素點不僅僅表示位置，而是具有一定面積的單位矩形網(wǎng)格。判定圖元是否覆蓋某個像素點是通過該圖元是否覆蓋像素點的中心位置坐標(即采樣點)決定的，如果輸入幾何流水線的三角形圖元較小，按照正常的采樣，該三角形可能被忽略，從而造成被渲染的圖形細節(jié)丟失，此時，就需要采用多重采樣方法。多重采樣方法將圖元的采樣點細分為多個子采樣點，通過細分，原本只由一個采樣點決定是否覆蓋一個像素，而現(xiàn)在由多個子采樣點決定，正常采樣與多重采樣示意圖如圖3所示。

圖3 正常采樣與多重采樣示意

可以看出，當采用正常采樣方法時，圖3(a)中的三角形圖元將被忽略，而采用多重采樣方法時，該三角形圖元不會被完全忽略。

考慮到顯示某些位置特殊但希望被最終渲染的小三角形，在生成包圍盒之前對小三角形圖元進行多重采樣。

2.3.2 利用邊函數(shù)保留多重采樣點

判斷多重采樣開啟時子采樣點是否被覆蓋需要基于三角形圖元的邊函數(shù)。三角形的邊所在的直線可以用邊函數(shù)ax+by+c=0來表示，其中a、b、c表示該條邊函數(shù)的系數(shù)。由于三角形的每條邊都是具有方向的矢量且方向統(tǒng)一，因此，判斷某個點的位置是位于三角形內(nèi)側(cè)還是外側(cè)，只需要將該點坐標代入圖元的3條邊的邊函數(shù)中，通過判斷函數(shù)值的正負來確定點與三角形3條邊的位置信息。利用邊函數(shù)的多重采樣點保留的具體步驟如下。

步驟1根據(jù)三角形圖元尺寸判斷是否符合小三角形的尺寸條件，符合條件則進入步驟2，否則終止。

步驟2對三角形圖元的每條邊進行邊函數(shù)系數(shù)的計算。

步驟3根據(jù)多重采樣的采樣類型，設置采樣點位置。

步驟4根據(jù)步驟3中計算得到的邊函數(shù)值的正負判斷采樣點是否被覆蓋，當數(shù)值為負或為0表示采樣點位于圖元內(nèi)部或邊界上，產(chǎn)生覆蓋標志位。

多重采樣算法對光柵化后片元的顏色信息產(chǎn)生影響，以四采樣為例，四采樣顏色調(diào)和示意圖如圖4所示。正常采樣的1個像素點對應多重采樣的4個子采樣點。若多重采樣的1個子采樣點被覆蓋，則可以用1/4的圖元顏色信息來調(diào)和像素的顏色。

圖4 四采樣顏色調(diào)和示意

2.4 包圍盒裁剪與剔除

包圍盒是指與裁剪窗口的邊界對齊，包圍住一個圖元的最小矩形框。當圖元被包圍盒包裹住，接下來只需要判斷包圍盒與裁剪平面之間的關系。相較于需要對圖元逐邊裁剪的算法，包圍盒裁剪只需要通過圖元的頂點坐標確定包圍盒的最大和最小尺寸。當處理具有較多邊的多邊形時，包圍盒的優(yōu)勢就會體現(xiàn)出來。

若視口外的圖元無法被觀察到，需要將二維包圍盒不在視口范圍內(nèi)的部分剔除。視口剔除操作示意圖如圖5所示。

圖5 視口剔除操作示意

1)若包圍盒完全位于視口范圍內(nèi)，則無需剔除操作，包圍盒被完全保留作為新的包圍盒，如圖5(a)所示。

2)若視口范圍完全位于包圍盒內(nèi)，則需要剔除包圍盒位于視口范圍外的部分，將視口作為新的包圍盒，如圖5(b)所示。

3)若包圍盒完全位于視口范圍外，則需要將包圍盒完全剔除，無需對該包圍盒內(nèi)圖元繼續(xù)渲染，如圖5(c)所示。

4)若包圍盒部分位于視口范圍內(nèi)，則需要剔除包圍盒位于視口范圍外的部分，留下的部分作為新的包圍盒，如圖5(d)所示。

更新的包圍盒還需要判斷其與裁剪窗口的位置關系。若裁剪窗口外的圖元無法被觀察到，則需要將不在裁剪窗口內(nèi)的部分剔除，剔除方法與視口剔除操作相同。

2.5 Tile分層切割及鏈表建立

2.5.1 Tile分層切割

設計Tile的最小尺寸為16×16個像素點，并將其定義為Tile的第0層級，以此為單位劃分邏輯屏幕，此時包圍盒邊界坐標對應此層級下的坐標值如圖6所示。圖中的Tile共有8個可選層級編號，分別對應的Tile尺寸為(16×2i)×(16×2i)個像素點，其中i=0,1,2,…,7表示Tile層級編號。

圖6 第0層級的Tile坐標

由每個Tile層級編號對應的單位坐標確定該層級下包圍盒的邊界坐標值，再由邊界坐標值確定覆蓋的每個Tile坐標。設計中對不同Tile層級設定權(quán)值，根據(jù)圖元的大小和包圍盒在不同層級編號對應的面積值，綜合權(quán)值數(shù)據(jù)，得到最合適的Tile層級編號。

2.5.2 多邊形鏈表建立

不同Tile層級中的每一個Tile對應一個多邊形鏈表，Tile的層級不同，對應的多邊形鏈表的存儲空間起始地址不同。根據(jù)Tile層級編號可以匹配到對應多邊形鏈表存儲空間。

Tile層級確定后，還需要根據(jù)包圍盒覆蓋的Tile坐標確定對應的多邊形鏈表索引。索引的計算公式為

n=xT+yTwx

其中：xT，yT表示圖元覆蓋的Tile坐標；wx表示在當前Tile層級編號對應的單位坐標下x方向的最大Tile數(shù)。

根據(jù)多邊形鏈表索引計算可以得到對于整個多邊形鏈表結(jié)構(gòu)。多邊形鏈表的編號計算公式為

N=nbe+xT+yTwx

其中nbe表示初始索引。Tile層級編號為0的多邊形鏈表索引范圍為0～511，以此類推，Tile層級編號為1的多邊形鏈表起始索引為512。

3 硬件電路的實現(xiàn)

幾何流水線用于將頂點信息通過剔除、裁剪等操作最終轉(zhuǎn)換為多邊形鏈表，主要包含頂點抓取模塊、圖元裝配模塊、包圍盒模塊、Tile切割模塊和多邊形鏈表構(gòu)建及寫回模塊。幾何流水線的整體框架示意如圖7所示。

圖7 幾何流水線整體框架

其中，頂點抓取模塊接收幾何流水線開始工作的有效信號，根據(jù)不同的繪制模式、分配的起始地址和分支偏移去主存抓取數(shù)據(jù)。若繪制模式為Draw Elements，頂點抓取模塊將根據(jù)地址將頂點數(shù)據(jù)的索引讀回，再依據(jù)索引從主存讀回頂點數(shù)據(jù)，當繪制模式為Draw Arrays，頂點數(shù)據(jù)將根據(jù)地址讀回頂點數(shù)據(jù)。

圖元裝配模塊根據(jù)圖元類型裝配頂點坐標信息，得到相對應的圖元，再將圖元拆分成基本圖元并傳送給包圍盒模塊。

包圍盒模塊完成剔除、裁剪等操作后，使用最小的矩形框包裹住圖元并將矩形框的邊界信息送至Tile切割模塊。包圍盒模塊接收圖元裝配模塊傳來的圖元頂點坐標和基本圖元類型，首先會進行視見體剔除。視見體剔除模塊根據(jù)OpenGL指定的視見體邊界信息判斷基本圖元的頂點坐標數(shù)據(jù)是否在視見體內(nèi)。若圖元頂點數(shù)據(jù)位于視見體內(nèi)則將頂點信息送至背面剔除模塊。背面剔除模塊可以通過輸入頂點坐標數(shù)據(jù)和頂點索引信息，計算得到的圖元為正面圖元還是背面圖元。通常情況下，會對背面圖元進行剔除，未被剔除的圖元將傳輸給基于邊函數(shù)的小三角形處理模塊?；谶吅瘮?shù)的小三角形進行處理時首先需要對于三角形的大小進行限制，較大三角形無須進行本模塊的處理，而對于小三角形則采用多重采樣算法和邊函數(shù)算法進行處理。處理后還需要進行裁剪，對裁剪窗口外的部分進行剔除。

Tile切割模塊的作用是從給定的不同Tile層級中找到最合適的層級。該模塊接收來自包圍盒模塊的以16×16 個Tile為單位坐標的包圍盒邊界坐標信息，同時，從頂點著色器獲取當前有效的層級標志信息。Tile切割模塊首先根據(jù)包圍盒在不同Tile的面積、對應的權(quán)重以及當前所處的層級信息計算出最合適的層級。其次，將最合適的層級下的包圍盒邊界部分覆蓋的Tile拆分為2×2個相同的子Tile，并將包圍盒是否覆蓋其邊界的每個Tile對應的子Tile用4位的標志位coverage表示。最后，Tile切割模塊將選定最合適的層級編號、在此層級下的包圍盒覆蓋的每個Tile的坐標以及對應的子Tile標志位coverage傳輸給多邊形鏈表構(gòu)建及寫回模塊。

多邊形鏈表構(gòu)建及寫回模塊接收圖元頂點坐標、Tile坐標、Tile的層級編號和Tile的coverage掩碼信息，將這些信息發(fā)送給數(shù)據(jù)壓縮模塊，將其壓縮為包含上述信息且位寬格式相同的鏈表數(shù)據(jù)。壓縮完成的數(shù)據(jù)需要地址計算模塊根據(jù)基地址信息為其分配地址，將分配好的地址和其對應的數(shù)據(jù)傳輸給寫回模塊并完成寫回操作。地址計算模塊將每個Tile對應的起始地址根據(jù)Tile編號存入多邊形鏈表Cache中，然后將每個Tile的起始地址都寫入Tile地址存儲空間。

4 流水線性能的測試與驗證

為測試幾何流水線的性能，將圖形處理器電路下載到VU440開發(fā)板上，編寫OpenGL ES 2.0應用程序，對經(jīng)典的小鳥、艾希、蘋果、金克斯和亞索等5種圖形學測試場景進行測試，以測試圖形處理器的功能正確性、穩(wěn)定性以及效率。這5種經(jīng)典測試場景中包含大量的三角形圖元，涉及復雜計算，適合用于測試圖形處理器的性能。各測試場景對應的三角形數(shù)和幀率如表2所示。測試結(jié)果如圖8所示。

表2 圖形處理器性能測試

圖8 測試結(jié)果

測試結(jié)果表明，所提設計方法可以正確處理不同的圖形，通過渲染含有不同三角形數(shù)的圖形，得到了較高的幀率，同時設計的幾何流水線可以穩(wěn)定而正確工作。

5 結(jié)語

研究了TBR架構(gòu)中幾何流水線的相關算法，優(yōu)化了視見體剔除與背面剔除算法，采用超采樣處理小三角形，避免小三角形丟失，使渲染場景更加逼真，加入包圍盒裁剪與Tile分層設計，提高了圖形處理的性能。在此基礎上，實現(xiàn)了一種GPU中的幾何流水線并將其嵌入到整個GPU設計中，在VU440開發(fā)板上驗證了GPU設計，并用OpenGL ES 2.0編寫經(jīng)典的圖形學測試場景，結(jié)果表明，所提的幾何流水線設計可以穩(wěn)定工作。