杜慧敏，季凱柏，蔣忭忭，郭沖宇

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

?

重心坐標(biāo)插值的三角形著色算法硬件實(shí)現(xiàn)

杜慧敏，季凱柏，蔣忭忭，郭沖宇

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

針對三角形的平滑著色技術(shù)，設(shè)計(jì)并實(shí)現(xiàn)一種三角形顏色插值的硬件加速器。根據(jù)三角形建立單元輸入的三角形頂點(diǎn)數(shù)據(jù)，利用邊界方程計(jì)算三角形的面積以及面積倒數(shù)。通過掃描轉(zhuǎn)化模塊篩選出每個(gè)三角形覆蓋的有效像素塊，最后利用三角形建立單元得到的邊界方程值與三角形面積倒數(shù)值，通過插值模塊實(shí)現(xiàn)經(jīng)過掃描轉(zhuǎn)換模塊處理后的三角形內(nèi)所有片元的顏色插值。測試結(jié)果表明，該加速器最大工作頻率可達(dá)約為222.2 MHz，能夠?qū)崿F(xiàn)嵌入式GPU中圖形平滑著色的要求。

重心坐標(biāo)插值；平滑著色；嵌入式GPU

嵌入式圖形處理器(Graphic Processing Unit, GPU)可繪制真實(shí)感的三維圖形, 提高用戶的視覺效果，已經(jīng)成為圖形處理技術(shù)的研究重點(diǎn)之一[1]。

在嵌入式GPU圖形流水線中，三角形著色通常是根據(jù)3個(gè)頂點(diǎn)的顏色，通過插值的方式計(jì)算出光柵化后每個(gè)片元的顏色，以便其后對片元進(jìn)行其他處理，形成屏幕上顯示的像素[2-3]。三角形光柵化及片元的屬性插值運(yùn)算量非常大，需要通過高性能硬件加速器實(shí)現(xiàn)，才能保證GPU的性能。三角形屬性插值有許多種方法，最基本的屬性插值算法主要有平面插值算法、透視校正插值算法和重心坐標(biāo)插值算法[4]。其中,重心坐標(biāo)插值算法是平面插值算法的一種優(yōu)化改進(jìn)，計(jì)算復(fù)雜度相對低，更適合硬件高效實(shí)現(xiàn)[5]。

本文擬通過分析重心坐標(biāo)插值算法，設(shè)計(jì)并實(shí)現(xiàn)一種三角形顏色插值的硬件加速器。利用光柵化階段三角形三條邊的邊界函數(shù)值和片元坐標(biāo)，計(jì)算三角形內(nèi)重心坐標(biāo)插值所需要的參數(shù)，從而對三角形內(nèi)的片元進(jìn)行顏色插值，以期滿足嵌入式GPU中圖形平滑著色的要求。

1　算法概述

1.1三角形重心坐標(biāo)

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

三角形abc內(nèi)任意P點(diǎn)坐標(biāo)(x,y)可表示為[6]

(1)

(2)

根據(jù)P點(diǎn)的邊界函數(shù)，可將式(2)化簡為[7]

(3)

其中l(wèi)ca為三角形ca邊的直線方程，其中l(wèi)ab為三角形ab邊的直線方程，且三角形內(nèi)任意P點(diǎn)重心坐標(biāo)α，β，γ滿足以下關(guān)系

α+β+γ=1。

(4)

因此，只需計(jì)算其中任意兩個(gè)，利用式(4)便可快速的計(jì)算出第三個(gè)插值系數(shù)。

1.2基于重心坐標(biāo)算法的顏色插值

若已知三角形abc的3個(gè)頂點(diǎn)的R、G、B顏色值可表示[8]為

(5)

其中Ca為三角形中a點(diǎn)的顏色值，Cb為三角形中b點(diǎn)的顏色值，Cc為三角形中c點(diǎn)的顏色值，CP為三角形中P點(diǎn)的顏色值。

根據(jù)三角形內(nèi)任意P點(diǎn)重心坐標(biāo)α，β，γ，可將三角形abc內(nèi)任意P點(diǎn)的顏色值CP[9]表示為

CP=αCa+βCb+γCc。

(6)

根據(jù)式(5)和式(6)可知，三角形內(nèi)任意P點(diǎn)的R,G,B的顏色分量可以表示為

(7)

由式(3)可知，在計(jì)算三角形內(nèi)任意一點(diǎn)的重心坐標(biāo)時(shí)，參數(shù)A對于一個(gè)特定的三角形圖元而言是固定的，因此只需要計(jì)算一次，利用光柵化時(shí)計(jì)算出的邊函數(shù)可以快速地計(jì)算三角形的重心坐標(biāo)，縮減了整個(gè)插值算法的計(jì)算量，從而能夠加快顏色插值的速度。

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

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

三角形光柵化與重心坐標(biāo)插值硬件電路頂層主要包括面積計(jì)算模塊、面積倒數(shù)計(jì)算模塊、重心坐標(biāo)計(jì)算模塊和顏色插值模塊。硬件電路的總體設(shè)計(jì)如圖2所示。

圖2　硬件電路總體設(shè)計(jì)

對于計(jì)算三角形內(nèi)任意一點(diǎn)的顏色值, 將進(jìn)行3路并行處理。

熊珍琴[25]等基于Fluent軟件，采用RNG-ε非穩(wěn)態(tài)模型模擬了重力影響下的空氣源熱泵熱水器在加熱過程中的水箱溫度分布情況。仿真結(jié)果與實(shí)驗(yàn)非常一致，驗(yàn)證了該模型的可靠性，并定性分析了改善水箱盤管布置的方向，為水箱及其同類設(shè)備的研發(fā)和優(yōu)化提供了參考。

2.2面積計(jì)算模塊

采用流水結(jié)構(gòu)實(shí)現(xiàn)面積的計(jì)算。該流水線結(jié)構(gòu)計(jì)算三角形的面積需要有5個(gè)浮點(diǎn)a×b功能的加法單元和2個(gè)a×b功能的浮點(diǎn)乘法單元。具體的硬件結(jié)構(gòu)如圖3所示。其中，MUL代表32位的浮點(diǎn)乘法器，ADD代表32位的浮點(diǎn)加法器。

圖3　面積計(jì)算的硬件結(jié)構(gòu)

2.3面積倒數(shù)計(jì)算模塊

結(jié)合二次多項(xiàng)式逼近算法[10-11]實(shí)現(xiàn)三角形建立單元中三角形面積倒數(shù)的計(jì)算，硬件結(jié)構(gòu)如圖4所示。

圖4　三角形面積倒數(shù)計(jì)算的硬件結(jié)構(gòu)

三角形的面積用32bit單精度浮點(diǎn)數(shù)格式表示，記為F，則三角形面積的倒數(shù)可表示為

(8)

由式(8)可知，F(xiàn)的倒數(shù)計(jì)算主要由符號位的計(jì)算、尾數(shù)位的計(jì)算以及指數(shù)位的計(jì)算3部分組成。符號位和指數(shù)位的處理比較簡單，且易于硬件實(shí)現(xiàn)，在硬件設(shè)計(jì)中可以和尾數(shù)位的計(jì)算進(jìn)行并行處理，不影響電路整體的速度和性能，而尾數(shù)位的計(jì)算是設(shè)計(jì)中最為關(guān)鍵和復(fù)雜的。 尾數(shù)處理的關(guān)鍵在于計(jì)算尾數(shù)的倒數(shù)，通過將尾數(shù)區(qū)間縮小到[1,2)，利用多項(xiàng)式逼近實(shí)現(xiàn)尾數(shù)的倒數(shù)，減少了計(jì)算復(fù)雜度。

2.3.1尾數(shù)位的倒數(shù)計(jì)算

尾數(shù)位為nbit的二進(jìn)位小數(shù)(包含1位隱藏位)，其范圍在[1,2)之間。把X分解為高位X1和低位X2兩部分，其中高位X1占mbit，低位X2占n-mbit，具體分解如圖5所示。

圖5　尾數(shù)的分解

由圖5可知，X1=[x1x2…xm]，X2=[xm+1xm+2…xn]×2-m，將在歸一化的[1,2)區(qū)間內(nèi)分為2m段,每一段的長度為2-m，其中尾數(shù)的高m位決定分段的個(gè)數(shù)。在每一分段區(qū)間上進(jìn)行二次多項(xiàng)式逼近,則任意一個(gè)分段X1≤X≤X1+2-m，在一定誤差范圍內(nèi)可以用二次多項(xiàng)式近似表示為

f(X)≈AX2+BX+C。

(9)

尾數(shù)倒數(shù)計(jì)算模塊主要由查找表、平方運(yùn)算器和2個(gè)乘法融合樹組成，硬件結(jié)構(gòu)如圖6所示。

圖6　尾數(shù)倒數(shù)計(jì)算的硬件結(jié)構(gòu)

2.3.2階碼的調(diào)整

已知輸入的三角形面積為一個(gè)正浮點(diǎn)數(shù)(F)，則該浮點(diǎn)的倒數(shù)可以表示為

(10)

2.4重心坐標(biāo)計(jì)算模塊

重心坐標(biāo)計(jì)算模塊主要實(shí)現(xiàn)三角形內(nèi)片元的重心坐標(biāo)計(jì)算。其計(jì)算過程如下所示。

第1階段利用光柵化算出的邊函數(shù)(lca，lab)是32位浮點(diǎn)數(shù)，該模塊浮點(diǎn)乘加運(yùn)算較多，為減少硬件資源開銷，保證計(jì)算重心坐標(biāo)時(shí)參數(shù)lca和lab的精度滿足2-16，仿照標(biāo)準(zhǔn)IEEE單精度格式自定義浮點(diǎn)數(shù)格式：浮點(diǎn)數(shù)用24位表示，其中1位符號位S，7位階碼位E,16位尾數(shù)位F，如圖7所示。

圖7　自定義浮點(diǎn)格式

該浮點(diǎn)格式表示的值為

V=(-1)S×2(E-63)×1.F。

(11)

第2階段完成重心坐標(biāo)β，γ的計(jì)算。需要進(jìn)行2次浮點(diǎn)乘法運(yùn)算。

第3階段完成α的計(jì)算，需要進(jìn)行2次浮點(diǎn)加法運(yùn)算。硬件結(jié)構(gòu)如圖8所示。

圖8　重心坐標(biāo)產(chǎn)生的模塊

2.5顏色插值模塊

顏色插值模塊主要實(shí)現(xiàn)了三角形內(nèi)片元的顏色插值計(jì)算。為了縮短三角形內(nèi)片元顏色值的運(yùn)算時(shí)間，在已知三角形3個(gè)頂點(diǎn)的顏色值R,G,B分量及三角形內(nèi)片元的重心坐標(biāo)的條件下，采用流水線結(jié)構(gòu)實(shí)現(xiàn)三角形內(nèi)片元的顏色值的計(jì)算，如圖9所示。其中ADD表示24位的浮點(diǎn)加法器，MUL表示24位的浮點(diǎn)乘法器。

圖9　顏色插值流水線結(jié)構(gòu)

3　測試結(jié)果與分析

通過分析基于邊函數(shù)的光柵化和重心插值算法，設(shè)計(jì)并實(shí)現(xiàn)一種三角形顏色插值的硬件加速器，并在Xilinx的ZC706開發(fā)平臺上移植了Linux操作系統(tǒng)，在Linux操作系統(tǒng)下使用OpenGL ES語言編寫簡單的圖形，進(jìn)一步對算法進(jìn)行了驗(yàn)證。

基于重心坐標(biāo)顏色插值算法的硬件加速器，采用Synopsys DC工具0.13微米工藝綜合，頻率約為222.2 MHz。在Linux操作系統(tǒng)下使用OpenGL ES語言編寫實(shí)現(xiàn)的三角形和立方體的平滑著色效果圖，如圖10所示。

(a) 三角形的平滑著色

4　結(jié)語

采用流水線結(jié)構(gòu)以及并行處理的方式，設(shè)計(jì)并實(shí)現(xiàn)一種三角形顏色插值的硬件加速器。測試結(jié)果表明，該加速器可實(shí)現(xiàn)對任意三角形的平滑著色，能夠滿足嵌入式GPU中圖形平滑著色的要求。

[1]MOSMONDOR M, KOMERICKI H, PANDZIC I. 3D Visualization on mobile devices[J/OL]. Handbook of Research on User Interface Design & Evaluation for Mobile Technology, 2006, 32(2-3):181-191[2016-05-23].http://dx.doi.org/10.1007/s11235-006-9137-3.

[2]TOMAS A M, ERIC H.實(shí)時(shí)計(jì)算機(jī)圖形學(xué)[M]. 2版.普建濤,譯.北京:北京大學(xué)出版社,2004:213-244.

[3]EDWARD A, DAVE S.交互式計(jì)算機(jī)圖形學(xué)[M]. 6版. 張榮華,譯.北京:電子工業(yè)出版社,2011:107-109.

[4]李玉云. 面向移動(dòng)設(shè)備的光柵化處理器的研究與設(shè)計(jì)[D]. 合肥:中國科學(xué)技術(shù)大學(xué), 2010：19-25.

[5]郭安泰,郭立,楊毅,等.一種圖形光柵的硬件實(shí)現(xiàn)算法[J/OL].中國圖象圖形學(xué)報(bào),2009 14(1):176-182[2016-05-23].http://www.cnki.com.cn/Article/CJFDTotal-ZGTB200901033.htm.

[6]ANAND V B. Computer Graphics and Geometric Modeling for Engineers[M]//New York: John Wiley & Sons,1996:55-68.

[7]SUN C H, TSAO Y M, LOK K H. Universal rasterizer with edge equations and tile-scan triangle traversal algorithm for graphics processing units[C/OL]// ICME’09 Proceedings of the 2009 IEEE international conference on Multimedia and Expo, NJ:IEEE,2009:1358-1361[2016-05-23]. http://dx.doi.org/10.1109/ICME.2009.5202755 .

[8]BROWN R A. Barycentric Coordinates as Interpolants[EB/OL].[2016-05-23].http://arxiv.org/pdf/1308.1279v3.

[9]SKALA V. Duality, barycentric coordinates and intersection computation in projective space with GPU support[J/OL]. Wseas Transactions on Mathematics, 2010, 9(6):407-416[2016-05-23].https://otik.uk.zcu.cz/xmlui/bitstream/handle/11025/11337/Skala_2010_NAUN-journal.pdf?sequence=1.

[10]焦繼業(yè), 穆 榮, 郝 躍, 等. 面向移動(dòng)圖形頂點(diǎn)處理器的高性能低功耗定點(diǎn)特殊函數(shù)運(yùn)算單元[J/OL]. 電子與信息學(xué)報(bào), 2011, 33(11): 2764-2770[2016-05-23].http://dx.chinadoi.cn/10.3724/SP.J.1146.2011.00480.

[11]牛 濤, 沈海斌. 基于分段二次插值的初等函數(shù)逼近低成本設(shè)計(jì)[J/OL].計(jì)算機(jī)工程, 2013, 39(8):285-287[2016-05-23].http://dx.chinadoi.cn/10.3969/j.issn.1000-3428.2013.08.063.

[責(zé)任編輯：祝劍]

Implementation of triangle tinting algorithm based on the center of gravity coordinate interpolation

DU Huimin,JI Kaibo,JIANG Bianbian,GUO Chongyu

(School of Electronic Engineering, Xi’an University of Posts and Telecommunications, Xi’an 710121, China)

A hardware accelerator for triangle color interpolation is designed and accomplished. The area of the triangle and area reciprocal are calculated by using the boundary equation with triangle vertex data coming from triangular element. The effective pixel block of each triangle is selected by using the scan conversion module. The boundary value equation and reciprocal of the triangular area obtained from Triangle building unit are then used, and color interpolation of all slice elements in triangle processed by scan conversion module is achieved by using the interpolation module. Testing results show that the accelerator can achieve maximum working frequency of 222.2 MHz, which can achieve embedded GPU graphics smooth rendering.

gravity co-ordinate interpolation, smooth shading, embedded GPU

10.13682/j.issn.2095-6533.2016.05.008

2016-05-23

國家自然科學(xué)基金重點(diǎn)資助項(xiàng)目(61136002)；西安市科技發(fā)展計(jì)劃資助項(xiàng)目(CXY1440(10))

杜慧敏 (1966-)，女，博士，教授，從事計(jì)算機(jī)體系結(jié)構(gòu)和計(jì)算機(jī)圖形學(xué)研究。E-mail:228660529@qq.com.

季凱柏(1990-)，男，碩士研究生，研究方向?yàn)榧呻娐废到y(tǒng)設(shè)計(jì)。E-mail:964929756@qq.com.

TP391.4

A

2095-6533(2016)05-0039-04