重心坐標插值的三角形著色算法硬件實現

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

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

?

重心坐標插值的三角形著色算法硬件實現

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

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

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

重心坐標插值；平滑著色；嵌入式GPU

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

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

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

1　算法概述

1.1三角形重心坐標

圖1　三角形重心坐標插值

三角形abc內任意P點坐標(x,y)可表示為[6]

(1)

(2)

根據P點的邊界函數，可將式(2)化簡為[7]

(3)

其中lca為三角形ca邊的直線方程，其中lab為三角形ab邊的直線方程，且三角形內任意P點重心坐標α，β，γ滿足以下關系

α+β+γ=1。

(4)

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

1.2基于重心坐標算法的顏色插值

若已知三角形abc的3個頂點的R、G、B顏色值可表示[8]為

(5)

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

根據三角形內任意P點重心坐標α，β，γ，可將三角形abc內任意P點的顏色值CP[9]表示為

CP=αCa+βCb+γCc。

(6)

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

(7)

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

2　硬件實現

2.1硬件電路的總體設計

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

圖2　硬件電路總體設計

對于計算三角形內任意一點的顏色值, 將進行3路并行處理。

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

2.2面積計算模塊

采用流水結構實現面積的計算。該流水線結構計算三角形的面積需要有5個浮點a×b功能的加法單元和2個a×b功能的浮點乘法單元。具體的硬件結構如圖3所示。其中，MUL代表32位的浮點乘法器，ADD代表32位的浮點加法器。

圖3　面積計算的硬件結構

2.3面積倒數計算模塊

結合二次多項式逼近算法[10-11]實現三角形建立單元中三角形面積倒數的計算，硬件結構如圖4所示。

圖4　三角形面積倒數計算的硬件結構

三角形的面積用32bit單精度浮點數格式表示，記為F，則三角形面積的倒數可表示為

(8)

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

2.3.1尾數位的倒數計算

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

圖5　尾數的分解

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

f(X)≈AX2+BX+C。

(9)

尾數倒數計算模塊主要由查找表、平方運算器和2個乘法融合樹組成，硬件結構如圖6所示。

圖6　尾數倒數計算的硬件結構

2.3.2階碼的調整

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

(10)

2.4重心坐標計算模塊

重心坐標計算模塊主要實現三角形內片元的重心坐標計算。其計算過程如下所示。

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

圖7　自定義浮點格式

該浮點格式表示的值為

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

(11)

第2階段完成重心坐標β，γ的計算。需要進行2次浮點乘法運算。

第3階段完成α的計算，需要進行2次浮點加法運算。硬件結構如圖8所示。

圖8　重心坐標產生的模塊

2.5顏色插值模塊

顏色插值模塊主要實現了三角形內片元的顏色插值計算。為了縮短三角形內片元顏色值的運算時間，在已知三角形3個頂點的顏色值R,G,B分量及三角形內片元的重心坐標的條件下，采用流水線結構實現三角形內片元的顏色值的計算，如圖9所示。其中ADD表示24位的浮點加法器，MUL表示24位的浮點乘法器。

圖9　顏色插值流水線結構

3　測試結果與分析

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

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

(a) 三角形的平滑著色

4　結語

采用流水線結構以及并行處理的方式，設計并實現一種三角形顏色插值的硬件加速器。測試結果表明，該加速器可實現對任意三角形的平滑著色，能夠滿足嵌入式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.實時計算機圖形學[M]. 2版.普建濤,譯.北京:北京大學出版社,2004:213-244.

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

[4]李玉云. 面向移動設備的光柵化處理器的研究與設計[D]. 合肥:中國科學技術大學, 2010：19-25.

[5]郭安泰,郭立,楊毅,等.一種圖形光柵的硬件實現算法[J/OL].中國圖象圖形學報,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]焦繼業, 穆 榮, 郝 躍, 等. 面向移動圖形頂點處理器的高性能低功耗定點特殊函數運算單元[J/OL]. 電子與信息學報, 2011, 33(11): 2764-2770[2016-05-23].http://dx.chinadoi.cn/10.3724/SP.J.1146.2011.00480.

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

[責任編輯：祝劍]

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

國家自然科學基金重點資助項目(61136002)；西安市科技發展計劃資助項目(CXY1440(10))

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

季凱柏(1990-)，男，碩士研究生，研究方向為集成電路系統設計。E-mail:964929756@qq.com.

TP391.4

A

2095-6533(2016)05-0039-04