基于GPU加速的地形生成方法

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

關鍵詞：分形地形；GPU；Diamond-Square算法

目前，大多數使用的是DEM實時生成技術，這中技術的運算比較復雜，難度也比較大，所以出現了基于GPU加速的分形地形生成方法。基于GPU加速的分形地形生成方法是利用NVIDIA GPU的統一計算設備架構，把分形地形生成算法轉變成CUDA線程塊并行計算過程，讓地形的生成過程在GPU中加速運行。使用這種方法不僅能夠取得良好的模擬效果還能提高算法的運算效率。

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

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

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

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

⑶可以產生無級比例尺和大規模的地形場景，比較適合需要進行縮放和漫游的三圍地形場景。

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

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

2 GPU算法的過程

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

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

CUDA架構依據數據并行計算模型，每一個處理器能夠在不同的數據集上實行一樣的指令集合。可以使用二維數組來存儲正方形各點的高度值，其中數組的小標要對應著二維線程塊的線程引號。由于細分過程中需要比較多的隨機數，但是GPU并不能提供隨機數生成函數，可以通過在GPU中初始化隨機數數組來為細分過程提供大量的隨機數。具體的計算過程如下所述：

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

第二步：把第一步初始化完的數據傳到GPU。

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

第四步：對每個正方形進行Diamond-Square算法。

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

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

4 總結

在當前的三維地形顯示技術領域內，比較受關注的是地形生成。由于目前使用的地形生成方法的計算量比較大，還比較耗時，并不適合在大規模地形生成中使用，因此出現了一種基于GPU加速的分形地形生成方法。使用這種分形地形生成方法能夠提高算法的預算效率，產生的效果也比較好，并得到了廣泛的使用。

[參考文獻]

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

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

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