面向虛擬環(huán)境的地形自動(dòng)生成新方法

面向虛擬環(huán)境的地形自動(dòng)生成新方法

1自動(dòng)生成地形景觀模擬一直是一個(gè)充滿(mǎn)挑戰(zhàn)的研究領(lǐng)域。作為自然景觀中最為常見(jiàn)的形式之一的地形,其生成方法的研究有著重要的意義。近些年來(lái)關(guān)于3D地形模擬的主要方法,按照是否基于真實(shí)數(shù)據(jù)可以大致分為2類(lèi)。第一類(lèi)是基于真實(shí)地形數(shù)據(jù)的地形生成及實(shí)時(shí)顯示技術(shù):Boris等使用DTM數(shù)據(jù)直接生成地形;Florian等使用了LOD模型來(lái)簡(jiǎn)化地形數(shù)據(jù)并提高顯示速度;Hoppe提出PM(累進(jìn)網(wǎng)格)法用于地形網(wǎng)格的壓縮與累進(jìn)傳輸。這類(lèi)方法的特點(diǎn)是處理數(shù)據(jù)量大,需要使用較為復(fù)雜的壓縮算法和LOD算法來(lái)提高顯示速度。第二類(lèi)是基于數(shù)據(jù)擬合和分形理論的地形仿真技術(shù):Gardner和Alok等人分別使用曲面來(lái)擬合地形;Maedelbrot、Fournier、Miller和Musgrave等在生成地形時(shí)都使用了分形技術(shù)。這類(lèi)方法的特點(diǎn)是不使用真實(shí)的地形數(shù)據(jù),而是通過(guò)曲面插值或分形插值來(lái)生成地形高度場(chǎng)。在虛擬戰(zhàn)場(chǎng)、三維游戲等一些虛擬環(huán)境中,存在著大量的地形,由于地形的隨機(jī)性和復(fù)雜性,如何構(gòu)造這些地形是一個(gè)至關(guān)重要的問(wèn)題。如果采用傳統(tǒng)的方式,以人工幾何造型的方式進(jìn)行構(gòu)造,那么面對(duì)動(dòng)則數(shù)萬(wàn)個(gè)頂點(diǎn)的地形網(wǎng)格,一方面編輯工作量過(guò)于繁重,另一方面很難控制千變?nèi)f化的地形形態(tài)。如果從實(shí)測(cè)地形數(shù)據(jù)中抽取數(shù)據(jù)直接構(gòu)造地形,雖然地形不失真實(shí)性,但地形數(shù)據(jù)獲取渠道有限,代價(jià)昂貴,并且可控性差,特別是對(duì)于大多對(duì)地學(xué)精度要求不高的虛擬環(huán)境而言,并不是一種廉價(jià)而靈活的方法。如果單純使用分形生成方法,卻又不能對(duì)地形的大體輪廓進(jìn)行有效的控制。針對(duì)該問(wèn)題,文章對(duì)地形的自動(dòng)生成技術(shù)進(jìn)行了研究,給出了一種兼具自動(dòng)性和可控性的地形生成方法。將地形的生成過(guò)程分為兩個(gè)階段:在第一階段自動(dòng)生成地形模板,用來(lái)刻畫(huà)地形的特征輪廓,在該階段引入Perlin噪聲來(lái)構(gòu)造高度場(chǎng);在第二階段使用分形技術(shù)對(duì)地形模板進(jìn)行處理,增加多層次的地形細(xì)節(jié),最終生成真實(shí)感較強(qiáng)的地形。該方法的優(yōu)點(diǎn)在于:(1)通過(guò)控制Perlin噪聲的頻率和幅度,可以構(gòu)造出形態(tài)多樣的地形模板,從而以少量的數(shù)據(jù)從宏觀上描述地形的特征輪廓,并且其生成過(guò)程是自動(dòng)的。(2)通過(guò)控制分形維數(shù)、迭代次數(shù)、幅度系數(shù),使用分形技術(shù)可以給地形模板增加任意層次的地形細(xì)節(jié),大大增加了地形的真實(shí)感。(3)兩個(gè)階段的結(jié)合,使得地形的產(chǎn)生成為一個(gè)自動(dòng)、靈活而可控的過(guò)程,通過(guò)對(duì)幾個(gè)參數(shù)的控制,就可以得到形態(tài)各異細(xì)節(jié)豐富的地形數(shù)據(jù),并能方便地應(yīng)用到虛擬環(huán)境中去.2土地模型的生成2.1梯度生成中的噪聲函數(shù)Perlin噪聲是一種平滑偽噪聲,可用于產(chǎn)生過(guò)程紋理、人物自然動(dòng)作等。這里我們構(gòu)造2維Perlin噪聲函數(shù)。首先要構(gòu)造一個(gè)梯度。如圖1所示,噪聲控制點(diǎn)陣列中有m×n個(gè)控制點(diǎn),每一個(gè)控制點(diǎn)C都有一個(gè)梯度G,其方向和長(zhǎng)度隨機(jī)生成,一般情況下將長(zhǎng)度的最大值設(shè)定為單位長(zhǎng)度。盡管梯度是隨機(jī)的,但其生成過(guò)程是一次性的,噪聲函數(shù)對(duì)于相同的輸入總是返回相同的噪聲值。設(shè)噪聲函數(shù)為PerlinN(x,y),其輸入?yún)?shù)為點(diǎn)I(x,y)的坐標(biāo)值。假設(shè)I(x,y)落在四個(gè)相鄰噪聲控制點(diǎn)C(i-1,j-1),C(i,j-1),C(i-1,j)和C(i,j)所圍成的區(qū)域內(nèi),其中i,j為整數(shù),并且1≤i≤m,1≤j≤n。首先計(jì)算從每個(gè)相鄰控制點(diǎn)到I(x,y)的向量與該控制點(diǎn)的梯度的點(diǎn)積:設(shè)u和w分別為x和y的小數(shù)部分,在x方向上對(duì)d1和d2,d3和d4分別進(jìn)行三次調(diào)和插值:最后在y方向上對(duì)s1和s2進(jìn)行三次調(diào)和插值,就得到了二維Perlin噪聲函數(shù)的表達(dá)式:2.2均勻網(wǎng)格劃分地形的構(gòu)造一般基于一個(gè)矩形的地形區(qū)域。這里我們使用一個(gè)五元組Area(Base,Width,Col,Long,Row)來(lái)描述一個(gè)矩形地形區(qū)域。其中Base為基準(zhǔn)點(diǎn),Width和Col分別為x方向上的寬度和離散網(wǎng)格數(shù),Long和Raw分別為在y方向上的長(zhǎng)度和離散網(wǎng)格數(shù)。根據(jù)五元組中給出的參數(shù),這里對(duì)地形區(qū)域進(jìn)行均勻網(wǎng)格劃分,每個(gè)網(wǎng)格點(diǎn)Ii,j的x和y坐標(biāo)值都可以確切地計(jì)算出來(lái),而z坐標(biāo)值用于反映地形的高度場(chǎng)。設(shè)梯度場(chǎng)的長(zhǎng)寬都為整數(shù)GradLen,在使用Perlin噪聲計(jì)算地形區(qū)域的高度場(chǎng)時(shí),首先要將地形區(qū)域向梯度場(chǎng)進(jìn)行映射。設(shè)mod為取余函數(shù),則網(wǎng)格點(diǎn)Ii,j的映射結(jié)果為:為了豐富生成的地形模板的形態(tài),這里給Perlin噪聲加上一個(gè)頻率系數(shù)Freq和幅度Ampl,結(jié)合式(4),則高度場(chǎng)計(jì)算公式為:Freq實(shí)際上控制了地形區(qū)域向同一梯度場(chǎng)映射的重復(fù)頻率,Ampl用于縮放地形高度,這些控制參數(shù)使得產(chǎn)生的地形能夠呈現(xiàn)出豐富多樣的形態(tài),圖2.a～2.c給出了在同一地形區(qū)域上用不同頻率和幅度得到的地形模板高度場(chǎng)。3對(duì)地形細(xì)節(jié)的改進(jìn)通過(guò)控制參數(shù),用Perlin噪聲可以產(chǎn)生不同形態(tài)的地形模板,用以大致描述地形輪廓特征,比如地形的幅度,起伏頻率等。在一些虛擬環(huán)境中,比如虛擬飛行,大多情況下視點(diǎn)離地形有較遠(yuǎn)的距離,對(duì)地形細(xì)節(jié)沒(méi)有過(guò)多要求,這種情況下可以將地形模板數(shù)據(jù)直接應(yīng)用到虛擬環(huán)境中去,使用紋理映射技術(shù)增加地形的視覺(jué)真實(shí)感,也可以使用凹凸映射技術(shù)增加地形視覺(jué)細(xì)節(jié),從而得到比較滿(mǎn)意的效果。但對(duì)于一些對(duì)地形細(xì)節(jié)要求較高的虛擬系統(tǒng),比如地形漫游,虛擬戰(zhàn)場(chǎng)等,使用地形模板得到的模型就顯得較為簡(jiǎn)單。這里我們從分形技術(shù)出發(fā),使用中點(diǎn)位移迭代法給地形模板增加地形細(xì)節(jié),并使用分形維數(shù)、幅度系數(shù)和迭代次數(shù)來(lái)控制地形細(xì)節(jié)的特征。3.1復(fù)雜自然特征的分形在傳統(tǒng)的幾何造型技術(shù)中認(rèn)為,物體都是由一些可以用確定性的數(shù)學(xué)函數(shù)描述的光滑曲面組成,其中最常用的是可用線性函數(shù)描述的多邊形面,另外,使用由Bezier或B-樣條曲面定義的曲面片還可以使得造型過(guò)程變得靈活方便。這種造型技術(shù)廣泛地應(yīng)用在CAD,CAM等領(lǐng)域.但是,對(duì)于自然界中一些復(fù)雜而極不規(guī)則的自然景觀,如地形、樹(shù)木、流水等,單純地使用傳統(tǒng)的幾何造型技術(shù)則顯得困難重重。Mandelbrot于1975年提出了Fractal(分形)的概念,其主要特征是統(tǒng)計(jì)意義上的自相似性和分形維數(shù),其中分形維數(shù)可用于度量復(fù)雜圖形的不規(guī)則程度和填充空間的能力,一般情況下一個(gè)復(fù)雜研究對(duì)象的分形維數(shù)大于其拓?fù)渚S數(shù).分形的出現(xiàn)為研究一些不連續(xù)并難以用傳統(tǒng)特征長(zhǎng)度度量的圖形(如海岸線,Koach曲線等)提供了有力的理論基礎(chǔ),同時(shí)也為自然景觀的模擬提供了新的思路.Mandelbrot在文中提出了基于一維高斯隨機(jī)過(guò)程的fBM(分形布朗運(yùn)動(dòng))模型,可以用于生成多種復(fù)雜而自相似的圖形。Fournier等對(duì)fBM模型進(jìn)行了簡(jiǎn)化,提出了中點(diǎn)位移法,給出了Triangle子分和Square子分兩種迭代方法,將計(jì)算復(fù)雜度從O(NlogN)降為線性.Miller中發(fā)展了Diamond-Square子分迭代法,提出了Square-Square法。這些方法都可以用于地形模擬。3.2diamwd和化學(xué)約束中點(diǎn)位移法的特點(diǎn)是計(jì)算簡(jiǎn)單,容易實(shí)現(xiàn),數(shù)據(jù)存儲(chǔ)靈活。對(duì)于前面生成的地形模板來(lái)說(shuō),反映地形起伏分布等特征的數(shù)據(jù)已經(jīng)存在,需要增加的是地形細(xì)節(jié)部分.這里使用Diamond-Square子分迭代法,圖3簡(jiǎn)單示意了迭代過(guò)程.在圖3.a中,四個(gè)頂點(diǎn)ABCD圍成一個(gè)方形,四個(gè)頂點(diǎn)的高度值(z值)為已知.在每一次迭代過(guò)程中都要進(jìn)行兩個(gè)階段的處理:Diamond階段和Square階段。在Diamond階段,首先求方形ABCD的中點(diǎn)的高度值:式中,中點(diǎn)的高度值為ABCD四個(gè)頂點(diǎn)高度值的均值加上一個(gè)擾動(dòng)量,該擾動(dòng)量為符合高斯分布的隨機(jī)數(shù)。Fournier將高斯隨機(jī)數(shù)的數(shù)學(xué)期望取為0,標(biāo)準(zhǔn)差取為1,這里設(shè)高斯隨機(jī)數(shù)產(chǎn)生函數(shù)為Gauss(),則對(duì)應(yīng)的擾動(dòng)量為:其中i為當(dāng)前的迭代次數(shù);k為幅度系數(shù);h被Fournier稱(chēng)為“決定‘分形維數(shù)’的參數(shù)”。而Miller認(rèn)為,擾動(dòng)量是一個(gè)符合高斯分布的隨機(jī)變量,其標(biāo)準(zhǔn)差為:其中的i和k與式(7)中的意義相同;h被Miller直接稱(chēng)為“分形維數(shù)”。Musgrave認(rèn)為,式(7)和式(8)中的A與分形維數(shù)D之間的關(guān)系為h=3-D。這里,我們結(jié)合Fournier和Musgrave的思想,使用下面的公式來(lái)計(jì)算擾動(dòng)量:一般情況下,h在之間取值,對(duì)應(yīng)地分形維數(shù)D的取值區(qū)間為[2.0,3.0]。當(dāng)分形維數(shù)越接近3.0時(shí),產(chǎn)生的地形越粗糙,當(dāng)分形維數(shù)越接近2.0,產(chǎn)生的地形越平坦。在接下來(lái)的Square階段,求方形四條邊各自中點(diǎn)的高度值:公式中的隨機(jī)擾動(dòng)量的產(chǎn)生方法與式(6)中的相同。完成Diamond和Square處理,就完成了一次迭代過(guò)程,也就為地形模板增加了一個(gè)層次的細(xì)節(jié)。理論上可以進(jìn)行任意次的迭代,從而生成任意層次的地形細(xì)節(jié)。4地形模板迭代處理在生成地形的試驗(yàn)中,我們使用的地形區(qū)域的長(zhǎng)寬尺寸為128×128,長(zhǎng)寬方向上的原始離散點(diǎn)數(shù)為32×32,在分形迭代過(guò)程中離散點(diǎn)數(shù)會(huì)隨著迭代次數(shù)增加。為了簡(jiǎn)要而較清楚地展示生成的地形的形態(tài),在渲染過(guò)程中使用了簡(jiǎn)單的Phong光照模型,光源中只設(shè)定環(huán)境光和漫反射光成分,而沒(méi)有鏡面光。光照模型使用VertexShader程序?qū)崿F(xiàn),該Shader程序執(zhí)行于GPU而非CPU中,所以渲染速度較快。在使用Perlin噪聲生成地形模板時(shí),使用的梯度場(chǎng)的噪聲控制點(diǎn)數(shù)為256×256。通過(guò)取不同的頻率和幅度,可以得到不同形態(tài)的地形高度場(chǎng)模板。圖4給出了不同頻率和幅度所得到的地形模板的光照渲染圖,其中圖4.a中頻率Freq=4,幅度Ampl=0.3,圖4.b中頻率Freq=8,幅度Ampl=0.1.頻率和幅度根據(jù)應(yīng)用的具體情況進(jìn)行選取。如果地形區(qū)域的面積較大,或者希望地形的起伏密度較大,或者地形區(qū)域的網(wǎng)格劃分密度大,可以選取較大的頻率值,反之取較小值。如果希望地形高度差較大,或者地形區(qū)域的面積較大,可以選取較大的幅度,反之取較小值。從圖4中可以看出,使用Perlin噪聲產(chǎn)生的地形模板已經(jīng)可以描述地形的大致輪廓,并且32×32的離散網(wǎng)格所對(duì)應(yīng)的存儲(chǔ)數(shù)據(jù)量也很小.接下來(lái)使用中點(diǎn)位移法對(duì)地形模板進(jìn)行分形迭代處理,增加地形的多層次細(xì)節(jié),從而使得地形從一個(gè)簡(jiǎn)單而粗糙的狀態(tài),轉(zhuǎn)變?yōu)橐粋€(gè)宏觀輪廓與地形模板相同而細(xì)節(jié)又十分豐富的真實(shí)感很強(qiáng)的狀態(tài)。圖5給出了對(duì)模板迭代處理后得到的地形,從圖中可以看出,對(duì)比現(xiàn)實(shí)世界的地形,本文給出的方法所得到的地形比較真實(shí)。在迭代過(guò)程中,使用分形維數(shù)D、幅度系數(shù)k和迭代次數(shù)i來(lái)控制地形的細(xì)節(jié).圖5.a和圖5.b分別為對(duì)圖4中的地形模板A和B迭代處理后得到的結(jié)果,其中k=1.5,i=4,D=2.3.圖5.c和圖5.d分別為D=2.1和D=2.6時(shí)迭代模板A得到的地形,從圖中可以看出,分形維數(shù)越大,細(xì)節(jié)越豐富,地形顯得越粗糙。在生成較大面積地形,或者地形的高度差較大時(shí),可以取較大的分形維數(shù)值。迭代次數(shù)可根據(jù)地形模板的長(zhǎng)寬尺寸、長(zhǎng)寬方向上的網(wǎng)格點(diǎn)數(shù)目來(lái)確定。長(zhǎng)寬尺寸越大,相鄰網(wǎng)格點(diǎn)的間距越大,需要較多層次的地形細(xì)節(jié)來(lái)填充,可以增多迭代次數(shù);長(zhǎng)寬方向上的網(wǎng)格點(diǎn)數(shù)目越多,相鄰網(wǎng)格點(diǎn)的間距越小,需要較少的地形細(xì)節(jié)來(lái)填充,可以取較少的迭代次數(shù)。另外,計(jì)算時(shí)間和內(nèi)存占用空間也是取定迭代次數(shù)的考慮因素之一。依據(jù)試驗(yàn)和經(jīng)驗(yàn),一般情況下迭代2～8次較為合適。圖5.e給出了迭代2次得到的結(jié)果,相對(duì)于迭代4次的圖5.d明顯缺少層次細(xì)節(jié)。幅度系數(shù)k對(duì)生成的地形也有較大的影響。如圖5.f所示,將k值增大一倍,地形相對(duì)于圖5.d明顯變得粗糙.所以,在使用分形技術(shù)產(chǎn)生地形的過(guò)程中,地形的粗糙程度由分形維數(shù)、迭代次數(shù)和幅度系數(shù)共同決定,迭代次數(shù)決定細(xì)節(jié)的層次,分形維數(shù)決定兩個(gè)層次間細(xì)節(jié)的變化程度,而幅度系數(shù)描述了地形細(xì)節(jié)相對(duì)于地形模板高度的比例關(guān)系.表1給出了使用本文方法生成地形的時(shí)間效率。地形模板網(wǎng)格劃分方案為32×32,由于網(wǎng)格頂點(diǎn)的數(shù)量少,因此模板的生成速度很快。在迭代過(guò)程中,分形維數(shù)和幅度系數(shù)的不同取值對(duì)計(jì)算時(shí)間的影響可以忽略不計(jì),而迭代次數(shù)是影響計(jì)算時(shí)間的重要因素。由于地形生成階段位于渲染階段之前,因此生成時(shí)間毋需滿(mǎn)足實(shí)時(shí)性要求,可以先將生成的地形數(shù)據(jù)以文件的方式保存,然后導(dǎo)入到虛擬環(huán)境中去,表1也給出了地形渲染的速度,當(dāng)?shù)螖?shù)為2時(shí),地形的三角形為3,0752個(gè),渲染幀速達(dá)到每秒89.3幀;當(dāng)?shù)螖?shù)為4時(shí),地形的三角形數(shù)為492,032,渲染速度仍能達(dá)到每秒11.9幀。這里需要說(shuō)明的是,渲染速度一方面取決于組成地形的元素的數(shù)量,另一方面還取決于圖形硬件和系統(tǒng)平臺(tái)。這里的模擬試驗(yàn)基于PC平臺(tái),CPU為PⅣ-1.8G,圖形顯卡選用當(dāng)前流行配置的NVIDIA中檔顯卡GeForceFx5600版。如果使用專(zhuān)業(yè)顯卡或圖形工作站,渲染速度將會(huì)大幅提高.結(jié)