基于分形理論的三維模擬地形仿真

俞 靜,石晶晶

(1.西南交通大學信息科學與技術學院,四川成都 610031; 2.西南交通大學電氣工程學院,四川成都 610031)

0 引 言

山脈、平原和沙灘等類地形可以說是自然界中最為復雜的景物.而在虛擬現實技術中,將虛擬場景架設在連綿起伏的山脈、平原和沙灘等自然環境中,可以使虛擬場景的逼真度大幅提高.由于具有三維真實感的地形能夠逼真地反映真實世界,所以三維真實感地形的繪制方法一直是國內外計算機圖形學領域研究的熱點.

目前,三維真實感地形的生成分為兩類:真實地形和模擬地形.真實地形是現實世界中真實地形的再現,具有非常高的真實度,對于真實地形的構造,通常采用經緯度線構成的規格化網格體逼近的方法,其關鍵技術在于獲取網格點的有關參數,包括它的經緯度、高程和顏色等數據.而在一般的虛擬現實場景中,三維地形只需滿足感官上的要求即可,在這種情況下,可以采用模擬地形.模擬地形通常采用隨機生成的方法或采用分形法生成,圖形生成的速度較快.本文以OPENG L和VC++為基礎,并基于分形理論,利用改進的Diamond-Square算法完成模擬地形的三維地形仿真.

1 細節層次技術及分形理論

細節層次技術的思想,是指對同一個場景中的物體使用具有不同細節的描述方法,從而得到一組模型供繪制時選擇使用.層次細節簡化技術在不影響畫面視覺效果的條件下通過逐次簡化景物的表面細節來減少場景的幾何復雜性,從而提高繪制算法的效率[1].細節層次技術通常對每一個原始多面體模型建立幾個不同逼近精度的幾何模型,與原模型相比,每個模型均保留了一定層次細節.在繪制時,根據不同的標準選擇適當的層次模型來表示物體.通常的做法是把一些不重要的圖元(頂點、邊和三角形)從多邊形網格中移去.不過,在對同一物體簡化后,物體在旋轉、平移等運動過程中因模型的轉換而產生形狀差異.

1973年,Mandelbrot首次提出了分數維與分形幾何的設想,其研究對象是自然界和非線性系統中出現的不光滑和不規則幾何形體.由于分形關注的是物體的隨機性、奇異性和復雜性,因而具有細節無限以及統計自相似性的典型特征.它采用分形曲線,利用自然景物的輪廓具有“自相似”的特征,能夠得到逼真的效果,從而解決了使用光滑曲線這類不能進行微分計算的曲線對海岸線、山的輪廓描述時帶來的失真問題.分形理論的出現為地形仿真的發展注入了強大的動力,由分形曲線發展而來的分形曲面可以較好的描述地形地貌.另外,用分形方法產生的三維模型能完好地保持模型的拓撲結構,因而具有良好的反走樣效果,只是在精細結構上有一定差別.

2 Diamond-Square算法及改進

2.1 Diamond-Square算法

Diamond-Square算法由Fourniew等[2]提出,其又稱為“鉆石—四邊形”算法.Diamond-Square算法的具體步驟如圖1所示.

圖1 Diamond-Square算法原理圖

圖1中,(1)為原始的正方形,正方形的4個頂點依次為A、B、C、D,假設其高度分別為 hA、hB、hC和hD.經過第一個Diamond步后,生成正方形的中點O如圖1(2)所示,其中黑色圓點表示新生點,灰色圓點表示已知點.此時,正方形中點的高度值為 h0,

式中,RO為隨機變量,通常采用均值為0,方差為1的正態隨機分布函數來產生.

然后,進行第一個Square步,這一步分別生成正方形各邊中點,如圖1(3)中的點 p和點q,其高度值hp、hq為,

同樣的,式中的 Rp和Rq為隨機變量,取值與RO相同.

依次類推可以計算出每條邊的中點的高度值.這樣,完成一個完整的Diamond-Square步驟之后,由4個已知點變為了9個已知點.圖1(4)、(5)是第二個Diamond-Square步驟,第二步與第一步有兩點不同.首先,現在有4個正方形而不是一個,因此必須計算4個正方形面的中心;其次,生成隨機數的范圍已經被減小了,圖1(4)在這一步得到的4個正方形中心值顯示為黑色.完成了上述步驟之后,由9個已知點變成了25個已知點.

由此可見,采用Diamond-Square算法將一個正方形經過單獨一次細分過程,可得到4個正方形.第二次細分過程可得到16個正方形,第三次細分過程可得到64個正方形……正方形數目等于2n+2,其中,n為細分過程的迭代次數.如果分配更大的數組,可以將迭代過程進行更多遍,每一遍將加入更多的細節.所以,采用Diamond-Square算法對地形的生成速度很快,而且實現非常容易,且可以生成任意分辨率的三維地形.

2.2 改進的Diamond-Square算法

采用Diamond-Square算法實時繪制三維地形雖然有諸多優點,但該算法也存在一定的局限性.采用該方法生成的地形表面容易產生明顯的“褶皺”和“尖峰”[3,4].基于此,本文提出一種改進的Diamond-Square算法,其可以在一定程度上改善生成的地形表面出現“褶皺”和“尖峰”的現象.

算法的改進思想就是在每一次根據構成網格的4個角的高程計算網格中心點和正方形四邊中點的基礎上,增加由地形高程的自相似參數 H和方差δ構成的補償項.

地形高程的自相似參數 H反映了地形表面的復雜程度和粗糙度.參數 H值越小,表明地形越復雜、越粗糙,反之越平滑.地形高程的方差δ則反映區域地形整體形狀的起伏特征,δ的值越大,地形起伏就越大,反之就越小.地形的自相似參數 H和方差δ采用分形布朗運動的原理來提取,

令,

則,式(6)兩邊取對數可得,

由此可知,lgE(|f(x+△x)-f(x)|)與 lg‖△x‖與成線性關系,采用最小二乘法得其直線回歸的函數為,

式(8)最小化即可求出參數 H和δ.

同時,由分形布朗運動的性質和遞歸中點細分的原理可得,

現在加入補償項sk可得,

其中,gauss()函數服從標準正態分布,d為網格間距.

式(10)化簡可得,

3 仿真實驗

在仿真實驗中,仿真實現的硬件環境為,英特爾酷睿2 T6600雙核處理器,2 G B內存,512 MB獨立顯卡;軟件環境為,Windows XP專業版下Visual C++ 6.0及三維圖形標準OpenG L 2.1.

三維模擬地形的仿真結果如圖2所示.

圖2 三維模擬地形仿真結果

圖2中,在假設只有4個初始點的情況下生成三維分形地形.圖2(a)為經過第一步Diamond-Square算法步驟后的結果,圖2(b)、圖2(c)、圖2(d)的迭代次數依次為2,5,7.從圖2中可以明顯的看出,隨著迭代次數的增加,生成的模擬地形中點的個數是成指數增長的,并呈現出真實地形的粗糙感.

在圖2中,地形自相似參數 H值均為0.7.下面改變 H值,仿真結果如圖3所示.

圖3 采用不同 H值的模擬地形仿真結果

圖3(a)為采用改進的Diamond-Square算法迭代5次,地形自相似參數 H為0.9的三維地形生成圖,圖3(b)同樣為迭代5次,地形自相似參數 H為0.6的三維地形生成圖.由圖3可知,當 H值越大時,采用改進的Diamond-Square算法生成的三維模擬地形越平滑,當H值越小時,生成的三維模擬地形已經出現了明顯的凸起和溝壑.因此,在實際的應用中可以根據需要調整 H值來生成滿足實際需要的三維模擬地形.

圖4為使用改進的Diamond-Square算法生成三維模擬地形并賦予紋理貼圖后的渲染圖.在圖4中,三維模擬地形在高度值低的地方呈現出黑色,高度值高的地方呈現出灰色.此外,在具體的工程實際應用中,三維模擬地形的地形紋理圖片可根據實際需要選取,也可以通過在程序中進行設置而使地形的高程呈現出不同的顏色.

圖4 三維模擬地形渲染效果圖

4 結 論

利用分形理論生成的三維模型地形,首先需要靜態拼嵌高程數組來產生逼真程度很高的靜態地形,然后根據需要賦予不同的迭代次數和相關參數,從而生成具有動態特性的三維真實感地形圖.仿真實驗表明,采用改進的Diamond-Square算法,提取三維模擬地形的自相似參數 H和方差δ構成補償項加入有序的迭代步驟,可有效地改善直接采用Diamond-Square算法生成三維模擬地形時產生的“褶皺”和“尖峰”現象.

[1]祝清魯.大規模場景中LOD技術的研究與應用[D].北京:北京郵電大學,2009.

[2]和平鴿工作室.OpenG L高級編程與可視化系統開發[M].北京:中國水利出版社,2005.

[3]曹為剛.基于OpenG L的三維地形可視化技術與實現[J].四川建筑,2006,4(2):91-95.

[4]李捷,唐澤圣.三維復雜模型的事實連續多分辨率繪制[J].計算機學報,1998,6(6):481-491.

[5]姚慧敏,崔鐵軍.基于四叉樹的LOD地形模擬及其數據組織方法研究[J].地理信息世界,2007,12(6):56-59.

[6]聶永丹.實時虛擬環境幾何、運動和行為LOD技術研究[D].大慶:大慶石油學院,2009.

[7]劉 揚.分布環境下的海量三維地形可視化關鍵技術研究[D].北京:北京師范大學,2008.