趙建龍， 李 濤， 董中華， 馮臻夫

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

0 引 言

在圖形渲染管線中，光柵化是將頂點信息通過插值掃描轉(zhuǎn)換為像素片段的核心硬件，是圖形處理器的重要組成部分[1]。光柵化過程直接影響著整個圖形處理器繪制效率和渲染質(zhì)量。在光柵化過程中，內(nèi)部可視部分的填充是影響光柵化速度和效率的主要因素。為了提高填充效率和質(zhì)量，當(dāng)前的研究方向主要有兩方面：第一是優(yōu)化算法，減少像素遍歷數(shù)，降低計算量從而加快運算速度；第二是建立多條掃描線程，利用多線程并行處理填充過程[2]。針對以上兩個方向，本文在傳統(tǒng)邊函數(shù)單線程掃描算法的基礎(chǔ)上提出了雙向四行并行的掃描方式，優(yōu)化掃算法，增加線程數(shù)目，提高填充效，提高光柵化速率。

1 光柵化算法

1.1 算法研究

光柵化算法主要分為插值算法和掃描算法。

插值算法包括平面插值算法、透視校正插值算法和重心插值算法[3]。本設(shè)計采用重心坐標(biāo)系的透視校正插值算法，相比平面插值算法，重心插值計算復(fù)雜度低，利于硬件實現(xiàn)，同時滿足屬性校正需求[4]。

基于邊函數(shù)的掃描算法是通過邊界函數(shù)來判斷該像素點是否在三角形內(nèi)。除此之外，還需要確定遍歷三角形的掃描方式，其中最簡單的掃描方式就是全屏掃描，從左往右，從下往上對整個屏幕區(qū)域進(jìn)行掃描，這種方式硬件容易實現(xiàn)，但是掃描區(qū)域較大，像素掃描效率較低；常用矩形框掃描方式是通過三角形在x軸、y軸上的最大值和最小值，建立起三角形的包圍框，該掃描方式相對于全屏幕掃描減小了掃描區(qū)域，提高了掃描效率；中心線掃描方式是通過三角形中心線向左右兩邊掃描直到三角形邊界，該掃描方式需要對三角形進(jìn)項特殊處理，硬件設(shè)計復(fù)雜。本設(shè)計在此基礎(chǔ)上進(jìn)行算法優(yōu)化，采用雙向四行并行掃描方式，增加線程數(shù)目，減少像素遍歷數(shù)，提高像素填充率。

1.2 算法改進(jìn)

1.2.1 基于邊函數(shù)的雙向四行并行掃描算法

對A點坐標(biāo)(Xa,Ya)，B點坐標(biāo)(Xb,Yb)，C點坐標(biāo)(Xc,Yc)按逆時針排序確定Y值最小點為掃描初始點，陰影部分為掃描區(qū)域，掃描方式為雙向四行并行掃描，如圖1所示。

圖1 掃描方式

三角形從A點開始雙向四行并行掃描，通過三角形的邊界函數(shù)值判斷像素點是否在三角形內(nèi)，若左右像素點都在三角形內(nèi)，左右循環(huán)掃描；若左方向像素點不在三角形內(nèi)，左方向停止掃描，右方向繼續(xù)掃描；若左右方向像素點都不在三角形內(nèi)，則本行像素掃描完成，進(jìn)行換行掃描。如此循環(huán)，掃描至三角形的頂部，完成整個三角形的掃描。該掃方式能有效地減少遍歷的像素個數(shù)，提高填充效率。

1.2.2 基于重心坐標(biāo)系的透視校正插值算法

三角形ABC內(nèi)部任意一點P坐標(biāo)為(X,Y)。P點與三個頂點相連將三角形分割成三個小三角形，其中三角形ABC的面積為S，小三角形面積分別為Sa,Sb,Sc。三角形重心坐標(biāo)插值如圖2所示[5]。

圖2 三角形重心坐標(biāo)插值

三角形的面積公式

S=[(Xa-Xc)(Yb-Y)+(Xb-Xa)(Yc-Ya)]/2

(1)

插值系數(shù)[6]

m=[(Xa-Xc)(Y-Ya)+(X-Xa)(Yc-Ya)]/S

(2)

n=[(Xa-X)(Yb-Ya)+(Xb-Xa)(Y-Ya)]/S

(3)

p=1-m-n

(4)

插值系數(shù)m，n，p表示了每個頂點的屬性對三角內(nèi)部區(qū)域的貢獻(xiàn)值，W分量是輔助齊次變換方便而引入的，變換后如果不進(jìn)行校正除法規(guī)范化，投到屏幕的圖像是代入了投影縮放的。定義1/W=[1/Wa,1/Wb,1/Wc]為屏幕坐標(biāo)系到視窗坐標(biāo)系的矯正因子，通過插值系數(shù)和頂點屬性進(jìn)行加權(quán)求和以及校正除法規(guī)范化，屬性校正插值公式為式(5)所示[7,8]

(5)

2 硬件實現(xiàn)

2.1 硬件電路的總體設(shè)計

三角形光柵化模塊包括命令解析模塊(CMD_DECODE)，頂點排序模塊(VERTEX_SORT)，初始化參數(shù)計算模塊(PARAMETER_INITIAL)，雙向四行并行掃描模塊(LINE_SCAN)以及屬性插值(PROPERTY_CALCULATE)。光柵化加速器硬件整體結(jié)構(gòu)如圖3所示。

圖3 光柵化加速器硬件整體結(jié)構(gòu)圖

2.2 命令解析模塊

本模塊接收97位命令，對命令進(jìn)行譯碼，最高位為1代表指令，為0代表數(shù)據(jù)。通過命令解析模塊將三角形的頂點數(shù)據(jù)下發(fā)到頂點排序模塊。

2.3 頂點排序模塊

2.4 初始化參數(shù)計算模塊

初始化參數(shù)計算模塊分為兩級，第一級采用流水設(shè)計，計算X坐標(biāo)和Y坐標(biāo)的差值，求出三角形三條邊的邊線方程，完成三角形面積計算并送入除法器，最后將校正因子W送入除法器，實現(xiàn)紋理坐標(biāo)的校正。

第二級主要計算重心校正插值初始化參數(shù)，將接收到的頂點屬性由重心校正插值算法，計算出插值系數(shù)m，n，p，紋理校正因子W以及各個屬性在X方向Y方向的偏移。硬件電路圖如圖4所示。

圖4 初始化硬件電路

2.5 雙向四行并行掃描模塊

本模塊采用雙向四行并行掃描，從Y值最小點開始，迭代偏移到Y(jié)值最大點，直到三角形掃描結(jié)束。本模塊接收到初始化參數(shù)后，四個行掃描器根據(jù)自己的ID編號，進(jìn)行自己本行像素點的掃描。雙向四行并行掃描模塊結(jié)構(gòu)如圖5所示。

圖5 雙向四行并行掃描模塊結(jié)構(gòu)

控制雙向掃描以及判斷行掃描是否結(jié)束采用了6級狀態(tài)機(jī)，狀態(tài)轉(zhuǎn)移圖如圖6所示。1)SCAN_EN_START:狀態(tài)機(jī)使能開關(guān)，如果行掃描開始，則啟用狀態(tài)機(jī)。2)LEFT_SCAN:左方向掃描啟用。3)RIGHT_SCAN:右方向掃描啟用。4)PIXEL_POS_DETERMINE:根據(jù)邊線方程和邊界條件判斷像素點是否在三角形內(nèi)，對于在三角形內(nèi)部的像素進(jìn)行屬性校正插值計算，其他像素點不進(jìn)行處理。5)PIXEL_OUT:對在三角形內(nèi)部的像素點進(jìn)行屬性輸出。6)STATE_CONTROL:判斷行掃描是否結(jié)束以及控制雙向掃描狀態(tài)。

圖6 掃描控制狀態(tài)轉(zhuǎn)移

2.6 屬性校正插值計算模塊

本模塊主要實現(xiàn)對三角形內(nèi)部像素點的屬性校正插值計算。通過初始化參數(shù)的計算，以及雙向行掃描的狀態(tài)對三角形頂點屬性進(jìn)行迭代運算。主要分為以下四種情形：1)行迭代運算：頂點屬性加Y方向的偏移量。2)左方向迭代運算：頂點屬性減X方向的偏移量。3)右方向迭代運算：頂點屬性加X方向的偏移量。4)紋理校正運算：進(jìn)行校正除法運算。

3 仿真驗證

本設(shè)計采用Modelsim工具進(jìn)行功能仿真，將光柵化產(chǎn)生的像素片段信息打印到文本中，通過軟件對文本信息的讀取顯示，判斷光柵化結(jié)果是否正確。搭建驗證平臺，OpenGL測試程序以命令流方式通過PC機(jī)經(jīng)PCIE主橋?qū)懭牖贔PGA的GPU原形中的顯存中，將光柵化結(jié)果通過VGA顯示，光柵化結(jié)果如圖7所示[10]。

圖7 光柵化顯示結(jié)果

圖7光柵化結(jié)果表明，圖形顯示完整，光柵化結(jié)果正確。不同形狀三角形性能測試結(jié)果如表1所示，掃描像素點個數(shù)平均減少17 450個，所需時鐘周期數(shù)平均減少112 086個，性能提升70.05 %。

表1 性能對比表

4 結(jié)束語

本文在基于重心坐標(biāo)系的透視校正算法下，采用雙向四行并行掃描方式，實現(xiàn)了光柵化加速器的硬件設(shè)計。通過FPGA平臺對整個硬件電路的功能驗證，結(jié)果表明:本文設(shè)計優(yōu)化后的掃描算法和多線程的硬件設(shè)計減少了遍歷的像素數(shù)，提高了光柵化速率，滿足快速實時的光柵化要求。