1、第27卷第8期2007年8月文章編號:1001-9081(2007)08-2033-03計算機應(yīng)用ComputerApplicationsVol.27No.8Aug.2007基于GPU快速光線跟蹤算法的設(shè)計與實現(xiàn)楊俊華,符紅光,郭惠(1.中國科學(xué)院成都計算機應(yīng)用研究所,成都610041;2.電子科技大學(xué)計算機科學(xué)與工程學(xué)院,成都610054)(tietong01)摘要:設(shè)計和實現(xiàn)了GPU上基于流的光線跟蹤算法,采用一種基于線索二叉樹的KD2Tree結(jié)構(gòu)組織場景,避免了傳統(tǒng)KD2Tree結(jié)構(gòu)在遍歷場景時在堆棧上的開銷。算法在組織復(fù)雜場景上,優(yōu)于利用傳統(tǒng)KD2Tree和均勻剖分結(jié)構(gòu)加速場景遍歷的方

2、法,在普通PC。關(guān)鍵詞:GPU;光線跟蹤;KD2Tree;線索二叉樹中圖分類號:TP391.41文獻標(biāo)志碼:A2DesignandimpleoningbasedonGPUFUHong2guang,GUOHui23(1.ofApplication,ChineseAcademyofSciences,ChengduSichuan610041,China;2.SchoolmputerScienceandEngineering,UniversityofElectronicScienceandTechnologyofChina,ChengduSichuan610054,China)Abstract:Lig

3、httrackingalgorithmbasedonGPUwiththestreamarchitecturewasdesignedandimplemented.Meanwhile,toavoidtheoverheadinstackoperationofthetraditionalKD2Treewhentraversing,aKD2Treestructurebasedonthreadedbinarytreewasusedtoorganizescene.ThemethodissuperiortotheuseoftraditionalKD2Treeanduniformsplitstructureto

4、acceleratetraversinginorganizingcomplexscenes,andtherapidtrackingrenderingoflightwasachievedinordinaryPC.Keywords:GPU;raytracing;KD2Tree;threadedbinarytree0引言隨著計算機圖形硬件的快速發(fā)展,真實感圖形繪制成為圖形學(xué)研究的熱點。光線跟蹤算法是一種經(jīng)典的真實感繪制算法,它利用光路可逆原理,通過追蹤光線,能很好地渲染真實世界。國內(nèi)外在這方面做了大量的研究1-3。因為光線跟蹤算法需要追蹤每條從視點發(fā)出的光線,因此涉及到大量的求交測試運算。提高該算法

5、效率的關(guān)鍵在于提高求交測試的效率,而包圍盒技術(shù)則是提高求交測試效率的通用辦法。常見的包圍盒包括軸向包圍盒(Axis2AlignedBoundingBoxes,AABB)、方向包圍盒(OrientedBoundingBoxes,OBB)、離散方向多面體(K2DOP)等。隨著GPU的可編程特性及可編程硬件高級語言(如GLSL,CG等)的發(fā)展,人們開始關(guān)注和研究如何利用GPU強大的運算能力將CPU從繁重的運算中解放出來3?；?,5GPU的光線跟蹤成為了一個活躍的研究方向。本文借鑒文獻6的方法,提出了GPU下的基于流的多遍繪制的光線跟蹤構(gòu)架體系。同時,改變了傳統(tǒng)的基于均勻剖分的加速算法,采用了一種改

6、進的2維KD2Tree加速算法組織復(fù)雜場景。實驗證明,該算法提高了光線跟蹤的效率,實現(xiàn)了光線跟蹤的實時渲染。水線互相連接(如圖1),構(gòu)成了處理能力強大的GPU并行處理流水線。同時,支持對GPU編程的高層GPU編程語言也隨之出現(xiàn),用戶可以通過編寫VertexShader和FragmentShader,實現(xiàn)更多強大的功能。然而,GPU還是有它的一些局限性:可編程GPU仍然是一種SIMD架構(gòu),CPU與GPU的切換常會導(dǎo)致較大的系統(tǒng)開銷,這給基于GPU的應(yīng)用帶來了困難。圖1OpenGL流水線解決該問題的一個有效辦法就是采用GPU多pass渲染技術(shù)。多pass渲染技術(shù)需要將計算的中間結(jié)果作為后一過程的輸

7、入繼續(xù)進行計算。為了進行這種多pass渲染,并避免從顯存中反饋數(shù)據(jù)到CPU端(這是一項非常耗時的操作),我們將計算任務(wù)主要在片元操作中完成。在片元操作部分,可測試和混合等操作以利用紋理合成、深度測試、模板測試、來完成比較復(fù)雜的計算。計算結(jié)果可以作為紋理繼續(xù)使用。紋理在這里就如同一個矢量型臨時變量。通過這種多pass渲染的技術(shù),可以實現(xiàn)較為復(fù)雜的計算。1可編程GPU簡介及多Pass渲染技術(shù)近年來,GPU可編程能力大大提高,主流GPU都提供了頂點處理器和片元處理器兩個可編程處理器與傳統(tǒng)的圖形流2改進的KD2Tree算法2.1KD2Tree算法簡介KD2Tree已經(jīng)被證明是在基于CPU光線跟蹤中組織

8、復(fù)雜收稿日期:2006-12-26;修回日期:2007-04-14。作者簡介:楊俊華(1983-),男,福建龍巖人,碩士研究生,主要研究方向:計算機圖形學(xué);符紅光(1965-),男,四川成都人,研究員,博士,主要研究方向:算法幾何;郭惠(1981-),女,山西長治人,碩士,主要研究方向:計算機圖形學(xué)。2034計算機應(yīng)用才停止。3.1基于流的GPU多pass渲染體系2007年場景最有效的方法6,2維KD2Tree是其中最簡單的一種。該樹中的每個節(jié)點代表一個軸向包圍盒;每一個內(nèi)部節(jié)點表示分離平面,該平面將場景劃分為兩個子區(qū)域。劃分包圍盒的方法是沿軸循環(huán)分割,首先從根節(jié)點沿x軸對盒子進行分割,然后再

9、沿y軸分割子盒子,最后再沿z軸分割孫子盒子,以此循環(huán)。標(biāo)準(zhǔn)的KD2Tree算法的遍歷采用了一個堆棧來存放所有需要遍歷的節(jié)點。關(guān)鍵算法2光線跟蹤的本質(zhì)是一個基于流的多遍處理的過程。為了避免CPU和GPU之間的頻繁切換,我們利用GPU的多pass渲染技術(shù),將光線頂點、方向向量、頂點坐標(biāo)和三角片等信息寫入到紋理中作為輸入。如圖2,通過光線生成、場景遍歷、模型求交、光照計算和光線衍生五大內(nèi)核的多次迭代運算,最終生成效果圖。所有的這些內(nèi)核都是在GPU中完成的,每個內(nèi)核對應(yīng)于片元操作中的一個pass,避免了CPU和GPU間頻繁切換帶來的系統(tǒng)開銷,提高了效率。如下所示:算法1KD2Tree構(gòu)建算法1)從根節(jié)

10、點開始求交,并求出射線在該根包圍體的全局跨度區(qū)間global-min,global-max。并按如下規(guī)則遞歸求解該KD2Tree的每個節(jié)點;2)如果是中間節(jié)點,則通過分離軸將跨度區(qū)間分為min,mid,mid,max兩部分;3),GPU的五大核心模塊的關(guān)系33.2.1光線生成模塊同時穿過兩個子包圍盒,個字節(jié)點壓入堆棧4)否則,;5)如果該節(jié)點是葉子節(jié)點,且射線和該子節(jié)點有交,則用兩塊m×m的紋理來存儲光線信息:其中一塊用來存儲光線的起點坐標(biāo),另一塊用來存儲光線的向量信息。一個RGBA紋理的每個像素具有四個分量,分別用來表示起點和返回成功;6)否則,將堆棧中的子節(jié)點彈出,返回2)。在這

11、個算法中,利用了一個跨度區(qū)間tmin,tmax對求交作出了限制。如果遇到的是該樹的內(nèi)部節(jié)點,就將該區(qū)間分為左右兩部分分別處理。然而,由于用到了堆棧,效率受到了限制,而且也不便于硬件實現(xiàn)。2.2基于線索二叉樹的KD2Tree遍歷求交方向向量的四個分量。用GLSL語言描述如下:structlightOriginalPosX,PosY,PosZ,structRaydirdirX,dirY,dirZ,hitflag/起點紋理/方向向量紋理其中,起點紋理分量定義了該光線的貢獻率,0,1,其他三個向量定義了頂點的三個分量。對于方向向量,hitflag記錄該光線的求交情況,而其他三個向量定義了方向向量在三個

12、坐標(biāo)軸方向的分量。3.2.2場景組織模塊經(jīng)過分析并借鑒前人的一些辦法6后發(fā)現(xiàn),可以簡化以避免堆棧操作。本文利用線索二叉樹改進了原來的KD2Tree結(jié)構(gòu),使每個節(jié)點都可以方便地訪問它的前驅(qū)和后序節(jié)點。改進的遍歷算法描述如下:算法2改進的遍歷算法1)建立2維KD2Tree;2)在求交和遍歷之前將該樹中序線索化;3)對于算法1的第3)步,改進為只要先遍歷第一個節(jié)利用場景組織模塊來加速光線的遍歷,遍歷的結(jié)構(gòu)為KD2Tree。為了說明問題的方便,只用三角形作為處理單元。定義該模塊用到的數(shù)據(jù)結(jié)構(gòu)如下所示:Structtrianglefloatx;floaty;floatz;floatattri;/三角形紋

13、理點,不將第二個節(jié)點壓入堆棧;4)對于算法1的第6)步,改進為直接搜索該節(jié)點的后繼節(jié)點,避免堆棧操作。利用本文的算法可避免堆棧操作帶來的開銷。當(dāng)然,建立線索二叉樹本身也會有一定的開銷,但該操作在初始化時一次完成,后面的每次操作都將加快遍歷速度。在實際應(yīng)用中,我們限制了中間節(jié)點的深度,并保證KD2Tree的平衡性,平均的算法時間復(fù)雜度為O(log2n)。其中,x,y,z分別是頂點在頂點紋理中的偏移量,Attri是三角形塊在屬性紋理中的偏移量。這兩個紋理比較簡單,不再詳述。StructleafnodefloattriangleOffset;floattriangleCount;/葉子節(jié)點紋理其中,

14、triangleoffset用于儲存三角形在三角形紋理中的偏移量,triangleCount用于儲存三角形的個數(shù)。由于一個葉子節(jié)點可能有多個三角形,也可能沒有一個三角形,所以規(guī)定:1)如果triangleCount為0,triangleOffset為-1,表示該節(jié)點沒有三角形;2)如果triangleCount為正整數(shù),表示該節(jié)點的三角形個數(shù),triangleOffset為該葉子節(jié)點的第一個三角形;3)如果triangleCount為-1,triangleOffset為葉子節(jié)點的后續(xù)三角形。StructsplitnodefloatsplitValue;floatleftchild;/中間節(jié)點/

15、分離軸值3基于流的光線跟蹤法的基本框架經(jīng)典的光線跟蹤法可以用一個遞歸算法實現(xiàn)。對于每個像素點,產(chǎn)生一條由視點出發(fā)指向該像素點的光線。對于每條射線,遍歷整個場景,找到與之最近的物體,然后從這條光線與該物體的相交點出發(fā)向每個光源都發(fā)出一條射線,檢測是否有物體阻擋或削弱這條光線,從而判斷是否處于陰影內(nèi)。從這個相交點還可以衍生出新的光線。如果物體可以放射或折射光線,則在反射或折射方向上生成新的光線,通過對陰影和反射光線的反復(fù)檢測,這條射線可以拾取物體在這個方向上的顏色值。這個遞歸過程一直到達某個最大深度值時第8期floatrightchild;floatflag;楊俊華等:基于GPU快速光線跟蹤算法的

16、設(shè)計與實現(xiàn)20354試驗結(jié)果及分析如圖3在普通PC機上(Pentium43.0G,ATI9500),通過實驗對比了基于均勻網(wǎng)格加速的、基于普通KD2Tree加速的和基于本文方法加速的GPU光線跟蹤法在性能上的優(yōu)劣。可以看出,在場景本身并不復(fù)雜的情況下,基于均勻網(wǎng)格加速的方法最有效,然而,隨著場景復(fù)雜度的增加,本文的方法將優(yōu)于前兩種。表1各種方法的耗時比較(s)場景中三角形個數(shù)644500000線索二叉樹需要兩個標(biāo)量來表示其為子樹或是前驅(qū)后繼,本文利用了leftchild和rightchild的符號。由于紋理的偏移量為正整數(shù),所以,可利用leftchild和rightchild的符號來區(qū)分左右子

17、樹和前驅(qū)后繼。規(guī)定leftchild/rightchild為正數(shù)時指向下一個中間節(jié)點,否則指向葉子節(jié)點。而flag用來區(qū)分分離軸的方向和左右子樹的指向(是葉子節(jié)點還是中間節(jié)點)。因為一共有3×2×2種組合關(guān)系,所以用12個正整數(shù)來表示。在這個體系中,每個節(jié)點需要占用128bit。由于每個偏移量用一個浮點數(shù)表示,但首位為標(biāo)志位,所以一共可以訪問r個三角形。如果場景過于復(fù)雜,i1.83KD2Tree0.350.985.91本文0.380.855.12理中。3.2.3場景的遍歷和求交,D2Tree構(gòu)建。由于GPU是一個SIMD結(jié)構(gòu),其片元處理單元一次可以處理多個紋理像素,所以,每

18、次都將并行處理多條光線。本文采用了一個光線包來管理并行處理的一組光線。同時,記錄下每條光線的狀態(tài),而每條光線的狀態(tài)可以用一個有限狀態(tài)機來管理5。由于是并行處理,所以存在某些節(jié)點處于場景遍歷狀態(tài),而某些處于模型求交狀態(tài)。這樣,就需要CPU參與調(diào)度以平衡遍歷和求交運算。由于二者相互依賴,如果等到全部節(jié)點都遍歷完成再求交,效率顯然是很低下的。實驗證明,當(dāng)需要求交的射線個數(shù)大于總射線個數(shù)的20%時,將場景遍歷模塊切換到模型求交模塊的CPU調(diào)度開銷最小3.2.4光線衍生4圖3試驗結(jié)果5結(jié)語本文設(shè)計了基于流的GPU光線跟蹤方法,提出了改進的場景組織方法,避免了KD2Tree組織場景時進退棧的開銷,提高了效

19、率?，F(xiàn)在,基于GPU的研究成為了圖形學(xué)的研究熱點,在圖形學(xué)甚至通用計算領(lǐng)域,基于GPU都得到了廣泛的應(yīng)用。然而,現(xiàn)在的GPU仍然還是一個SIMD體系,在很多方面還不如CPU靈活,隨著GPU的快速發(fā)展,它必將得到更大地改進和更好地應(yīng)用。參考文獻:1SHREINERD,WOOM.OpenGL編程指南M.4版.鄧鄭祥,。如果模型可以反射或折射光線,將進入光線衍射模塊。根據(jù)phone光照模型,反射和折射光線可由如下的公式給出1:反射光線:R=2N(NL)-L(1)折射光線:T=L-(coscos2-1)N;(2)譯.北京:人民郵電出版社,2005.2FOLEYT,SUGERMANJ.KD2treeaccelerationstructures,foraGPUraytracerC/SIGGRAPH/EUROGRAPHICSWorkshopOnGraphicsHardware:ProceedingsoftheACMSIGGRAPH/EURO2GRAPHICSconferenceonGraphicshardware.NewYork:ACMPress,2005:15-22.3CHRISTENM.RayTracingonGPUD.