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

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

?

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

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

摘要：

關鍵詞：

0　引言

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

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

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

1　參與介質理論

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

2　基于GPU的BVH樹的構建

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

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

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

具體步驟如下：

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

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

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

（4）循環執行第（2）（3）步，直至每層的節點完成劃分，接著進入下一個層次。

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

3　實驗結果

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

表1　

表2　

4　結語

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

圖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，Faculty 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：

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

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

基金項目：

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

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

DOI：10.3969/j.issn.1007-1423.2016.14.005

作者簡介：

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

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

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