俞 靜,石晶晶

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

0 引 言

山脈、平原和沙灘等類地形可以說(shuō)是自然界中最為復(fù)雜的景物.而在虛擬現(xiàn)實(shí)技術(shù)中,將虛擬場(chǎng)景架設(shè)在連綿起伏的山脈、平原和沙灘等自然環(huán)境中,可以使虛擬場(chǎng)景的逼真度大幅提高.由于具有三維真實(shí)感的地形能夠逼真地反映真實(shí)世界,所以三維真實(shí)感地形的繪制方法一直是國(guó)內(nèi)外計(jì)算機(jī)圖形學(xué)領(lǐng)域研究的熱點(diǎn).

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

1 細(xì)節(jié)層次技術(shù)及分形理論

細(xì)節(jié)層次技術(shù)的思想,是指對(duì)同一個(gè)場(chǎng)景中的物體使用具有不同細(xì)節(jié)的描述方法,從而得到一組模型供繪制時(shí)選擇使用.層次細(xì)節(jié)簡(jiǎn)化技術(shù)在不影響畫面視覺效果的條件下通過(guò)逐次簡(jiǎn)化景物的表面細(xì)節(jié)來(lái)減少場(chǎng)景的幾何復(fù)雜性,從而提高繪制算法的效率[1].細(xì)節(jié)層次技術(shù)通常對(duì)每一個(gè)原始多面體模型建立幾個(gè)不同逼近精度的幾何模型,與原模型相比,每個(gè)模型均保留了一定層次細(xì)節(jié).在繪制時(shí),根據(jù)不同的標(biāo)準(zhǔn)選擇適當(dāng)?shù)膶哟文Ｐ蛠?lái)表示物體.通常的做法是把一些不重要的圖元(頂點(diǎn)、邊和三角形)從多邊形網(wǎng)格中移去.不過(guò),在對(duì)同一物體簡(jiǎn)化后,物體在旋轉(zhuǎn)、平移等運(yùn)動(dòng)過(guò)程中因模型的轉(zhuǎn)換而產(chǎn)生形狀差異.

1973年,Mandelbrot首次提出了分?jǐn)?shù)維與分形幾何的設(shè)想,其研究對(duì)象是自然界和非線性系統(tǒng)中出現(xiàn)的不光滑和不規(guī)則幾何形體.由于分形關(guān)注的是物體的隨機(jī)性、奇異性和復(fù)雜性,因而具有細(xì)節(jié)無(wú)限以及統(tǒng)計(jì)自相似性的典型特征.它采用分形曲線,利用自然景物的輪廓具有“自相似”的特征,能夠得到逼真的效果,從而解決了使用光滑曲線這類不能進(jìn)行微分計(jì)算的曲線對(duì)海岸線、山的輪廓描述時(shí)帶來(lái)的失真問(wèn)題.分形理論的出現(xiàn)為地形仿真的發(fā)展注入了強(qiáng)大的動(dòng)力,由分形曲線發(fā)展而來(lái)的分形曲面可以較好的描述地形地貌.另外,用分形方法產(chǎn)生的三維模型能完好地保持模型的拓?fù)浣Y(jié)構(gòu),因而具有良好的反走樣效果,只是在精細(xì)結(jié)構(gòu)上有一定差別.

2 Diamond-Square算法及改進(jìn)

2.1 Diamond-Square算法

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

圖1 Diamond-Square算法原理圖

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

式中,RO為隨機(jī)變量,通常采用均值為0,方差為1的正態(tài)隨機(jī)分布函數(shù)來(lái)產(chǎn)生.

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

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

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

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

2.2 改進(jìn)的Diamond-Square算法

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

算法的改進(jìn)思想就是在每一次根據(jù)構(gòu)成網(wǎng)格的4個(gè)角的高程計(jì)算網(wǎng)格中心點(diǎn)和正方形四邊中點(diǎn)的基礎(chǔ)上,增加由地形高程的自相似參數(shù) H和方差δ構(gòu)成的補(bǔ)償項(xiàng).

地形高程的自相似參數(shù) H反映了地形表面的復(fù)雜程度和粗糙度.參數(shù) H值越小,表明地形越復(fù)雜、越粗糙,反之越平滑.地形高程的方差δ則反映區(qū)域地形整體形狀的起伏特征,δ的值越大,地形起伏就越大,反之就越小.地形的自相似參數(shù) H和方差δ采用分形布朗運(yùn)動(dòng)的原理來(lái)提取,

令,

則,式(6)兩邊取對(duì)數(shù)可得,

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

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

同時(shí),由分形布朗運(yùn)動(dòng)的性質(zhì)和遞歸中點(diǎn)細(xì)分的原理可得,

現(xiàn)在加入補(bǔ)償項(xiàng)sk可得,

其中,gauss()函數(shù)服從標(biāo)準(zhǔn)正態(tài)分布,d為網(wǎng)格間距.

式(10)化簡(jiǎn)可得,

3 仿真實(shí)驗(yàn)

在仿真實(shí)驗(yàn)中,仿真實(shí)現(xiàn)的硬件環(huán)境為,英特爾酷睿2 T6600雙核處理器,2 G B內(nèi)存,512 MB獨(dú)立顯卡;軟件環(huán)境為,Windows XP專業(yè)版下Visual C++ 6.0及三維圖形標(biāo)準(zhǔn)OpenG L 2.1.

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

圖2 三維模擬地形仿真結(jié)果

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

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

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

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

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

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

4 結(jié) 論

利用分形理論生成的三維模型地形,首先需要靜態(tài)拼嵌高程數(shù)組來(lái)產(chǎn)生逼真程度很高的靜態(tài)地形,然后根據(jù)需要賦予不同的迭代次數(shù)和相關(guān)參數(shù),從而生成具有動(dòng)態(tài)特性的三維真實(shí)感地形圖.仿真實(shí)驗(yàn)表明,采用改進(jìn)的Diamond-Square算法,提取三維模擬地形的自相似參數(shù) H和方差δ構(gòu)成補(bǔ)償項(xiàng)加入有序的迭代步驟,可有效地改善直接采用Diamond-Square算法生成三維模擬地形時(shí)產(chǎn)生的“褶皺”和“尖峰”現(xiàn)象.

[1]祝清魯.大規(guī)模場(chǎng)景中LOD技術(shù)的研究與應(yīng)用[D].北京:北京郵電大學(xué),2009.

[2]和平鴿工作室.OpenG L高級(jí)編程與可視化系統(tǒng)開發(fā)[M].北京:中國(guó)水利出版社,2005.

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

[4]李捷,唐澤圣.三維復(fù)雜模型的事實(shí)連續(xù)多分辨率繪制[J].計(jì)算機(jī)學(xué)報(bào),1998,6(6):481-491.

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

[6]聶永丹.實(shí)時(shí)虛擬環(huán)境幾何、運(yùn)動(dòng)和行為L(zhǎng)OD技術(shù)研究[D].大慶:大慶石油學(xué)院,2009.

[7]劉 揚(yáng).分布環(huán)境下的海量三維地形可視化關(guān)鍵技術(shù)研究[D].北京:北京師范大學(xué),2008.