孟金玉 袁永生

摘 要：針對傳統(tǒng)三維地形生成算法在生成大規(guī)模地形數據時用時較多的問題，提出了一種結合雙線性插值和Perlin Noise的地形生成算法。該方法首先將初始地形數據進行擴展，之后利用雙線性插值和Perlin Noise進行地形細節(jié)生成。該方法能夠有效降低生成大規(guī)模地形數據時的時間，并且該算法還可利用低分率地形數據生成高分辨率地形數據。

關鍵詞：三維地形; Diamond-Square; 雙線性插值; Perlin Noise

中圖分類號：TP391 ? ? ?文獻標識碼：A

三維地形生成技術一直是一個熱門的研究方向，國內外研究人員對此進行了大量的研究，并提出許多生成方法。目前三維地形的生成有多種形式，其中研究最為廣泛的有兩種，第一種是基于程序的地形生成方法，一般采用基于分型幾何的方法生成;另一種是基于數據的地形的生成方法，一般為基于數字高程模型的生成。

分形幾何算法主要有泊松階躍法、中點位移法、逐次隨機增加法、傅里葉濾波法、帶限噪音累計法等五種方法[1]。其中，中點位移法是最基礎和應用最廣泛的方法，較為著名的有Miller提出的“Diamond-Square”算法[2]，該算法在生成大規(guī)模高程數據時，存在時間較長的問題。

提出一種新的地形生成算法——Bilinear-Perlin算法。該算法將雙線性插值與Perlin Noise算法有效融合，通過在低分辨率高程數據基礎上進行插值獲得高分辨率數據。利用該算法能夠有效降低“Diamond-Square”算法在生成高分辨率大規(guī)模地形數據時的生成時間，并能夠在低分辨率的數字高程模型下通過插值獲得高分辨率地形。

1 Diamond-Square算法

Diamond-Square（以下簡稱DS）算法主要分為正方形和菱形兩個步驟。迭代這兩個步驟，不斷計算獲得高程數據，細化地形內部網格。

算法如圖1所示，現在作如下定義：Size表示欲生成高程數據的數據規(guī)模邊長，例將生成的數據規(guī)模為512*512，則Size為512。RectSize表示當前步長，此變量在一次正方形步驟后，縮小為原來的1/2。已知A、B、C、D四點數據，分別記為Ha、Hb、Hc和Hd。

由DS算法效果圖能夠看到，DS算法生成的效果較為真實，但是由于算法特性，在生成小規(guī)模數據時速度較快，生成大規(guī)模數據時，速度較慢。

3 Bilinear-Perlin算法

3.1 算法思想

Bilinear-Perlin（以下簡稱BP）算法的核心思想為插值計算，即通過對小規(guī)模高程數據進行擴展，擴展到大規(guī)模數據后，產生的空白區(qū)域通過插值計算獲得?？瞻讌^(qū)域數據首先采用雙線性插值獲得，但由于雙線性插值算法得到的數據較為光滑，與真實地形不符，通過Perlin Noise算法添加隨機值，增加地形表面粗糙度，以此得到較為真實的高程數據。最后，利用平滑濾波函數對所有數據進行一次平滑濾波，最終得到插值計算后的大規(guī)模數據。BP算法流程圖如圖5所示。

3.2 雙線性插值

雙線性插值是有兩個變量的插值函數的線性插值擴展，其核心思想是在兩個方向分別進行一次線性插值[5]。

三維地形高程數據通常存放于二維數組中，數組坐標表示地形點的屏幕坐標，數組的值表示當前點的高程值。如圖6所示，在已知點（0，0）、（0，1）、（1，0）（1，1）四點值，求點（x，y）的值，其中0≤x≤1，0≤y≤1。此時需要利用雙線性插值獲得點（x，y）的值。

對于計算任意給定的（x，y）坐標上的精確高度，首先計算x和y值，以xRelative和yRelative表示。代碼如下：

int xLow= xCoord;

int xHig=xLower+ 1;

float xRelative = （xCoord-xLow） / （xHig- xLow）;

int yLow= yCoord;

int yHig=yLower+ 1;

float yRelative= （yCoord-yLow） / （yHig- yLow）;

在獲得xRelative和yRelative后，需要獲得其所對應的具體高程值。三維地形的繪制采用三角形的方式進行繪制，但是可以有兩種方式進行繪制，如圖7所示。兩種地形繪制方式的不同，會影響到P點的高度。

在地形繪制中，通常采用右側的繪制方式，因為右側的繪制方式能夠更容易的確定點P（x，y）在哪個三角形上。在右圖中，如果xRelative + yRelative等于1的話，P（x，y）在對角線上;如果和小于1，P（x，y）位于左下三角形內;否則，P（x，y）在右上三角形內。

在獲得了對應點的坐標，以及點位于哪個三角形中，通過四個頂點的高度利用雙線性插值的方法獲得精確高度。

定義：boolpointAboveLowerTriangle。

如果點在左下三角形中，pointAboveLowerTriangle為true，否則為false。

其中點在左下三角形中，計算方法如下：

finalGht = ghtLxLy;

finalGht += yRelative*（ghtLxHy-ghtLxLy）;

finalGht += xRelative*（ghtHxLy-ghtLxLy）;

點在右上三角形中，計算方法如下：

finalGht = ghtHxHy;

finalGht += 1.0f-yRelative * ghtHxLy-ghtHxHy;

finalGht += 1.0f-xRelative * ghtLxHy-ghtHxHy;

其中，LxHy表示在四個點中，x值較低與y值較高的坐標，即左上角坐標，其他坐標同理。根據以上計算方法，我們就能夠獲得所有點的插值數據，但是這些點的數據由于采用線性計算，插值產生的地形過于平滑，與真實的地形不符，因此我們需要進行添加隨機高度，使地形產生粗糙表面。

3.3 Perlin Noise

1985年，Ken Perlin首次發(fā)表了Perlin Noise[6]算法。Perlin Noise算法通過混合不同頻率不同振幅的噪聲函數，使得相鄰數據差異較小，使整體數據符合自然環(huán)境的隨機狀態(tài)。目前，人們通常使用Perlin Noise算法生成木頭、石頭、云狀和火焰等紋理。

Perlin Noise算法由兩部分組成，噪聲函數和插值函數。噪聲函數用來隨機產生整點數據，插值函數用于平滑整點數據。

3.3.1 噪聲函數

噪聲函數的本質為一個隨機生成函數，其是離散的。通過輸入整數參數，返回一個隨機數。如圖8所示，輸入x值，對應產生一個0到1之間的隨機數，但是當輸入的x值相等時，輸出的隨機數相等，此特性為Perlin Noise算法的最主要特性。由于其是離散的點組成的，因此我們只需要構建離散點數據即可，并且噪聲函數的頻率和振幅都能自行控制。

3.3.2 插值函數

噪聲函數產生的值是離散的，因此需要通過插值函數，填補兩個離散點之間的部分，生成一個非整數參數的連續(xù)函數。目前常用的插值函數共有三種：

（1）線性插值函數：

A×1-x + B×x（7）

參數：A，B為需要插值的兩個離散點終點。x取值為0到1，表示插值在兩點間的比例。x=0表示在A點，x=1表示在B點。

（2）余弦插值函數：

fx=1-cos（xπ）×0.5

return A×1-fx +B×fx（8）

參數：同線性插值函數。但是此種插值函數更為平滑。

（3）立方插值函數：

P=（v3-v2）-（v0-v1）

Q=（v0-v1）-P

R=v2-v0

S=v1

return Px3 + Qx2 + Rx + S（9）

參數：立方插值函數需要五個參數v0、v1、v2、v3、x，v1，v2，x同上面參數，v0，v3為前一點和后一點。此種方法最為平滑，但是效率較低。

3.3.3 Perlin Noise函數

在介紹Perlin Noise函數之前，首先需要明確兩個概念，振幅（Amplitude）和頻率（Frequency）。如圖9所示，振幅表示最大值和最小值的差值，頻率表示為1/波長。

如圖10示不同頻率和振幅的噪聲函數?？梢钥吹?，通過改變振幅和頻率，能夠得到不同樣式的噪聲函數。

Perlin Noise的核心就是將不同頻率和振幅的噪聲函數進行疊加，如圖11所示，疊加了圖10所示的噪聲函數。大振幅低頻率的噪聲函數決定了圖形的形狀，例如山脈的輪廓;小振幅高頻率的噪聲函數決定了圖形的細節(jié)，例如地形的侵蝕狀。

以上分別介紹了雙線性插值和Perlin Noise算法，每次利用雙線性插值算法獲得插值數據后，添加相應的Perlin Noise函數點。這樣插值獲得的數據不僅能夠和原有地形走勢相同，并且還能夠與真實的地形一樣，產生地形的粗糙感，使其更真實。

4 DS算法改進

前文已經介紹，由于DS算法的原因，其在生成大規(guī)模地形數據時，生成時間會非常大。下面利用BP算法對DS算法進行改進，首先采用DS算法生成小規(guī)模數據，然后利用BP對小規(guī)模數據進行插值擴展為大規(guī)模數據。此方法能夠在保證較高地形細節(jié)的基礎上，生成速度得到明顯提高。

將改進的DS算法稱為DS-P算法。DS-P算法的算法流程圖如圖12所示。

5 算法比較

5.1 DS-P算法與DS算法比較

由圖[4]和圖[13]對比可知，DS-P和DS算法在生成地形的趨勢和細節(jié)上基本是一致的，DS-P算法生成的地形滿足基于程序的地形生成算法的要求。

下面將對兩種算法生成時間進行對比。實驗環(huán)境如下所示。

1.硬件環(huán)境

CPU： Intel Core i3-2120 ?主頻3.30GHz

內存：4GB

顯卡：Intel Graphics Family

2.軟件環(huán)境

操作系統(tǒng)：32位Windows7 SP1

編譯環(huán)境：VS2010

編譯語言：C#

實驗采用多次平均方法，在同樣環(huán)境下，各種算法分別進行生成地形數據，各生成50次，然后平均處理，得出生成時間，其中DS-P算法的初始規(guī)模數據位64×64。時間統(tǒng)計如表1所示。

圖15為兩種算法所用時間的曲線圖。由圖可以看到隨著地形數據規(guī)模的增加，DS算法的地形生成所需時間會陡然加劇，而改進的DS-P算法耗時會遠遠小于DS算法。

5.2 BP算法生成高分辨率地形

BP算法不僅能夠有效降低DS算法在生成大規(guī)模地形數據時的生成時間，并能夠在低分辨率的數字高程模型下通過插值獲得高分辨率地形。

現將三種高程數據進行對比，第一組：原始數據分辨率30m×30m;第二組：在第一組的基礎上進行間隔采樣，每三個點采樣一個，分辨率降低為90m×90m;第三組：利用BP算法對第二組數據進行插值，使分辨率重新達到30m×30m 。渲染顯示如圖16所示。

由上圖可知，中間圖形與左圖對比，地形出現明顯折痕，細節(jié)度幾乎沒有，對原有數據的還原效果極差。右側圖形與中間圖形對比，細節(jié)度明顯提高，與左側圖形對比，差異較小，如圖17所示。

6 結 論

DS算法在生成大規(guī)模地形數據時，會存在生成時間過長的問題。本文提出BP算法，并根據此算法提出了改進的DS-P算法。通過實驗表明，在不改變原有地形細節(jié)時，DS-P算法在生成相同地形數據規(guī)模時，所用時間大大減少。并且，BP算法能夠應用到將現有的低分辨率的數字高程模型下通過插值獲得高分辨率地形，細節(jié)還原較高。

參考文獻

[1] MUSGRAVE F K ， KOLB C E ， MACE R S . The synthesis and rendering of eroded fractal terrains[J]. Computer Graphics， 1989， 23（3）：41-50.

[2] MILLE R， GAVIN S P. The definition and rendering of terrain maps[J]. Computer Graphics， 1986，20（4）：39-48.

[3] 朱慶.分形理論及其在數字地形分析和地面仿真中的應用[D]. 北京：北方交通大學，1995.

[4] 雷磊. 三維地形生成及可視化技術研究[D].哈爾濱：哈爾濱工程大學，2005.

[5] 葉金印， 邱旭敏， 黃勇，等. 氣象遙感圖像及格點場重采樣插值方法[J]. 計算機工程與應用， 2013， 49（18）：237-241.

[6] PERLIN K. An image synthesizer [J].Computer Graphics，1985，19（3）：287-296.