蔡 鵬, 孔德慧, 尹寶才

（北京工業(yè)大學計算機學院多媒體與智能軟件技術北京市重點實驗室，北京 100124）

基于柵格的全局光子圖重建

蔡 鵬, 孔德慧, 尹寶才

（北京工業(yè)大學計算機學院多媒體與智能軟件技術北京市重點實驗室，北京 100124）

基于光子圖的光子映射算法能產(chǎn)生高質(zhì)量的照片級圖像。對于光照復雜的場景，光子圖需要存儲大量光子以提高生成圖像的質(zhì)量，這不僅占用大量的內(nèi)存空間，而且光照估計的時間長。論文提出基于柵格的全局光子圖重建的算法，即在光子包圍盒被柵格化后，其非空柵格中一定比例的光子被用來重建新的光子圖，并保證重建前后柵格內(nèi)光子能量和守恒，這使得重建前后光子圖的光照估計的效果相近。通過增加特定柵格中的重建光子數(shù)目，能有效減少由幾何偏差引起的光照估計誤差，增強直接聚焦（焦散）和間接聚焦光照的繪制效果；并使用簡單方法檢測生成圖像中少量噪聲，增加少量采樣即可有效減少相應的噪聲。全局光子圖重建算法的計算成本低，并保持生成圖像的視覺獨立性。

光子映射；全局光子圖重建；幾何偏差；焦散

真實感圖形學在虛擬現(xiàn)實、動畫影視和系統(tǒng)仿真等領域中得到廣泛應用。光線跟蹤[1-2]能計算陰影、光的反射和折射以及其他全局光照效果。但對于輝映和聚焦（或通過鏡面所間接看到的聚焦）光照效果的計算，光線跟蹤是非常低效的。Jensen等[3-6]提出基于光子圖的光子映射技術，對于光照復雜的場景，它需要存儲大量光子在光子圖中，以使光照估計的效果接近真實光照。這將占用大量的內(nèi)存空間，并且它需要在所存儲的光子中定位最近的若干光子，故其計算成本很高。

本文提出基于柵格的全局光子圖重建方法，相對于使用相同光子數(shù)目的光子圖所生成的圖像，利用重建后的全局光子圖進行光照估計所生成的圖像，具有更少的噪聲，并減少幾何偏差引起的光照估計的誤差，增強直接聚焦（焦散）和間接聚焦的繪制效果；通過簡單的方法，檢測出生成圖像易產(chǎn)生噪聲的區(qū)域，并增加少量采樣即可減少相應的噪聲。本文的全局光子圖的重建時間少，并保持生成圖像的視覺獨立性。

1 以前的工作

Jensen提出的具有兩個子階段的標準的光子映射方法[6]。

第一個子階段：利用光子跟蹤建立光子圖，即從場景的光源(L)出發(fā)跟蹤大量的光子，構造高密度的焦散光子圖和低密度的全局光子圖。當光子擊中漫反射表面(D)或略微光滑表面(G)時，存儲光子信息到相應的光子圖中，并決定光子是否被吸收或反射。焦散光子圖存放的光子至少被鏡面反射或折射(S)一次，即它經(jīng)歷的路徑為L(S)+(D︱G)。全局光子圖存儲所有經(jīng)歷各種路徑(L(D︱G|S)*(D︱G))的光子（+、*、︱分別代表≥1次、≥0次、或）。

光子圖存儲的光子i，具有能量或通量Φi、輸入方向ωi和位置pi等信息。場景中光照估計位置x的反射方向ω的光照Lr，可以通過在光子圖中定位距x最近的M個光子來估計：

其中，fr是雙向反射分布函數(shù)(BRDF)，rM(x)是x與M個光子中距x最遠的某個光子的距離。這對應最近鄰居密度估計[7]，通常在球體范圍內(nèi)查找最近的若干光子。為了有效地定位最近的光子，光子圖采用平衡二叉樹作為光子搜索的數(shù)據(jù)結構。

第二個子階段：使用光子圖進行光照估計，即從圖像每個像素出發(fā)的光線，在場景中經(jīng)過多次或零次的鏡面反射或折射后，擊中漫反射表面時，基于式(1)計算交點位置的光照。算法以兩種方式重建光照，第一種方式是先用局部光照公式計算直接光照，焦散光子圖計算焦散光照，全局光子圖計算間接光照，然后進行綜合而得出實際的光照值；第二種方式用全局光子圖計算場景中所有的全局光照，當光子數(shù)目越多，則光照計算的精度越高。本文只用全局光子圖進行光照計算。

Peter和 Pietrek[8]提出基于重要性驅(qū)動的光子圖構造算法，即用重要性圖引導更多的光子到場景中視覺重要的區(qū)域?；谶@種重要性驅(qū)動的光子跟蹤，構造一個包含場景中全局光照信息的光子圖。然而，在產(chǎn)生的光子圖中，高能量的光子與低能量的光子相混合，造成光照估計中光照不一致現(xiàn)象增多。

Suykens和Willems[9]介紹了光子密度控制的方法，避免光子存儲在過于密集的或不重要的區(qū)域；并提出基于視點重要性的方法，但全局光子圖的視覺獨立性被丟失，且計算成本高（包括上面Peter等的方法）。

Schregle[10]提出基于光子圖的光子密度的光照估計的偏差補償方法。他給出了最小帶寬（即對應的光照估計的偏差最?。┖妥畲髱挘丛肼曌钚。?，根據(jù)噪聲的高斯分布的概率統(tǒng)計，在最小帶寬和最大帶寬之間，利用二分折半搜索得到最佳帶寬（光照估計中的最近的光子數(shù)目），以使光照估計的偏差和噪聲均最小。

Herzog等[11]在光線空間內(nèi)，使用光線Splatting技術對具有漫反射和略微光滑表面的場景進行光子密度估計，以有效地計算間接光照。此方法能很好地減少由幾何偏差引起的光照誤差。

Spencer等[12]提出層次性的光子映射，他們通過光子的能量傳遞，將平衡二叉樹的下層的光子能量逐層傳遞到上層的光子能量中，以提高光照估計的效率。他們用光線的足跡計算光照估計的面積，而不是用光子密度得到它；并根據(jù)光照估計的區(qū)域的特征，動態(tài)地調(diào)整光線的足跡，大大減少光照估計的噪聲。

Hachisuka等[13]提出漸進式的光子映射，它是一個多道處理過程，即光線跟蹤子階段和許多光子跟蹤子階段。在有限內(nèi)存的空間內(nèi)，漸進的光子映射能使圖像的像素光照值收斂到真實的光照值。其缺點是當切換視點時，需要重新進行時間很長的光子跟蹤過程。

2 基于柵格的全局光子圖重建

2.1 基本方案

在光子映射的光子跟蹤階段，場景中的光源發(fā)出大量的光子，其中與漫反射表面交互的光子被保存在全局光子圖（以下簡稱為光子圖）中。

本文先計算光子圖中所有光子的包圍盒，將其均勻分割成一定數(shù)目的柵格，并按光子產(chǎn)生的順序?qū)⑵浯鎯Φ较鄳臇鸥裰小?/p>

如圖1所示，在每個非空柵格中取出前面的若干光子（按光子的存放順序）以用來重建光子圖，并按重建前后柵格內(nèi)光子能量和守恒的原則計算光子能量。設定的光子包圍盒的柵格數(shù)目為Ngd，則計算光子包圍盒的柵格結構如下：

其中，V為光子包圍盒的體積，dx、dy、dz分別為包圍盒的棱長，Nx、Ny、Nz分別為包圍盒的x、y、z軸上的柵格數(shù)目。

圖1 基于柵格的光子圖重建的基本方案

基于柵格的全局光子圖重建的基本方案是在重建前的每個非空柵格中，按光子的存放順序以相同比例取出前面的若干光子進行光子圖重建，即：

其中，Nold為重建前光子的數(shù)目，Nset為設定的重建光子的數(shù)目，Nnew為實際的重建光子的數(shù)目。Nold[i]和Nnew[i]分別為第i個非空柵格的重建前和重建后光子的數(shù)目，Ngrid為非空柵格的數(shù)目。若Nnew[i]為0，則Nnew[i]置為1。重建后的柵格中Nnew[i]個光子對應重建前相應柵格的Nold[i]個光子中的前Nnew[i]個（按光子的存放順序）。通常，Nold遠大于Nset和Nnew，Nnew接近Nset。

在第i個非空柵格中，記光子的紅、綠、藍3個通道的能量，在重建前分別為Φr0[j]、Φg0[j]、Φb0[j]，在重建后分別為Φr1[j]、Φg1[j]、Φb1[j]。對于(Nold[i]-Nnew[i])個非重建光子，其相應通道的能量平均分配到Nnew[i]個重建光子的相應通道的能量上，以保證柵格內(nèi)光子能量和守恒，具體計算過程, 如式(5)所示。通過設置適當?shù)臇鸥癯叽?，大多?shù)相鄰的非空柵格的光子的能量變化不大。因此，用其中很少的光子來重建光子圖，其光照估計的效果與基于重建前光子圖的光照估計的效果相近。

2.2 優(yōu)化方案

論文在基于柵格的全局光子圖重建的基本方案基礎上，為達到減少幾何偏差引起的光照誤差和增強焦散光照的繪制效果的目的，提出相應的優(yōu)化方案。

對于曲率大的漫反射表面的光照估計，在球體范圍內(nèi)查找最近的若干光子，容易從不屬于光照估計范圍的表面引入光子，如圖2(a)和圖2(b)的左部。通常的做法是在光照估計的表面法線方向上將光照估計范圍的球體壓成橢球體或圓盤，如圖2(a)和圖2(b)的右上部，但存在其投影面積不能正確表示光子所覆蓋面積的問題，通過凸包算法計算面積或利用濾波減小相應的光照誤差[6]。

圖2 在場景中曲率大的漫反射表面某位置光照估計

上述做法在某種程度上減小光照估計中由幾何偏差引起的光照誤差，但同時大大增加光照估計的計算成本。與之不同，論文增加對應場景中漫反射表面的曲率大的柵格中的重建光子，如圖2(a)和圖2 (b)的右下部所示，則曲率大的位置的光子密度變大，在光照估計的球體范圍內(nèi)包含同樣光子數(shù)目的情況下，則球體范圍變小，即從不屬于光照估計范圍的表面引入光子的數(shù)目變小，從而達到減小此類誤差的目的，其優(yōu)點是在光照估計中不增加額外的計算成本。特別是，對于光子泄露[11]，傳統(tǒng)的橢球體估計范圍包含垂直的不透明擋板另一側的光子，增加了光照估計的誤差，如圖 2(b)上部，文獻[11]也不能解決此問題；本文的方法能有效解決光子泄露的情況，如圖2(b)下部，原因如前所述。

在場景中，聚焦光照比其它光照對視覺影響大。通常將光子圖分成高密度的焦散光子圖和低密度的全局光子圖的做法[6]，只能增強直接聚焦(焦散)的光照效果，而不能增強間接聚焦的光照效果（即被漫反射表面反射的光子經(jīng)鏡面反射或折射后而產(chǎn)生的聚焦光照）。論文通過增加含聚焦光子（所有經(jīng)鏡面反射或折射后擊中漫反射表面的光子）較多的柵格的重建光子數(shù)目，能增強直接聚焦和間接聚焦的光照估計的效果。

如上所述，將式(3)修改如下：

其中，Kj為柵格j中漫反射表面曲率的度量值，Sj為柵格j中聚焦光照增強的權值。如式(6)所示，若相應柵格的Kj和Sj值越大，則重建后相應柵格中的光子越多。

圖3 場景中三角網(wǎng)格被分成小三角網(wǎng)格，并且小三角網(wǎng)格通過其中心被定位在相應的柵格中

如圖3所示，以柵格邊長的若干分之一為單位長度，將場景中對應的漫反射表面的每個三角網(wǎng)格拆分成一些相等的小三角網(wǎng)格。若某個小三角網(wǎng)格的中心在某個柵格內(nèi)，即此柵格包含了該小三角網(wǎng)格。令njk為柵格j和與之鄰近柵格的對應空間中的第k個小三角網(wǎng)格，m為小三角網(wǎng)格個數(shù)，由式(7)計算漫反射表面的曲率的度量值Kj。設ε為大于零的參數(shù)值（通常取ε= 0.03），它能調(diào)節(jié)漫反射表面的曲率度量值大的柵格(Kj＞ε)和曲率度量值為零的柵格（Kj=ε，即對應柵格空間中漫反射表面接近平面）的Kj值的相對大小。

由式(8)計算聚焦光照增強的權值Sj，其中Nold[j]和Nspe[j]分別為第j個非空柵格中重建前的光子和聚焦光子的數(shù)目，滿足0≤Nspe[j]≤Nold[j]。Nold和Nspe分別為重建前的所有非空柵格中光子和聚焦光子的數(shù)目和，滿足0≤Nspe≤Nold。在通常的場景中，Nspe[j]和Nold[j]均遠小于Nspe和Nold。第j個非空柵格的聚焦光子數(shù)目Nspe[j]的系數(shù)比非聚焦光子數(shù)目(Nold[j]-Nspe[j])的系數(shù)大，即對Sj影響大。因此，光子數(shù)目Nold[j]越大，特別是聚焦光子數(shù)目Nspe[j]越大，則此柵格的聚焦光照增強的權值Sj越大。

2.3 圖像的濾波處理

對于漫反射表面的曲率度量值大或聚焦光子比例大的柵格，基于柵格的全局光子圖重建的的優(yōu)化算法增加了這些柵格中重建光子數(shù)目。通過式(6)和式(5)計算，對應這些區(qū)域的光子能量與周圍區(qū)域的光子能量相差比較大，在光照估計時容易產(chǎn)生少量的噪聲。

3 實驗研究與結果分析

本文給出基于柵格的全局光子圖重建的實驗研究與結果分析。以下所有實驗是在 3GB內(nèi)存、2.66GHz Intel (R)CPU的硬件平臺上實現(xiàn)，生成圖像的像素均為400×400。

采取分別用基于柵格的光子圖重建的基本方案和優(yōu)化方案做實驗，3個場景分別為：場景1（含玻璃球、鏡面球）、場景2（含兩個玻璃正方體）、場景3（含具有漫反射表面的波動幾何體和擋板）。3個場景的重建前光子圖中均存儲107個光子，重建后光子圖的光子數(shù)目均稍小于5×105個。

本文設置場景的柵格數(shù)目Ngd為107，得到相應的光子包圍盒的結構（X、Y和Z軸上的柵格數(shù)目）：216×216×216。3個場景的非空柵格數(shù)目Ngrid分別為：231540、231528和329572。

每個場景的光子圖的重建前光子數(shù)目均為107個，依光子產(chǎn)生的順序存儲到相應場景的柵格中。如表1所示，列出3個場景的兩種方案的相關參數(shù)（重建前的光子數(shù)目Nold、設定的重建光子數(shù)目Nset）與實際的重建光子數(shù)目Nnew和光子圖重建時間（包含建立平衡二叉樹的時間）。

表1 兩種重建方案的參數(shù)和結果（時間：毫秒）

對于重建前具有107個光子的光子圖，設定光照估計的光子包圍球最多含 320個最近的光子。對于在光子數(shù)目（5×105個）大致相同的條件下進行對比的光子圖和本文的兩種方案的重建光子圖，設定光子包圍球最多含 80個最近的光子。這4種光子圖的光子搜索的數(shù)據(jù)結構均為平衡二叉樹。

如表2所示，列出每個場景的相應光子圖的光照估計時間（即圖像的生成時間）。因為，重建前光子圖的光子數(shù)目為重建后的 20倍，且光子包圍球的最大光子數(shù)目為重建后的4倍，所以表2中重建前光子圖的光照估計時間遠大于重建光子圖的相應時間。

表2 場景的4種光子圖的光照估計時間（時間：毫秒）

以上4種光子圖的光照估計的效果，如圖4～圖6所示，對于這3個場景，重建前的光子數(shù)目（107個光子）比兩種方案的重建后的光子數(shù)目（約為5×105個光子）的20倍稍多，但光照估計的效果差別很小。相對于本文的基本方案，其優(yōu)化方案更接近重建前光子圖的光照估計的效果，這是因為由幾何偏差引起的光照估計誤差被減小，且聚焦光照的繪制效果得到增強。圖6中的場景3的左局部表明優(yōu)化方案有效地減少了光子泄露（由特殊幾何偏差引起的光照誤差，具體解釋見本文2.2小節(jié)）。在圖4～圖6中，基于空間分布的光子圖重建的兩種方案生成的光子圖遠比作為對比的光子圖（具有大致相同的光子數(shù)目，即5×105個）的光照估計的效果好。

圖4 場景1對應的4種光子圖的光照估計的效果

圖5 場景2對應的4種光子圖的光照估計的效果

圖6 場景3對應的4種光子圖的光照估計的效果

圖7 利用優(yōu)化算法生成的光子圖進行光照估計時，檢測出圖像中易產(chǎn)生噪聲的區(qū)域(白色)。

在 2.3小節(jié)，提到優(yōu)化方案生成的光子圖，進行光照估計而生成的圖像有少量的噪聲，如圖7所示，顯示了用2.3小節(jié)的簡單方法檢測出的這些易產(chǎn)生噪聲的區(qū)域。圖4～圖6是由優(yōu)化方案生成的光子圖進行光照估計而產(chǎn)生的圖像，并在易產(chǎn)生噪聲圖像區(qū)域增加了少量的采樣點，所以能有效地減少這些少量的噪聲，僅比基本方案增加了少量的光照估計時間，如表2所示。

4 結 論

本文提出基于柵格的全局光子圖重建方法，相對于相同光子數(shù)目的光子圖的生成圖像，利用重建后的光子圖進行光照估計生成的圖像，具有更少的噪聲，并且減少由幾何偏差引起的光照估計的誤差，增強直接聚焦（焦散）和間接聚焦的繪制效果；以及通過簡單的方法，檢測生成圖像中容易產(chǎn)生噪聲的區(qū)域，并增加少量采樣以有效減少這些噪聲。

[1]Lafortune E P, Willems Y D. A theoretical framework for physically based rendering [J]. Computer Graphics Forum, 1994, 13(2)：97-107.

[2]Veach E, Guibas L J. Optimally combining sampling techniques for monte carlo rendering [J]. Computer Graphics Proceedings, Annual Conference Series,1995：419-428.

[3]Jensen H W. Global illumination using photon maps [J].Eurographics Rendering Workshop. New York City：1996：21-30.

[4]Jensen H W. Rendering caustics on non-lambertian surfaces [J]. Computer Graphics Forum, 1997, 16(1)：57-64.

[5]Jensen H W, Christensen P H. Efficient simulation of light transport in scenes with participating media using photon maps [J]. Computer Graphics, 1998：311-320.

[6]Jensen H W. Realistic image synthesis using photon mapping [M]. Peters A K, 2001.

[7]Silverman B W. Density Estimation for statistics and data analysis [M]. New York：Chapmann and Hall,1986.

[8]Peter I, Pietrek G. Importance driven construction of photon maps [J]. Proceedings of Eurographics Rendering Workshop. New York：1998：269-280.

[9]Suykens F, Willems Y D. Density control for photon maps [J]. Proc. Eurographics Workshop Rendering(Rendering Techniques ’00), 2000：23-34.

[10]Schregle R. Bias compensation for photon maps [J].Computer Graphics Forum, 2003, 22 (4)：729-742.

[11]Herzog R, Havran V, Kinuwaki S, et al. Global illumination using photon ray splatting [J].Eurographics, 2007, 26(3)：503-513.

[12]Spencer B, Jones M W. Hierarchical photon mapping [J].IEEE Transactions on visualization and computer graphics, 2009, 15 (1)：49-61.

[13]Hachisuka T, Ogaki S, Jensen H W. Progressive photon mapping [J]. ACM Trans. Graph, 2008, 27(5)：1-8.

A Grid-based Reconstruction of Global Photon Maps

Cai Peng, Kong Dehui, Yin Baocai
( Beijing Key Laboratory of Multimedia and Intelligent Software Technology, College of Computer Science and Technology,Beijing University of Technology, Beijing 100124, China )

Photon mapping based on photon maps can efficiently render high-quality photorealistic images. It stores many photons in photon map to improve rendering qualities of complex illumination, leading to high memory overhead and long reconstruction time. This paper presents a grid-based reconstruction of global photon maps. We divide bounding box of photons into a number of grids. Based on the number of photons, we take a certain rate of photons in grids to reconstruct global photon map, and ensure conservation of total energy of photons in each grid before and after reconstruction, which make estimated illumination effects of photon maps before and after reconstruction almost same. By adding photons in special grids, we effectively reduce illumination error due to all kinds of geometry biases and enhance rendering effects of direct and indirect caustic. This paper checks a few noises in rendering pictures by simple method, and adds a few samples to effectively reduce these noises. Our reconstruction method of photon maps takes fewer time and ensures viewpoint independence of rendering pictures.

photon mapping; reconstruction of global photon map; geometry bias; caustic

TP 391

A

2095-302X (2013)04-0010-06

2012-09-02；定稿日期：2013-03-06

國家自然科學基金資助項目（U0935004,61227004）

蔡 鵬（1977-），男，江蘇句容人，博士研究生，主要研究方向為計算機圖形學、真實感圖形。E-mail：caipeng568@163.com

孔德慧（1968-），女，內(nèi)蒙古包頭人，教授，博士，博士生導師，主要研究領域為虛擬現(xiàn)實與圖形學。E-mail：kdh@bjut.edu.cn