基于轮廓草图的三维地形建模方法研究

徐　勇　马　燕　康建成

1(上海师范大学计算机科学与技术系　上海 200234)2(上海师范大学地理系　上海 200234)



基于轮廓草图的三维地形建模方法研究

徐勇1马燕1康建成2

1(上海师范大学计算机科学与技术系上海 200234)2(上海师范大学地理系上海 200234)

针对传统的三维地形建模耗时、提取特征值困难以及建模效果不佳的特点，提出基于轮廓草图的三维地形建模的改良方法。系统通过道格拉斯-普克算法分析轮廓的几何特性，使用高斯高通滤波器对重构出三维地形进行去噪。实验结果表明该方法生成的三维地形模型有良好的可视化效果，也验证了道格拉斯-普克算法适合于分析勾勒、分解和重构轮廓，高斯高通滤波器对地形的平滑有良好的效果。

地形建模道格拉斯-普克算法数字高度图

0　引　言

在计算机图形学、虚拟现实以及三维可视化技术等领域[1]，许多学者正为找出更加逼真的三维地形建模系统[2]而努力。与二维平面地形相比，三维地形可以将繁杂地理数据及其分析结果数字化，成为用户能够直观理解的信息，在此基础上进行地理信息显示和空间分析。我们都在思考：怎样根据视点的变化与漫游的需要来实时模拟地形的各种形态？

现有的建模技术大致上可以分为两类，一是使用传统的3D建模工具，如Blender、Maya和3DMAX；二是分形方法。前一类方法为用户提供了一个能够控制地形外观的建模方法，但耗时长、速度缓慢，要求用户具有较强的图形知识和编程能力，没有图形学经验的用户很难用这类方法实现建模。相比之下，后一类方法是自动完成的，耗时短、速度较快，但它存在一个致命问题，即用户无法控制最后生成的地形效果。综上所述，这两类建模工具都要求用户具备较强的编程能力，所以它们不适合一般用户。因此先前的研究者们把以上述两类方法的优点加以结合，提出基于草图的三维建模方法。

基于草图方法[3]的三维地形建模在电脑游戏和电影领域使用频繁。在先前的研究中，有图形研究小组开发了一个基于草图与等高线[4]的地形模型，它使用绘画方法。这种模型对普通用户而言易于使用，且生成三维地形的可视化效果也较好，但缺乏反映地形详细特征的能力，如平滑的丘陵或崎岖蜿蜒的山脉。这种基于手绘草图[5]的地形模型不能很好地描绘地形形状，所以生成的三维地形模型缺乏准确性和真实性。

为了使建模工具能反映更详细的三维地形信息，通过对上述方法的研究与分析，本文提出一种新的基于轮廓草图的三维地形建模方法。该方法需要用户描绘某个地形的部分轮廓，然后自动分析轮廓与地形的哪些部分匹配，分析出的轮廓的几何特性，并根据相应的地形作出修正，通过道格拉斯-普克算法提取轮廓的几何特性。该建模方法的目的是为没有图形学经验的用户提供最后生成结果的可控性。此方法同时具有耗时短、速度快的优点，能较逼真地反映三维地形[6]模型。

1　基于轮廓草图的三维地形建模方法

1.1设计概述

首先简单介绍下早期基于草图轮廓的三维地形建模，如图1所示，当用户输入简单轮廓与箭头后(图1上左)；系统使用几组特定算法来分析轮廓与箭头，取得它们的主要特征(图1上中)；在人机交互界面生成匹配的高程值(图1上右)；最后生成三维地形模型[7](图1下)，而我们发现这种匹配出三维地形可视化程度很低。

图1　早期基于草图轮廓的三维地形建模

我们的设计理念是新的基于轮廓草图的建模方法能获得轮廓与地形区域高度匹配的效果。

因此，系统需要满足以下的设计要求：

(1) 能让用户特别是对于没有经验的用户绘制一个轮廓。

(2) 可以识别和区分不同的轮廓，检测正确的等高线域，每个轮廓构造不同的三维地形模型。

(3) 应用一些算法来分析的轮廓，以获得重要的特征信息。整合这些信息，计算并重构出三维地形模型的功能。

(4) 当用户不满意他勾画的地形时，轮廓可以进行修改并在人机交互界面上重新勾画。

(5) 生成地三维地形模型具有与用户输入的草图有高度的相似性，匹配性好。轮廓的所有主要特征应该显示在三维地形模型中。

(6) 提供一个3D窗口观察，从不同的角度研究三维地形模型。

为满足上述要求，我们创建二维草图窗口[8]的用户界面来方便用户勾画一个二维的轮廓。

1.2使用道格拉斯-普克算法来提取草图信息

目前有很多适合于分析与匹配轮廓的技术，其中大多都包括大量的数学公式与相关几何的科学。我们在实验中发现基于道格拉斯-普克算法更适合用于识别轮廓[9]的主要特点。通过迭代使用道格拉斯-普克算法，我们能得到大部分需要的信息。

在项目实现的过程中，为了创建逼真的地形的三维模型[10]，我们打算找出一些更有效的函数来重建草图，包括轮廓的主要特征值，最好是在程序的运行过程中添加的随机峰，但是添加的随机峰又不能损失过多的资源，包括运行时间与影响轮廓匹配的相似度。于是在项目中系统引入了地形的平滑函数，无论是随机值和函数都应该受到标准偏差的约束。由于时间不足以及能力有限，一些要求在本系统中还没有实现。

1.3使用包围盒来识别草图

本文使用的包围盒算法识别草图的运行情况如下：

(1) 连接草图上起点A和终点B。起点和终点AB之间的距离作为包围盒的宽度。

(2) 找到与C点距离最长的点(CD)垂直于草图上直线AB。

(3) 计算AB与CD的长度比值。

(4) 根据该比率，我们把草图分成不同的组。

正如说明所述，AB连接作为基准线和从草图最远的点C点到AB上的D点。比例是通过使用AB/CD的比率计算。

1.4使用道格拉斯-普克算法分析轮廓

轮廓一旦可被识别，接下来就是分析轮廓，确定的轮廓所包含的信息。例如提取出轮廓包含的峰和谷的数目等。程序需要用户指定最高峰以及最低盆地的位置。当系统分析完轮廓后，我们便得到轮廓的主要特征。算法接着调用插值函数用于进一步分析，目的是为了把轮廓信息转换成不同形式的信号，对信号最常用的分析工具就是快速傅立叶变换和离散小波变换，在本文中，我们使用了道格拉斯-普克算法[11]，可能不大常见，但我们使用效果却很理想。道格拉斯-普克算法可以去除噪声并且不改变轮廓线的主要特征值。与FFT和DWT相比，道格拉斯-普克算法更适合于非周期信号的分析和重建。道格拉斯-普克算法可以分解不同层次的细节特征。系统使用这些数据来表现的轮廓的几何形状，重构与之相匹配的几何性质2D地形，算法得出的结果满足我们的要求。

如图2所示，为了分解轮廓在不同高程上的细节，我们迭代利用道格拉斯-普克算法分析轮廓，首先我们取得距离基准线的最大距离的点，基准线被定义为一条直线，它是轮廓线起点到终点，这个最大距离是可被认为轮廓第一个确定的层次属性。接下来，我们利用道格拉斯-普克算法的ε值等于最大距离的一半获取更多轮廓属性。每次调用的道格拉斯-普克算法时，ε值降低为原来的ε值的一半，以此递推。

图2　使用道格拉斯-普克算法来分析轮廓的例子

1.5侦测轮廓域

有两种方法来侦测出某个特定区域来调用这样的重建函数，一是让用户预先定义使用区域；二是系统基于轮廓线域自动调用重建函数。如采用第一种方法，必须让用户绘制出另一张草图来指示出使用区域，但添加新草图的做法会导致与原始轮廓线产生冲突，系统无法分辨到底那张草图是原始输入的草图，因此本文中选取第二种方法。

通常情况下，当与用户输入一条轮廓线后，这条轮廓线是一段连续的曲线[12]，我们可以认为它有多段峰谷组成，轮廓线也存在极值点，极值点满足两个条件：

(1) 不存在其他轮廓线比它的最高点更高。

(2) 不存在其他轮廓线比它的最低点更低。

如果存在一条轮廓线满足上述两个条件之一，我们把它定义为一条极值线。系统被设计为让用户来预定义哪些轮廓线区域适用重构函数，因此文章构思了一个简单的方法来满足要求。

如图3所示：首先我们建立由轮廓起点和终点的连接线为基线，显然我们发现了基准线与轮廓线相交，于是本文定于与基线相交的区域为调用重建函数区域。当然，如果系统可直接自动识别出了相交域，这样调用重建函数就会更方便。

为了证实是外部轮廓线，我们给定三个步骤来考虑。第一步是计算出轮廓线与基准线相交后的交点。第二步是计算两个交点之间的距离。第三步是找到两个交叉点之间的最大距离。

图3　例轮廓线与基准线相交

1.6与其他项目比较

图4是早期通过使用基于草图的三维地形建模技术[13]生成地三维地形模型简单粗糙，原本应该是陡峭山脉的地方几乎与盘山公路在同一个平面上。

与基于草图的地形模型相比，本文让用户绘制地形的轮廓，该系统自动分析该轮廓和它的几何性质，确定地形区域。生成了光滑的山丘，与轮廓相对应的地形高度相似，构造了较好的三维地形模型，创建了一个更加逼真的山峰而不是一个平面[14]。

图4　两个结果的例子，基于草图的地形模型(上3幅)，本文(下2幅)

1.7不使用高斯高通滤波器

项目的实现过程中发现一个有意思的问题，如果不使用高斯高通滤波器[15]，生成的三维是不逼真的，可视化程度较差。以图5作为举例说明。三维地形在Y轴出现了多个意想不到的山峰与山谷，这些峰谷的出现才有机会让高斯高通滤波大显身手，这是在本文先前设计时没有考虑到的。

产生如图5所示的糟糕结果的原因在于：有些像素在系统应用重构函数的时候没有被修改为理想的高程值，在重构时以原值的形式重新运用到了3D地形建模中，与它相邻已经被修改的像素之间产生了非常大的差异。当用户从不同的角度观察生成的地形时，三维地形模型中出现了多个峰谷。

图5　意外出现的山谷

1.8最后的结果

当系统调用了轮廓线重构函数后，会重新生成用于渲染3D地形模型的数字高度图。由于保存在数组中的高程值并不是一组连续的值，所以系统调用高程值后，应该使用高斯高通滤波器去剔除与相邻像素有较大差异的高程值，舍去低频信号，创建出平滑的地形。

如图6所示，该系统允许用户通过二维的窗口绘制轮廓。这个轮廓由程序自动识别。然后我们按照不同细节将轮廓分解成不同高程。该系统用这些层次采集的特征值来来重构与之等效的几何性质，创建出二维地形。接下来系统会判断能够反应这个轮廓的地形区域，并调用重构函数到这个区域中。在很短的时间里，系统就重建了高相似度的三维地形模型。轮廓的主要属性很都能在形成的三维地形中反应出来。

图6　2D草图窗口(左上)，其他图为从不同角度观察的三维地形

实验中还发现高斯高通滤波功能存在缺陷：一是系统如果要调用高斯高通函数，必须先建立一个二维数组来存储原始高程值，然后还需要设计另一组二维数组来存储已被修正过的高程值，便于系统对这些值进行滤波去噪，这占用了大量计算机内存，减慢系统运行时间，所以要注意存储器分配，以免产生存储冲突。二是生成的三维地形由于滤波损失了部分精度，某些主要的特征值会得不到很好的重构。

2　结　语

轮廓在基于草图的地形建模中是一项令人兴奋的技术。特

别是在电脑游戏和计算机图形学领域。这个程序给用户提供了一把钥匙，用户只需勾画二维的草图就可以得出三维的地形。

本文中，首先提出了一系列的算法对草图进行分析，并对这些算法做了简要介绍，随后提出了一种新方法来分析复杂的和非周期性轮廓。后来，我们验证了道格拉斯-普克算法[13]可以分解和重构轮廓。我们把轮廓的细节按照不同的高程来分解，使用这些层次来反映的轮廓的几何形状，并通过调用函数来采集轮廓的二维信息。最后，本文证明了高斯高通滤波器适用于创造平滑的地形模型。本文中利用此滤波器替换不合理的高程值，移除了意想不到的山谷。

在未来，我们希望实现3D建模更加真实，匹配程度更高。让这项技术在电脑游戏、视景仿真、地理、气象和军事发挥更大的作用。当用户输入草图后，系统能完全匹配的轮廓区域，高程值也不会损失，实现完美匹配。

[1] 郭涛，平西建. 基于OpenGL的三维地形可视化技术研究[J]. 计算机工程与设计，2008(1)：193-196.

[2] 韩红波. 基于手绘草图三维建模方法研究[D]. 南京航空大学， 2008.

[3]ZeleznikRobertc，HerndonKennethP，HughesJohnF.SKETCH：aninterfaceforsketching3Dscenes[C]//ComputerGraphicsProceedings，AnnualConferenceSeries，ACMSIGGRAPH，NewOrleans，1996：161-170.

[4]IgarashiT,MatsuokaS,TanakaH.Teddy:Asketchinginterfacefor3Dfreeformdesign[C]//ComputerGraphicsProceedings,AnnualConferenceSeries,ACMSIGGRAPH,LosAngeles,California,1999:409-416.

[5] 孙正兴，冯桂焕，周若鸿．基于草图的人机交互技术研究进展[J]．计算机辅助设计与图形学学报，2005，17(9)：1889-1899.

[6]QinSF,WrightDK，JordanovIN.Fromon-linesketchto2Dand3Dgeometry:Asystembasedonfuzzyknowledge[J].ComputerAidedDesign,2000，32(14)：851-866.

[7]CherlinJosephJ，FaramarzSamavati，MarioC．Sousa，etal.Sketch-basedmodelingwithfewstrokes[C]//ProceedingsoftheSpringConferenceonComputerGraphics(SCCG’05)，Budmerice，2005：1-9.

[8]HartsonRH，HixD.Human-ComputerInterfaceDevelopment：ConceptsandSystemsforItsManagement[J].ACMComputingSurveys，1989,21(1)：5-92.

[9]CohenJM，HughesJF，ZeleznikRC.Harold:aworldmadeofdrawings[J].ProceedingsoftheFirstInternationalSymposiumonNonPhotorealisticAnimation&Rendering,2000：83-90.

[10] 周炜，董福安，吉楠. 基于分形和高度图控制的三维地形生成技术研究[J]. 电光与控制，2007,14(7)：66-71.

[11]DouglasDH，PeuckerT.Algorithmsforthereductionofthenumberofpointsrequiredtorepresentadigitizedlineoritscaricature[J].TheCanadianCartographer，1973，10(2)：112-122.

[12] 雷海峰. 基于DEM的地形信息提取及运用[D]. 成都理工大学， 2012.

[13]DouglasPeucker.Ramer-Douglas-Peuckeralgorithm[DB/OL]. [2010-2-2].http：//en.wikipedia.org/wiki/Ramer-Douglas-Peuckeralgorithm.

[14] 伍燕萍. 基于图像的三维重建[D]. 北京交通大学，2009.

[15] 谢勤岚. 图像降噪的自适应高斯平滑滤波器[J]. 计算机工程与应用，2009(16)：182-186.

RESEARCHONCONTOURSKETCH-BASED3DTERRAINMODELLINGMETHOD

XuYong1MaYan1KangJiancheng2

1(Department of Computer Science and Technology,Shanghai Normal University,Shanghai 200234,China)2(Department of Geography,Shanghai Normal University,Shanghai 200234,China)

Aimingattraditional3Dterrainmodellingcharacteristicssuchastimeconsuming,difficultineigenvalueextractionandpoormodellingeffect,weputforwardthecontoursketch-basedimprovedmethodfor3Dterrainmodelling.ThesystemanalysesthegeometriccharacteristicsofcontourwithDouglas-Peuckeralgorithm,anddenoisesthereconstructed3DterrainwithGausshigh-passfilter.Experimentalresultsshowedthatthe3Dterrainmodelgeneratedbythismethodhadgoodvisualisationeffect,andprovedaswellthattheDouglas-Peuckeralgorithmissuitablefortheanalysisofoutlining,decomposingandreconstructingcontour,andthatGausshigh-passfilterhasgoodeffectonterrainsmoothing.

TerrainmodellingDouglas-PeuckeralgorithmDigitalelevationmap

2014-10-18。徐勇，助理工程师，主研领域：图形学。马燕，教授。康建成，教授。

TP3

ADOI:10.3969/j.issn.1000-386x.2016.03.028