一种交互编辑与自动生成的三维地形综合构建方法与实现

万 苗，张新家，宋佳音

（西北工业大学 自动化学院，陕西 西安 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.