基于聚類和動態(tài)LOD的三維地形建模方法

吳曉彥，顧韻華，張俊勇，杜 杰

（南京信息工程大學(xué) 計(jì)算機(jī)與軟件學(xué)院，江蘇 南京210044）

0 引 言

DEM （digital elevation model）是描述海拔高度分布的一種數(shù)據(jù)模型，它不但可以在地理空間中完成精確定位，還能對地面特性或者地貌進(jìn)行空間數(shù)字描述，是反映地形特征的有效手段［1］。DEM 數(shù)據(jù)對于不同地形類型均采用相同密度采樣點(diǎn)描述，而大地形覆蓋的區(qū)域可能包含不同地形特征，既有高程值變化不大的平坦區(qū)域，又有高程值差異很大的山丘和山峰地形，因此DEM 的規(guī)則格點(diǎn)數(shù)據(jù)結(jié)構(gòu)直接用于三維大地形建模，將會存在數(shù)據(jù)大量冗余從而影響地形繪制效率的問題?？紤]到三維地形建模中不規(guī)則格網(wǎng) （triangulated irregular network，TIN）具 有 數(shù) 據(jù) 冗 余少、細(xì)節(jié)特征刻畫充分，且支持層次細(xì)節(jié) （level of details，LOD）多分辨率模型提高效率等優(yōu)點(diǎn)，本文提出一種基于聚類和動態(tài)LOD 的三維地形建模方法，將聚類分析引入到對原始DEM 數(shù)據(jù)的地貌特征提取中，通過DEM 規(guī)則格網(wǎng)數(shù)據(jù)簡化為不規(guī)則點(diǎn)集構(gòu)建TIN 不規(guī)則格網(wǎng)，從而降低建模的數(shù)據(jù)量；同時(shí)在三維地形建模中基于視點(diǎn)移動采用局部優(yōu)化算法，并結(jié)合細(xì)化評價(jià)函數(shù)，構(gòu)建動態(tài)LOD 多分辨率層次模型，以達(dá)到精確反映地形地貌細(xì)節(jié)特征并提高繪制效率等目標(biāo)。

1 相關(guān)研究

國內(nèi)外學(xué)者對三維地形建模研究主要集中在數(shù)據(jù)簡化和繪制效率提高等方面。文獻(xiàn) ［2－4］分別從地貌特征角度考慮，提出了基于地理信息強(qiáng)度指數(shù)確定特征點(diǎn)的方法保證地貌特征結(jié)構(gòu)，通過計(jì)算頂點(diǎn)特征度的方法簡化網(wǎng)格，根據(jù)地勢特征提出了自適應(yīng)分割的簡化方法，從而構(gòu)建出具有真實(shí)感的地形。文獻(xiàn) ［5，6］對細(xì)分過程中的點(diǎn)，分別采用距離加權(quán)函數(shù)構(gòu)造新點(diǎn)實(shí)現(xiàn)模型細(xì)分，基于克里金插值法進(jìn)行反向多級細(xì)化。文獻(xiàn) ［7］通過改進(jìn) “離核”繪制機(jī)制，構(gòu)建可變地形，文獻(xiàn) ［8，9］分別通過平面曲率構(gòu)建層次模型，通過邊誤差的判定調(diào)整細(xì)節(jié)模型，文獻(xiàn)［10，11］分別通過建立不完全四叉樹結(jié)構(gòu)和Hilbert填充曲線提高繪制效率，通過改進(jìn)基于Bowyer－Watson增量插點(diǎn)內(nèi)核的Delaunay算法降低了地形網(wǎng)格規(guī)模，文獻(xiàn) ［12］提出了基于視點(diǎn)選擇的外存調(diào)度層次模型，提高了繪制效率。

由以上研究可知，為了保證簡化后的地形不發(fā)生變化，都將區(qū)域特征這一因素考慮進(jìn)來，如曲率、地勢等；為了提高繪制效率，都采用基于LOD 技術(shù)的思想，對數(shù)據(jù)進(jìn)行分塊處理，或通過改進(jìn)算法降低網(wǎng)格規(guī)模，或采用內(nèi)外存調(diào)度策略等。然而存在的不足是，對區(qū)域特征的量化計(jì)算都比較復(fù)雜，忽略了數(shù)據(jù)特征自身的相似性，對原始數(shù)據(jù)集和地貌特征之間沒有建立自動關(guān)聯(lián)；而分塊LOD 方法易產(chǎn)生塊間裂縫問題，基于外存的LOD 方法可能會存在調(diào)度效率問題等。針對以上存在的問題，本文提出一種基于聚類和動態(tài)LOD 的三維地形建模方法，首先對原始DEM 數(shù)據(jù)集進(jìn)行K－means聚類分析，將高程值數(shù)據(jù)集與地貌特征分類關(guān)聯(lián)在一起，實(shí)現(xiàn)客觀、無干預(yù)的區(qū)域特征描述；然后，在聚類分析得到的采樣點(diǎn)地貌特征附加屬性值基礎(chǔ)上，對原始DEM 數(shù)據(jù)進(jìn)行粗化處理，形成不規(guī)則點(diǎn)集，構(gòu)建Delaunay三角網(wǎng)；最后，在三維地形繪制的視點(diǎn)變化過程中，采用局 部 優(yōu) 化LOP （local optimization procedure）算法，并結(jié)合節(jié)點(diǎn)細(xì)化評價(jià)函數(shù)進(jìn)行有限域內(nèi)的三角形分裂，同時(shí)采用基于無偏估計(jì)的克里金 （Kriging）插值法來計(jì)算高程值以提高數(shù)據(jù)精度，從而實(shí)現(xiàn)了多分辨率層次模型，精確反映地貌細(xì)節(jié)特征并提高繪制效率。

2 基于K－means聚類和動態(tài)LOD的地形建模方法

本文提出的三維地形建模方法包括數(shù)據(jù)預(yù)處理、構(gòu)建不規(guī)則三角網(wǎng)和建立LOD 多分辨率層次細(xì)節(jié)模型等3個(gè)階段，如圖1所示。在數(shù)據(jù)預(yù)處理階段，對讀取的DEM 高程數(shù)據(jù)集進(jìn)行K－means聚類分析，在采樣點(diǎn)和地貌特征分類之間建立關(guān)聯(lián)。然后，根據(jù)每一個(gè)點(diǎn)的分類值，進(jìn)行原始數(shù)據(jù)集的粗化處理，建立不規(guī)則三角網(wǎng)。最后采用LOP算法進(jìn)行局部優(yōu)化處理并采用克里金法計(jì)算插入點(diǎn)的高程值，從而動態(tài)生成多分辨率地形模型。與通常的靜態(tài)生成LOD四叉樹結(jié)構(gòu)不同，本文的LOD 多分辨率層次細(xì)節(jié)模型是在三角形分裂的過程中動態(tài)生成的，并采用棧結(jié)構(gòu)表示。

圖1 地形建模流程

2.1 基于K－means的地貌聚類分析

地貌是指地面高低起伏的自然狀態(tài)，地貌特征的表達(dá)決定了構(gòu)建三維地形的真實(shí)度。地貌通常劃分為平原、丘嶺或山峰等類型，不同地貌細(xì)節(jié)程度差異較大，山峰因其海拔高度局部劇烈變化，細(xì)節(jié)特征比較豐富，而平原由于其相對比較平穩(wěn)，具有較少的細(xì)節(jié)特征，丘嶺則介于二者之間，因此可以根據(jù)建模區(qū)域的海拔高度 （相對海拔高度），很容易度量微觀區(qū)域的地貌特征。本文采用聚類分析方法的K－means法，該算法具有實(shí)現(xiàn)簡單，尤其是對大數(shù)據(jù)集執(zhí)行速度快的特點(diǎn)。通過K－means聚類分析方法，在高程值數(shù)據(jù)集合中尋找具有同類屬性的數(shù)據(jù)集合，那么每一類劃分中就反映了該區(qū)域的地貌特征。

K－means聚類方法是基于樣本間相似性度量的間接聚類方法，它把n個(gè)對象的集合分為K 簇，采用一個(gè)中心點(diǎn)的值來表示該分類的值，簇內(nèi)的相似度高，而簇間相似度低。設(shè)給定m 個(gè)樣本為｛x（1），…，x（m）｝，該算法過程如下：

步驟1 隨機(jī)初始化K 個(gè)質(zhì)心 （cluster centroids）為μ1，μ2，…，μk∈Rn；

步驟2 重復(fù)下面過程，直到J（c，μ）函數(shù)收斂。

（1）對于每一個(gè)樣本i，計(jì)算其屬于的類

（2）對于每一個(gè)類j，重新計(jì)算該類的質(zhì)心

其中，畸變函數(shù) （distortion function）為

畸變函數(shù)J 定義了樣本x（i）到對應(yīng)質(zhì)心c（i）的距離平方和，K－means收斂即是最小化J 函數(shù)的值。每一次調(diào)整都要做兩步操作，首先保持質(zhì)心不變，調(diào)整每個(gè)樣本的屬類得到J 函數(shù)的最小值；保持屬類不變，調(diào)整質(zhì)心得到J 函數(shù)的最小值。經(jīng)過兩個(gè)單調(diào)遞減過程反復(fù)處理，該函數(shù)值將達(dá)到最小，意味著μ 和c 同時(shí)收斂。K 是分類數(shù)，c（i）是樣本i所屬的分類。

根據(jù)地貌分類，本文將相應(yīng)DEM 高程數(shù)據(jù)代表的地貌劃分為高山、丘嶺和平原三大類，采用K－means聚類分析方法計(jì)算出每個(gè)分類的中心值。分別以S1 （平原），S2（丘嶺），S3 （高山）表示3類地貌，設(shè)每一分類的中心值分別為：δ1、δ2和δ3，現(xiàn)作如下定義：

定義1 對于任意采樣點(diǎn)pi的高程值h，存在一個(gè)閾值φj（j＝1，2，3），使︱h－δj︱＜φj，而不存在︱h－δm︱＜φm（m＝1，2，3且m?。絡(luò)）且︱h－δn︱＜φn （n＝1，2，3且n?。絡(luò)，n！＝m）成立，那么點(diǎn)pi∈Sj，則稱pi點(diǎn)是Sj地貌的。

定義2 當(dāng)pi∈Sj （j＝1，2，3）時(shí)，定義pi地貌屬性為j，記為C（pi）＝j(luò)。

例如，當(dāng)pi∈S2 時(shí)，稱pi是S2 地貌的，即丘嶺地貌；其C（pi）＝2，即該pi點(diǎn)的地貌屬性為2。

該算法能夠保證同一聚類中的點(diǎn)具有較高的相似性，而不同劃分中點(diǎn)的相似度較小，因此每一個(gè)集合中的點(diǎn)就描述了一類地貌特征。通過對高程值數(shù)據(jù)集的分類，為每一個(gè)采樣點(diǎn)關(guān)聯(lián)一個(gè)地貌特征分類屬性值。在粗化過程中可依據(jù)其微觀地貌特征不同，采取不同的策略實(shí)現(xiàn)模型數(shù)據(jù)的簡化，如S1區(qū)域則可以適當(dāng)刪除點(diǎn)，也滿足地形細(xì)節(jié)特征的表達(dá)，其它區(qū)域則可適當(dāng)簡化滿足細(xì)節(jié)表達(dá)要求。

2.2 網(wǎng)格模型粗化處理

通過對高程數(shù)據(jù)的聚類分析，規(guī)則網(wǎng)格中的每一個(gè)采樣點(diǎn)均可按照定義1和定義2，得出其所屬地形微觀區(qū)域特征，以及地貌屬性C（pi）的值。在此基礎(chǔ)上，對DEM 高程數(shù)據(jù)進(jìn)行簡化，即依據(jù)每個(gè)點(diǎn)的地貌特征分類屬性值，對原始數(shù)據(jù)集進(jìn)行粗化處理。粗化處理策略為剔除與鄰近點(diǎn)地貌屬性值相同的點(diǎn)。剔除點(diǎn)一般限于C（pi）＝1的地形區(qū)域點(diǎn)，即選擇平原區(qū)域采用粗化處理降低建模數(shù)據(jù)量。若精度要求較低，亦可對C（pi）＞1的區(qū)域點(diǎn)適當(dāng)粗化。

具體計(jì)算過程如下：設(shè)原始數(shù)據(jù)集為R，對其中的每個(gè)采樣點(diǎn)pi，分別計(jì)算與pi相鄰的上 （pt）、下 （pb）、左（pl）、右 （pr）4個(gè)點(diǎn)的地貌屬性C 值，若C（pi）＝1且與鄰近的4個(gè)點(diǎn)之一的地貌屬性值相同，則將當(dāng)前點(diǎn)pi剔除。粗化處理后的數(shù)據(jù)集記為R1，則此時(shí)R1中數(shù)據(jù)網(wǎng)格已不是規(guī)則結(jié)構(gòu)。調(diào)整閾值φ1、φ2、φ3，可以找出更多滿足定義1的點(diǎn)集屬于S1，即該粗化處理過程可以重復(fù)多次。每一次的處理數(shù)據(jù)集分別記為R2、R3……Rn，數(shù)據(jù)集將越來越小，數(shù)據(jù)冗余將降低。若按此方法調(diào)整C（pi）＞1的采樣點(diǎn)，則可進(jìn)一步簡化數(shù)據(jù)，但可能會丟失山丘或高山的地貌特征，所以在建立初級層次模型精度要求不高時(shí)可考慮調(diào)整C（pi）＞1的采樣點(diǎn)。由于粗化處理中保留的點(diǎn)不再具有規(guī)則網(wǎng)格特性，因此粗化處理后的數(shù)據(jù)集將構(gòu)成不規(guī)則點(diǎn)集。對形成的不規(guī)則點(diǎn)集構(gòu)建Delaunay 三角網(wǎng)，即可生成TIN 模型。

2.3 LOD層次細(xì)節(jié)模型的建立

在三維地形繪制中的視點(diǎn)變化過程中，隨著視點(diǎn)與地形的距離拉近，需要更高精度的高程數(shù)據(jù)，因此需要建立LOD 多分辨率層次細(xì)節(jié)模型。構(gòu)建LOD 多分辨率層次細(xì)節(jié)模型的過程如圖2所示。經(jīng)過粗化處理所構(gòu)建的不規(guī)則三角網(wǎng)即為層次模型LOD 的根，其所在的層次用0表示，其下一層用1表示，依此類推。由第i （i＝0，1，…）層向第i＋1層轉(zhuǎn)換的過程中，根據(jù)節(jié)點(diǎn)細(xì)化評價(jià)函數(shù)，對局部三角形進(jìn)行分裂，重新生成具有豐富細(xì)節(jié)的三角網(wǎng)，細(xì)化過程中采用克里金法確定新點(diǎn)的值，使局部區(qū)域更精確的展現(xiàn)出來。

圖2 層次細(xì)節(jié)模型建立過程

2.3.1 節(jié)點(diǎn)細(xì)化評價(jià)函數(shù)

三維地形是基于視點(diǎn)進(jìn)行區(qū)域繪制的，在視點(diǎn)變化過程中，視點(diǎn)與地形距離拉近，更多地形細(xì)節(jié)將展現(xiàn)在視野中。而在視點(diǎn)距模型由遠(yuǎn)到近的過程中，低分辨率的模型需要逐層細(xì)化，滿足視覺要求。因此，需要根據(jù)地貌細(xì)節(jié)特征來進(jìn)行局部地形的優(yōu)化。局部優(yōu)化算法通常依據(jù)節(jié)點(diǎn)細(xì)化評價(jià)函數(shù)來進(jìn)行。多數(shù)情況下節(jié)點(diǎn)細(xì)化都是針對規(guī)則網(wǎng)格的，其節(jié)點(diǎn)細(xì)化評價(jià)函數(shù)也主要針對常用的LOD 四叉樹結(jié)構(gòu)，對節(jié)點(diǎn)細(xì)化評價(jià)準(zhǔn)則的定義分別考慮了視距、地形的特征及該區(qū)域的能量函數(shù)等。而本文是基于不規(guī)則格網(wǎng)的細(xì)分，上述評價(jià)函數(shù)不再適用。因此本文考慮不規(guī)則網(wǎng)格特點(diǎn)，考慮地貌屬性值、視距及不規(guī)則地形區(qū)域等要素，定義節(jié)點(diǎn)細(xì)化評價(jià)函數(shù)F如式 （4）所示

式中：C（pi）——三角形3 個(gè)點(diǎn)地貌特征屬性平均值，l——三角形距視點(diǎn)的距離，d——三角形地塊的最大邊長，在漫游的過程中根據(jù)觀察者視點(diǎn)位置移動實(shí)時(shí)計(jì)算更新。

節(jié)點(diǎn)細(xì)化評價(jià)函數(shù)給出了進(jìn)行三角型分裂操作的條件，當(dāng)F＜1時(shí)，對三角形進(jìn)行分裂操作；當(dāng)F≥1時(shí)，該三角形僅進(jìn)行繪制，不進(jìn)行細(xì)分操作。

2.3.2 局部優(yōu)化算法和三角形分裂

（1）局部優(yōu)化算法

不規(guī)則Delaunay三角網(wǎng)中的每一個(gè)三角形均滿足空外接圓的性質(zhì)，而當(dāng)構(gòu)建層次LOD 模型時(shí)，當(dāng)前層次中的一系列三角形需要分裂，構(gòu)成有豐富細(xì)節(jié)的三角網(wǎng)，將會出現(xiàn)三角形不再滿足空外接圓性質(zhì)的情況。因此需要進(jìn)行局部優(yōu)化處理。本文采用Lawson設(shè)計(jì)的局部優(yōu)化算法對已有的三角形進(jìn)行分裂操作［13］，算法基本原理如圖3所示。

圖3 局部優(yōu)化

圖4 三角形分裂

圖4中，若ABC 是待拆分的三角形，因A、B、C 是原始采樣點(diǎn)，在三角形ABC 內(nèi)必包含若干剔除點(diǎn)，根據(jù)點(diǎn)的坐標(biāo)數(shù)量關(guān)系可以在該三角形內(nèi)還原出一個(gè)點(diǎn)O，點(diǎn)O分別與點(diǎn)A、B、C 連接形成3 個(gè)新三角形。根據(jù)LOP 局部優(yōu)化原理，對每一個(gè)新三角形進(jìn)行局部優(yōu)化處理。如AOB，考察與AB 共邊的兩個(gè)三角形是否滿足空外接圓準(zhǔn)則，不滿足則調(diào)整與AOBG 四邊形的對角線為OG，再遞歸調(diào)整與AOG 共邊為AG 組成的四邊形、與OBG 共邊為BG的四邊形；其余三角形做相同調(diào)整操作。經(jīng)過有限次局部調(diào)整，即可形成下一層的Delaunay三角網(wǎng)。

2.3.3 相關(guān)數(shù)據(jù)結(jié)構(gòu)及操作

為了便于層次模型建立，本文采用棧結(jié)構(gòu)存儲LOD 細(xì)節(jié)層次模型，定義以下數(shù)據(jù)結(jié)構(gòu)。

圖3 （a）中ADC 和AEC 是一個(gè)Delaunay三角網(wǎng)，B是插入三角形內(nèi)部的點(diǎn)，可以看出ADC 空外接圓性質(zhì)被破壞。根據(jù)局部優(yōu)化算法調(diào)整ABCD 四邊形的對角線AC→BD，此時(shí)四邊形的兩個(gè)三角形重新構(gòu)成Delaunay三角網(wǎng)。

（2）三角形分裂

當(dāng)計(jì)算出的節(jié)點(diǎn)細(xì)化評價(jià)函數(shù)F＜1時(shí)，需進(jìn)行三角型分裂。圖4是一個(gè)三角形分裂過程。

設(shè)置兩個(gè)棧tris＿add和tris＿delete，分別保存新增三角形和刪除的三角形。三角形分裂操作過程中，使用LOP（）優(yōu)化函數(shù)，對新產(chǎn)生的三角形遞歸地優(yōu)化為Delaunay三角網(wǎng)。在此過程中，上一層的三角形被刪除的同時(shí)，需記錄在棧tris＿delete中，目的是方便回溯，快速恢復(fù)上一層的模型；同樣，新增加的三角形也記錄在tris＿add棧中。

2.3.4 克里金插值確定分裂點(diǎn)高程值

當(dāng)三角形在視點(diǎn)區(qū)域內(nèi)進(jìn)行分裂時(shí)，需要確定分裂點(diǎn)的高程值。本文采用基于無偏估計(jì)的克里金 （Kriging）法計(jì)算高程值，該方法原理參見文獻(xiàn)［14］。插值公式如下所示

式中：Z（x0）——待估算值，xi（i＝1，…，n）為x0周圍的區(qū)域觀測點(diǎn)，z（xi）——觀測值，λi是區(qū)域化變量z（xi）的權(quán)重，用來表示樣本的觀測值z（xi）對估算值Z （x0）的貢獻(xiàn)程度。系數(shù)λi由式 （6）所示方程組求得

式中：γ（xi，xj）是Z 在采樣點(diǎn)xi和xj之間的半方差；γ（xi，x0）是Z 在采樣點(diǎn)xi和估算點(diǎn)x0之間的半方差；φ是極小化處理時(shí)的拉格朗日乘數(shù)。由式 （6）可組成n＋1階線性方程組，求解式 （6）所示線性方程組可得n 個(gè)加權(quán)系數(shù)λi和拉格朗日算子φ。求得各λi值和φ 值后，由式（5）便可得出x0點(diǎn)的估值Z（x0）。

3 實(shí)驗(yàn)與分析

為檢驗(yàn)本文方法的有效性，從數(shù)據(jù)簡化率、地形特征保持和層次化模型的繪圖效率三方面開展實(shí)驗(yàn)。所有實(shí)驗(yàn)數(shù)據(jù)均采用SRTM 高程數(shù)據(jù)作為制作地形數(shù)據(jù)來源，它是由等間距的規(guī)則網(wǎng)格構(gòu)成，分辨率為90m （0.00083333°×0.00083333°）。在 建 模 中，采 用Visual C＋＋2010 和OpenGL為基礎(chǔ)平臺，運(yùn)行環(huán)境為Windows 7／32位，處理器Intel Pentium Dual Cpu1.6GHZ，顯卡1GB，內(nèi)存2GB，硬盤120GB。

3.1 不同地形簡化率對比實(shí)驗(yàn)

選取江蘇中部 （平原多，山地少）、河南西部 （山區(qū)多，平原少）、云南西南部 （幾乎全是山脈），進(jìn)行對比實(shí)驗(yàn)。分別選取128×128、256×256、512×512、1024×1024、2048×2048大小的地塊進(jìn)行測試，其中簡化率定義為：（N－P）／N，P 為參與建模的采樣點(diǎn)數(shù)，N 為原始數(shù)據(jù)集采樣點(diǎn)數(shù)。表1給出了對不同地形的數(shù)據(jù)簡化率。

表1 不同地形類型本文方法的簡化率

由實(shí)驗(yàn)結(jié)果可知，本文方法對以平原為主區(qū)域的數(shù)據(jù)簡化率最高，表明該區(qū)域數(shù)據(jù)冗余度高，進(jìn)行數(shù)據(jù)簡化效果最為明顯。而對于山區(qū)和平原混合的地形類型，簡化率低于平原為主的區(qū)域，但整體仍然較高的簡化率，例如河南西南部地區(qū)在2048×2048地塊情形下簡化率可達(dá)90%，表明本文方法對于該類地形仍有較好的簡化效果，這是因?yàn)楸痉椒ㄖ锌紤]了微觀區(qū)域的特征，避免了地貌特征點(diǎn)被簡化掉。對于山地相對集中的區(qū)域，地貌特征比較復(fù)雜，數(shù)據(jù)冗余度最小，但本方法對數(shù)據(jù)的簡化也有一定效果，如云南西南部山區(qū)在2048×2048地塊情形下簡化率仍可達(dá)77%。對原始數(shù)據(jù)集的簡化可提高三維地形建模效率。

3.2 地形特征保持測試

為了測試本文方法在不同簡化率下地形特征的保持能力，選取具有明顯地貌特征的區(qū)域進(jìn)行對比實(shí)驗(yàn)。所選區(qū)域?yàn)榻?jīng)緯度起始點(diǎn)為112.4°、30.8°的200×300 的局部區(qū)域，位于河南省的西南部。圖5是實(shí)驗(yàn)結(jié)果，給出了原始地形和該區(qū)域不同簡化率下地形的三角網(wǎng)模型對比。圖5（a）為原始地形三角網(wǎng)模型，圖5 （b）、圖5 （c）、圖5（d）對滿足C（pi）＝1的采樣點(diǎn)進(jìn)行了粗化處理所得到的簡化率分別為82%、89%、92%的地形三角網(wǎng)模型。實(shí)驗(yàn)結(jié)果表明，3種簡化率下的地形都保留了較多的地貌特征，并且隨著簡化率的提高，主要地貌特征依然能夠很好的保持。例如，圖5 （c）為89%簡化率的情形，山峰特征保持得很好，山丘特征也被較好的保持了。但92%簡化率情形下，山峰特征仍保持得很好，但山丘特征的保持較差。表明本文算法在山峰細(xì)節(jié)特征上處理較好，而山丘細(xì)節(jié)特征處理上仍有優(yōu)化之處。另外，為了保持邊界輪廓，避免在粗化中由于過度簡化造成地形輪廓丟失，對邊界情況進(jìn)行了特殊處理，限制簡化采樣點(diǎn)。

圖5 原始地形和不同簡化率地形三角網(wǎng)模型對比

3.3 三維地形建模效率測試

為了測試本文方法所生成的LOD 多分辨率層次化細(xì)節(jié)模型的繪圖效率，將本文方法與經(jīng)典基于二叉樹的ROAM算法、以及未簡化時(shí) （即直接使用高程數(shù)據(jù)進(jìn)行三維地形生成）的繪制效率進(jìn)行對比。ROAM 算法的核心是基于等腰直角三角形、通過二叉樹遞歸分解來構(gòu)建層次模型。實(shí)驗(yàn)區(qū)域數(shù)據(jù)塊大小分別為128×128、256×256、512×512、1024×1024、2048×2048，圖6為3種方法的繪制效率對比結(jié)果。

三維地形建模效率以每秒繪制的幀數(shù) （frame per second，F(xiàn)PS）來度量。圖中橫軸為地形數(shù)據(jù)塊大小，縱軸為FPS。由圖6可見，當(dāng)數(shù)據(jù)量超過500×500時(shí)，未簡化的情形下，進(jìn)行漫游時(shí)出現(xiàn)明顯停滯。而本文方法通過網(wǎng)格簡化和視域選擇繪制的方法，在大地形時(shí)仍能實(shí)現(xiàn)流暢漫游，傳統(tǒng)基于二叉樹ROAM 算法［15］相比，效率有所提升。實(shí)驗(yàn)說明了對大場景的規(guī)則網(wǎng)格數(shù)據(jù)建模時(shí)，對數(shù)據(jù)簡化可以提升性能，通過局部三角形的分裂細(xì)化，并保存相鄰層次間的數(shù)據(jù)，也節(jié)約了計(jì)算時(shí)間，避免重復(fù)計(jì)算從而提升繪圖效率。

圖6 三維地形建模效率測試

4 結(jié)束語

在大地形建模過程中，地形模型的簡化處理不但能降低程序的復(fù)雜性，而且還可提高軟件的交互效率。本文通過采用K－means聚類分析法，對原始數(shù)據(jù)集合進(jìn)行分類，從而發(fā)現(xiàn)數(shù)據(jù)的相似性，實(shí)現(xiàn)了地貌特征的客觀、自動分類，完成了采樣點(diǎn)與地貌特征屬性的關(guān)聯(lián)。在此基礎(chǔ)上，實(shí)現(xiàn)了微觀區(qū)域中不同地貌類型的粗化，降低了建模的數(shù)據(jù)量。同時(shí)，在滿足精度的要求下改變閾值設(shè)置，還可以進(jìn)一步對數(shù)據(jù)進(jìn)行簡化。在LOD 層次調(diào)整的過程中，根據(jù)細(xì)化評價(jià)函數(shù)和局部優(yōu)化算法實(shí)現(xiàn)了層次模型中局部三角形的調(diào)整，降低了高分辨率下三角形分裂操作帶來的時(shí)間消耗，提高了模型更新性能。

［1］TANG Guo’an，LIU Xuejun，LU Guonian.Digital elevation model tutorial［M］.2nd ed.Beijing：Science Press，2010：11－12 （in Chinese）.［湯國安，劉學(xué)軍，閭國年.數(shù)字高程模型教程［M］.2版.北京：科學(xué)出版社，2010：11－12.］

［2］DONG Youfu，TANG Guo’an.Research on terrain simplification using terrain significance information index from digital elevation models［J］.Journal of Wuhan University（Information Science Edition），2013，38 （3）：353－357（in Chinese）.［董有福，湯國安.利用地形信息強(qiáng)度進(jìn)行DEM 地形簡化研究 ［J］.武漢大學(xué)學(xué)報(bào)（信息科學(xué)版），2013，38 （3）：353－357.］

［3］HUA Haiyang，ZHAO Huaici.Mesh simplification algorithm for terrain model based on feature degree［J］.Journal of Computer－Aided Design ＆ Computer Graphics，2011，23 （4）：594－599 （in Chinese）.［花海洋，趙懷慈.保持地形特征的網(wǎng)格模型簡化算法 ［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2011，23 （4）：594－599.］

［4］ZHANG Huijie，LU Yinghua，LIU Shuhua.A terrain model simplification method based on adaptive areas division ［J］.Journal of Computer Research and Development，2010，47（1）：53－61 （in Chinese）.［張慧杰，呂英華，劉淑華.一種基于自適應(yīng)區(qū)域分割的地形模型簡化方法 ［J］.計(jì)算機(jī)研究與發(fā)展，2010，47 （1）：53－61.］

［5］FU Yanqiang，HAN Huijian.Three－dimensional terrain modeling based on regional feature distance weighting ［J］.Journal of Computer Applications，2012，32 （12）：3377－3380 （in Chinese）.［付延強(qiáng)，韓慧健.基于區(qū)域特征距離加權(quán)的三維地形建模方法［J］.計(jì)算機(jī)應(yīng)用，2012，32 （12）：3377－3380.］

［6］CHEN Xichao，NING Yu.Research on Kriging－based multilevel backward refinement of dynamic terrain modeling ［J］.Computer Engineering and Applications，2013，49 （9）：171－175 （in Chinese）.［陳錫超，寧芋.基于Kriging方法的動態(tài)地形反向多級細(xì)化研究［J］.計(jì)算機(jī)工程與應(yīng)用，2013，49 （9）： 171－175.］

［7］ William E Brandstetter III，Joseph D Mahsman，Cody J White，et al.Multi－resolution deformation in out－of－core terrain rendering ［J］.International Journal of Computers and Their Applications，2011，18 （4）：262－272.

［8］Zarrabeitia LA，Hernández Mederos V.Multiresolution terrain modeling using level curve information ［J］.Journal of Computational and Applied Mathematics，2013，240 （3）：87－98.

［9］Narcís Coll，MaritéGuerrieri.Adaptive simplification of huge sets of terrain grid data for geosciences applications［J］.Journal of Computational and Applied Mathematics，2011，236（6）：1410－1422.

［10］TANG Guiwen，CHEN Xuexia，REN Chao.Research of key technique on virtual reality application based on view－dependent LOD quad tree algorithm ［J］.Computer Engineering and Design，2008，29 （4）：928－930 （in Chinese）. ［唐桂文，陳學(xué)霞，任超.視點(diǎn)相關(guān)LOD四叉樹算法在虛擬現(xiàn)實(shí)應(yīng)用中的關(guān)鍵技術(shù)研究［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2008，29 （4）：928－930.］

［11］HUANG Zhengke，CHEN Jianjun，ZHENG Yao.Triangulated irregular network based chunk gridding algorithm for terrain rendering ［J］.Journal of Zhejiang University （Engineering Science），2009，23 （10）：1939－1943 （in Chinese）.［黃爭舸，陳建軍，鄭耀.基于不規(guī)則三角網(wǎng)的分塊地形網(wǎng)格生成算法 ［J］.浙江大學(xué)學(xué)報(bào) （工學(xué)版），2009，23 （10）：1939－1943.］

［12］FENG Jie，ZHA Hongbin.Simplification and view－dependent LOD control for large 3D mesh models［J］.Journal of Computer－Aided Design ＆ Computer Graphics，2006，18 （2）：186－193 （in Chinese）. ［馮潔，查紅彬.大型三維網(wǎng)格模型的簡化及基于視點(diǎn)的LOD控制 ［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2006，18 （2）：186－193.］

［13］XIE Zengguang.Divided－and－conquer algorithm for constructing Delaunay triangulation of planar points ［J］.Computer Engineering and Design，2012，33 （7）：2652－2658 （in Chinese）. ［謝增廣.平面點(diǎn)集Delaunay三角剖分的分治算法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2012，33 （7）：2652－2658.］

［14］ZHOU Chenghu，PEI Tao.Principles of GIS spatial analysis［M］.Beijing：Science Press，2011：161－182 （in Chinese）.［周成虎，裴韜.地理信息系統(tǒng)空間分析原理 ［M］.北京：科學(xué)出版社，2011：161－182.］

［15］ZHAO Huizhong.Research on theory and visual application of ROAM algorithm ［J］.Geometrics ＆ Spatial Information Technology，2010，33 （5）：124－129 （in Chinese）. ［趙 慧中.ROAM 算法原理及其可視化應(yīng)用研究 ［J］.測繪與空間地理信息，2010，33 （5）：124－129.］