王海波（湖南科技學(xué)院電子與信息工程學(xué)院，永州　425100）

?

一種基于BVH的參與介質(zhì)繪制算法研究

王海波
（湖南科技學(xué)院電子與信息工程學(xué)院，永州425100）

摘要：

關(guān)鍵詞：

0　引言

空氣中的介質(zhì)如云霧、煙塵、冰雪、灰塵等細小顆粒會在傳播過程對光線產(chǎn)生吸收、發(fā)射、散射現(xiàn)象，光子映射算法是由Jensen1996[1]年提出的全局光照算法，該算法可用于參與介質(zhì)的繪制，能取得較好效果。光子映射可分為兩個階段：第一階段光源向場景發(fā)射光子，并將符合條件的光子及其接觸表面的信息存儲在光子圖（Photon Map）中；第二階段則從視點出發(fā)向場景中發(fā)出光線并跟蹤光線，利用第一階段光子圖中的光子以及相交表面的信息，求得圖像平面上相應(yīng)點的光輻射強度并繪制圖形。

在第二階段的光線跟蹤算法中，構(gòu)造加速結(jié)構(gòu)即將面片組織成新的層次結(jié)構(gòu)是重要的一步，好的構(gòu)造結(jié)構(gòu)可減少無效的光線遍歷和相交操作。常用的層次構(gòu)造結(jié)構(gòu)有層次包圍盒（BVH）[2-3]、kd樹[4-5]、二叉空間樹（BSP）[6]、分段層次包圍盒（BIH）[7]、八叉樹（octree）[8]等，每種結(jié)構(gòu)各有優(yōu)點，層次包圍盒（BVH）是一種折中選擇。Carr等[9]在GPU上實現(xiàn)了層次包圍盒（BVH）光子遍歷，但任需在CPU上計算層次結(jié)構(gòu)；Lauterbach C[10]實現(xiàn)了層次包圍盒在GPU中的構(gòu)造，但并沒有充分發(fā)揮GPU[11]的并行優(yōu)點，只用線程塊去處理層次包圍盒結(jié)構(gòu)中的一個結(jié)點。

新算法將根據(jù)參與介質(zhì)以及BVH結(jié)構(gòu)的特點，采用啟發(fā)式（SAH）[12-14]最佳分割點方法來構(gòu)造加速結(jié)構(gòu)，使GPU線程在整個構(gòu)造中都保持高效使用，最終縮短整個參與介質(zhì)的繪制時間。

1　參與介質(zhì)理論

參與介質(zhì)的吸收是指光的輻射能量轉(zhuǎn)換成其他形式的能量，導(dǎo)致發(fā)光強度減小，距離的不同，能量減小的程度不同；發(fā)射是指介質(zhì)中的粒子發(fā)光等因素，增加光照在傳播過程中的能量；散射是指光線與介質(zhì)中的粒子發(fā)生碰撞從而導(dǎo)致光線向不同的方向發(fā)射，包括內(nèi)散射（in-scattering）和外散射（out-scattering），其中內(nèi)散射增加光照在傳播過程中的能量，而外散射則減少光照在傳播過程中的能量。光線在介質(zhì)中的輻射傳熱公式為式（1）所示：

2　基于GPU的BVH樹的構(gòu)建

在光子發(fā)射完后，構(gòu)造加速結(jié)構(gòu)時，先采用寬度優(yōu)先的方式，在3個坐標軸上計算采樣分割點的SAH花費，然后選取坐標軸上花費最小的分割點。若每個坐標軸上取p個采樣，則共需3p次采樣，可用GPU線程承擔采樣任務(wù)，并使其處于滿負荷狀態(tài)，這樣可縮短構(gòu)造時間。分割BVH樹的計算方式[15]如（2）式所示。

其中KT為遍歷父節(jié)點所產(chǎn)生的花費，K1為對采樣點進行相交操作所產(chǎn)生的花費，SA（V）是V的表面積，SA（VL）、SA（VR）分別代表左右子節(jié)點的表面積，NL、NR分別對應(yīng)左、右節(jié)點所含面片數(shù)量。可使用規(guī)約操作找出花費最小的最優(yōu)分割點。這些計算相互獨立，可通過處理核的SIMD并行處理。

隨著構(gòu)造層次的加深，結(jié)點所包含的面片數(shù)越來越少，GPU線程不能獲得足夠多的采樣點，從而導(dǎo)致GPU空閑，此時選擇相當于虛擬流多處理器的GPU線程塊去處理每個節(jié)點，把每個節(jié)點分割成2個節(jié)點，新節(jié)點放入全局存儲區(qū)，這些分割工作可以獨立進行。若有N個虛擬流多處理器的GPU線程塊，可在構(gòu)造到log2N層時，切換到這種新的計算模式下。

具體步驟如下：

（1）在全局存儲區(qū)域中開設(shè)2個隊列來記錄節(jié)點位置，這樣做可避免使用鎖機制帶來的同步開銷。一個隊列用于存放待劃分包圍盒的節(jié)點，另一個隊列存放新產(chǎn)生的節(jié)點，節(jié)點在隊列中的編號對應(yīng)該節(jié)點在存儲區(qū)域中的位置。

（2）當GPU線程塊空閑時，從第1隊列取出節(jié)點，進行劃分，接著將新產(chǎn)生的節(jié)點放入第2隊列。如果在第1隊列中該節(jié)點為k，則在第2隊列中的編號則為2k+t（t=0，1）點，t值可在共享存儲區(qū)里計算。

（3）當處理完畢第1隊列中的所有節(jié)點后，如有空節(jié)點可用緊湊操作方式清除，接著清空第1隊列；空閑GPU線程塊，從第2隊列中取出待劃分的節(jié)點，進行劃分，并將新產(chǎn)生的節(jié)點放入第1隊列，直至第2隊列中等待進行劃分節(jié)點都處理完畢。編號為j的節(jié)點所產(chǎn)生的新節(jié)點放入第一隊列中編號為2j+t（t=0，1），t值可在共享存儲區(qū)里計算。

（4）循環(huán)執(zhí)行第（2）（3）步，直至每層的節(jié)點完成劃分，接著進入下一個層次。

為了避免出現(xiàn)負載不均的現(xiàn)象，可采用寬度優(yōu)先的方法處理，依層次處理各節(jié)點，每個線程劃分不同的包圍節(jié)點，直至每個節(jié)點的面片數(shù)少于4。

3　實驗結(jié)果

實驗所用的微機配有Intel Core i5處理器、3.47 GB內(nèi)存以及Nvidia GeForce 405 GPU。使用VC ++ 2010和CUDA2.3編寫程序在包圍盒的每個維度被分為64個等分空間。實驗所用的測試場景如圖1，圖2，圖3所示，其中圖1的光子數(shù)為10M，圖2光子數(shù)15M，圖3光子數(shù)20M。表1給出了本文算法創(chuàng)建光子圖的時間t1，用kd樹創(chuàng)建光子圖的時間t2，Lauterbach C算法創(chuàng)建光子圖的時間t3。由表1可以看出：①t1高于t2，t3；②面片數(shù)越多，t1提高的值越大。表2給出參與介質(zhì)圖1，圖2，圖3的整個繪制時間，表中T1均比T2，T3略高。

表1　

表2　

4　結(jié)語

針對參與介質(zhì)的層次包圍盒BVH加速結(jié)構(gòu)沒有充分利用GPU并行計算的情況，提出了一種新的基于GPU的BVH的并行參與介質(zhì)算法。通過上述方法，可以最大限度的利用GPU的硬件計算資源和存儲資源，發(fā)揮GPU強大的并行計算能力，提高了整個參與介質(zhì)的繪制時間。

圖1　

圖2　

圖3　

參考文獻：

[1]Wojciech Jarosz，HenrikWann Jensen，Craig Donner.Advanced Global Illumination Using Photon Mapping[M].Siggraph 2008，August 15，2008.

[2]JEFFREY J.Automatic Creation of Object Hierarchies for Ray Tracing[J].IEEE Computer Graphics and Applications，1987，7（5）：14-20.

[3]C Gilles and LBernard.Coupled Use of BSP and BVH Trees in Order to Exploit Ray Bundle Performance[C].IEEE/EG Symposium on Interactive Ray Tracing，2007.

[4]KZhou，QHou.Real-Time Kd-Tree Construction on Graphics Hardware[J].ACM Trans.Graph，2008，27（5）：126：1-11.

[5]INGO W，VLASTIMIL H.On Buiding Fast Kd-Trees for Ray Tracing，and on Doning that in o（nlongn）[R].Utah：University of Utah，2006.

[6]DAN G，SHUHONG C.Front-to-Back Display of BSP Tree[J].IEEE Computer Graphics and Application，1991，11（5）：79-85.

[7]CARSTEN W，ALEXANDER K.Instant Ray Tracing：the Bounding Interval Hierarchy[C].Proceeding of the 17th Eurographics Symposium on Rendering.Nicosia，Cyprus：EG Press，2006：39-149.

[8]ANDREW S.AN Introduction to Ray Tracing[M].Mary-land：Academic Press，1989.

[9]Lauterbach C，Gar land M，Sengupta S.Fast BVH Construction on GPUs[J].Computer Graphics Forum，2009，28（2）：375-384.

[10]Nvidia Company，Whitepaper NVIDIA's Next Generation CUDATM Compute Architecture：FermiTM[M].US 2009，September 30，2009.

[11]J Goldsmith and J Salmon.Automatic Creation of Object Hierarchies for Ray Tracing[J].IEEE Computer Graphics and Applications，1987，7（5）：14-20.

[12]D J Macdonald and K S Booth.Heuristics for Ray Tracing using Space Subdivision[C].In Proceedings of Graphics Interface，1989：152-163.

[13]V Havran.Heuristic Ray Shooting Algorithms[D].PhD thesis，F(xiàn)aculty of Electrical Engineering，Czech Technical University in Prague，2001.

[14]IWald，W RMark，JGunther，SBoulos，TIze，W Hunt，SG Parker and PShirley.State of the Art in Ray Tracing Animated Scenes[C].In STAR Proceedings of Euro Graphics，2007.

[15]IWald.On fast Construction of SAH based Bounding Volume Hierarchies[C].In Proceedings of the 2007 Euro Graphics/IEEE Symposium on Interactive Ray Tracing，2007.

Research on a Rendering Algorithm of Participating Media Based on Bounding Volume Hierarchy

WANG Hai-bo
（School of Electronic and Information Engineer，Hunan University of Science and Engineering，Yongzhou 425100）

Abstract：

Photon mapping is an important algorithm to render participating media，and the acceleration construction is a key step.Proposes a novel approach for rendering participate media，which is based on unified programming architecture on GPU，utilizes the property of participating media（BVH）and multi-core architecture，and adapts surface area heuristic（SAH）strategy to construct acceleration in two phases.Experimental results show that the novel approach can speed up the rendering time of participating media.

Keywords：

光子映射算法是重要的參與介質(zhì)繪制方法，為解決其中構(gòu)造加速結(jié)構(gòu)慢的問題，可采用圖形處理器（GPU）統(tǒng)一編程架構(gòu)，結(jié)合參與介質(zhì)與的特點，利用多核架構(gòu)和層次包圍盒（BVH）的性質(zhì)，用面積啟發(fā)式（SAH）最佳分割點方法，來構(gòu)造加速結(jié)構(gòu)，進而提出一種新的參與介質(zhì)算法。實驗表明該方法可以有效地提高參與介質(zhì)的繪制時間。

參與介質(zhì)；圖形處理器（GPU）；層次包圍盒（BVH）；面積啟發(fā)式（SAH）

基金項目：

湖南省教育廳項目（No.13C337）

文章編號：1007-1423（2016）14-0023-04

DOI：10.3969/j.issn.1007-1423.2016.14.005

作者簡介：

王海波（1980-），男，湖南郴州人，碩士，講師，研究方向為圖像真實感與虛擬現(xiàn)實

收稿日期：2016-03-08修稿日期：2016-04-28

Participating Media；Graphics Processing Unit（GPU）；Bounding Volume Hierarchy（BVH）；Surface Area Heuristic（SAH）