一種交互編輯與自動生成的三維地形綜合構建方法與實現

萬 苗，張新家，宋佳音

（西北工業大學 自動化學院，陜西 西安 710129）

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

交互編輯是最初采用的地形建模方法，用戶利用專門的建模工具設計自己的地形。這種方法構建的地形模型精度高，效果逼真。但這種方法的建模過程繁瑣效率很低，對專業知識水平要求高。而且大部分建模工具的使用都比較復雜，需要長期的經驗積累。因此很多地形模型應用系統（如軍事訓練游戲）的終端用戶只能使用預定義地形或雇傭專業的地形模型設計團隊為其制作專用地形。

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

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

1 地形模型建模流程

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

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

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

圖2 地形網格示意圖Fig.2 Terrain meshes

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

圖3 地形編輯系統界面圖Fig.3 Interface chart of the terrain editor

2 地形模型綜合構建方法

2.1 地形草圖編輯與地形數據生成

要建立地形模型首先要獲取用于建模的地形數據，對于真實地形來說這些數據通常來自于現有的地形圖或實地測量數據或遙感影像數據。這些數據的獲取通常比較困難，獲取周期長、成本較高。而虛構地形則不存在這一問題，因為虛構地形的數據來自于人腦的構想，我們只需要將這一構想轉換為現實的數據，下面將介紹一種方法來完成這種轉換。

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

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

2.2 地形模型構建

如第二部分所述，基于數字高程模型的地形建模方法主要有規則網建模法和不規則網建模法。針對虛構地形對精度要求不高而系統對地形生成與渲染效率要求高的特點，本文選用規則網建模的基本方法構建地形模型。同時為了彌補規則網建模法數據冗余過多和復雜多變地形表現能力差的缺點，將對標準規則網建模法做出一定的改進。

2.2.1 預處理

對于一塊地形（特別是尺寸較大的地形），用戶定義的采樣點數量是很有限的，僅用這些原始采樣點所構建的地形模型很粗糙，地形效果不平滑缺乏真實感。于是需要對原始數據進行一定的預處理，即在原始采樣點之間內插若干高程點。可供選用的內插算法有很多，湯國安等從不同的角度對這些算法做了比較全面的總結[10]。本文綜合考慮算法實現的簡單性和生成地形的平滑性，選用加權平均算法內插高程點。

2.2.2 規則網建模法的改進

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

對于一個精度要求高，范圍大的地形來說，這種建模方法的數據冗余量很大，而且無法體現復雜地形區域的細節，如坡度大的地形區域就應該有更大的高程點密度，以體現該區域的細節，增強地形效果的真實感。為了克服這些缺點，本文對規則網模型進行了如下進一步處理。首先設計一個指標用來表示地形區域的復雜程度，我們稱之為最大高程差，它的表達式為

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

圖4 地形單元結構及分割方法示意圖Fig.4 Construction of terrain cell and the method to divide a cell

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

圖5 三維地形網格效果圖Fig.5 3D terrain meshes

2.2.3 出現的問題及解決方案

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

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

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

3 實現

第3部分描述了地形建模綜合構建機制，本節將討論這一機制的實現細節。本系統選用Microsoft Visual Studio 2010作為開發環境在Windows平臺上實現。為了提供一種直觀的用戶編輯功能，首先需要一個交互式圖形用戶界面。MFC應用框架具有強大的界面開發能力，是一個較優的選擇，圖2-3就是用MFC開發的一個WIMP風格的交互界面。

系統實現的核心內容是地形的數字化描述和地形模型數據的管理，這部分的實現涉及兩個重要的數據結構。第一個是用來描述地形單元的數據結構，主要實現代碼及說明如下：

Ter_Node

{ //屬性

float m_elevs[9]; //存放每個地形單元所包含的9個高程點的高程值

bool b_split; //標識本地形單元是否需要進行分割

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

//方法

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

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

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

}

第二個是用來組織地形模型數據的數據結構，其實質是一個十字鏈表的實例，主要實現代碼及說明如下：

Ter_Link

{ //屬性

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

Ter_Node*p_current; //當前正在處理的地形單元節點

Ter_Node*p_left,p_right,Ter_Node*p_up,Ter_Node*p_down; //分別指向當前節點的左右上下側地形單元

//方法

void DrawTer(); //繪制地形：遍歷到每個節點時調用該節點的 DrawNode（）函數繪制

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

}

渲染地形使用的圖形接口選用OpenGL（Open Graphic Library），它是由SGI開發的一套圖形軟件處理系統，能實現高性能的三維圖形功能，將OpenGL函數嵌入MFC框架中實現三維地形數據的可視化。

4 結束語

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

[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]湯國安,劉學軍,閭國年.數字高程模型及地學分析的原理與方法[M].北京：科學出版社，2005.