徐　勇　馬　燕　康建成

1(上海師范大學計算機科學與技術(shù)系　上海 200234)2(上海師范大學地理系　上海 200234)

?

基于輪廓草圖的三維地形建模方法研究

徐勇1馬燕1康建成2

1(上海師范大學計算機科學與技術(shù)系上海 200234)2(上海師范大學地理系上海 200234)

針對傳統(tǒng)的三維地形建模耗時、提取特征值困難以及建模效果不佳的特點，提出基于輪廓草圖的三維地形建模的改良方法。系統(tǒng)通過道格拉斯-普克算法分析輪廓的幾何特性，使用高斯高通濾波器對重構(gòu)出三維地形進行去噪。實驗結(jié)果表明該方法生成的三維地形模型有良好的可視化效果，也驗證了道格拉斯-普克算法適合于分析勾勒、分解和重構(gòu)輪廓，高斯高通濾波器對地形的平滑有良好的效果。

地形建模道格拉斯-普克算法數(shù)字高度圖

0　引　言

在計算機圖形學、虛擬現(xiàn)實以及三維可視化技術(shù)等領(lǐng)域[1]，許多學者正為找出更加逼真的三維地形建模系統(tǒng)[2]而努力。與二維平面地形相比，三維地形可以將繁雜地理數(shù)據(jù)及其分析結(jié)果數(shù)字化，成為用戶能夠直觀理解的信息，在此基礎(chǔ)上進行地理信息顯示和空間分析。我們都在思考：怎樣根據(jù)視點的變化與漫游的需要來實時模擬地形的各種形態(tài)？

現(xiàn)有的建模技術(shù)大致上可以分為兩類，一是使用傳統(tǒng)的3D建模工具，如Blender、Maya和3DMAX；二是分形方法。前一類方法為用戶提供了一個能夠控制地形外觀的建模方法，但耗時長、速度緩慢，要求用戶具有較強的圖形知識和編程能力，沒有圖形學經(jīng)驗的用戶很難用這類方法實現(xiàn)建模。相比之下，后一類方法是自動完成的，耗時短、速度較快，但它存在一個致命問題，即用戶無法控制最后生成的地形效果。綜上所述，這兩類建模工具都要求用戶具備較強的編程能力，所以它們不適合一般用戶。因此先前的研究者們把以上述兩類方法的優(yōu)點加以結(jié)合，提出基于草圖的三維建模方法。

基于草圖方法[3]的三維地形建模在電腦游戲和電影領(lǐng)域使用頻繁。在先前的研究中，有圖形研究小組開發(fā)了一個基于草圖與等高線[4]的地形模型，它使用繪畫方法。這種模型對普通用戶而言易于使用，且生成三維地形的可視化效果也較好，但缺乏反映地形詳細特征的能力，如平滑的丘陵或崎嶇蜿蜒的山脈。這種基于手繪草圖[5]的地形模型不能很好地描繪地形形狀，所以生成的三維地形模型缺乏準確性和真實性。

為了使建模工具能反映更詳細的三維地形信息，通過對上述方法的研究與分析，本文提出一種新的基于輪廓草圖的三維地形建模方法。該方法需要用戶描繪某個地形的部分輪廓，然后自動分析輪廓與地形的哪些部分匹配，分析出的輪廓的幾何特性，并根據(jù)相應的地形作出修正，通過道格拉斯-普克算法提取輪廓的幾何特性。該建模方法的目的是為沒有圖形學經(jīng)驗的用戶提供最后生成結(jié)果的可控性。此方法同時具有耗時短、速度快的優(yōu)點，能較逼真地反映三維地形[6]模型。

1　基于輪廓草圖的三維地形建模方法

1.1設(shè)計概述

首先簡單介紹下早期基于草圖輪廓的三維地形建模，如圖1所示，當用戶輸入簡單輪廓與箭頭后(圖1上左)；系統(tǒng)使用幾組特定算法來分析輪廓與箭頭，取得它們的主要特征(圖1上中)；在人機交互界面生成匹配的高程值(圖1上右)；最后生成三維地形模型[7](圖1下)，而我們發(fā)現(xiàn)這種匹配出三維地形可視化程度很低。

圖1　早期基于草圖輪廓的三維地形建模

我們的設(shè)計理念是新的基于輪廓草圖的建模方法能獲得輪廓與地形區(qū)域高度匹配的效果。

因此，系統(tǒng)需要滿足以下的設(shè)計要求：

(1) 能讓用戶特別是對于沒有經(jīng)驗的用戶繪制一個輪廓。

(2) 可以識別和區(qū)分不同的輪廓，檢測正確的等高線域，每個輪廓構(gòu)造不同的三維地形模型。

(3) 應用一些算法來分析的輪廓，以獲得重要的特征信息。整合這些信息，計算并重構(gòu)出三維地形模型的功能。

(4) 當用戶不滿意他勾畫的地形時，輪廓可以進行修改并在人機交互界面上重新勾畫。

(5) 生成地三維地形模型具有與用戶輸入的草圖有高度的相似性，匹配性好。輪廓的所有主要特征應該顯示在三維地形模型中。

(6) 提供一個3D窗口觀察，從不同的角度研究三維地形模型。

為滿足上述要求，我們創(chuàng)建二維草圖窗口[8]的用戶界面來方便用戶勾畫一個二維的輪廓。

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

目前有很多適合于分析與匹配輪廓的技術(shù)，其中大多都包括大量的數(shù)學公式與相關(guān)幾何的科學。我們在實驗中發(fā)現(xiàn)基于道格拉斯-普克算法更適合用于識別輪廓[9]的主要特點。通過迭代使用道格拉斯-普克算法，我們能得到大部分需要的信息。

在項目實現(xiàn)的過程中，為了創(chuàng)建逼真的地形的三維模型[10]，我們打算找出一些更有效的函數(shù)來重建草圖，包括輪廓的主要特征值，最好是在程序的運行過程中添加的隨機峰，但是添加的隨機峰又不能損失過多的資源，包括運行時間與影響輪廓匹配的相似度。于是在項目中系統(tǒng)引入了地形的平滑函數(shù)，無論是隨機值和函數(shù)都應該受到標準偏差的約束。由于時間不足以及能力有限，一些要求在本系統(tǒng)中還沒有實現(xiàn)。

1.3使用包圍盒來識別草圖

本文使用的包圍盒算法識別草圖的運行情況如下：

(1) 連接草圖上起點A和終點B。起點和終點AB之間的距離作為包圍盒的寬度。

(2) 找到與C點距離最長的點(CD)垂直于草圖上直線AB。

(3) 計算AB與CD的長度比值。

(4) 根據(jù)該比率，我們把草圖分成不同的組。

正如說明所述，AB連接作為基準線和從草圖最遠的點C點到AB上的D點。比例是通過使用AB/CD的比率計算。

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

輪廓一旦可被識別，接下來就是分析輪廓，確定的輪廓所包含的信息。例如提取出輪廓包含的峰和谷的數(shù)目等。程序需要用戶指定最高峰以及最低盆地的位置。當系統(tǒng)分析完輪廓后，我們便得到輪廓的主要特征。算法接著調(diào)用插值函數(shù)用于進一步分析，目的是為了把輪廓信息轉(zhuǎn)換成不同形式的信號，對信號最常用的分析工具就是快速傅立葉變換和離散小波變換，在本文中，我們使用了道格拉斯-普克算法[11]，可能不大常見，但我們使用效果卻很理想。道格拉斯-普克算法可以去除噪聲并且不改變輪廓線的主要特征值。與FFT和DWT相比，道格拉斯-普克算法更適合于非周期信號的分析和重建。道格拉斯-普克算法可以分解不同層次的細節(jié)特征。系統(tǒng)使用這些數(shù)據(jù)來表現(xiàn)的輪廓的幾何形狀，重構(gòu)與之相匹配的幾何性質(zhì)2D地形，算法得出的結(jié)果滿足我們的要求。

如圖2所示，為了分解輪廓在不同高程上的細節(jié)，我們迭代利用道格拉斯-普克算法分析輪廓，首先我們?nèi)〉镁嚯x基準線的最大距離的點，基準線被定義為一條直線，它是輪廓線起點到終點，這個最大距離是可被認為輪廓第一個確定的層次屬性。接下來，我們利用道格拉斯-普克算法的ε值等于最大距離的一半獲取更多輪廓屬性。每次調(diào)用的道格拉斯-普克算法時，ε值降低為原來的ε值的一半，以此遞推。

圖2　使用道格拉斯-普克算法來分析輪廓的例子

1.5偵測輪廓域

有兩種方法來偵測出某個特定區(qū)域來調(diào)用這樣的重建函數(shù)，一是讓用戶預先定義使用區(qū)域；二是系統(tǒng)基于輪廓線域自動調(diào)用重建函數(shù)。如采用第一種方法，必須讓用戶繪制出另一張草圖來指示出使用區(qū)域，但添加新草圖的做法會導致與原始輪廓線產(chǎn)生沖突，系統(tǒng)無法分辨到底那張草圖是原始輸入的草圖，因此本文中選取第二種方法。

通常情況下，當與用戶輸入一條輪廓線后，這條輪廓線是一段連續(xù)的曲線[12]，我們可以認為它有多段峰谷組成，輪廓線也存在極值點，極值點滿足兩個條件：

(1) 不存在其他輪廓線比它的最高點更高。

(2) 不存在其他輪廓線比它的最低點更低。

如果存在一條輪廓線滿足上述兩個條件之一，我們把它定義為一條極值線。系統(tǒng)被設(shè)計為讓用戶來預定義哪些輪廓線區(qū)域適用重構(gòu)函數(shù)，因此文章構(gòu)思了一個簡單的方法來滿足要求。

如圖3所示：首先我們建立由輪廓起點和終點的連接線為基線，顯然我們發(fā)現(xiàn)了基準線與輪廓線相交，于是本文定于與基線相交的區(qū)域為調(diào)用重建函數(shù)區(qū)域。當然，如果系統(tǒng)可直接自動識別出了相交域，這樣調(diào)用重建函數(shù)就會更方便。

為了證實是外部輪廓線，我們給定三個步驟來考慮。第一步是計算出輪廓線與基準線相交后的交點。第二步是計算兩個交點之間的距離。第三步是找到兩個交叉點之間的最大距離。

圖3　例輪廓線與基準線相交

1.6與其他項目比較

圖4是早期通過使用基于草圖的三維地形建模技術(shù)[13]生成地三維地形模型簡單粗糙，原本應該是陡峭山脈的地方幾乎與盤山公路在同一個平面上。

與基于草圖的地形模型相比，本文讓用戶繪制地形的輪廓，該系統(tǒng)自動分析該輪廓和它的幾何性質(zhì)，確定地形區(qū)域。生成了光滑的山丘，與輪廓相對應的地形高度相似，構(gòu)造了較好的三維地形模型，創(chuàng)建了一個更加逼真的山峰而不是一個平面[14]。

圖4　兩個結(jié)果的例子，基于草圖的地形模型(上3幅)，本文(下2幅)

1.7不使用高斯高通濾波器

項目的實現(xiàn)過程中發(fā)現(xiàn)一個有意思的問題，如果不使用高斯高通濾波器[15]，生成的三維是不逼真的，可視化程度較差。以圖5作為舉例說明。三維地形在Y軸出現(xiàn)了多個意想不到的山峰與山谷，這些峰谷的出現(xiàn)才有機會讓高斯高通濾波大顯身手，這是在本文先前設(shè)計時沒有考慮到的。

產(chǎn)生如圖5所示的糟糕結(jié)果的原因在于：有些像素在系統(tǒng)應用重構(gòu)函數(shù)的時候沒有被修改為理想的高程值，在重構(gòu)時以原值的形式重新運用到了3D地形建模中，與它相鄰已經(jīng)被修改的像素之間產(chǎn)生了非常大的差異。當用戶從不同的角度觀察生成的地形時，三維地形模型中出現(xiàn)了多個峰谷。

圖5　意外出現(xiàn)的山谷

1.8最后的結(jié)果

當系統(tǒng)調(diào)用了輪廓線重構(gòu)函數(shù)后，會重新生成用于渲染3D地形模型的數(shù)字高度圖。由于保存在數(shù)組中的高程值并不是一組連續(xù)的值，所以系統(tǒng)調(diào)用高程值后，應該使用高斯高通濾波器去剔除與相鄰像素有較大差異的高程值，舍去低頻信號，創(chuàng)建出平滑的地形。

如圖6所示，該系統(tǒng)允許用戶通過二維的窗口繪制輪廓。這個輪廓由程序自動識別。然后我們按照不同細節(jié)將輪廓分解成不同高程。該系統(tǒng)用這些層次采集的特征值來來重構(gòu)與之等效的幾何性質(zhì)，創(chuàng)建出二維地形。接下來系統(tǒng)會判斷能夠反應這個輪廓的地形區(qū)域，并調(diào)用重構(gòu)函數(shù)到這個區(qū)域中。在很短的時間里，系統(tǒng)就重建了高相似度的三維地形模型。輪廓的主要屬性很都能在形成的三維地形中反應出來。

圖6　2D草圖窗口(左上)，其他圖為從不同角度觀察的三維地形

實驗中還發(fā)現(xiàn)高斯高通濾波功能存在缺陷：一是系統(tǒng)如果要調(diào)用高斯高通函數(shù)，必須先建立一個二維數(shù)組來存儲原始高程值，然后還需要設(shè)計另一組二維數(shù)組來存儲已被修正過的高程值，便于系統(tǒng)對這些值進行濾波去噪，這占用了大量計算機內(nèi)存，減慢系統(tǒng)運行時間，所以要注意存儲器分配，以免產(chǎn)生存儲沖突。二是生成的三維地形由于濾波損失了部分精度，某些主要的特征值會得不到很好的重構(gòu)。

2　結(jié)　語

輪廓在基于草圖的地形建模中是一項令人興奮的技術(shù)。特

別是在電腦游戲和計算機圖形學領(lǐng)域。這個程序給用戶提供了一把鑰匙，用戶只需勾畫二維的草圖就可以得出三維的地形。

本文中，首先提出了一系列的算法對草圖進行分析，并對這些算法做了簡要介紹，隨后提出了一種新方法來分析復雜的和非周期性輪廓。后來，我們驗證了道格拉斯-普克算法[13]可以分解和重構(gòu)輪廓。我們把輪廓的細節(jié)按照不同的高程來分解，使用這些層次來反映的輪廓的幾何形狀，并通過調(diào)用函數(shù)來采集輪廓的二維信息。最后，本文證明了高斯高通濾波器適用于創(chuàng)造平滑的地形模型。本文中利用此濾波器替換不合理的高程值，移除了意想不到的山谷。

在未來，我們希望實現(xiàn)3D建模更加真實，匹配程度更高。讓這項技術(shù)在電腦游戲、視景仿真、地理、氣象和軍事發(fā)揮更大的作用。當用戶輸入草圖后，系統(tǒng)能完全匹配的輪廓區(qū)域，高程值也不會損失，實現(xiàn)完美匹配。

[1] 郭濤，平西建. 基于OpenGL的三維地形可視化技術(shù)研究[J]. 計算機工程與設(shè)計，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] 孫正興，馮桂煥，周若鴻．基于草圖的人機交互技術(shù)研究進展[J]．計算機輔助設(shè)計與圖形學學報，2005，17(9)：1889-1899.

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

[7]CherlinJosephJ，F(xiàn)aramarzSamavati，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] 周煒，董福安，吉楠. 基于分形和高度圖控制的三維地形生成技術(shù)研究[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。徐勇，助理工程師，主研領(lǐng)域：圖形學。馬燕，教授?？到ǔ?，教授。

TP3

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