宋偉華，譚衢霖，夏 宇，祝 清

（1.北京交通大學(xué) 土木建筑工程學(xué)院，北京 100044；2.北京交通大學(xué) 線路工程勘測空間信息研究所，北京 100044）

三維地形建模和可視化是在計算機(jī)上對地形數(shù)據(jù)進(jìn)行三維顯示、模擬仿真、簡化、多分辨率表達(dá)和網(wǎng)絡(luò)傳輸?shù)囊豁椉夹g(shù)，它涉及到測繪學(xué)、現(xiàn)代數(shù)學(xué)、計算機(jī)三維圖形學(xué)、計算幾何、地理信息系統(tǒng)、虛擬現(xiàn)實、科學(xué)計算可視化、計算機(jī)網(wǎng)絡(luò)等眾多學(xué)科領(lǐng)域[1]。利用計算機(jī)三維可視化技術(shù)，將遙感影像和數(shù)字高程模型（DEM，Digital Elevation Model）相疊加，可以建立逼真的三維地形環(huán)境[2]。

在三維地形建模和可視化研究方面，文獻(xiàn)[3]研究了基于三角形網(wǎng)格的地形建模的基本理論和方法,包括規(guī)則數(shù)據(jù)的三角網(wǎng)生成以及不規(guī)則三角網(wǎng)（TIN，Triangulated Irregular Network）的生成算法；文獻(xiàn)[4]應(yīng)用遙感影像與DEM數(shù)據(jù)，基于Infraworks平臺建立了某線路段地形、構(gòu)造物、沿線附屬設(shè)施等三維可視化模型；文獻(xiàn)[5]通過層次細(xì)節(jié)技術(shù)和基于網(wǎng)格的模型簡化技術(shù)對三維地形建模進(jìn)行簡化，并且對該技術(shù)進(jìn)行了相應(yīng)的改善，從而能夠更好地實現(xiàn)三維地形建模簡化技術(shù)的應(yīng)用。

為了滿足實時三維繪制與漫游的需求，減少數(shù)據(jù)量，且保證數(shù)據(jù)的必要精度，本文主要針對三維地形空間數(shù)據(jù)的海量特性，試驗了三維地形構(gòu)建的2種常用表達(dá)模型，并對其輕量化處理方法進(jìn)行了研究。

1 DEM數(shù)據(jù)

1.1 DEM數(shù)據(jù)概述

DEM是用于構(gòu)建線路工程三維地形的重要信息之一，它描述了地面高程信息，是對地形表面形態(tài)的離散化數(shù)字表達(dá)[6]。線路是一個狹長帶狀構(gòu)造物，三維地形建模僅需線路中線兩側(cè)一定寬度內(nèi)的DEM數(shù)據(jù)，可根據(jù)直線、曲線、多邊形等不同的提取方法來提取所需范圍內(nèi)的地形模型數(shù)據(jù)。

1.2 DEM數(shù)據(jù)獲取

DEM的獲取方法主要有地面測量、航空攝影測量、衛(wèi)星立體測圖、衛(wèi)星定位測量、采集現(xiàn)有地形圖、干涉雷達(dá)等[7]。DEM獲取方式如表1所示。通常可直接獲取的DEM數(shù)據(jù)源如表2所示。

表1 DEM獲取方式列表

表2 DEM數(shù)據(jù)來源列表

2 地形模型構(gòu)建及輕量化

2.1 地形模型表達(dá)

目前，用于線路設(shè)計的數(shù)字地形模型主要有方格網(wǎng)式、三角網(wǎng)式、離散式、分塊離散型和魚骨式模型[8]。其中應(yīng)用最為廣泛的是方格網(wǎng)式和三角網(wǎng)式。

方格網(wǎng)數(shù)字地形模型通常被分割為規(guī)則的正方形、矩形或三角形等網(wǎng)格，規(guī)則網(wǎng)格將區(qū)域空間切分為規(guī)則的格網(wǎng)單元，每個格網(wǎng)單元存儲了相應(yīng)的高程值，如圖1 a所示。方格網(wǎng)數(shù)字地面模型（DTM，Digital Terrain Model）適合數(shù)據(jù)的存儲、分割、合并、內(nèi)插，便于計算區(qū)域內(nèi)等高線、坡度、坡向、山坡陰影等地理要素，適用于分布較為規(guī)則的地形環(huán)境，在線路設(shè)計領(lǐng)域已成功運用于狹長窄帶線路優(yōu)化設(shè)計之中。但是，方格網(wǎng)DTM數(shù)據(jù)的分辨率單一，不能精確表示地形的結(jié)構(gòu)細(xì)部，難以表達(dá)復(fù)雜地形的突變現(xiàn)象，在地形平坦的區(qū)域存在大量的數(shù)據(jù)冗余，造成數(shù)據(jù)量過于龐大，給數(shù)據(jù)信息管理帶來諸多困難。

TIN原始數(shù)據(jù)點間無任何聯(lián)系且隨機(jī)分布，將地形點覆蓋在數(shù)字模型區(qū)域上的三角形的各頂點，利用分布不規(guī)則的數(shù)據(jù)生成連續(xù)的三角面來逼近地形表面，高程由該點所處的三角形區(qū)域確定，如圖1 b所示。TIN沒有改變原始數(shù)據(jù)點，其精度高，便于表征特征性、斷裂線、邊界線，既適用于規(guī)則分布的數(shù)據(jù)，也適用于不規(guī)則分布的數(shù)據(jù)。

圖1 數(shù)字地形模型

本文分別利用DTM和TIN數(shù)字模型建立三維地形曲面，地形曲面數(shù)據(jù)對比如表3所示。對比發(fā)現(xiàn)，主要曲面參數(shù)（如最小高程、最大高程）沒有區(qū)別，但在最大坡率上出現(xiàn)了較大的變動。TIN模型能用更少的數(shù)據(jù)來精確地表示含有大量斷裂線和構(gòu)造線的地形表面，更精確合理地表達(dá)復(fù)雜地表形態(tài)，從而使建立的三維地形環(huán)境更為精確。故本文選用TIN進(jìn)行三維地形環(huán)境建模。

2.2 Delaunay三角剖分

2.2.1 Delaunay三角剖分性質(zhì)

如何把離散集合剖分成不均勻的三角形網(wǎng)格，即散點集的三角形剖分問題，是建立三維地形環(huán)境的關(guān)鍵[9-10]。實際中運用最多的三角剖分方法是Delaunay三角剖分法。Delaunay三角剖分法有2個重要性質(zhì)。

表3 不同數(shù)字地形曲面參數(shù)對比列表

（1）空外接圓性質(zhì)

Delaunay三角網(wǎng)是一系列相連但不重疊的三角形的集合，在Delaunay三角網(wǎng)中任一三角形的外接圓范圍內(nèi)不會有其他點存在。如圖2所示，設(shè)AB邊是三角形ABC和三角形ABD的公共邊。若D點不落在三角形ABC的外接圓內(nèi)，則稱AB邊是局部最優(yōu)化的，即該三角形具有空外接圓特性。當(dāng)三角形不具備外接圓特性時，則交換對角線生成另一種三角劃分，使得三角形具有空外接圓特性，該過程稱為局部優(yōu)化過程（LOP ，Local Optimization Procedure）。

圖2 局部優(yōu)化過程示意圖

（2）最大化最小角特性

在散點集可能形成的三角剖分中，Delaunay三角剖分所形成的三角網(wǎng)的最小角最大，是最接近于規(guī)則化的的三角網(wǎng)。其任意2個相鄰的三角形構(gòu)成的凸四邊形，在相互交換對角線后，6個內(nèi)角的最小角不再增大，如圖3所示。

圖3 最大化最小角示意圖

2.2.2 Delaunay三角網(wǎng)生成算法

根據(jù)構(gòu)建TIN算法的實現(xiàn)過程，可將Delaunay三角網(wǎng)生成算法劃分為分治算法、三角網(wǎng)生長法和逐點插入法[11-12]。分治算法將點集劃分到足夠小，使其易于生成三角網(wǎng)，然后把局部三角網(wǎng)合并生成最終的三角網(wǎng)，劃分過程中，用LOP算法保證Delaunay三角網(wǎng)的構(gòu)建；三角形生長算法先找出點集中相距最短的2點，將其連接成為一條Delaunay邊，然后按判別法搜尋包含此邊的另一端點，并依次處理所有新生成的邊；逐點插入法先在包含數(shù)據(jù)點的一個多邊形中建立初始三角網(wǎng)，再將剩余的點逐一插入，用LOP算法構(gòu)建Delaunay三角網(wǎng)。

三角網(wǎng)生長算法時間效率低下，目前較少采用；分治算法復(fù)雜度較優(yōu)，但需要占據(jù)較大的內(nèi)存空間且預(yù)處理和優(yōu)化工作量較大；逐點插入法實現(xiàn)簡單、占用內(nèi)存小，但時間復(fù)雜度差、運行速度慢。由于線路工程里程較長、方案較多，為保證精度導(dǎo)致所取離散點數(shù)目較多，需對數(shù)字地形模型維護(hù)和更新等原因，在綜合分析各算法優(yōu)劣的基礎(chǔ)上，采用內(nèi)存占用較小的逐點插入算法，算法流程如下：

（1）建立初始三角網(wǎng)，如圖4所示，給定點集的包容盒 Box（Xmin，Xmax，Ymin，Ymax）并將其剖分為2個初始三角形A，其中，Xmin為數(shù)據(jù)點X坐標(biāo)極小值；Xmax為數(shù)據(jù)點x坐標(biāo)極大值；Ymin為數(shù)據(jù)點y坐標(biāo)極小值；Ymax為數(shù)據(jù)點y坐標(biāo)極大值。

圖4 初始三角形剖分示意圖

（2）從點集中取出一點P，在已建立的三角網(wǎng)中找到包含該點的三角形進(jìn)行定位，如圖5 a所示。

（3）在包含P點的三角形拓?fù)潢P(guān)系中，利用空外接圓性質(zhì)找出外接圓包含的三角形集合，其外邊界即為要確定的影響域，如圖5 b所示。設(shè)三角形abc，如圖6所示，按逆時針排列，空外接圓性質(zhì)判斷按公式（1）計算。若F＜0，則d在外接圓內(nèi)側(cè)；若F＞0，則d在外接圓外側(cè)；若F=0，則d在外接圓上。

圖5 插入P點重構(gòu)三角網(wǎng)過程圖

圖6 空外接圓判斷示意圖

其中，ax、ay、bx、by、cx、cy、dx，dy分別為數(shù)據(jù)點a、b、c、d的橫縱坐標(biāo)。

（4）依據(jù)Delaunay性質(zhì)在影響域內(nèi)進(jìn)行三角網(wǎng)重構(gòu)，將影響域各邊界交點與插入點順次連接，即得插入點后重構(gòu)的三角網(wǎng)，如圖5 c。

（5）待所有點內(nèi)插完后，刪除邊界冗余三角形。將獲取的DEM數(shù)據(jù)根據(jù)Delaunay三角剖分算法構(gòu)建TIN，建立三維地形曲面模擬地形空間分布。圖7為試驗區(qū)域的TIN模型，圖8為三維地形曲面模型。

圖7 線路走廊帶TIN模型示意圖

圖8 線路走廊帶三維地形曲面模型示意圖

2.3 數(shù)據(jù)輕量化

由于線路具有工程距離長、覆蓋范圍廣的特點，導(dǎo)致根據(jù)Delaunay三角剖分建立的三維地形曲面數(shù)據(jù)量較大。臃腫的三維曲面數(shù)據(jù)造成系統(tǒng)運行緩慢，為后續(xù)的線路設(shè)計帶來困難。因此，需要對海量的數(shù)據(jù)進(jìn)行簡化處理來優(yōu)化曲面性能，在保證地形曲面精度的同時減少數(shù)據(jù)量的冗余。數(shù)據(jù)輕量化主要有邊緣收縮法和點刪除法2種方式。

2.3.1 邊緣收縮法

邊緣收縮法使三角形的一條邊收縮到單一點，每次邊緣收縮可以刪除一個點，同時減少2個三角形。設(shè)每個三角形平面方程為：

其中，a，b，c，d為三角形平面方程的系數(shù)。

定義p=[a b c d]T，則每個三角形的矩陣誤差為：

頂點v的誤差矩陣為環(huán)繞網(wǎng)格頂點周圍三角面片的平均矩陣誤差∑Q/n，n為環(huán)繞在網(wǎng)格頂點v周圍的三角面片的個數(shù)，即誤差為：

其中，v為三角形收縮邊的頂點坐標(biāo)。

三角形收縮邊緣的頂點v1和v2合并到新頂點v，其邊緣收縮的誤差為：

誤差最小點即為新頂點，同時刪除誤差較大的點，方法過程如圖9所示。

圖9 邊緣收縮簡化示意圖

2.3.2 點刪除法

點刪除法按照簡化比例進(jìn)行曲面點的選擇和刪除，刪除三角網(wǎng)格中，在高程容許誤差范圍內(nèi)，且不會導(dǎo)致拓?fù)浣Y(jié)構(gòu)改變的點。高程容許誤差范圍計算公式為：

其中，h為初始高程；h'為刪除點后的高程；ε為容許誤差。

同時對由此刪除操作引起的空洞進(jìn)行三角化再構(gòu)建TIN，方法過程如圖10所示。

圖10 點刪除簡化示意圖

2.3.3 方法對比

基于原始DEM數(shù)據(jù)構(gòu)建地形曲面，分別采用邊緣收縮法和點刪除法對原始地形曲面進(jìn)行簡化，2種方法刪除點數(shù)所占百分比均為50%，詳細(xì)參數(shù)如表4所示。由表4中參數(shù)對比分析可知，利用邊緣收縮法簡化曲面后，曲面的最大坡率、最小三角網(wǎng)面積等參數(shù)出現(xiàn)了較大波動，而利用點刪除法對曲面可進(jìn)行有效地簡化，且曲面參數(shù)未發(fā)生明顯改變，失真較小。

表4 三維曲面不同優(yōu)化方式參數(shù)對比列表

3 結(jié)束語

隨著長大線路工程數(shù)字信息化程度的提高，項目建設(shè)過程中形成的數(shù)據(jù)種類越來越多，數(shù)據(jù)量越來越龐大。研究線路工程三維模型的構(gòu)建方法及有效地輕量化處理方式是線路工程數(shù)字信息化變革的技術(shù)挑戰(zhàn)之一。本文針對三維地形空間數(shù)據(jù)的海量特性，通過Delaunay逐點插入算法構(gòu)建TIN模型，實驗證明該算法能夠用更少的數(shù)據(jù)來合理地表達(dá)復(fù)雜地表形態(tài)，更適用于線路工程三維地形建模；對比了2種數(shù)據(jù)輕量化方法，試驗參數(shù)對比表明，點刪除法對三維地形模型的簡化更為有效。