基于八叉樹鄰域分析光線跟蹤的云三維模擬

鄭 義，謝永華,2，姬 瑜，朱超凡

(1.南京信息工程大學(xué) 計(jì)算機(jī)與軟件學(xué)院，江蘇 南京 210044；2.南京信息工程大學(xué) 江蘇省網(wǎng)絡(luò)監(jiān)控中心，江蘇 南京 210044)

0 引 言

由于云[1]具有不規(guī)則的模糊邊界、整體不光滑性以及運(yùn)動(dòng)的多變性，這些特征使得云很難被計(jì)算機(jī)模擬，尤其是在云的光照模擬中，光線進(jìn)入云后具有十分復(fù)雜的傳播方式，很難用精確的模型去描述。

在計(jì)算機(jī)上模擬三維云，最重要的是模擬云的真實(shí)感，主要過程包括建模和渲染兩個(gè)方面。在渲染方面，研究者們針對光線的傳播過程，提出了多種加速光線與節(jié)點(diǎn)求交的方法。Wong等[2]結(jié)合八叉樹和分層網(wǎng)格結(jié)構(gòu)，提出了八叉樹網(wǎng)格，通過減少相位測試的數(shù)量來加快碰撞檢測，一定程度上提高了運(yùn)行速度，但是該方法在計(jì)算節(jié)點(diǎn)的過程中需要進(jìn)行大量的遞歸運(yùn)算，效率依然不高。王皛等[3]通過KD-Tree設(shè)計(jì)出一種完全流水化的方法，并結(jié)合硬件處理的方式提升了光線遍歷性的能力，有效地提高了繪制速度，但該方法仍然需要遍歷所有的節(jié)點(diǎn)，計(jì)算量非常的龐大，不適用于大規(guī)模三維云場景的模擬。周海英等[4]提出了一種八叉樹空間編碼鄰域搜索方法，該方法通過存儲初始節(jié)點(diǎn)的空間編碼以及層次差來解決不同層次間節(jié)點(diǎn)的計(jì)算，加快了光線與節(jié)點(diǎn)的求交速度，但是該方法在構(gòu)建八叉樹時(shí)需要額外一部分存儲空間來存儲節(jié)點(diǎn)與其鄰域節(jié)點(diǎn)的層次差，降低了存儲空間的利用率。袁昱緯等[5]采用八叉樹自適應(yīng)技術(shù)，將空白節(jié)點(diǎn)自適應(yīng)的聚集為包圍體，減少光線與空白節(jié)點(diǎn)的求交次數(shù)來提高光線跟蹤算法的計(jì)算效率，但是該方法只能夠處理大規(guī)模動(dòng)態(tài)場景中局部更新的問題，并不適用于云三維模擬場景。

針對以上方法的不足，本文提出了基于八叉樹鄰域分析的光線跟蹤算法，并用于天氣預(yù)報(bào)模式(weather research and forecasting，WRF)數(shù)值的三維模擬。該方法首先使用八叉樹結(jié)構(gòu)優(yōu)化光線跟蹤的數(shù)據(jù)存儲結(jié)構(gòu)，然后通過存儲節(jié)點(diǎn)編碼和劃分層次改進(jìn)鄰域分析算法對不同劃分層次節(jié)點(diǎn)的計(jì)算方式，加快光線的求交速度，并對光線折射公式做出改進(jìn)，簡化了光照模型。實(shí)驗(yàn)結(jié)果表明，該方法能有效提高云圖繪制速度和渲染效果，更好展現(xiàn)真實(shí)三數(shù)據(jù)的物理特性。

1 基于八叉樹鄰域分析的光線跟蹤算法

1.1 數(shù)據(jù)存儲結(jié)構(gòu)優(yōu)化

光線跟蹤是一個(gè)比光線投射[6]或者掃描線渲染[7]更加逼真的實(shí)現(xiàn)方法，其通過反向跟蹤所有光線的方式，求出光線與物體的交點(diǎn)，并在交點(diǎn)處累積光線直接照射光強(qiáng)、反射光強(qiáng)以及折射光強(qiáng)，經(jīng)過疊加色度和不透明度來確定屏幕上所有像素點(diǎn)的顏色，最終達(dá)到渲染的目的。但是云粒子的數(shù)據(jù)量十分龐大，當(dāng)視點(diǎn)發(fā)生改變時(shí)，需要重新計(jì)算每一條光線，因此無論對于云數(shù)據(jù)的存儲，還是光線的計(jì)算，消耗的資源是巨大的。

針對以上不足，本文采用了八叉樹結(jié)構(gòu)優(yōu)化傳統(tǒng)光線跟蹤算法的數(shù)據(jù)存儲結(jié)構(gòu)，以提高數(shù)據(jù)存儲效率。

首先確定整個(gè)云場景的包圍盒，公式如下

(1)

然后將包圍盒按照八叉樹層次結(jié)構(gòu)劃分為0、1、2、3、4、5、6、7這8個(gè)子節(jié)點(diǎn)，如圖1所示，再根據(jù)需要對子節(jié)點(diǎn)遞歸劃分，但逐層劃分過程中對應(yīng)的節(jié)點(diǎn)的編碼位數(shù)會不斷的增加。在實(shí)驗(yàn)中，當(dāng)八叉樹結(jié)構(gòu)達(dá)到最大深度或者達(dá)到某個(gè)閾值時(shí)停止劃分。在此基礎(chǔ)上，本文算法將光線與云的求交問題轉(zhuǎn)化為光線與八叉樹節(jié)點(diǎn)求交，如果一條光線與某一個(gè)節(jié)點(diǎn)沒有相交，那么可以直接舍去該節(jié)點(diǎn)[8]。這樣一來，可以節(jié)省大量的數(shù)據(jù)存儲空間，優(yōu)化光線跟蹤算法的數(shù)據(jù)存儲結(jié)構(gòu)。

圖1 八叉樹劃分

1.2 改進(jìn)的鄰域分析算法

八叉樹結(jié)構(gòu)劃分完成后，光線如何從當(dāng)前八叉樹節(jié)點(diǎn)計(jì)算出下一個(gè)節(jié)點(diǎn)是提高光線跟蹤算法效率的關(guān)鍵。傳統(tǒng)八叉樹光線跟蹤算法為了存取某一個(gè)節(jié)點(diǎn)，必須先遍歷其余7個(gè)節(jié)點(diǎn)后才能進(jìn)行，造成了大量的遞歸運(yùn)算，導(dǎo)致了光線跟蹤算法效率的降低。張文勝等[9]提出了一種新的鄰域分析算法，通過簡單的0-1互換，可以從當(dāng)前節(jié)點(diǎn)快速的求出下一節(jié)點(diǎn)，加快了光線跟蹤的計(jì)算速度，但是該方法需要額外的判斷節(jié)點(diǎn)的層次關(guān)系，造成了大量的判斷和重新計(jì)算。針對以上不足，本文提出了一種改進(jìn)的鄰域分析算法[10]來加快不同劃分層次節(jié)點(diǎn)間的計(jì)算速度，該算法在0-1互換算法的基礎(chǔ)上，通過存儲節(jié)點(diǎn)的編碼和劃分層次來改變不同層次節(jié)點(diǎn)間的計(jì)算方式，可從當(dāng)前節(jié)點(diǎn)的編碼和射出方向直接計(jì)算出下一個(gè)節(jié)點(diǎn)，避免了大部分的遞歸運(yùn)算，極大地提高了計(jì)算效率。

首先將0到7這8個(gè)子節(jié)點(diǎn)劃分到6個(gè)基準(zhǔn)向的集合中X+={0，1，2，3}，X-={4，5，6，7}，Y+={2，3，6，7}，Y-={0，1，4，5}，Z+={0，2，4，6}，Z-={1，3，5，7}。假設(shè)一條光線入射到節(jié)點(diǎn)N，該節(jié)點(diǎn)的Morton碼為n，n1為節(jié)點(diǎn)第一層所處的位置，nk為節(jié)點(diǎn)第k層所處的位置，則n=n1n2n3…nk，r為該節(jié)點(diǎn)所在的劃分層次數(shù)，然后將該節(jié)點(diǎn)以如下形式存儲：(n，r)，則如圖2劃分后可將節(jié)點(diǎn)表示為 {(0，1)，(1，1)，(251，3)，(255，3)，(34，2)，(35，2)，(4，1)，(5，1)，(7，1)}。 最后根據(jù)節(jié)點(diǎn)N的Morton碼和所處的劃分層次進(jìn)行不同的方式計(jì)算，由已知的節(jié)點(diǎn)和光線的方向可以快速的求出下一節(jié)點(diǎn)。

具體步驟為：

(1)提取光線射出節(jié)點(diǎn)編碼n及所在層次rout，光線射入節(jié)點(diǎn)所在層次rin；

(2)當(dāng)rout≥rin時(shí)，從左向右保留n的rin位編碼，其余舍去；

1)提取保留后編碼的最后一位nk，將其轉(zhuǎn)換成二進(jìn)制碼，即nk=4ax+2ay+az，其中ax、ay、az=0或1；

2)進(jìn)行0-1互換，假設(shè)求X+、X-方向的鄰域節(jié)點(diǎn)，若ax=1，則ax=0；若ax=0，則ax=1，同理可求出Y和Z方向上的鄰域節(jié)點(diǎn)；

3)將互換后的二進(jìn)制碼再轉(zhuǎn)回八進(jìn)制碼mk，并替換nk，判斷mk是否與nk屬于同一個(gè)方向集合，若不是，則提取nk的前一位nk-1，轉(zhuǎn)入步驟1)；若是，則計(jì)算結(jié)束；

(3)當(dāng)rout

1)求出光線與該射出節(jié)點(diǎn)包圍盒的交點(diǎn)，判斷該交點(diǎn)在所處平面上的位置來添加相應(yīng)的編碼，增加編碼的位數(shù)為Δr，Δr=rin-rout；

2)進(jìn)行0-1互換，具體步驟同上。

如圖2所示，假設(shè)光線從節(jié)點(diǎn)“255”的X+方向射出，所求鄰域節(jié)點(diǎn)與節(jié)點(diǎn)“255”處于同一劃分層次，即rout=rin，那么提取該節(jié)點(diǎn)末位編碼“5”轉(zhuǎn)為二進(jìn)制碼“101”，則ax=1，ay=0，az=1，因?yàn)榍骕+方向，所以將ax進(jìn)行0-1互換，即ax=0，得到二進(jìn)制碼“001”，再轉(zhuǎn)成八進(jìn)制碼得“1”，判斷“1”屬于X+方向集合，計(jì)算結(jié)束，得出鄰域節(jié)點(diǎn)“251”。假設(shè)光線從節(jié)點(diǎn)“251”的Z-方向射出，由于節(jié)點(diǎn)“251”的劃分層次rout=3，所求節(jié)點(diǎn)的劃分層次rin=2，先根據(jù)rin=2從左向右保留2位編碼得出節(jié)點(diǎn)“25”，再根據(jù)0-1互換算法求出節(jié)點(diǎn)“34”。假設(shè)光線從節(jié)點(diǎn)“34”的Z+方向射出，rout=2，所求節(jié)點(diǎn)劃分層次rin=3，那么先根據(jù)求出光線與節(jié)點(diǎn)“34”包圍盒的交點(diǎn)，判斷該交點(diǎn)處于該平面的右下方，根據(jù)劃分規(guī)則，在節(jié)點(diǎn)“34”末位增加1位編碼“0”，得出節(jié)點(diǎn)“340”，在根據(jù)0-1互換算法計(jì)算出下一節(jié)點(diǎn)“251”。

圖2 光線求交

張文勝等[9]提出的0-1互換算法計(jì)算得出的是大小相同的節(jié)點(diǎn)，也就是劃分層次相同的節(jié)點(diǎn)，對于不同層次的節(jié)點(diǎn)，就需要經(jīng)過一系列節(jié)點(diǎn)層次關(guān)系的判斷，其算法步驟如圖3(a)所示，而且在提取部分葉子節(jié)點(diǎn)的時(shí)候需要滿足一個(gè)條件，在節(jié)點(diǎn)編碼后加上的標(biāo)號所屬的基準(zhǔn)向必須與射出節(jié)點(diǎn)的基準(zhǔn)向相反，再將所有滿足條件的葉子節(jié)點(diǎn)提取出來，并逐一判斷光線射出的交點(diǎn)是否在葉子節(jié)點(diǎn)包圍盒的范圍內(nèi),在這個(gè)過程中需要進(jìn)行大量的判斷和遞歸計(jì)算，降低了算法的計(jì)算效率。而本文算法通過存儲節(jié)點(diǎn)編碼和劃分層次的方式，可直接通過當(dāng)前節(jié)點(diǎn)計(jì)算出光線進(jìn)入的下一節(jié)點(diǎn)，解決了不同層次節(jié)點(diǎn)間的計(jì)算問題，避免了大量由于判斷節(jié)點(diǎn)不同層次帶來的遞歸運(yùn)算，其算法步驟如圖3(b)所示，最大限度提高了鄰域分析算法的計(jì)算效率，大大加快了光線與不同層次節(jié)點(diǎn)間的求交速度，對大規(guī)模三維云渲染速度起到了非常關(guān)鍵的作用。

圖3 算法對比

2 云三維模擬

光照模型是生成真實(shí)感圖形的基礎(chǔ)，它根據(jù)光學(xué)物理定律，計(jì)算物體表面任意一點(diǎn)投向觀察者眼中的光照強(qiáng)度，通過將光線上采樣點(diǎn)的顏色和透明度疊加，形成像素點(diǎn)，最終合成圖像。渲染技術(shù)的不同，采用的光照模型也不一樣，而全局光照模型是最適用光線跟蹤算法的光照模型。

2.1 光照模型優(yōu)化

Whitted[11]光照模型是典型的全局光照模型，該模型在簡單光照模型的基礎(chǔ)上增加了環(huán)境光在鏡面反射方向和規(guī)則折射方向?qū)Ρ徽丈潼c(diǎn)產(chǎn)生的光強(qiáng)，更符合三維云的真實(shí)效果，該模型可表示為

I=Ilocal+KsIs+KtIt

(2)

其中，Ilocal為光源的直接反射光，Is和It為環(huán)境鏡面反射光強(qiáng)和規(guī)則折射光強(qiáng)Ks和Kt為反射系數(shù)和折射系數(shù)，取值均在0～1之間。

在計(jì)算折射光強(qiáng)的過程中，折射光線的計(jì)算公式為

T=(cosθ2-(η1/η2)cosθ1)N-(η1/η2)d

(3)

其中，θ1和θ2分別表示光線入射角和折射角，η1和η2分別表示入射光線和折射光線所在空間介質(zhì)的折射率，N和d分別表示單位法向量和入射光線的單位方向向量。

但該折射光線的計(jì)算公式過于繁瑣，不利于云三維的實(shí)時(shí)繪制，因此本文在該公式的基礎(chǔ)上做出改進(jìn)，具體步驟如下：

如圖4所示，d、R、T分別為入射、反射、折射光線的方向向量，N為單位法向量，那么

T=-N+T1

(4)

R1=d+N

(5)

因?yàn)镹為單位向量，則

R1/T1=sinθ1/sinθ2=η2/η1

(6)

由式(6)得出

T1=(η1/η2)R1

(7)

將式(5)帶入式(7)，可得

T1=(η1/η2)(d+N)

(8)

再將式(8)帶入式(4)，得出

T=(η1/η2)(d+N)-N

(9)

運(yùn)用改進(jìn)后的光線折射公式，降低了計(jì)算復(fù)雜度，在大規(guī)模三維云實(shí)時(shí)渲染的過程中有效地提高了繪制速度。

圖4 折射光線求解

2.2 渲染流程

三維云的渲染包括預(yù)處理和實(shí)時(shí)處理兩個(gè)部分，在預(yù)處理階段，利用光線跟蹤算法對云粒子進(jìn)行采樣以及插值計(jì)算，計(jì)算出粒子的光強(qiáng)。在實(shí)時(shí)處理階段，通過式(10)計(jì)算得出粒子的不透明度和顏色值

(10)

其中，Cnow和αnow表示為當(dāng)前體素的顏色值和不透明度，Cin和αin表示光線進(jìn)入當(dāng)前體素時(shí)的顏色值和不透明度，Cout和αout表示光線穿過體素后的顏色值和不透明度，本文實(shí)驗(yàn)中設(shè)定當(dāng)α=1時(shí)，停止計(jì)算。最終將粒子的不透明度和顏色值賦予屏幕像素，合成圖像。

3 實(shí)驗(yàn)結(jié)果

本實(shí)驗(yàn)所用的硬件配置是Intel i5-6500，3.20 GHz CPU，8.00 G內(nèi)存，Nvidia GTX 1060顯卡，操作系統(tǒng)為Windows 7。使用的語言為C++，可視化部分使用OpenGL和Vapor輔助完成。實(shí)驗(yàn)數(shù)據(jù)為中尺度天氣預(yù)報(bào)模式WRF v3.3.1模擬數(shù)據(jù)。模擬區(qū)域?yàn)椋?00km×400km范圍；水平格距1 km；中心緯度：23°；中心經(jīng)度：129°；經(jīng)度范圍：127°至131°；緯度范圍：21°至25°；垂直層數(shù)：50層三維氣象數(shù)據(jù)。

圖5為傳統(tǒng)八叉樹光線跟蹤算法和本文算法渲染效果對比圖，表1為兩種方法繪制所用時(shí)間。分析圖5和表1可以得出，本文方法有效地改善了鋸齒化現(xiàn)象，對光線的明暗效果和云縷的展現(xiàn)都具有明顯提升，更好展現(xiàn)了真實(shí)數(shù)據(jù)云的物理特性，同時(shí)極大地提高了渲染速度，比傳統(tǒng)方法提高了60.4%。

圖5 傳統(tǒng)八叉樹光線跟蹤和本文方法渲染效果對比

表1 繪制時(shí)間對比

圖6為八叉樹空間分割技術(shù)[12]、KD-Tree方法[3]以及空間均勻網(wǎng)格技術(shù)[13]與本文算法的渲染效果對比圖，表2為以上方法渲染幀率對比。實(shí)驗(yàn)數(shù)據(jù)為中尺度模式WRF v3.3.2模擬數(shù)據(jù)，經(jīng)度范圍：106°至110°；緯度范圍：30°至34°。分析圖6可以看出，八叉樹空間剖分整體繪制效果較差，在云的細(xì)節(jié)上效果不明顯。KD-Tree方法對于云整體效果有所改進(jìn)，但是在云周邊出現(xiàn)了鋸齒化現(xiàn)象?？臻g均勻網(wǎng)格鋸齒化現(xiàn)象明顯，光線的明暗效果較差，而且沒有很好展現(xiàn)云縷效果，和本文方法比較起來整體效果不夠清晰。分析表2可以得出，本文方法在提高了繪制效果的基礎(chǔ)上，有效地減少了繪制時(shí)間，平均渲染幀率提高了7.1幀。

4 結(jié)束語

本文提出一種八叉樹鄰域分析的光線跟蹤算法并用于三維氣象云數(shù)據(jù)可視化，該方法首先利用八叉樹結(jié)構(gòu)優(yōu)化了光線跟蹤算法的數(shù)據(jù)存儲結(jié)構(gòu)，然后改進(jìn)鄰域分析算法，通過存儲節(jié)點(diǎn)編碼和劃分層次，改善了不同節(jié)點(diǎn)間的計(jì)算方式，加快了光線與三維云的求交速度，最終改進(jìn)了折射光線的計(jì)算公式，簡化了Whitted光照模型，在算法的實(shí)現(xiàn)過程中利用OpenGL和Vapor輔助完成。該方法有效降低了渲染時(shí)間，提高了繪制效果和渲染幀率。在以后的研究

圖6 各類方法渲染效果對比

表2 渲染幀率對比

工作中，還要考慮以下幾個(gè)問題，在云邊界處，云粒子較少的情況下會產(chǎn)生鋸齒化現(xiàn)象，后期將采用球形粒子來改善這種情況。