摘 要：三維地形是虛擬仿真領(lǐng)域中視景系統(tǒng)的比較重要的一部分。當(dāng)前在地形仿真領(lǐng)域中，通常使用的都是DEM實時生成技術(shù)，但是DEM實時生成技術(shù)的數(shù)據(jù)量比較大，也比較復(fù)雜。通常情況下，在虛擬仿真系統(tǒng)中注重的是產(chǎn)生實時動畫的效果，因此，算法的效率就顯得比較重要。由于分形地形生成方法具有簡潔高效的特點，在地形生成領(lǐng)域中得到了普遍的使用。本篇文章將論述的是基于GPU加速的分形地形生成方法。

關(guān)鍵詞：分形地形；GPU；Diamond-Square算法

目前，大多數(shù)使用的是DEM實時生成技術(shù)，這中技術(shù)的運算比較復(fù)雜，難度也比較大，所以出現(xiàn)了基于GPU加速的分形地形生成方法?；贕PU加速的分形地形生成方法是利用NVIDIA GPU的統(tǒng)一計算設(shè)備架構(gòu)，把分形地形生成算法轉(zhuǎn)變成CUDA線程塊并行計算過程，讓地形的生成過程在GPU中加速運行。使用這種方法不僅能夠取得良好的模擬效果還能提高算法的運算效率。

1 菱形—方形（Diamond-Square算法）分形地形生成方法

地形生成和分形技術(shù)之間有著密切的聯(lián)系，由于地形地貌中擁有許多的分行特征，可以用分形來很好的描述地形地貌中的海岸線以及山脈線等。比如，山脈線具有無限自相似的特性，而這卻也是分形的特色之一。在繪制三維地形中使用分形技術(shù)具有很多的優(yōu)點，主要有以下幾個優(yōu)點：

⑴分形技術(shù)可以產(chǎn)生具有無限自相似性的地形場景，產(chǎn)生的地形場景與真實的地形相符合。

⑵能夠產(chǎn)生基于不同層次和不同分辨率的地形場景模型，這種基于不同層次的地形能夠很好的適應(yīng)三維地形的硬件。

⑶可以產(chǎn)生無級比例尺和大規(guī)模的地形場景，比較適合需要進(jìn)行縮放和漫游的三圍地形場景。

⑷使用分形算法形成的地形圖可以用來進(jìn)行插值與平滑化的處理，處理的過程比較簡單。同時還能依據(jù)地形數(shù)據(jù)形成自然過度紋理。

分形地形的建模方法有很多種。但是，由于地形具有復(fù)雜性，真實的模擬大規(guī)模地形需要計算的數(shù)據(jù)量比較大，所以，需要找到一些高效率的計算方法，特別是在虛擬仿真系統(tǒng)中，更多注重的是產(chǎn)生的實時動畫效果，算法的效率顯得更加重要。在建地形模型的時候使用的方法是中點位移法，由于中點位移法具有運算速度快、實現(xiàn)簡單的特點，成為應(yīng)用最廣泛的地形建模方法。細(xì)分方法主要包括三角形細(xì)分和Diamond-Square算法等。在生成大規(guī)模地形的時候，應(yīng)用最廣泛的是Diamond-Square算法，Diamond-Square算法的速度比較快。

2 GPU算法的過程

Diamond-Square算法是從用種子點組成的正方形開始的，通過多次把中點位移法進(jìn)行隨機的迭代后，不斷的細(xì)分種子正方形，最終獲得貼近實際的三維地形。首先，取出四個點形成一個正方形，同時要確定這四個點的高度，然后通過使用計算公式計算出正方形中心點以及各邊中點的高度。這樣，由原先的一個正方形變成四個小的正方形，之后再在每個小的正方形上進(jìn)行一樣的操作：取四條邊的中點與正方形的中心，計算出這些點的新的高度值，并且要把原先的正方形分成四個比較小的正方形。上述的細(xì)分過程每次都要把新形成的正方形分成更小的正方形，如此一直重復(fù)下去，直至新形成的正方形的邊長小于指定的值。若以上重復(fù)的次數(shù)夠多，就能夠得到一個比較精細(xì)的數(shù)字高程模型。

3 基于GPU加速的分形地形生成

CUDA架構(gòu)依據(jù)數(shù)據(jù)并行計算模型，每一個處理器能夠在不同的數(shù)據(jù)集上實行一樣的指令集合?？梢允褂枚S數(shù)組來存儲正方形各點的高度值，其中數(shù)組的小標(biāo)要對應(yīng)著二維線程塊的線程引號。由于細(xì)分過程中需要比較多的隨機數(shù)，但是GPU并不能提供隨機數(shù)生成函數(shù)，可以通過在GPU中初始化隨機數(shù)數(shù)組來為細(xì)分過程提供大量的隨機數(shù)。具體的計算過程如下所述：

第一步：初始化數(shù)據(jù)：確定地形四個頂點的初始值，初始化隨機數(shù)數(shù)組。

第二步：把第一步初始化完的數(shù)據(jù)傳到GPU。

第三步：計算目前最小的正方形的變長。

第四步：對每個正方形進(jìn)行Diamond-Square算法。

第五步：判斷最后新形成的正方形的邊長小于指定的值。

在實際的編程過程中，每執(zhí)行一次細(xì)分過程就需要減掉一半的隨機數(shù)范圍，這樣做是為了改善細(xì)分過程中出現(xiàn)的折痕問題，使生成的地形比較平滑。算法結(jié)束之后的分形地形數(shù)據(jù)都在GPU中生成，之后渲染緩存中的數(shù)據(jù)，同時需要進(jìn)行紋理、陰影等處理，這樣就能夠?qū)崿F(xiàn)地形的仿真模擬。

4 總結(jié)

在當(dāng)前的三維地形顯示技術(shù)領(lǐng)域內(nèi)，比較受關(guān)注的是地形生成。由于目前使用的地形生成方法的計算量比較大，還比較耗時，并不適合在大規(guī)模地形生成中使用，因此出現(xiàn)了一種基于GPU加速的分形地形生成方法。使用這種分形地形生成方法能夠提高算法的預(yù)算效率，產(chǎn)生的效果也比較好，并得到了廣泛的使用。

[參考文獻(xiàn)]

[1]柳有權(quán)，劉學(xué)慧，吳恩華.基于GPU帶有復(fù)雜邊界的三維實時流體模擬[J].軟件學(xué)報，2006（3）.

[2]譚兵，徐青，周楊.大區(qū)域地形可視化技術(shù)的研究[J].中國圖像圖形學(xué)報，2003（5）.

作者簡介：李媛（1992.1-），女，陜西西安人，本科，研究方向：基于GPU的數(shù)字地形分析并行算法研究。