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

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

0 引 言

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

1 光柵化算法

1.1 算法研究

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

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

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

1.2 算法改進(jìn)

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

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

圖1 掃描方式

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

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

三角形ABC內(nèi)部任意一點(diǎn)P坐標(biāo)為(X,Y)。P點(diǎn)與三個(gè)頂點(diǎn)相連將三角形分割成三個(gè)小三角形，其中三角形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表示了每個(gè)頂點(diǎn)的屬性對(duì)三角內(nèi)部區(qū)域的貢獻(xiàn)值，W分量是輔助齊次變換方便而引入的，變換后如果不進(jìn)行校正除法規(guī)范化，投到屏幕的圖像是代入了投影縮放的。定義1/W=[1/Wa,1/Wb,1/Wc]為屏幕坐標(biāo)系到視窗坐標(biāo)系的矯正因子，通過(guò)插值系數(shù)和頂點(diǎn)屬性進(jìn)行加權(quán)求和以及校正除法規(guī)范化，屬性校正插值公式為式(5)所示[7,8]

(5)

2 硬件實(shí)現(xiàn)

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

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

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

2.2 命令解析模塊

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

2.3 頂點(diǎn)排序模塊

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

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

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

圖4 初始化硬件電路

2.5 雙向四行并行掃描模塊

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

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

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

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

2.6 屬性校正插值計(jì)算模塊

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

3 仿真驗(yàn)證

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

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

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

表1 性能對(duì)比表

4 結(jié)束語(yǔ)

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