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

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

0 引 言

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

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

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

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

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

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

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

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

(1)

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

圖1 八叉樹劃分

1.2 改進的鄰域分析算法

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

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

具體步驟為：

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

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

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

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

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

(3)當rout

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

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

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

圖2 光線求交

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

圖3 算法對比

2 云三維模擬

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

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

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

I=Ilocal+KsIs+KtIt

(2)

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

在計算折射光強的過程中，折射光線的計算公式為

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

(3)

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

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

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

T=-N+T1

(4)

R1=d+N

(5)

因為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)

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

圖4 折射光線求解

2.2 渲染流程

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

(10)

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

3 實驗結(jié)果

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

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

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

表1 繪制時間對比

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

4 結(jié)束語

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

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

表2 渲染幀率對比

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