基于空間均勻網(wǎng)格的光子映射算法研究

王海波+陳中+朱喜基+周華先

摘 要：光子映射是一種全局光照方法，在渲染輝映、焦散、漫反射等方面效果良好。通常的方法是發(fā)射光子，建立基于K-D tree的光子圖，然后在此基礎上尋找與估算點相應的光子完成光輻射強度估算，最后渲染圖形，具有生成圖形慢、內(nèi)存消耗大等缺點。鑒于此，提出一種新方法：先建立空間均勻網(wǎng)格，發(fā)射光子后，再利用GPU的并行功能建立光子與網(wǎng)格映射關系偏移表，之后尋找估算點的光子完成光輻射強度估算，渲染圖形。實驗結果表明，新算法生成的圖形速度更快、更清晰，具有更高的實用價值。

關鍵詞：光子映射；均勻網(wǎng)格；GPU；偏移表

DOIDOI：10.11907/rjdk.162461

中圖分類號：TP311

文獻標識碼：A文章編號：1672-7800（2016）012-0019-03

0 引言

光子映射是全局光照算法，通常先從光源向場景發(fā)射光子，建立基于K-D tree的光子圖，接著從光子圖中尋找估算點的光子完成對估算點光輻射強度估算，最后生成圖形[1]。光子映射的光子圖與場景表述可以分離，光子映射能處理很復雜的場景，包括千萬個三角面片、實例化的幾何體、復雜的過程式物體[2]。

針對通常算法消耗內(nèi)存大、生成圖形慢的缺點，Per H Christensen[3]于2002年提出凸多邊形的思路，該方法是獲取一組離估算點最近的光子，再求出包圍光子的最小凸多邊形，進而利用凸邊形的面積作為估算光輻射強度估算時的分母。該方法能比較精確地估算光輻射強度，但耗時很長。同年Heinrich Hey[4]提出另一種精確估算光輻射強度的算法。該算法的思想是：場景中的每個物體都用網(wǎng)格表示出來，采用立方體收集光子，并求出每個立方體內(nèi)的多邊形面積，每個光子的能量平均分配到光子正對著的多邊形，每個多邊形的光輻射能應與沿著光子入射方向的投影面積成正比。2005年Szbolcs Czuczou[5]應用圖形硬件的紋理結構存儲光子，用濾波方式搜索最鄰近的光子信息，該方法的好處是可以一步獲取所有頂點的輻射能，缺點是獲取的輻射能僅是平均值。2008年Hachisuka等[6]采用逐步縮小估算半徑，同時采用加大光子密度的辦法，在渲染水面焦散時效果較好。2009年Dan A.Alcantara[7]等在GPU上實現(xiàn)光子的哈希并行算法，搜索有效光子的速度更快，但需開辟較大的共享內(nèi)存。耿中元、徐慶為[8]為了改善物體細節(jié)部分的繪制效果，2009 年提出對搜索范圍內(nèi)的每個光子都求出它在繪制點上的切平面投影，通過判斷投影點與繪制點之間的距離是否小于搜索半徑，進而決定是否使用該光子計算光輻射強度。2011年Wojciech Jarosz[9]等提出采用自適應光子束方法渲染有參與介質(zhì)的柱狀型光照時取得較好效果。2012年Doidge[10]結合漸進光子映射算法與路徑跟蹤算法的優(yōu)點，在渲染焦散現(xiàn)象時采取光子映射算法，渲染其它現(xiàn)象時則采用光線跟蹤算法，兩種算法互相切換的花費較大。2013年Ben Spencer[11]等先為每個光子劃分一個沃羅諾伊空間，接著采用漸進光子的方式計算光輻射強度。2013年Mara、Luebke、McGuire[12]利用GPU的柵格硬件，在對光輻射強度估算時采用多面體方法獲取光子，提高了光輻射強度的精度，先從理論上證明該方法的一致性，實驗上也驗證了該算法的有效性，但該算法在處理較復雜的場景時會對估算點重復計算。

新算法先將物理空間分成均勻網(wǎng)格，然后發(fā)射光子，再建立均勻網(wǎng)格與光子的映射關系偏移表，實驗結果比通?；贙-D tree的光子映射算法更快，圖像也更清晰。

1 網(wǎng)格算法

Step1：空間均勻網(wǎng)格建立。先將場景分為可與圖形像素一樣多的包圍盒[13-14]，之后再根據(jù)統(tǒng)一的尺寸劃分網(wǎng)格，一般網(wǎng)格以搜索半徑r[15]為長度。劃分網(wǎng)格時間只占整個網(wǎng)格構建的一小部分時間。

Step2：為每個光子計算索引。網(wǎng)格建好后需要為每個光子分配光子索引可采用如下方式分配索引：

Idx（p）=G（p）.x+G（P）.y.GridSize.x+G（p）.Z.GridSize.x.GridSize.y（1）

其中，G（p）=[（p-worldOrigo）/cellSize]。GridSizex表示x軸上的網(wǎng)格數(shù)，GridSizey表示y軸上的網(wǎng)格數(shù)，GridSizez表示z軸上的網(wǎng)格數(shù)。索引值的范圍為0～N，其中N=GridSizex.GridSizey.GridSizez.所有的光子都分配到0～N-1中去，由于這部分可以并行進行，采用GPU的kuda作并行計算[16-17]。

Step3：偏移表（Offset Table）計算。完成均勻網(wǎng)格劃分、光子存儲、光子與網(wǎng)格對應關系建立，再建光子偏移表，用于光子搜索，如圖1所示。

Step4：利用均勻網(wǎng)格尋找光子。利用存儲光子的數(shù)組和偏移表，查找估算點的光子，如圖2所示，需要尋找到所有符合要求的光子。先找到估算點要達到的最小網(wǎng)格和最大網(wǎng)格，如在x軸的最小網(wǎng)格和最大網(wǎng)格半徑內(nèi)，如果網(wǎng)格空間的大小正好等于搜尋半徑，則在立體空間中最多需要搜尋8個網(wǎng)格，可用GPU的kuda并行搜尋。算法描述如下：

xMin=Max（0，[p.x-worldOrigo.x-radius]/cellSize）]

xMax=Min（GridSize.x-1，[p.x-worldOrigo.x-radius]/cellSize）]）

normPosition ：p-worldOrigo；

xMin：=max（0，floor（normPosition.x-R）/cellSize）

xmax：=min（GridSize.x-1，floor（normPosition.x+R）/cellSize）；

yMin：=max（0，floor（normPosition.y-R）/cellSize）；

yMax：=min（GridSize.y-1，floor（normPosition.x+R）/cellSize）；

zMin：=max（0，floor（normPosition.z-R）/cellSize）

zMax：=min（GridSize.z-1，floor（normPosition.z+R）/cellSize）；

getHashValue（x，y，z）{

return x+y*gridSize.x+z*gridSize.x*gridSize.y；}

If（xMin<=xMax）{

For（y：=yMin； y <=yMax； y++）{

For（z：=zMin； z<=zMax； z++）{ hashFrom：=getHashValue（xMin，y，z）； hashTo；=hashFrom+（xMax-xMin）； offsetFrom：=offsetTable[hashFrom]； offsetTo：=offsetTable[hashTo+1]；

for（i：=offsetFrom； i

photon：=photons[i]；

if（length（photon.position-p）<=R）{

Accumulate power of photon i

}

}

}

}

}

2 結果分析

實驗條件：系統(tǒng)Win7，處理器Intel I5處理器2.5G，內(nèi)存8G，Geforce 610，使用C++GL渲染圖形。在網(wǎng)格劃分好后，使用GPU的cuda技術，場景1為像素640×480，發(fā)射的光子數(shù)為50 000個；場景2像素為1 366×768，發(fā)射的光子數(shù)為100 000；場景3像素1 366×768，發(fā)射的光子數(shù)為200 000個。從圖形清晰度來看，網(wǎng)格算法的清晰度比K-D tree算法清晰度更高，原因是網(wǎng)格算法建立光子的映射關系更精準。從表1、表2、表3可以看出，在各場景中網(wǎng)格的構建時間比kd樹的構建時間都快，最大內(nèi)存消耗網(wǎng)格算法比K-D tree算法低，在總的渲染時間上，網(wǎng)格算法比K-D tree算法低。

3 結語

新的算法是先將空間劃分成均勻網(wǎng)格，發(fā)射光子后，再利用GPU的并行功能建立光子與網(wǎng)格映射光子，最后利用該映射關系來查找估算點的光子，進而渲染圖形。在以后的研究中可以更多地利用GPU并行功能加速圖形的生成，并進一步優(yōu)化光子與網(wǎng)格的映射。

參考文獻：

[1] H W Jensen.Global illumination using photon maps，proceedings of the seventh eurographics workshop on rendering1996[C].Switzerland：Aire-la-Ville，1996：19-26.

[2] HEINRICH HEY，WERNER PURGATHOFER.Advanced radiance estimation for photon map global illumination proceeding of eurographics，2002[C].Switzerland：Eurographics，2002：541-545.

[3] WOJCIECH JAROSZ，HENRIK W JENSEN.Advanced global illumination using photon mapping[C].USA：Siggraph，2008：65-70.

[4] HEINRICH HEY，WERNER PURGATHOFER.Advanced radiance estimation for photon map global illumination，proceeding of eurographics[C].Switzerland：Eurographics，2002：541-545.

[5] SZABOLCS CZUCZOR，LáSZló SZIRMAY-KALOS，LáSZló NEUMANN.Photon map gathering on the GPU[C].Spanish-Hungarian：EUROGRAPHICS，2005：143-152.

[6] WOJCIECH JAROSZ，HENRIK W JENSEN.Advanced global illumination using photon mapping[C].USA：Siggraph，2008：65-70.

[7] DAN A ALCANTARA，ANDREI SHARF.Real-time parallel hashing on the GPU[C].Asia：Proceedings of ACM SIGGRAPH，2009：243-252.

[8] 耿中元，徐慶，孫濟洲.改進的光輻射強度估算[J].系統(tǒng)仿真學報，2009（14）：4471-4474.

[9] WOJCIECH JAROSZ，DEREK NOWROUZEZAHRAI，ROBERT THOMAS.Progressive photon beams[C].NY：Proceedings of ACM SIGGRAPH Asia，2011：546-555.

[10] IAN C，DOIDGE MARK W，JONES，et al.Monte carlo and progressive rendering for improved global illumination[J].The Visual Computer June，2012（28）：603-612.

[11] BEN SPENCER，MARK W.JONES.Progressive photon relaxation[J].ACM Transactions on Graphics，2013（32）：562-570.

[12] MICHAEL MARA，DAVID LUEBKE， MORGAN MCGUIRE.Toward practical real-time photon mapping：efficient GPU density estimation[C].New York：ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games，2013：71-78.

[13] JEFFREY J.Automatic creation of object hierarchies for ray tracing[J].IEEE Computer Graphics and Applications，1987（5）：14-20.

[14] C GILLES，LBERNARD.Coupled use of BSP and BVH trees in order to exploit ray bundle performance[C].NewYork：IEEE/EG Symposium on Interactive Ray Tracing，2007：231-240.

[15] V GARCIA，E DEBREUVE，M BARLAUD.Fast k nearest neighbor search using GPU[C].Anchorage：CVPR Workshop on Computer Vision on GPU，2008：567-575.

[16] NVIDIA CORPORATION.CUDA ToolKit homepage[EB/OL].https：//developer.nvidia.com/cuda-toolkit.

[17] R FARBER.CUDA Application design and development：applications of GPU computing series[M].San Francisco：Morgan Kaufmann，2011：245-253.

（責任編輯：孫 娟）