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

徐　勇　馬　燕　康建成

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

?

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

徐勇1馬燕1康建成2

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

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

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

0　引　言

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

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

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

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

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

1.1設計概述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.3使用包圍盒來識別草圖

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

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

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

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

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

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

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

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

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

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

1.5偵測輪廓域

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

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

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

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

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

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

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

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

1.6與其他項目比較

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

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

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

1.7不使用高斯高通濾波器

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

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

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

1.8最后的結果

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

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

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

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

2　結　語

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

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

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

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

[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，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] 周煒，董福安，吉楠. 基于分形和高度圖控制的三維地形生成技術研究[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