視點相關的真實感三維風景區模擬研究與實現

摘要:提出采用八叉樹組織真實山體數據，根據視點距離采用不同的細節層次LOD表示山體各部分，并結合視覺剪裁和幀間相關性進一步減少繪制的山體，達到加速三維地形的繪制和漫游的目的#65377;使用混合紋理映射#65380;陰影渲染技術，并加入山谷中的水面模擬，生成具有真實感的大規模三維風景場景#65377;實驗結果表明該方法有效地減少了算法復雜度，易實現碰撞檢測，大大提高了繪制效率，在PC機上能實時地生成高分辨率#65380;具有真實感的場景，完全滿足VR交互要求#65377;

關鍵詞:地形; 八叉樹; 視覺約束體; 可視性剪裁; 數字高程模型

中圖分類號:TP391.41文獻標志碼:A

文章編號:1001-3695(2007)04-0192-03

0引言

近幾年來，隨著計算機硬件技術和計算機圖形學#65380;三維仿真#65380;虛擬現實等技術的快速發展，具有廣泛應用領域的虛擬室外場景的技術成為現實#65377;該技術能創造出非常逼真的#65380;有說服力的虛擬自然風景區的實時漫游#65377;由于其巨大的經濟效益而成為人們關注的焦點#65377;

虛擬風景區的場景數據來源于高度圖，通過導入圖中真實地形數據生成地形模型#65377;由于數據量大#65380;地形場景大，在研制大型可視化系統時，必須使用一定的技術對場景中模型進行管理#65377;許多學者在這方面做了大量研究工作#65377;文獻[1]通過基于網格的四叉樹劃分表示塊，對三角形實現自下而上的合并，實時生成與視點相關的連續LOD模型;但處理塊間的裂縫時方法過于復雜，計算量太大且影響實時效果#65377;Hugues^[2]在地形方面應用PM(Progressive Mesh)模型實現連續的LOD模型，并且提供了與視點相關的支持;但不能解決塊的拼接問題，塊與塊之間不進行簡化，在一定程度上影響了簡化的效率#65377;M.de Berg^[3]構造了與視點相關的TIN結構#65377;當視點改變時根據誤差控制標準重構TIN模型，但任何局部的修改都要影響到全局，降低構網速度，影響實時性效果#65377;

本文基于八叉樹數據結構，提出了一種結合可視化剪裁和幀間相關性的地形繪制簡化算法#65377;該算法依據視點的變化動態生成不同層次細節的LOD模型表示山體，利用視覺剪裁選出位于視覺可見體內的節點，根據幀間相關性挑選出節點中未渲染的三角形面，實時生成三維地形;并在該三維地形基礎上加入水面#65380;多分辨率紋理映射和陰影繪制，生成具有真實感的三維風景區#65377;本算法有效降低了計算復雜度，并且局部的數值修改不會影響全局效果，同時易于實現與山體的碰撞檢測#65377;

1地形的來源和數據組織

1.1數字高程模型

風景區中的真實地形是現實世界中真實地形的再現，具有非常高的真實度，必須采用真實世界中的具體數據來構造#65377;在這種情況下一般采用數字高程模型(Digital Elevation Model，DEM)方法#65377;對于真實地形的構造，通常采用經緯度線構成的規格化網格體逼近的方法#65377;其主要關鍵技術在于獲取網格點的有關參數，包括它的經緯度#65380;高程和顏色等數據#65377;顯然在地形數字化時，經緯度的自變量是可以自動獲取的，而高程和顏色等數據則是自變量的函數，隨著經緯度的變化而變化#65377;因此，關鍵的問題是如何獲取對應經緯度網格點的高程和顏色數據等#65377;本系統采用一種理想的全自動化的獲取高程值，獲取用256灰度級的灰度圖像作為高程的地形圖，讀取對應網格點的顏色數據，再通過查表或函數關系來計算它的高程#65377;網格點的顏色數據可以通過真實照片來獲取，從而生成具有高度真實感和精確性的地形#65377;

1.2八叉樹的優點

本系統采用八叉樹組織山體數據是因為八叉樹在地形可視化中具有如下優點:①空間中任意形狀的實體都可采用統一的立方體表示，數據結構簡單且容易實現#65377;②易于檢測空間實體間的碰撞#65377;③樹中各節點在數據結構中總是排好序的，易實現消隱及顯示輸出#65377;④把場景組織在一個樹結構中，可以快速判斷出可視區域#65377;⑤對節點大小的不同劃分，決定碰撞檢測的精度;精度要求高則節點小，幀速隨之下降，反之節點大可提高幀速，應用時可根據用戶具體要求實現兩者間的動態平衡#65377;

1.3地形LOD層的劃分

現有的DEM數據大多采用規則格網結構#65377;規則格網是一個二維點陣#65377;該結構已經對DEM數據進行了很好的組織，因此只需將格網數據讀入內存，直接對讀入的DEM數據塊進行LOD層次劃分^[4]即可#65377;

在不影響畫面視覺效果的條件下，通過層次細節顯示和簡化技術LOD(Level Of Detail)逐次簡化地形的表面細節來減少場景的幾何復雜性，從而提高繪制算法的效率#65377;按LOD的思想，遠視點地形區域的繪制無須使用與近視點一樣的精度#65377;因此為了加快可視化速度，按視點距離對規則格網進行LOD分層是一種直觀簡明的方法#65377;如圖1所示，Point為觀察視點位置，θ為觀察視角，Height為觀察點的高度，P為DEM上的視點中心，則在虛線正方形所在的區域內需要較高精度的LOD層次(實際的觀察區域為圓，為了計算上的方便，用該圓的外切正方形代替該圓)，則不同LOD層次為大小不同的嵌套正方形區域#65377;基于此簡單思想，可以很方便地得到任一時刻#65380;任一視點位置的LOD層次劃分#65377;

2地表的實現

2.1地形數據的預處理

對地形采用八叉樹進行空間劃分，樹內節點的三角形通過鏈表相連#65377;

建立八叉樹節點，需要考慮兩個基本問題:①在分解過程中的原則#65377;這可以通過規定一個閾值K(K表示空間對象的個數)來解決，即當區域中空間對象(三角形)的個數多于K時，該區域需進行二次劃分#65377;②分辨率，即分解時允許達到的最小子區是多大的問題#65377;這可以規定一個不需要分割的正方體大小來解決以上問題，以上劃分的依據決定碰撞檢測的精度#65377;以遞歸方式劃分地形后，八叉樹中存在兩類節點#65377;一類是代表未被物體占據的子區域的空葉節點，即在劃分過程中一旦該節點不包括地形數據，則停止劃分并作為葉節點保存;另一類則是代表被山體一部分占據的最小尺寸單元#65377;

2.2可見體性篩選及動態LOD生成

提高虛擬場景繪制速率的有效途徑是采用預處理技術，將顯示流程中盡可能多的工作事先存儲起來，場景生成時只需調用這些信息即可實現實時繪制#65377;可見性預計算技術就是基于這種思想的一種消隱算法#65377;實驗證明，隨著觀察點的運動，場景中約有34%~80%的實體處于視覺體外#65377;因此視覺體剪裁對整個地形繪制速度起著重要的作用#65377;

用戶在漫游時，須更新視覺可見體，并相應計算八叉樹節點與約束體之間的位置關系#65377;如果當前節點完全不可見或完全可見，那么它的所有子節點也必然完全不可見或完全可見#65377;以上兩種情況均不必在遞歸判斷子節點，直接設置節點的可視標志后跳出循環#65377;如果當前節點部分可見，那必須依次判斷其各自子節點的可見性，直到葉子節點為止#65377;

當視點移動時，必須及時更新山體的LOD模型#65377;以視點和山體的距離作為選取不同精度模型的依據，由八叉數的遞歸次數來生成不同精度的LOD模型#65377;相鄰的LOD模型精度相差一倍#65377;

2.3幀間相關性篩選

經上述處理后，八叉樹節點分為三類，即完全可見#65380;部分可見和完全不可見#65377;對于完全可見和部分可見節點的三角形，根據幀間相關性進一步進行篩選#65377;在漫游中，前后幀之間繪制的三角形存在一定的相關性:在第N幀中繪制的三角形如果也出現在N+1幀，則不必重繪#65377;因此，在渲染部分只繪制未在上一幀中繪制的三角形#65377;系統中通過檢測三角形繪制時的幀號是否等于當前幀號來判斷是否需要渲染該三角形#65377;將幀號不等的三角形(未繪制)頂點組織成表，繪制該表實現場景的刷新，并更新三角形的幀號#65377;

綜上所述，在本系統中，對需要渲染部分的處理步驟是:

(1)根據視點的位置#65380;方向#65380;視角#65380;視域長寬比例和遠裁剪面，生成視覺約束體面#65377;

(2)遍歷八叉樹，選擇所有在視覺約束體內和與視覺約束體相交的葉節點，并根據節點中心和視點的距離選擇相應的LOD模型#65377;

(3)根據幀間相關性，在上述結果中選擇未繪制節點的三角形組織成繪制列表#65377;

(4)下一幀中渲染三角形列表#65377;

3真實感的加強

3.1水波模擬

在真實風景區中，山谷中常常存在河流#65380;湖泊#65377;為真實地再現其場景，必須對水面進行模擬#65377;系統中水面的模擬采用覆蓋整個地表的網格實現#65377;網格以三角形相連，其可見性由其垂直方向上方是否存在山體節點決定，若存在非空節點則該位置的水面不可見#65377;

為模擬水面中存在起伏的波浪，系統設定相隔一定時間產生新的波浪，隨機地選擇網格內部某點作為該水波的中點#65377;水波的傳播和疊加通過修改接觸點周圍頂點的位移直接得到#65377;假設邊界條件是齊次的(即邊緣不上下運動)且水面的初始z速度為零，則可以采用中心差分來模擬二維波動方程中的偏導數^[5]#65377;如式(1)中zni， j表示坐標為(i， j)的頂點在n時刻的高度;C是水波越過水面傳播的速度;h表示網格在x和y方向上相鄰頂點之間的距離;t表示水面的連續兩個狀態之間的時間間隔#65377;

為反射達到水面的光線，產生光影變換，達到水面漣漪的效果(圖2)，需要及時更新每個三角形的法矢量#65377;其法向量N的計算如下:

3.2紋理添加和陰影渲染

應用紋理映射技術把從真實世界中的物體表面圖像貼到三維場景中同種物體的表面，可使渲染后的物體與真實世界中的物體惟妙惟肖#65377;在現實的山體中，不同的高度對應不同的景物，為達到逼真的模擬效果，選用多幅紋理#65377;系統中選用四幅地形紋理，分別是雪地#65380;巖石#65380;草地#65380;沙子#65377;根據地面高度使用式(3)改變混合因子Percent:

其中，h1為高度權重，雪地#65380;巖石#65380;草地#65380;沙子的取值分別為255#65380;192#65380;128及64;h2為該點的實際高度，依據該因子對對應點進行Alpha混合，產生混合紋理，結果如圖2所示#65377;

三維場景中的陰影可以給出有關場景的信息#65380;物體間的空間關系以及光源的位置，沒有陰影的場景很不真實#65377;山體在光照作用下產生陰影，因此需要生成山體的陰影#65377;對于每一個柵格點，選擇從光源點發出的光線到地圖的交點(圖3)#65377;圖3中，A為柵格中當前的工作目標點;光源位置坐標為C;B為光源的投影坐標;L為從光源到工作點的光線矢量;P表示光線經過路線的所有投影點，用來參與從點A到點B之間的2D線計算;X(P)為投影點P在光線矢量上的坐標#65377;任意點P，如果在山體的高度值大于點X(P)的Y值，表明光線L與山體相交，點A的光照值就等于環境光值Ambient，接著處理下一個目標點#65377;如果所有的P類型的點都測試完沒有發現交點，則點A的光照值就使用式(4):

然后將光照值的范圍擴展為[0，255]#65377;設置地形坐標的每一個點的顏色為它相應陰影圖中的顏色，以達到渲染陰影的效果#65377;

4用戶漫游

在用戶的漫游過程中必須檢測視點位置的有效性，即視點必須位于山體的外側#65377;因此必須對視點和山體進行碰撞檢測#65377;根據用戶的移動速度和運動方向預測下一幀是否會與山體發生碰撞#65377;如果發生碰撞則停止視點移動#65377;

視點camera(m_ fX，m_ fY，m_ fZ)與八叉樹節點中心node(x，y，z)的距離如下:

式(6)用于預測在下一幀中，視點移動后是否發生碰撞，即是否到達節點內部:

Dist-m_fSpeed×Interval>Length/2未碰撞≤Length/2發生碰撞(6)

其中，m_fSpeed為用戶漫游的速度;Interval為下一幀到來時間間隔，一般取為0.05 s;Length為節點的長度#65377;

5實驗結論

根據上述算法，在Visual C++6.0平臺上采用OpenGL開發了具有真實感的地形引擎#65377;表1中給出本文算法和文獻[6，7]中的算法在相同配置機器上的性能比較，屏幕和紋理的分辨率分別取800×600和256×256#65377;表2給出了在Pentium 4微機(主頻2.6 GHz，內存512 MB，顯卡GeForce 4)，本引擎在不同分辨率下繪制的三角形數目和幀速的關系#65377;

算法對比項

本文算法文獻[6]文獻[7]

數據結構八叉樹四叉樹LOD二叉樹LOD

篩選方法視覺體剪裁+幀間相關性視覺體剪裁視覺體剪裁

陰影#65380;水波支持未提及未提及

不同分辨率支持未提及未提及

屏幕分辨率紋理分辨率

三角形數八叉樹節點劃分(值)

山體水面最多三角形(個)最大尺寸(網格間距)

由表1可以看出，算法在地形簡化方面比文獻[6，7]的算法簡單，程序上容易實現#65377;相同的實驗平臺下，采取本算法編寫的引擎系統在漫游時的幀速高于文獻[6，7]，并且本算法支持山體陰影繪制#65380;動態水波渲染和不同的屏幕分辨率及紋理分辨率，有效地增加了三維場景的真實感#65377;在進行碰撞檢測時可根據用戶對八叉樹節點的劃分尺度動態調節幀速和碰撞檢測精度間的平衡，滿足不同用戶的要求#65377;由表2可以看出，即使在漫游相當高分辨率的大規模山體場景，仍能滿足或超過實時動態交互的要求#65377;

在屏幕分辨率為1 600×1 200，紋理分辨率為2 048×2 048，節點最多三角形數目為20個，最大尺寸為15格間距的條件下漫游1 min，獲得的性能曲線如圖4所示#65377;

實驗證明，運用上述技術后，即使在高分辨率#65380;精細劃分節點情況下，幀速也保持在20 fps左右，保證了

視覺上漫游的流暢性，滿足地形場景實時漫游的效果#65377;圖5(a)為風景區的灰度高度數據圖，圖5(b)為高度圖所對應的三維場景#65377;

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。