王海波

摘要：光輻射強(qiáng)度估算是光子映射算法一個(gè)關(guān)鍵技術(shù)，傳統(tǒng)使用簡(jiǎn)單、有效的k近鄰（kNN）算法，但kNN具有計(jì)算復(fù)雜度高，內(nèi)存需求量的缺點(diǎn)，新算法針對(duì)kNN的缺點(diǎn)，改進(jìn)kNN搜索光子的方式，先將空間分割為多個(gè)固定長(zhǎng)度的立方體，每個(gè)立方體體包含一定數(shù)量的光子數(shù)，通過測(cè)試各個(gè)立方體與光線接觸點(diǎn)之間的位置搜索接觸點(diǎn)周圍的k個(gè)最近鄰光子，進(jìn)而估算光輻射強(qiáng)度，實(shí)驗(yàn)表明新算法搜索光子的速度更快，而且圖形清晰度更高。

關(guān)鍵詞：光子映射;光輻射強(qiáng)度估算;kNN;空間網(wǎng)格

中圖分類號(hào)：TP3? ?文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2019）28-0286-03

光子映射是較好的真實(shí)感圖形渲染方式之一，與光線跟蹤方法比較，光子映射能較好地渲染輝映、焦散效果[1]。光子映射分為兩個(gè)階段第一個(gè)階段發(fā)射光子，跟蹤光子，建立光子圖;第二階段利用光子圖估算光照，從圖形像素的角度發(fā)出光線，如果遇到反射或折射后，記錄接觸點(diǎn)，搜索接觸點(diǎn)周圍的光子，對(duì)接觸點(diǎn)進(jìn)行光輻射強(qiáng)度估算，渲染圖形。因此光輻射強(qiáng)度估算是光子映射算法的第二階段的一個(gè)關(guān)鍵技術(shù)。

為了準(zhǔn)確估算光輻射強(qiáng)度，需要尋找到對(duì)接觸點(diǎn)光輻射強(qiáng)度有影響的光子，傳統(tǒng)的光子映射算法采用K-近鄰算法對(duì)光輻射強(qiáng)度進(jìn)行估算，k-近鄰算法具有簡(jiǎn)單、有效的優(yōu)點(diǎn)，但發(fā)射光子量較大時(shí)k-近鄰算法的計(jì)算時(shí)間比較久。

為了改進(jìn)計(jì)算精度，提高計(jì)算效率Garcia采用常核函數(shù)方法，并且放棄第K個(gè)光子輻射通量的計(jì)算，以避免偏差[2][3];PerChristensen主張對(duì)第K個(gè)光子計(jì)算1/2的光輻射通量[4];Reinhard Klein主張根據(jù)第k-1與第k個(gè)光子的平均距離來計(jì)算第k個(gè)光子對(duì)接觸點(diǎn)的影響[5];對(duì)于核函數(shù)可選擇圓錐核函數(shù)、高斯核函數(shù)、Epanechnikov核函數(shù)、Silverman核函數(shù)[6][7][8][9]。為實(shí)現(xiàn)光輻射強(qiáng)度估算無無偏差性，Hachisuka等提出漸進(jìn)式光子映射算法，可從理論上對(duì)光輻射強(qiáng)度的計(jì)算達(dá)到無偏差計(jì)算，但需要循環(huán)發(fā)射大量光子[10][11]。

kNN算法具有簡(jiǎn)單、有效的特點(diǎn)，因此如何利用kNN算法的優(yōu)點(diǎn)，提高光輻射強(qiáng)度估算也是新算法研究的方向之一。本算法先將空間分割為多個(gè)固定長(zhǎng)度的立方體，每個(gè)立方體包含一定數(shù)量的光子數(shù)，通過測(cè)試各個(gè)球體與接觸點(diǎn)之間的位置速搜索測(cè)試點(diǎn)周圍的k個(gè)最近鄰光子，進(jìn)而估算光輻射強(qiáng)度。

1 光子映射

光子映射是一種全局光照，分兩階段。第一階段從場(chǎng)景的光源發(fā)出大量的光子，跟蹤光子建立光子圖，建立密度低的全局光子圖及密度高的焦散光子圖。焦散光子圖要求光子至少被鏡面反射或折射一次，全局光子圖存儲(chǔ)各種路徑的光子，當(dāng)光子擊中漫反射表面或略微光滑表面時(shí)，光子信息都會(huì)被存儲(chǔ)到相應(yīng)的光子圖中。光子圖存儲(chǔ)每個(gè)光子，并記錄光子能量或通量、輸入方向和位置等信息，光子圖采用平衡二叉樹作為光子搜索的數(shù)據(jù)結(jié)構(gòu)。

第二階段是利用光子圖計(jì)算光輻射強(qiáng)度，即從圖形的每個(gè)像素發(fā)出光線，光線在場(chǎng)景中經(jīng)過若干次鏡面反射、折射后、漫反射后，記錄接觸點(diǎn)x既估算點(diǎn)，然后利用全局光子圖及焦散光子圖，搜索離估算點(diǎn)最近的若干光子如圖1所示，并計(jì)算估算點(diǎn)的光輻射強(qiáng)度如式（1）所示

其中，x是估算點(diǎn)，fr是雙向反射分布函數(shù)（BRDF），[Φi]是第i個(gè)光子的光通量，[rk]是x與 k個(gè)光子中距x最遠(yuǎn)的某個(gè)光子的距離。當(dāng)光子數(shù)目越多，則光輻射強(qiáng)度的計(jì)算精度越高。因此光子的發(fā)射量影響到光輻射強(qiáng)度的計(jì)算，如何快速查找光子成為人們研究的方向。

2 快速K近鄰模型

K近鄰（KNN）算法是非常有效的基于距離的算法，被廣泛應(yīng)用于回歸模型，主要思想是：待測(cè)樣本的特征屬性等于最近鄰的k個(gè)樣本特征屬性的平均值。假設(shè)訓(xùn)練集合A包含s個(gè)樣本，每個(gè)樣本又含有t個(gè)屬性既：{Ai=（Ai1，Ai2，…，Ait），i=1，2，…，s };待測(cè)樣本為B，屬性為（B1，B2，…，Bt）;則求得樣本B的特征屬的步驟如下：

3 快速kNN

3.1 構(gòu)建新算法

新算法使用空間網(wǎng)格的方法先將空間劃分為若干立方體，將所有光子置入到這些立方體中。立方體網(wǎng)格單元太大太小，都會(huì)對(duì)整個(gè)查找過程產(chǎn)生不良影響，若立方體網(wǎng)格單元太小，會(huì)增加存儲(chǔ)量，降低效率;若立方體網(wǎng)格單元太大，則每個(gè)立方體單元會(huì)包含過多面片，對(duì)求交造成困難，因此新算法劃分立方體的個(gè)數(shù)為p=n/t其中n是光子總數(shù)，t是未知數(shù)，一般取值為20，立方體的邊長(zhǎng)為L(zhǎng)，滿足[L3=n/t]。如果有多個(gè)不包含光子的立方體連續(xù)在一起，則合并為一個(gè)立方體，保證生成的空間單元數(shù)不超過O（n），如算法1所示。接著搜索估算點(diǎn)周圍的k個(gè)立方體，并從k個(gè)立方體中搜索最近的k個(gè)光子，完成對(duì)估算點(diǎn)光輻射強(qiáng)度的估算如算法2，圖2所示。

3.2 算法分析

設(shè)發(fā)射光子數(shù)n，k為kNN算法參數(shù)，m為估算點(diǎn)的個(gè)數(shù)。傳統(tǒng)KNN的時(shí)間復(fù)雜度為O（mnk），表示每個(gè)估算點(diǎn)要計(jì)算同n個(gè)光子的距離，同時(shí)為求出k個(gè)最近鄰的光子，內(nèi)存中要維持一個(gè)k長(zhǎng)度的插入排序表，在排序表中，每插入一個(gè)新值，對(duì)表的最大操作次數(shù)為k。新算法中設(shè)立方體的總數(shù)為p，時(shí)間復(fù)雜性包含求k個(gè)最小立方體及其所包含樣本中的k個(gè)最近鄰樣本。每個(gè)立方體平均包含的光子數(shù)為n/p，因此時(shí)間復(fù)雜性為O（mpk+mnk2/p）=O（mk（p+nk/p）），故當(dāng)p+nk/pp2/（p-k）時(shí)，新算法的時(shí)間復(fù)雜性低于傳統(tǒng)kNN算法，由于k取值同立方體數(shù)相比要小得多，故當(dāng)n>p>k時(shí)，實(shí)際取值p<=n/20，因此n>p>k條件是成立的，新算法的運(yùn)行效率優(yōu)于傳統(tǒng)的kNN算法。

4 算法實(shí)現(xiàn)

采用vs2013和OpenGL的編程環(huán)境，在一臺(tái)配置為Intel（R） Core（TM） i5，8GB內(nèi)存，NVIDIA GeForce 610M顯卡，win7下進(jìn)行實(shí)驗(yàn)。

實(shí)驗(yàn)所用的測(cè)試場(chǎng)景如圖1，圖2，圖3 所示，表1給出了各圖的參數(shù)及渲染時(shí)間，其中圖1的發(fā)射的光子數(shù)為10M，圖2發(fā)射的光子數(shù)為15M，圖3發(fā)射的光子數(shù)為12M。由表中可以看出：新算法與傳統(tǒng)kNN的算法發(fā)射的光子數(shù)及需搜索的光子數(shù)是一樣的，新算法的每個(gè)立方體包含的光子數(shù)為20，從表中可以看出新算法的渲染時(shí)間比傳統(tǒng)kNN算法要快，圖1快24.7%，圖2快33.0%，圖3快23.1%，圖2增快的幅度最大是因?yàn)榭臻g分割最緊密。從圖1、圖2、圖3的圖形渲染質(zhì)量方面來看新算法也比傳統(tǒng)的kNN算法更清晰。

5 總結(jié)

新算法針對(duì)kNN搜索光子的計(jì)算量大的缺點(diǎn)，改進(jìn)了kNN搜索光子的方式，先將空間分割為多個(gè)固定長(zhǎng)度的立方體，每個(gè)立方體體包含一定數(shù)量的光子數(shù)，通過測(cè)試各個(gè)球體與接觸點(diǎn)之間的位置速搜索測(cè)試點(diǎn)周圍的k個(gè)最近鄰光子，進(jìn)而估算光輻射強(qiáng)度，實(shí)驗(yàn)表明新算法搜索光子的速度更快，而且圖形清晰度更高。

參考文獻(xiàn)：

[1] Per H Christensen， Henrik W Jensen， Toshi Kato， Frank Suykens. A Practical Guide to Global Illumination Using Photon Mapping [R].USA： Siggraph， 2002

[2]Garcia， R.， Urena， C.， Sbert， M.. Description and solution of an unreported intrinsic bias in photon mapping density estimation with constant kernel[J]. Comput. Graph. Forum， 2012，31（1）：33-41.

[3]Garcia， R.， Urena， C.， Poch， J.， et al.， 2014. Overestimation and underestimation biases in photon mapping with non-constant kernels[J]. IEEE Trans. Visual. Comput. Graph.， 20（10）：1441-1450.

[4]Jensen H W， Christensen P. High quality rendering using ray tracing and photon mapping[C]// Siggraph 07： Acm Siggraph Courses， Acm. 2007.

[5] R. Garc??a， C. Ure ? na， and M. Sbert， “Description and solution of an unreported intrinsic bias in photon mapping density estimation

with constant kernel.” Presented at Eurographics 24th Symposium on Rendering. Invited paper from Computer GraphicsForum， 2013.

[6] Roland， S. Bias compensation for photon maps Comput[J]. Graph. Forum， 2003，22（4）：729-742.

[7]Myszkowski， K.， 1997. Lighting reconstruction using fast and adaptive density estimation techniques. Proc. Eurographics Workshop on Rendering Techniques， p.251-262.

[8] Schjoth， L.， 2009. Anisotropic Density Estimation in Global Illumination. PhD Thesis， University of Copenhagen， Denmark

[9]Schjoth， L.， Sporring， J.， Olsen， O.F.， 2008. Diffusion based photon mapping.

[10] T. Hachisuka， S. Ogaki， and H. W. Jensen， “Progressivephoton mapping，” ACM Trans. Graph.， vol. 27， pp. 130：1–130：8， December 2008.

[11] C. Knaus and M. Zwicker， “Progressive photon mapping： A probabilistic approach，” ACM Trans. Graph.， vol. 30，no. 3， pp. 25：1–25：13， May 2011.

【通聯(lián)編輯：梁書】