一種交互編輯與自動(dòng)生成的三維地形綜合構(gòu)建方法與實(shí)現(xiàn)

萬 苗，張新家，宋佳音

（西北工業(yè)大學(xué) 自動(dòng)化學(xué)院，陜西 西安 710129）

隨著視景仿真技術(shù)的發(fā)展，三維地形建模技術(shù)作為其最基礎(chǔ)和最重要的內(nèi)容之一也逐漸成為研究熱點(diǎn)，并在飛行模擬、戰(zhàn)場模擬、軍事訓(xùn)練、園林設(shè)計(jì)、電腦游戲和電影制作等應(yīng)用中發(fā)揮著重要作用。根據(jù)用于建模的地形數(shù)據(jù)的來源不同，地形模型可以分為真實(shí)地形和虛構(gòu)地形。真實(shí)地形的建模數(shù)據(jù)來自對現(xiàn)實(shí)世界中某處地形的數(shù)字化；虛構(gòu)地形的建模數(shù)據(jù)來自用戶的構(gòu)想，這類地形類型豐富，能滿足不同用戶的個(gè)性化需求。本文的研究內(nèi)容主要是針對虛構(gòu)地形的建模。

交互編輯是最初采用的地形建模方法，用戶利用專門的建模工具設(shè)計(jì)自己的地形。這種方法構(gòu)建的地形模型精度高，效果逼真。但這種方法的建模過程繁瑣效率很低，對專業(yè)知識水平要求高。而且大部分建模工具的使用都比較復(fù)雜，需要長期的經(jīng)驗(yàn)積累。因此很多地形模型應(yīng)用系統(tǒng)（如軍事訓(xùn)練游戲）的終端用戶只能使用預(yù)定義地形或雇傭?qū)I(yè)的地形模型設(shè)計(jì)團(tuán)隊(duì)為其制作專用地形。

為了克服交互編輯方法的缺點(diǎn)，研究人員開始轉(zhuǎn)向自動(dòng)生成方法的研究，諸多學(xué)者在近幾十年里提出了許多自動(dòng)生成方法。這些方法可總結(jié)為兩大類，一類是基于分形幾何的建模方法，此類方法的主要思想是不規(guī)則形體通過細(xì)分可以看作是由許多規(guī)則形體構(gòu)成，最早體現(xiàn)在Mandelbrot的研究中[1]，隨后一些學(xué)者對這種方法進(jìn)行了改進(jìn)與豐富，如Fournier等人提出的隨機(jī)中點(diǎn)位移法[2]，Voss提出的逐次隨機(jī)位移法[3]等。另一類是基于物理原理的建模方法，這類方法是根據(jù)物理原理模擬自然現(xiàn)象建立地形模型。如Kelley等人通過模擬水流對地形的侵蝕過程建立了一塊近似自然地形[4]，Ken Musgrave等人在1989年提出的氣流侵蝕算法[5]，以及后人對這兩種方法的改進(jìn)（參照文獻(xiàn)[6-8]）。自動(dòng)生成方法也有其缺點(diǎn)，首先這類方法通常沒有交互能力，用戶控制作用弱，只能對全局輸入進(jìn)行修改無法對局部細(xì)節(jié)進(jìn)行調(diào)整，如Belhadj和Audibert在2005年提出的方法——根據(jù)山脊線和河流網(wǎng)自動(dòng)生成周邊地形，用戶只能修改山脊線不能對生成的其他地形區(qū)域作調(diào)整[9]。其次由于自動(dòng)生成過程中一般會含有隨機(jī)數(shù)據(jù)生成環(huán)節(jié)，所以這類方法會具有一定的隨機(jī)性。

為了克服兩種方法的缺點(diǎn)，近幾年有研究人員開始嘗試在自動(dòng)生成與用戶控制之間找到一種平衡。為此文中提出了一種交互式的綜合建模方法，既能為用戶提供簡單直觀的編輯功能又能實(shí)現(xiàn)的地形模型的快速自動(dòng)生成。

1 地形模型建模流程

如圖1所示，為本文所述地形建模方法的基本工作流程。

圖1 地形建模流程圖Fig.1 Flow chart the terrain modeling

建模工作的第一個(gè)環(huán)節(jié)是手工編輯環(huán)節(jié)，文中提出一種地形高程網(wǎng)格圖用于描繪地形輪廓（地形高程網(wǎng)格圖的具體內(nèi)容將在下一節(jié)中詳細(xì)介紹），用戶通過手工繪制地形高程網(wǎng)格圖來設(shè)計(jì)自己的地形，其實(shí)質(zhì)是為下一環(huán)節(jié)——原始高程數(shù)據(jù)的生成設(shè)置參數(shù)和限制條件，使生成的數(shù)據(jù)滿足用戶的要求。接下來是自動(dòng)生成環(huán)節(jié)，這一環(huán)節(jié)是整個(gè)地形建模的核心環(huán)節(jié)，通過自動(dòng)生成算法的運(yùn)用可大大縮短建模時(shí)間提高效率。本文采用的是基于高程數(shù)據(jù)的建模方法，這類方法可分為規(guī)則網(wǎng)建模法和不規(guī)則網(wǎng)建模法，這兩種方法構(gòu)建的地形網(wǎng)格示意圖如圖2(a)和(b)，他們最主要的區(qū)別是前者高程點(diǎn)分布均勻而后者高程點(diǎn)分布不均勻。規(guī)則網(wǎng)建模法具有拓?fù)浼軜?gòu)簡單、易于管理和實(shí)現(xiàn)的優(yōu)點(diǎn)但數(shù)據(jù)冗余較大，而不規(guī)則網(wǎng)建模法數(shù)據(jù)冗余小但實(shí)現(xiàn)算法相對復(fù)雜。本文將在規(guī)則網(wǎng)建模的基礎(chǔ)上作出改進(jìn)以減少數(shù)據(jù)冗余量，詳細(xì)內(nèi)容將在下一節(jié)中介紹。

圖2 地形網(wǎng)格示意圖Fig.2 Terrain meshes

地形模型生成后需要及時(shí)的將建模效果反饋給用戶，這個(gè)任務(wù)就要通過地形顯示環(huán)節(jié)來完成。這一環(huán)節(jié)的實(shí)質(zhì)是利用三維數(shù)據(jù)可視化技術(shù)將地形模型數(shù)據(jù)轉(zhuǎn)換為圖像數(shù)據(jù)直觀、生動(dòng)地展示給用戶。用戶根據(jù)地形效果圖判斷地形是否滿足要求，若滿足則可將地形模型數(shù)據(jù)導(dǎo)出用于各種具體應(yīng)用中；若不滿足要求，用戶可對地形高程網(wǎng)格圖進(jìn)行修改，工作流程回到地形高程數(shù)據(jù)生成環(huán)節(jié)并重復(fù)上述流程直到地形效果滿足用戶要求為止。這種建模過程是一個(gè)循環(huán)的交互過程。如圖3所示的地形編輯系統(tǒng)界面中，工作區(qū)分為兩部分。左半部分為網(wǎng)格區(qū)，用于編輯地形高程網(wǎng)格圖；右半部分為圖形區(qū)，用于顯示所編輯地形的效果圖。地形高程網(wǎng)格圖被修改后對地形效果的影響會即時(shí)地反應(yīng)在圖形區(qū)的三維地形效果圖中。

圖3 地形編輯系統(tǒng)界面圖Fig.3 Interface chart of the terrain editor

2 地形模型綜合構(gòu)建方法

2.1 地形草圖編輯與地形數(shù)據(jù)生成

要建立地形模型首先要獲取用于建模的地形數(shù)據(jù)，對于真實(shí)地形來說這些數(shù)據(jù)通常來自于現(xiàn)有的地形圖或?qū)嵉販y量數(shù)據(jù)或遙感影像數(shù)據(jù)。這些數(shù)據(jù)的獲取通常比較困難，獲取周期長、成本較高。而虛構(gòu)地形則不存在這一問題，因?yàn)樘摌?gòu)地形的數(shù)據(jù)來自于人腦的構(gòu)想，我們只需要將這一構(gòu)想轉(zhuǎn)換為現(xiàn)實(shí)的數(shù)據(jù)，下面將介紹一種方法來完成這種轉(zhuǎn)換。

如圖3，地形編輯系統(tǒng)界面的左視圖區(qū)用于顯示地形設(shè)計(jì)草圖，我們把它叫做地形高程網(wǎng)格圖。地形高程網(wǎng)格圖類似于一個(gè)正方形網(wǎng)格，其中的每個(gè)網(wǎng)格單元代表一個(gè)地形塊并且有一個(gè)數(shù)值與之對應(yīng)，此數(shù)值代表該地形塊中點(diǎn)處的高程值。用戶可以定義地形高程網(wǎng)格圖的大小和每個(gè)網(wǎng)格單元代表的地形塊的尺寸，從而確定設(shè)計(jì)地形的尺寸和地形高程點(diǎn)的采樣密度。

系統(tǒng)提供了一種簡單直觀的地形高程網(wǎng)格圖的編輯方法，即使用畫筆為每個(gè)網(wǎng)格著色。如圖3左側(cè)邊緣的調(diào)色板中有12種顏色可以被選為畫筆的顏色，其中每種顏色代表的不是一個(gè)高程值而是一個(gè)高程范圍，用戶可對每種顏色對應(yīng)的高程范圍進(jìn)行定義（如0～20 m）。地形高程網(wǎng)格圖繪制完成后，系統(tǒng)會根據(jù)每個(gè)網(wǎng)格單元的顏色隨機(jī)生成一個(gè)相應(yīng)范圍內(nèi)的數(shù)值，這個(gè)數(shù)值就表示該網(wǎng)格單元所對應(yīng)地形塊的中點(diǎn)處高程值。所有網(wǎng)格單元的數(shù)值生成完畢時(shí)，我們即可得到所設(shè)計(jì)地形的數(shù)字高程模型（DEM）。

2.2 地形模型構(gòu)建

如第二部分所述，基于數(shù)字高程模型的地形建模方法主要有規(guī)則網(wǎng)建模法和不規(guī)則網(wǎng)建模法。針對虛構(gòu)地形對精度要求不高而系統(tǒng)對地形生成與渲染效率要求高的特點(diǎn)，本文選用規(guī)則網(wǎng)建模的基本方法構(gòu)建地形模型。同時(shí)為了彌補(bǔ)規(guī)則網(wǎng)建模法數(shù)據(jù)冗余過多和復(fù)雜多變地形表現(xiàn)能力差的缺點(diǎn)，將對標(biāo)準(zhǔn)規(guī)則網(wǎng)建模法做出一定的改進(jìn)。

2.2.1 預(yù)處理

對于一塊地形（特別是尺寸較大的地形），用戶定義的采樣點(diǎn)數(shù)量是很有限的，僅用這些原始采樣點(diǎn)所構(gòu)建的地形模型很粗糙，地形效果不平滑缺乏真實(shí)感。于是需要對原始數(shù)據(jù)進(jìn)行一定的預(yù)處理，即在原始采樣點(diǎn)之間內(nèi)插若干高程點(diǎn)?？晒┻x用的內(nèi)插算法有很多，湯國安等從不同的角度對這些算法做了比較全面的總結(jié)[10]。本文綜合考慮算法實(shí)現(xiàn)的簡單性和生成地形的平滑性，選用加權(quán)平均算法內(nèi)插高程點(diǎn)。

2.2.2 規(guī)則網(wǎng)建模法的改進(jìn)

按照規(guī)則網(wǎng)建模的思想，我們將一塊完整的地形劃分為多個(gè)大小相同的正方形區(qū)域，每個(gè)區(qū)域稱為一個(gè)地形單元（或地形網(wǎng)格）。每個(gè)地形單元由9個(gè)高程點(diǎn)組成其結(jié)構(gòu)如圖4（a）所示，地形單元中每條邊（除整塊地形的邊界外）上的3個(gè)高程點(diǎn)（如5、6、7三個(gè)點(diǎn)）由相鄰的兩個(gè)地形單元所共有。以每個(gè)地形單元作為一個(gè)節(jié)點(diǎn)，可將整塊地形組織為一個(gè)十字鏈表，遍歷整個(gè)十字鏈表就能生成地形網(wǎng)格。

對于一個(gè)精度要求高，范圍大的地形來說，這種建模方法的數(shù)據(jù)冗余量很大，而且無法體現(xiàn)復(fù)雜地形區(qū)域的細(xì)節(jié)，如坡度大的地形區(qū)域就應(yīng)該有更大的高程點(diǎn)密度，以體現(xiàn)該區(qū)域的細(xì)節(jié)，增強(qiáng)地形效果的真實(shí)感。為了克服這些缺點(diǎn)，本文對規(guī)則網(wǎng)模型進(jìn)行了如下進(jìn)一步處理。首先設(shè)計(jì)一個(gè)指標(biāo)用來表示地形區(qū)域的復(fù)雜程度，我們稱之為最大高程差，它的表達(dá)式為

其中dj為圖4（a）所示地形單元中任意一點(diǎn)的高程差，i和 j的取值為 0、1、2、3、4、5、6、7、8。S 的值越大表示地勢越陡峭，反之表示地勢越平緩。我們可為最大高程差指標(biāo)設(shè)一閥值，然后遍歷十字鏈表中的所有節(jié)點(diǎn)并求出每個(gè)節(jié)點(diǎn)所描述地形單元的最大高程差。對于滿足條件S＞C的地形單元進(jìn)行分割處理，分割方法如圖4(b)所示：在地形單元中標(biāo)號9～24所示位置插入16個(gè)高程點(diǎn)，插入算法采用與預(yù)處理過程中相同的加權(quán)平均算法，再將這25個(gè)高程點(diǎn)表示的地形區(qū)域劃分為4個(gè)地形子單元 （圖中分別用四個(gè)正方形覆蓋的區(qū)域），子單元同樣可組織為十字鏈表。

圖4 地形單元結(jié)構(gòu)及分割方法示意圖Fig.4 Construction of terrain cell and the method to divide a cell

為每個(gè)地形子單元計(jì)算最大高程差，若仍滿足條件，則采用同樣的方法再對子單元進(jìn)行分割，直到上述條件對所有子單元都不成立為止。比較圖5（a）和（b）可以看出利用改進(jìn)方法生成的地形效果在復(fù)雜地形區(qū)域具有更多的三角形面，精度更高，真實(shí)感更強(qiáng)。

圖5 三維地形網(wǎng)格效果圖Fig.5 3D terrain meshes

2.2.3 出現(xiàn)的問題及解決方案

根據(jù)地形單元的結(jié)構(gòu)特點(diǎn)，地形單元可以三角形扇的形式繪制，圖6（a）。然而使用改進(jìn)方案建立的模型在繪制時(shí)會出現(xiàn)裂縫現(xiàn)象，如圖6（a）中為三個(gè)水平方向上相鄰的地形單元，其中第二個(gè)地形單元被分割為四個(gè)子單元。此時(shí)在橢圓覆蓋部分，當(dāng)c點(diǎn)的高程值與a、b兩點(diǎn)的高程平均值不相等時(shí)，折線段acb與線段ab不重合，導(dǎo)致效果圖中此處出現(xiàn)裂縫，稱為“T”形裂縫。

為了消除裂縫現(xiàn)象，在繪制每個(gè)地形單元之前需要對其進(jìn)行有選擇的微調(diào)。具體方法為：根據(jù)相鄰的已繪制單元判斷是否需要對當(dāng)前單元進(jìn)行調(diào)整，若相鄰單元與當(dāng)前單元的分辨率相同則不需要進(jìn)行調(diào)整，否則需要進(jìn)行調(diào)整；具體調(diào)整方法分為兩種，當(dāng)當(dāng)前地形單元比已繪制單元的分辨率高時(shí)，刪除高程點(diǎn)，減少三角形數(shù)量，如圖6（b）繪制第二個(gè)單元時(shí)，將小橢圓處的線段刪除，兩個(gè)三角形合并為一個(gè)；當(dāng)當(dāng)前地形單元比已繪制單元的分辨率低時(shí)，添加高程點(diǎn)，增加三角形數(shù)量，如圖6（b）繪制第三個(gè)單元時(shí)，在大橢圓處添加線段，一個(gè)三角形被拆分為二。此方法不僅能消除裂縫現(xiàn)象，而且算法是在繪制時(shí)進(jìn)行，不需要為了消除裂縫而對地形鏈表再進(jìn)行一次遍歷，為提高建模的速度做出了重要的貢獻(xiàn)。

圖6 裂縫現(xiàn)象及消除方法原理圖Fig.6 Crevices and the principle to eliminate them

3 實(shí)現(xiàn)

第3部分描述了地形建模綜合構(gòu)建機(jī)制，本節(jié)將討論這一機(jī)制的實(shí)現(xiàn)細(xì)節(jié)。本系統(tǒng)選用Microsoft Visual Studio 2010作為開發(fā)環(huán)境在Windows平臺上實(shí)現(xiàn)。為了提供一種直觀的用戶編輯功能，首先需要一個(gè)交互式圖形用戶界面。MFC應(yīng)用框架具有強(qiáng)大的界面開發(fā)能力，是一個(gè)較優(yōu)的選擇，圖2-3就是用MFC開發(fā)的一個(gè)WIMP風(fēng)格的交互界面。

系統(tǒng)實(shí)現(xiàn)的核心內(nèi)容是地形的數(shù)字化描述和地形模型數(shù)據(jù)的管理，這部分的實(shí)現(xiàn)涉及兩個(gè)重要的數(shù)據(jù)結(jié)構(gòu)。第一個(gè)是用來描述地形單元的數(shù)據(jù)結(jié)構(gòu)，主要實(shí)現(xiàn)代碼及說明如下：

Ter_Node

{ //屬性

float m_elevs[9]; //存放每個(gè)地形單元所包含的9個(gè)高程點(diǎn)的高程值

bool b_split; //標(biāo)識本地形單元是否需要進(jìn)行分割

Ter_Link*p_children; //若本單元需要分割，則指向分割的子單元所組成的鏈表，否則為空

//方法

bool DoJudge(); //判斷本單元是否需要進(jìn)行分割

Ter_Link*DoSplit(); //將本單元分割為四個(gè)子單元并放入一個(gè)新的鏈表中

void DrawNode(); //調(diào)用圖形接口繪制本地形單元

}

第二個(gè)是用來組織地形模型數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，其實(shí)質(zhì)是一個(gè)十字鏈表的實(shí)例，主要實(shí)現(xiàn)代碼及說明如下：

Ter_Link

{ //屬性

Ter_Node*p_head,p_tail; //指向左上角和右下角地形單元

Ter_Node*p_current; //當(dāng)前正在處理的地形單元節(jié)點(diǎn)

Ter_Node*p_left,p_right,Ter_Node*p_up,Ter_Node*p_down; //分別指向當(dāng)前節(jié)點(diǎn)的左右上下側(cè)地形單元

//方法

void DrawTer(); //繪制地形：遍歷到每個(gè)節(jié)點(diǎn)時(shí)調(diào)用該節(jié)點(diǎn)的 DrawNode（）函數(shù)繪制

void Traverse(); //遍歷鏈表（從左至右、從上至下遍歷地形單元節(jié)點(diǎn)）

}

渲染地形使用的圖形接口選用OpenGL（Open Graphic Library），它是由SGI開發(fā)的一套圖形軟件處理系統(tǒng)，能實(shí)現(xiàn)高性能的三維圖形功能，將OpenGL函數(shù)嵌入MFC框架中實(shí)現(xiàn)三維地形數(shù)據(jù)的可視化。

4 結(jié)束語

文中提出了一種地形模型的構(gòu)建方法，這種方法綜合了交互編輯與自動(dòng)生成的優(yōu)點(diǎn)，既為用戶提供了交互功能使用戶對地形的生成具有較強(qiáng)的控制能力，又保證了建模的簡單性和高效性。其中地形高程網(wǎng)格圖的提出為用戶提供了一種簡單直觀的地形編輯途徑并實(shí)現(xiàn)了局部地形細(xì)節(jié)的調(diào)整，又通過改進(jìn)規(guī)則網(wǎng)建模法增加了對復(fù)雜地形區(qū)域的表現(xiàn)能力和地形效果的真實(shí)感。當(dāng)然，本文所介紹的建模方法以及系統(tǒng)的實(shí)現(xiàn)還有很多需要改進(jìn)和完善的地方。例如，描述地形的信息可以更加豐富，除了高程值外還可以加入地形類型和土壤材質(zhì)等；又如，可進(jìn)一步研究在裸地地形上進(jìn)行地物和實(shí)體編輯的方法。后續(xù)的工作將在這些方面進(jìn)行進(jìn)一步的研究與探索。

[1]Mandelbrot B B.The fractal geometry of nature[M].San Francisco,CA:Freeman,1982.

[2]Fournier A,Fussell D,Carpenter L.Computer rendering of stochastic models[J].Communications of the ACM,1982,25(6):371-384.

[3]Voss R.Random fractal forgeries[M].Earnshaw R.Fundamental Algorithms for Computer Graphics.Springer Berlin Heidelberg,1991:805-835.

[4]Kelley A D,Malin M C,Nielson G M.Terrain simulation using a model of stream erosion [J].ACM Siggraph Computer Graphics,1988.22(4):263-268.

[5]Musgrave F K,Kolb C E,Mace R S.The synthesis and rendering of eroded fractal terrains[J].ACM Siggraph Computer Graphics,1989,23(3):41-50.

[6]JA˙KO˙B,TO˙TH B.Fast hydraulic and thermal erosion on GPU[C]//The Eurographics Association.Eurographics 2011-Short Pages.2011:57-60.

[7]Benes B,Forsbach R.Layered data representation for visual simulation of terrain erosion[C]//IEEE,Spring Conference on Computer Graphics In 2001,2001:80-86.

[8]HA¨GGSTRO¨M H.Real-time generation and rendering of realistic landscapes[D].Helsinki:University of Helsinki,2006.

[9]Fares B,Pierre A.Modeling Landscapes with Ridges and Rivers[C]//ACM.ACM Symposium on Virtual Reality Software and Technology,2005:151.

[10]湯國安,劉學(xué)軍,閭國年.數(shù)字高程模型及地學(xué)分析的原理與方法[M].北京：科學(xué)出版社，2005.