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

王海波

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

關鍵詞：參與介質;光子映射;光輻射強度估算;k近鄰

中圖分類號：TP3 文獻標識碼：A

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

1參與介質

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

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

參與介質的光輻射強度的估算的原理圖如圖1所示，像素接受到來自從Xs發出的，方向為ω的光線，Tr為光線透過率，L為Xs點發出的光強度角度為ω，L經過參與介質后到達像素處既圖中眼睛處，像素的光強度如（1）式所示。

2.2構建新算法

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

算法1：構造立方體

Step1：計算n/t，算出立方體的數量σ

Step2：計算立方體的邊長

Step3：劃分立方體。

算法2：尋找估算點的最近鄰光子

Step1：查找出估算點附件的包含自己在內的k個立方體，

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

2.3算法分析

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

3算法實現

采用vs2013和OpenGL的編程環境，在一臺配置為Intel（R）Core（TM）i5，8GB內存，NVIDIA GeForce 610M顯卡，win7下進行實驗。

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

4結束語

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