改進(jìn)的三維剪裁算法及其硬件設(shè)計(jì)

鄧惠子，韓俊剛，馬 超，楊 婷，查 理

(西安郵電大學(xué)專用集成電路中心，陜西西安 710061)

隨著人類對(duì)視覺(jué)感受的無(wú)限追求，越來(lái)越多復(fù)雜細(xì)膩的圖形圖像出現(xiàn)在各類顯示設(shè)備上，比如手機(jī)、平板電腦等［1］。在此背景下，將主處理器從繁重的圖形計(jì)算任務(wù)中解放出來(lái)，設(shè)計(jì)一個(gè)專用的圖形處理器變得越來(lái)越迫切［2］。圖形處理器以處理復(fù)雜3D圖形為主要任務(wù)［3］，也包含紋理貼圖和光照顯示［4］，同時(shí)實(shí)現(xiàn)對(duì)圖像的裁剪功能。三維剪裁使用視景體對(duì)物體進(jìn)行裁剪，保留 Cannonical View Volume(CVV)內(nèi)的部分［5］。常用算法(Sutherland-Hodgman，S-H)在進(jìn)行裁剪時(shí)較快捷［1］，但計(jì)算頂點(diǎn)屬性時(shí)存在大量的冗余操作。三維裁剪的CVV存在6個(gè)固定的裁剪平面，依照S-H算法每次用一個(gè)裁剪面進(jìn)行操作，完成后會(huì)對(duì)產(chǎn)生的新點(diǎn)進(jìn)行屬性插值，然后對(duì)由新點(diǎn)構(gòu)成的圖形進(jìn)行新一輪裁剪。如果本次產(chǎn)生的新點(diǎn)在新一輪計(jì)算中被裁剪掉，則之前計(jì)算的屬性不僅占用了存儲(chǔ)資源還使系統(tǒng)進(jìn)行了無(wú)用的操作。

針對(duì)常用算法中存在的問(wèn)題，提出一種改進(jìn)的裁剪算法以保證在進(jìn)行插值屬性時(shí)的點(diǎn)都在CVV內(nèi)。同時(shí)，利用多邊形的幾何關(guān)系對(duì)雙線性插值進(jìn)行改進(jìn)。最終利用硬件進(jìn)行仿真，證明針對(duì)裁剪進(jìn)行的改進(jìn)是合理的。

1 改進(jìn)算法介紹

三維剪裁模塊使用規(guī)范視景體即單位立方體對(duì)點(diǎn)、線或三角形等圖元進(jìn)行裁剪，運(yùn)用插值計(jì)算新點(diǎn)的各種屬性，根據(jù)裁剪后的頂點(diǎn)數(shù)目完成圖元的再裝配。以下為三角形的插值計(jì)算方法，如圖1所示。

圖1 三角形插值計(jì)算

根據(jù)幾何學(xué)可知三角形中任意一點(diǎn)與其3個(gè)頂點(diǎn)都有線性關(guān)系［6］，可知公式

成立，并且k1+k2+k3=1，可以使用三角形原始3個(gè)頂點(diǎn)的屬性值，插值求得其內(nèi)任意一點(diǎn)的屬性值。如圖 1 所示三角形頂點(diǎn)A(xa，ya，za，wa)、B(xb，yb，zb，wb)、C(xc，yc，zc，wc)，設(shè)點(diǎn)G(xg，yg，zg，wg)的坐標(biāo)。根據(jù)上述插值思想可得

式中，k1、k2、k3為線性插值的系數(shù)，可得k1、k2、k3。當(dāng)求出系數(shù)k1、k2、k3后，其內(nèi)任意一點(diǎn)G的屬性有

其中，k1+k2+k3=1。

2 硬件設(shè)計(jì)

2.1 三維剪裁的數(shù)據(jù)通路與接口

接受器接收到命令以后，如果命令是CMD_XUPT_SHAPE，然后根據(jù)命令中的圖元類型選擇是點(diǎn)、線還是三角形剪裁，選擇不同的剪裁控制器;否則直接輸出。

接收到CMD_XUPT_SHAPE后，點(diǎn)剪裁器啟動(dòng)使能信號(hào)，然后進(jìn)行點(diǎn)剪裁，只需要簡(jiǎn)單判斷點(diǎn)是否在單位立方體內(nèi)，可以直接輸出或不輸出。

接收到CMD_XUPT_SHAPE后，線剪裁器啟動(dòng)使能信號(hào)，然后進(jìn)行線的剪裁，采用Cohen_Sutherland算法，它已經(jīng)在軟件平臺(tái)中得到驗(yàn)證。一般地，對(duì)于一條線，它裁剪后可能沒(méi)有輸出，輸出一個(gè)點(diǎn)或一條線段。

接收到CMD_XUPT_SHAPE后，三角形剪裁器啟動(dòng)使能信號(hào)，然后進(jìn)行三角形的剪裁，采用S-H算法計(jì)算交點(diǎn)，采用改進(jìn)算法計(jì)算交點(diǎn)的屬性。一般地，三角形裁剪后情況比較復(fù)雜，根據(jù)輸出頂點(diǎn)的數(shù)目，對(duì)它進(jìn)行判斷:若是多邊形，要把它裝配成幾個(gè)三角形后依次輸出?；蛘邲](méi)有輸出，或者輸出一條線段。對(duì)于如點(diǎn)、線和三角形3種圖元，剪裁完畢后要將輸出數(shù)據(jù)保存在寄存器R中，然根據(jù)剪裁結(jié)果重新編碼后輸出，如圖2所示。頂層模塊的接口信號(hào)，說(shuō)明如表1所示。

圖2 三維剪裁的數(shù)據(jù)通路

表1 總體接口信號(hào)說(shuō)明

2.2 設(shè)三維剪裁的狀態(tài)機(jī)實(shí)現(xiàn)

三維剪裁的實(shí)現(xiàn)采用數(shù)據(jù)驅(qū)動(dòng)數(shù)據(jù)流的處理方式。三維裁剪模塊通過(guò)一個(gè)狀態(tài)機(jī)控制，并用握手信號(hào)與上下級(jí)進(jìn)行通信。裁剪所要處理的對(duì)象是點(diǎn)、線和三角形，對(duì)每個(gè)圖元操作結(jié)束后，插值計(jì)算頂點(diǎn)屬性值，然后根據(jù)節(jié)點(diǎn)數(shù)目重新裝配，再傳送到下一級(jí)，如圖3所示。

圖3 三維剪裁的狀態(tài)機(jī)實(shí)現(xiàn)

3 FPGA仿驗(yàn)證平臺(tái)與仿真結(jié)果

3.1 驗(yàn)證平臺(tái)的架構(gòu)

搭建的驗(yàn)證平臺(tái)輸入激勵(lì)用于產(chǎn)生待測(cè)數(shù)據(jù)，已經(jīng)預(yù)先指定了測(cè)試功能點(diǎn)的命令順序;對(duì)于數(shù)據(jù)位值的產(chǎn)生，激勵(lì)產(chǎn)生器則采用給定確定值的方法來(lái)實(shí)現(xiàn);Design Under Verification(DUV)是文中設(shè)計(jì)的硬件電路;其中參考模型是本文設(shè)計(jì)的行為模型，用于和DUV進(jìn)行比較;輸出響應(yīng)為DUV運(yùn)行的結(jié)果比較，用于比較參考模型和DUV運(yùn)行的結(jié)果［7］，如圖4所示。

圖4 驗(yàn)證平臺(tái)的結(jié)構(gòu)框圖

驗(yàn)證平臺(tái)采用自動(dòng)比較機(jī)制，由輸入激勵(lì)單元為DUV和參考模型提供相同的測(cè)試激勵(lì)，比較DUV和參考模型運(yùn)行的結(jié)果是否一致。若不一致，則報(bào)錯(cuò)，及時(shí)停止仿真;否則，說(shuō)明DUV設(shè)計(jì)與參考模型完成的功能一致，從而進(jìn)一步驗(yàn)證DUV功能的正確性。

3.2 仿真結(jié)果

針對(duì)三維剪裁器處理的3種圖元，功能仿真按照點(diǎn)、線和三角形的順序給出波形圖，逐個(gè)分析其處理過(guò)程及其處理結(jié)果，最終，給出頂層模塊的功能仿真:使用Mentor公司的QuestaSim 6.5工具，按照點(diǎn)、線和三角形的順序逐一分析其處理過(guò)程，結(jié)合圖形流水線其他各部分的RTL級(jí)實(shí)現(xiàn)將處理結(jié)果通過(guò)Java 1.6環(huán)境下的JFrame窗體顯示，如圖5所示。

圖5 JFrame窗體顯示的仿真結(jié)果

圖5中視景體是規(guī)范視景體，激勵(lì)輸入:點(diǎn)(1.01，1.00，0.00，2.00)判斷其在視景體里輸出點(diǎn);第一條線(2.2，1.0，1.0，3.5)，(2.2，6.0，1.0，3.5)被裁了 1/2，第二條線(5.6，1.0，1.0，8.0)，(7.2，1.0，1.0，8.0)在實(shí)景體里;三角形(9.2，3.0，1.0，3.5)，(9.9，3.0，1.0，3.5)，(9.5，5.0，1.0，3.5)，被裁剪為四邊形。仿真證實(shí)硬件電路能夠正確實(shí)現(xiàn)規(guī)范視景體對(duì)點(diǎn)、線和三角形的裁剪功能。

仿真結(jié)果如圖6所示，當(dāng)使能信號(hào)enP為高時(shí)，激勵(lì)輸入了一個(gè)點(diǎn)(0.5，0.2，0.0)以及它的顏色和法向量，因?yàn)樗趩挝涣⒎襟w內(nèi)，所以經(jīng)過(guò)點(diǎn)裁剪后，將這個(gè)點(diǎn)的所有屬性值輸出，輸出完畢后Pfinished置高。否則，如輸入一個(gè)點(diǎn)(1.0，1.2，2.5)，因?yàn)樗诹⒎襟w外面，所以最后沒(méi)有輸出，此時(shí)Pfinished也置高，狀態(tài)返回初始狀態(tài)INIT。

圖6 點(diǎn)的剪裁

如圖7所示，當(dāng)使能信號(hào)enL為高時(shí)，激勵(lì)輸入了一條線段的兩個(gè)端點(diǎn)(1.5，2.0，2.0)和(0.0，0.0，0.0)，它們的顏色值分別是(1.0，0.0，0.0)和(0.0，1.0，0.0)，經(jīng)過(guò)線裁剪后，最終的線段被裁減為(0.75，1.0，1.0)和(0.0，0.0，0.0)的一條線段，他們的顏色值為(0.5，0.5，0.0)和(0.0，1.0，0.0)。

圖7 線的剪裁

如圖8所示，當(dāng)使能信號(hào)enT為高時(shí)，激勵(lì)輸入了一個(gè)三角形的3個(gè)頂點(diǎn)坐標(biāo)及顏色和法向量等，輸入坐標(biāo)分別為v0(-0.5，0.0)、v1(0.5，0.0)和v2(0.0，1.5)。經(jīng)單位立方體剪裁后，原來(lái)的三角形變成了一個(gè)四邊形，它的坐標(biāo)分表為v0(-0.16667，1.0)、v1(-0.5，0.0)、v2(0.5，0.0)和v3(1.0，0.16667)，顏色經(jīng)插值計(jì)算后是(0.333，0.0，0.667)，(1.0，0.0，0.0)，(0.0，1.0，0.0)，(0.0，0.333，0.667)，然后對(duì)這個(gè)四邊形進(jìn)行再裝配，將其裝配成兩個(gè)三角形v0v1v2和v0v2v3，從圖中可以看出輸出兩組三角形，共18個(gè)值。

圖8 三角形的剪裁

3.3 綜合結(jié)果

表2為改進(jìn)算法的電路綜合結(jié)果與經(jīng)典算法的電路綜合結(jié)果的比較，結(jié)果顯示改進(jìn)算法可以提高處理效率。

表2 傳統(tǒng)與改進(jìn)算法的電路綜合結(jié)果比較

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

硬件電路能夠正確地實(shí)現(xiàn)規(guī)范視景體對(duì)點(diǎn)、線和三角形的裁剪功能，提高處理效率，實(shí)驗(yàn)驗(yàn)證了該方法的有效性和可用性。下一步將考慮將建立微碼體系結(jié)構(gòu)的模型［8］實(shí)現(xiàn)改進(jìn)算法，與其他組件協(xié)作，完成圖形渲染。

［1］TOMAS A M，HANINES E，HOFFMAN N.Real-time rendering［M］.2版.夏文宇，胡艷祥，譯.北京:清華大學(xué)出版社，2000.

［2］韓俊剛，蔣林，杜慧敏，等.一種基于圖形加速器和著色器的體系結(jié)構(gòu)［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)報(bào)，2010，22(3):363-372.

［3］譚顯強(qiáng).基于FPGA的3D圖形處理器IP核的設(shè)計(jì)與實(shí)現(xiàn)［D］.南京:南京航空航天大學(xué)，2010.

［4］董梁，劉海，韓俊剛.圖像處理器中光照和紋理映射的設(shè)計(jì)和仿真研究［J］.計(jì)算機(jī)科學(xué)，2011，38(2):284-287.

［5］SREINER D，WOO M，NEIDER J，et al.OpenGL 編程指南［M］.7版.李軍，徐波，譯.北京:機(jī)械工業(yè)出版社，2010.

［6］何裕平，田華蘇.剖析三角形的基本要素［J］.數(shù)學(xué)教學(xué)通訊，2012，2(4):24-28.

［7］克里斯，斯皮爾.System Verilog驗(yàn)證［M］.2版.張春，麥宋平，趙益新，等，譯.北京:科學(xué)出版社，2009.

［8］許金綱，王維維.微處理器體系結(jié)構(gòu)［M］.北京:科學(xué)出版社，2008.