基于快速k近鄰的參與介質(zhì)算法研究

王海波

摘要：空氣中有許多細(xì)小顆粒形成的參與介質(zhì)如云霧、煙塵、冰雪，光子映射能較好地模擬參與介質(zhì)，對參與介質(zhì)的光輻射強(qiáng)度估算是參與介質(zhì)算法的一個關(guān)鍵技術(shù)，傳統(tǒng)使用簡單、有效的k近鄰（kNN）算法，但kNN具有計(jì)算復(fù)雜度高，內(nèi)存需求量的缺點(diǎn)，新算法針對kNN的缺點(diǎn)，改進(jìn)kNN搜索光子的方式，先將空間分割為多個固定長度的立方體，每個立方體體包含一定數(shù)量的光子數(shù)，通過測試各個立方體與估算點(diǎn)之間的位置搜索估算點(diǎn)周圍的k個最近鄰光子，減少計(jì)算復(fù)雜度，進(jìn)而改進(jìn)參與介質(zhì)的光輻射強(qiáng)度估算，實(shí)驗(yàn)表明基于新算法的參與介質(zhì)算法速度更快。

關(guān)鍵詞：參與介質(zhì);光子映射;光輻射強(qiáng)度估算;k近鄰

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

文章編號：1009-3044（2019）31-0278-02

1參與介質(zhì)

空氣中的細(xì)小顆粒形成的參與介質(zhì)如云霧、煙塵、冰雪，會在對光線產(chǎn)生吸收、發(fā)射、散射等現(xiàn)象。參與介質(zhì)的吸收是指光的輻射能量轉(zhuǎn)換成其他形式的能量，導(dǎo)致發(fā)光強(qiáng)度減小，距離的不同，能量減小的程度不同;發(fā)射是指介質(zhì)中的粒子發(fā)光等因素，增加光照在傳播過程中的能量;散射是指光線與介質(zhì)中的粒子發(fā)生碰撞從而導(dǎo)致光線向不同的方向發(fā)射，包括內(nèi)散射（in-scattering）和外散射（out-scattering），其中內(nèi)散射增加光照在傳播過程中的能量，而外散射則減少光照在傳播過程中的能量。光子映射算法繪制介質(zhì)參可取得較好的效果，光子映射算法能取得較好的模擬參與介質(zhì)。

光子映射分為兩個階段第一個階段發(fā)射光子，跟蹤光子，建立光子圖;第二階段利用光子圖估算光照，從圖形像素的角度發(fā)出光線，如果遇到反射或折射后，記錄接觸點(diǎn)，搜索接觸點(diǎn)周圍的光子，對接觸點(diǎn)進(jìn)行光輻射強(qiáng)度估算，渲染圖形。因此光輻射強(qiáng)度估算是光子映射算法的第二階段的一個關(guān)鍵技術(shù)。

參與介質(zhì)的光輻射強(qiáng)度的估算的原理圖如圖1所示，像素接受到來自從Xs發(fā)出的，方向?yàn)棣氐墓饩€，Tr為光線透過率，L為Xs點(diǎn)發(fā)出的光強(qiáng)度角度為ω，L經(jīng)過參與介質(zhì)后到達(dá)像素處既圖中眼睛處，像素的光強(qiáng)度如（1）式所示。

2.2構(gòu)建新算法

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

算法1：構(gòu)造立方體

Step1：計(jì)算n/t，算出立方體的數(shù)量σ

Step2：計(jì)算立方體的邊長

Step3：劃分立方體。

算法2：尋找估算點(diǎn)的最近鄰光子

Step1：查找出估算點(diǎn)附件的包含自己在內(nèi)的k個立方體，

Step2：從最近的k個立方體中查找k個最近鄰光子。

2.3算法分析

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

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

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

實(shí)驗(yàn)所用的測試場景如圖2，圖3，圖4所示，其中圖2的光子數(shù)為10M，圖3光子數(shù)15M，圖4光子數(shù)20M。由表1可看出新算法渲染比傳統(tǒng)kNN算法快，其中圖3快了%30，圖4快了29.8%，圖5快了28%，因此新算法提高了參與介質(zhì)的渲染速度

4結(jié)束語

新算法針對kNN的缺點(diǎn)進(jìn)行了改進(jìn)，先將空間分割為多個固定長度的立方體，每個立方體體包含一定數(shù)量的光子數(shù)，通過測試各個球體與接觸點(diǎn)之間的位置速搜索測試點(diǎn)周圍的k個最近鄰光子，進(jìn)而較好地改善了參與介質(zhì)的光輻射強(qiáng)度估算光輻射強(qiáng)度，實(shí)驗(yàn)表明基于新算法的參與介質(zhì)算法速度更快。