溫 永 寧，閭 囯 年，陳 旻

矢量空間數(shù)據(jù)漸進(jìn)傳輸研究進(jìn)展

溫 永 寧1，2，閭 囯 年1，陳 旻3

（1.南京師范大學(xué)虛擬地理環(huán)境教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210046;2.蘇州工業(yè)園區(qū)測(cè)繪有限公司，江蘇 蘇州 215021;3.香港中文大學(xué)太空與地球信息科學(xué)研究所，香港 沙田）

漸進(jìn)傳輸被認(rèn)為是解決目前海量空間數(shù)據(jù)傳輸與實(shí)時(shí)用戶體驗(yàn)之間矛盾的有效方法。柵格數(shù)據(jù)漸進(jìn)傳輸?shù)南嚓P(guān)研究比較成熟，但矢量數(shù)據(jù)的漸進(jìn)傳輸理論和技術(shù)還存在問(wèn)題。為了推進(jìn)矢量數(shù)據(jù)漸進(jìn)傳輸?shù)南嚓P(guān)研究，該文對(duì)與矢量數(shù)據(jù)漸進(jìn)傳輸密切相關(guān)的二維矢量數(shù)據(jù)、三維表面模型兩種數(shù)據(jù)的多分辨率表達(dá)和漸進(jìn)傳輸?shù)难芯楷F(xiàn)狀進(jìn)行歸納與總結(jié)，指出相關(guān)研究的發(fā)展方向，為海量空間數(shù)據(jù)適用于分布式網(wǎng)絡(luò)傳輸提供參考依據(jù)。

空間數(shù)據(jù);矢量數(shù)據(jù);漸進(jìn)傳輸

0 引言

傳統(tǒng)意義上，空間數(shù)據(jù)模型可分為矢量和柵格兩種;按照數(shù)據(jù)生產(chǎn)的目標(biāo)，又可分為4D產(chǎn)品，即數(shù)字線畫(huà)圖（DLG）、數(shù)字正射影像（DOM）、數(shù)字高程模型（DEM）和數(shù)字柵格地圖（DRG）。如何協(xié)調(diào)計(jì)算機(jī)有限的內(nèi)存、帶寬與海量空間數(shù)據(jù)傳輸之間的矛盾是當(dāng)前GIS研究的重要課題。雖然空間數(shù)據(jù)的類型不同，但在解決海量數(shù)據(jù)的應(yīng)用與傳輸問(wèn)題上存在一些通用方法：1）對(duì)數(shù)據(jù)進(jìn)行處理，建立數(shù)據(jù)的多分辨率表達(dá)，根據(jù)不同顯示需求所采用的比例尺或分辨率，傳遞相應(yīng)分辨率的數(shù)據(jù)。2）采用數(shù)據(jù)漸進(jìn)傳輸?shù)姆椒?，即如果高分辨率的?shù)據(jù)可以通過(guò)低分辨率數(shù)據(jù)增加細(xì)節(jié)增量而得到，則傳輸時(shí)先傳遞低分辨率的數(shù)據(jù)，然后根據(jù)需要依次傳遞細(xì)節(jié)增量，最終得到合適分辨率的數(shù)據(jù)。

目前，柵格數(shù)據(jù)漸進(jìn)傳輸研究比較成熟，相關(guān)國(guó)際標(biāo)準(zhǔn)和商業(yè)軟件已經(jīng)出現(xiàn)，部分算法和產(chǎn)品也已經(jīng)實(shí)用化。但矢量數(shù)據(jù)的漸進(jìn)傳輸還不是很成熟，主要原因有以下方面：

（1）矢量數(shù)據(jù)本身存在復(fù)雜性。影像/柵格數(shù)據(jù)結(jié)構(gòu)單一，可以認(rèn)為是一種結(jié)構(gòu)化數(shù)據(jù)。矢量數(shù)據(jù)則比較復(fù)雜，可分為要素和要素集合兩個(gè)層次。其中，要素又包括幾何和屬性兩部分，幾何部分包括點(diǎn)、線、面3種對(duì)象類型;幾何要素之間存在拓?fù)潢P(guān)系。

（2）矢量數(shù)據(jù)傳輸存在多目標(biāo)與多層次特征。影像/柵格漸進(jìn)傳輸?shù)哪繕?biāo)僅考慮可視化，以最終的視覺(jué)結(jié)果為判定標(biāo)準(zhǔn)。矢量數(shù)據(jù)的應(yīng)用包含制圖輸出和空間分析兩種不同的功能，其漸進(jìn)傳輸與制圖綜合問(wèn)題相關(guān)聯(lián)，不僅涉及單個(gè)地理要素的多分辨率組織與漸進(jìn)傳輸，還涉及多要素之間漸進(jìn)傳輸結(jié)果可視化的邏輯一致性問(wèn)題。

（3）缺乏堅(jiān)實(shí)的理論基礎(chǔ)。傳統(tǒng)的矢量數(shù)據(jù)漸進(jìn)傳輸通常被看做制圖綜合的逆向過(guò)程進(jìn)行研究。目前，雖然制圖綜合算法和數(shù)據(jù)模型被大量引入到漸進(jìn)傳輸與數(shù)據(jù)的多分辨率組織之中，但是制圖綜合本身尚有很多問(wèn)題需要解決，如在拓?fù)湟恢滦?、化?jiǎn)結(jié)構(gòu)的適用性方面尚有難以克服的困難。

（4）缺乏集成性?，F(xiàn)有的矢量數(shù)據(jù)漸進(jìn)傳輸算法較少考慮現(xiàn)代GIS體系結(jié)構(gòu)，為達(dá)漸進(jìn)傳輸目的而設(shè)計(jì)的獨(dú)立體系的數(shù)據(jù)結(jié)構(gòu)與模型很難融入GIS主流體系中。此外，基于關(guān)系數(shù)據(jù)庫(kù)存儲(chǔ)是GIS工程中矢量數(shù)據(jù)的通用存儲(chǔ)方案;在制圖綜合領(lǐng)域雖然設(shè)計(jì)了一些多分辨率的矢量數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，但以上結(jié)構(gòu)仍難以方便地映射為GIS關(guān)系存儲(chǔ)模型。

1 二維矢量數(shù)據(jù)漸進(jìn)傳輸?shù)南嚓P(guān)研究

Buttenfield等指出矢量數(shù)據(jù)漸進(jìn)傳輸應(yīng)該與制圖綜合緊密相連，是制圖綜合的逆過(guò)程［1－4］。因此，某些制圖綜合的算法、數(shù)據(jù)結(jié)構(gòu)經(jīng)過(guò)改造可以應(yīng)用于矢量數(shù)據(jù)的漸進(jìn)傳輸。

1.1 二維矢量數(shù)據(jù)漸進(jìn)傳輸框架研究

Buttenfield針對(duì)線特征提出了GIS數(shù)據(jù)漸進(jìn)傳輸?shù)膶?shí)現(xiàn)流程［1］，其思想是基于制圖綜合方法對(duì)原始數(shù)據(jù)進(jìn)行預(yù)處理，生成矢量數(shù)據(jù)的多分辨率表達(dá)模型。該模型的建立步驟：1）根據(jù)專題建立圖層，圖層基于文件方式分離存儲(chǔ);2）對(duì)圖層中的要素按照重要度排序;3）建立每個(gè)幾何要素的多分辨率模型。Buttenfield使用D-P算法對(duì)線要素進(jìn)行化簡(jiǎn)，并基于條帶樹(shù)進(jìn)行線要素的多分辨率存儲(chǔ)，該方法的缺陷在于只能針對(duì)線要素保持拓?fù)潢P(guān)系，不能保持其他空間對(duì)象間的拓?fù)潢P(guān)系。如果要保持拓?fù)潢P(guān)系，則需附加算法對(duì)數(shù)據(jù)進(jìn)行預(yù)處理。

Bertolotto等提出了基于胞腔復(fù)形矢量數(shù)據(jù)模型的漸進(jìn)傳輸組織方案［2－4］，該方案定義了線收縮、面收縮、區(qū)域細(xì)化、線合并、區(qū)域合并、點(diǎn)抽取、線抽取等地圖化簡(jiǎn)基本算子;通過(guò)上述算子，可以對(duì)地圖進(jìn)行遞歸化簡(jiǎn)，建立多分辨率模型。為了維護(hù)要素間的拓?fù)湟恢滦?，所有的矢量?shù)據(jù)都保存在一個(gè)圖層中。該方法的效果相當(dāng)于建立地圖級(jí)的離散LOD模型，但無(wú)法支持要素級(jí)別的漸進(jìn)傳輸。

與Bertolotto的方案相似，楊必勝等［5］提出了一種基于頂點(diǎn)刪除模式的矢量數(shù)據(jù)漸進(jìn)傳輸組織方案，該方案使用“面條模型”表達(dá)地圖，包含點(diǎn)、線和多邊形3種幾何對(duì)象，其中線和多邊形對(duì)象由頂點(diǎn)構(gòu)成。為了建立頂點(diǎn)、線與多邊形之間的拓?fù)潢P(guān)系，將頂點(diǎn)分為3種基本類型：1）一個(gè)或兩個(gè)同層對(duì)象共享的頂點(diǎn);2）兩個(gè)以上同層對(duì)象共享的頂點(diǎn);3）一個(gè)以上多層對(duì)象共享的頂點(diǎn)。基于頂點(diǎn)類型和原有拓?fù)潢P(guān)系，對(duì)頂點(diǎn)進(jìn)行刪除操作。類似于Visvalingam-Whyat算法［6］，對(duì)刪除的頂點(diǎn)進(jìn)行排序，并將刪除的頂點(diǎn)壓入堆棧結(jié)構(gòu)中供后續(xù)漸進(jìn)傳輸使用。該方法較之Bertolotto方法完整地實(shí)現(xiàn)了曲線的漸進(jìn)傳輸，在刪除過(guò)程中保持拓?fù)潢P(guān)系不變，但是沒(méi)有考慮其它制圖綜合算子。由于算法需要對(duì)整個(gè)地圖進(jìn)行漸進(jìn)式化簡(jiǎn)，所以最大的問(wèn)題在于無(wú)法根據(jù)可視區(qū)域組織漸進(jìn)數(shù)據(jù)流。

Ai等提出了一種基于變化累積模型的矢量數(shù)據(jù)漸進(jìn)傳輸組織方案［7］，定義了“加”、“減”和“替換”3種基本的變化累積操作，通過(guò)這3種操作將客戶端的實(shí)時(shí)綜合與服務(wù)器端的離線綜合統(tǒng)一起來(lái)。對(duì)多邊形特征利用層次分解技術(shù)，化簡(jiǎn)成一系列的凸殼和矩形，基于層次樹(shù)建立幾何對(duì)象的多分辨率表達(dá)。該算法適用于離散的多邊形對(duì)象（如湖泊、房屋等）的漸進(jìn)傳輸。此外，Cecconi等提出了實(shí)現(xiàn)矢量數(shù)據(jù)漸進(jìn)傳輸框架，并列出了3個(gè)核心研究點(diǎn)［8］：1）漸進(jìn)傳輸相關(guān)的地圖綜合算法;2）在客戶服務(wù)器模型下的數(shù)據(jù)傳輸機(jī)制;3）客戶端矢量數(shù)據(jù)組合的問(wèn)題。David等提出了面向服務(wù)的矢量數(shù)據(jù)漸進(jìn)傳輸框架［9］，該框架融合了在線制圖綜合技術(shù)，不僅可以在服務(wù)器端生成客戶端需要顯示的SVG文檔，還可以為客戶端提供下載文檔服務(wù)，并在后續(xù)傳輸時(shí)，通過(guò)XML DOM更新客戶端的顯示。

1.2 矢量數(shù)據(jù)制圖綜合與幾何化簡(jiǎn)

目前，制圖綜合算法被大量應(yīng)用于矢量數(shù)據(jù)漸進(jìn)傳輸研究中。綜合的目的是為了獲得特定分辨率的空間數(shù)據(jù)，由于矢量數(shù)據(jù)以要素集合的形式組織，所以多分辨率矢量數(shù)據(jù)被分為兩個(gè)級(jí)別：1）要素級(jí)的算法主要是針對(duì)曲線和多邊形邊界的化簡(jiǎn);2）要素集合級(jí)的算法則是要素之間制圖綜合過(guò)程，包括合并、移位、夸張等過(guò)程。

制圖綜合的基礎(chǔ)在于空間數(shù)據(jù)的化簡(jiǎn)算法，其中最重要的是曲線的化簡(jiǎn)。曲線的化簡(jiǎn)算法類型較多，如點(diǎn)刪除算法（以 D-P算法和 Visvalingam－Whyat算法為代表）、重采樣算法（以Li-Openshaw算法為代表）、基于小波分析的算法、曲線層次結(jié)構(gòu)方法、分形方法、組合優(yōu)化方法、網(wǎng)格化方法等。

Douglas-Peucker算法（簡(jiǎn)稱 D-P算法）是最常用的一種曲線數(shù)據(jù)壓縮算法。該算法基于點(diǎn)刪除原理，通過(guò)遞歸地刪除距離曲線兩個(gè)端點(diǎn)連線距離最近的點(diǎn)實(shí)現(xiàn)曲線壓縮。大量曲線壓縮和曲線化簡(jiǎn)算法是基于對(duì)D-P算法的改進(jìn)而實(shí)現(xiàn)的［10］。另外一種點(diǎn)刪除算法是Visvalingam-Whyat算法（簡(jiǎn)稱VW算法），該算法的原理是利用曲線上相鄰的3個(gè)點(diǎn)構(gòu)成三角形，如果該三角形是所有三角形中面積最小的，則可以將中間的點(diǎn)從三角形刪除，化簡(jiǎn)過(guò)程迭代到曲線中剩下兩個(gè)點(diǎn)為止［11］。Wang等對(duì)V-W算法進(jìn)行了擴(kuò)展，稱為Bend Simplification算法;該算法通過(guò)分析幾何對(duì)象的特征，刪除時(shí)的判斷因子不再是三角形面積，而是邊界圍成的凸殼和凹陷部分，同時(shí)該算法還集成了刪除、膨脹和合并的制圖綜合算子［12］。Yang等的算法均是在V-W算法基礎(chǔ)上考慮要素間拓?fù)潢P(guān)系的改進(jìn)版本［13－16］?；邳c(diǎn)刪除的算法與條帶樹(shù)、BLG樹(shù)、多尺度線性樹(shù)等多分辨率的數(shù)據(jù)結(jié)構(gòu)聯(lián)系緊密，算法的迭代運(yùn)行過(guò)程可以由這些結(jié)構(gòu)記錄，并通過(guò)“回放”實(shí)現(xiàn)漸進(jìn)傳輸。

Li-Openshaw算法［17］是一種基于自然規(guī)律的自適應(yīng)線狀要素綜合算法，其原理是用與比例尺相關(guān)的圓在原有曲線上滑動(dòng)，對(duì)曲線進(jìn)行重采樣，獲得綜合結(jié)果。其過(guò)程是對(duì)于特定的顯示分辨率，隨著比例尺變小，一個(gè)大的多邊形會(huì)形成一個(gè)小多邊形;當(dāng)該多邊形只能用一個(gè)點(diǎn)表示時(shí)，就達(dá)到了極限尺寸。朱鯤鵬等對(duì)算法做了進(jìn)一步改進(jìn)，主要考慮了曲線上極大值和采樣圓與曲線多點(diǎn)相交的問(wèn)題［18］。

基于小波的算法是實(shí)現(xiàn)曲線化簡(jiǎn)的另一條途徑。Saux將B－樣條與小波分析相結(jié)合，針對(duì)需要光滑和連續(xù)性的曲線，進(jìn)行曲線化簡(jiǎn)研究［19］。吳凡利用Mallat算法，研究了獲取整數(shù)尺度上曲線的綜合問(wèn)題，通過(guò)建立多尺度表達(dá)的一致性約束模型，對(duì)細(xì)節(jié)信息進(jìn)行增補(bǔ)和閾值調(diào)控，實(shí)現(xiàn)了介于任意兩個(gè)整數(shù)尺度之間的線狀特征空間數(shù)據(jù)近似表達(dá)［20］。Wang等基于小波分析理論，研究了基于小波多尺度分析的等高線數(shù)據(jù)壓縮模型和算法，利用D-P算法對(duì)小波變換的邊界進(jìn)行預(yù)處理，提取特征點(diǎn)，并在小波壓縮之后恢復(fù)特征點(diǎn)，保持了等高線的拓?fù)湟恢滦裕?1－23］。

構(gòu)建曲線的層次結(jié)構(gòu)并以此為化簡(jiǎn)依據(jù)是矢量數(shù)據(jù)化簡(jiǎn)的另一種策略。Guo提出了一種基于線對(duì)象結(jié)構(gòu)的漸進(jìn)式化簡(jiǎn)算法，該算法基于線上的特征（極值點(diǎn)、凸點(diǎn)、拐點(diǎn)、單調(diào)區(qū)間）建立線結(jié)構(gòu)及其層次關(guān)系，以此為約束對(duì)曲線進(jìn)行化簡(jiǎn)［24］。艾廷華等基于曲線彎曲層次的概念，通過(guò)將曲線自身作為約束，建立曲線的帶約束Delaunay三角網(wǎng)，并根據(jù)三角形與頂點(diǎn)、曲線的關(guān)系對(duì)其進(jìn)行分類;在分類基礎(chǔ)上，對(duì)Delaunay三角網(wǎng)應(yīng)用剝皮算法，記錄剝皮的過(guò)程，根據(jù)被剝皮的三角形類型，迭代構(gòu)建曲線的二叉樹(shù)組織結(jié)構(gòu)，再根據(jù)彎曲的層次結(jié)構(gòu)，對(duì)曲線進(jìn)行化簡(jiǎn)［25］。王橋等利用分形原理對(duì)線狀要素化簡(jiǎn)的步長(zhǎng)選擇問(wèn)題進(jìn)行研究，所提出的方法顧及了制圖綜合的目的，強(qiáng)調(diào)圖形形狀結(jié)構(gòu)特征，調(diào)整自動(dòng)綜合的效果，并能與其它方法配合使用［26，27］。Poorten等提出的算法能夠同時(shí)對(duì)多條曲線進(jìn)行綜合，通過(guò)三角形之間的聯(lián)通關(guān)系，維護(hù)曲線之間的拓?fù)湟恢滦裕?8］。杜維等提出了一種基于組合優(yōu)化策略的多邊形化簡(jiǎn)算法，其基本思想是以多邊形輪廓為目標(biāo)，依據(jù)曲線特征點(diǎn)將其分解為一系列的彎曲特征，并對(duì)此彎曲特征集實(shí)施組合優(yōu)化;通過(guò)將入圍的彎曲首尾相連，該算法可被應(yīng)用于多邊形的化簡(jiǎn)［29］。

網(wǎng)格法是將地理坐標(biāo)表示成一系列的網(wǎng)格單元，利用網(wǎng)格單元作為控制結(jié)構(gòu)實(shí)現(xiàn)要素的化簡(jiǎn)。在這一方面，Dutton提出了層次坐標(biāo)系統(tǒng)（Hierarchical Coordinate System）的概念，同時(shí)基于地球表面的結(jié)構(gòu)采用QTM（Quaternary Triangular Mesh）加以描述［30－32］。QTM是相互嵌套的層次性三角形網(wǎng)格，覆蓋全球;其網(wǎng)格單元按照一定規(guī)則編碼，一個(gè)網(wǎng)格單元可以代表一定分辨率下確定的地理位置。在某一分辨率下，一條曲線可以用一系列的頂點(diǎn)所經(jīng)過(guò)的單元ID表示;低分辨率的幾何要素由高分辨率的要素綜合得到，綜合過(guò)程受到QTM層次結(jié)構(gòu)的控制，通過(guò)將同屬于一個(gè)低分辨率網(wǎng)格單元的頂點(diǎn)進(jìn)行合并實(shí)現(xiàn)線狀要素的化簡(jiǎn)。Wang等提出了適應(yīng)性網(wǎng)格模型（Adaptive Lattice Model），并基于此建立了線和多邊形的綜合算法［33－35］。適應(yīng)性網(wǎng)格類似于一個(gè)CCD相機(jī)陣列，提供了一個(gè)固定分辨率控制機(jī)制，在該網(wǎng)格分辨率下，點(diǎn)的坐標(biāo)可以被四舍五入到網(wǎng)格上，某些頂點(diǎn)可以被合并，多邊形可以被聚合或者轉(zhuǎn)換成線狀要素。

1.3 二維矢量數(shù)據(jù)的多分辨率組織

矢量數(shù)據(jù)的多分辨率包含要素集合和要素兩個(gè)層次。通常通過(guò)樹(shù)結(jié)構(gòu)的層次性生成要素集合多分辨率，常采用反應(yīng)樹(shù)及其變種實(shí)現(xiàn)要素集合的多分辨率組織;通過(guò)化簡(jiǎn)綜合算法生成線要素的多分辨率組織，常采用基于D-P算法所產(chǎn)生的多分辨率曲線存儲(chǔ)模型，包括STRIP樹(shù)、BLG樹(shù)和多叉樹(shù)。

反應(yīng)樹(shù)（Reactive Tree）采用空間數(shù)據(jù)庫(kù)中進(jìn)行多分辨率空間對(duì)象管理和索引的結(jié)構(gòu)［36－38］，它是一種多路樹(shù)，其入口可分為對(duì)象和子樹(shù)兩種。每個(gè)節(jié)點(diǎn)包含若干入口，非葉子節(jié)點(diǎn)可以同時(shí)包含兩種節(jié)點(diǎn)，而葉子節(jié)點(diǎn)只能包含對(duì)象入口;每種入口都包含一個(gè)重要值指標(biāo)以反映節(jié)點(diǎn)的多分辨率特性。反應(yīng)樹(shù)可基于R樹(shù)、球樹(shù)、KD樹(shù)實(shí)現(xiàn)。李愛(ài)勤［39］討論了一種基于四叉樹(shù)的多分辨率數(shù)據(jù)組織模型，被認(rèn)為是反應(yīng)樹(shù)的四叉樹(shù)變種。

GAP樹(shù)（Generalized Area Partitioning tree）是管理平面分割的多分辨率組織結(jié)構(gòu)［40］。在GAP樹(shù)中，一個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)被綜合的多邊形區(qū)域，節(jié)點(diǎn)下還可以包含不重要的低級(jí)多邊形，追蹤葉子到根的過(guò)程反映了多邊形綜合的過(guò)程。C-Tree是基于GAP樹(shù)的一種實(shí)現(xiàn)［41］。

STRIP樹(shù)也稱條帶樹(shù)，是一種二叉樹(shù)［42］，它通過(guò)記錄低精度曲線到高精度曲線的增量來(lái)表示多分辨率數(shù)據(jù)，可存儲(chǔ)任意的曲線結(jié)構(gòu)。該樹(shù)可應(yīng)用于D-P算法，通過(guò)記錄條帶樹(shù)抽取結(jié)點(diǎn)過(guò)程實(shí)現(xiàn)多分辨率的表達(dá)。

BLG樹(shù)（Binary Line Generalization tree）作為反應(yīng)樹(shù)的補(bǔ)充［43，44］，也是基于二叉樹(shù)結(jié)構(gòu)，其主要思想在于將D-P算法執(zhí)行的中間過(guò)程按尺度特征進(jìn)行記錄，建立細(xì)節(jié)累加模型。

多尺度線性樹(shù)（Multi-Scale Line Tree，MSLT）借鑒了STRIP樹(shù)的思想［45］，但它是多路樹(shù)而非二叉樹(shù)，結(jié)構(gòu)的每個(gè)層次對(duì)應(yīng)一個(gè)隱含的最大條帶寬度。此外，MSLT是面向節(jié)點(diǎn)的，在每個(gè)層次存儲(chǔ)節(jié)點(diǎn)，這些節(jié)點(diǎn)是更高層次的細(xì)節(jié)的中間層次。

多叉樹(shù)常應(yīng)用于多邊形的多分辨率組織［46］，將按D-P算法抽取的不同層次細(xì)節(jié)的節(jié)點(diǎn)存儲(chǔ)在多叉樹(shù)結(jié)構(gòu)索引矩陣中，在矩陣同一行中描述的具有等值偏移量的節(jié)點(diǎn)屬于同一等級(jí)，從而實(shí)現(xiàn)數(shù)據(jù)的層次細(xì)節(jié)存儲(chǔ)?；诙嗖鏄?shù)結(jié)構(gòu)，任應(yīng)超等提出了一種面向線的多尺度表達(dá)的數(shù)據(jù)結(jié)構(gòu)，該結(jié)構(gòu)使用VW算法生成多分辨率曲線模型，支持曲線數(shù)據(jù)的編輯，利用關(guān)系模型將不同分辨率的數(shù)據(jù)存儲(chǔ)于不同的關(guān)系表中，以提升數(shù)據(jù)庫(kù)的訪問(wèn)效率［47］。

2 三維表面模型的化簡(jiǎn)與漸進(jìn)傳輸

不規(guī)則三角網(wǎng)（Triangulated Irregular Network，TIN）也稱為三角形網(wǎng)格（Triangle Mesh）或簡(jiǎn)稱網(wǎng)格（Mesh）。因?yàn)槿魏稳S表面都可以使用不規(guī)則三角網(wǎng)進(jìn)行逼近，所以不規(guī)則三角網(wǎng)是最為常用的一種三維表面建模方法。TIN是三維虛擬場(chǎng)景對(duì)象建模的基本模型，也是除柵格之外另一種表示DEM的數(shù)據(jù)結(jié)構(gòu)，所以TIN的多分辨率表達(dá)和漸進(jìn)傳輸既包括空間數(shù)據(jù)領(lǐng)域的研究工作，也包括計(jì)算機(jī)圖形學(xué)及三維動(dòng)畫(huà)、游戲方面的工作。

2.1 三維表面模型的化簡(jiǎn)算法

TIN的化簡(jiǎn)是生成多分辨率模型的關(guān)鍵，將化簡(jiǎn)后的模型組成序列就是該模型的多分辨率表達(dá)。按照在生成過(guò)程中使用的算子，可以將TIN的化簡(jiǎn)算法分為頂點(diǎn)刪除法、重新布點(diǎn)法、頂點(diǎn)聚合法、區(qū)域合并法、邊折疊法、三角形折疊法以及基于小波分析的算法等。

頂點(diǎn)刪除法基本思想是刪除滿足一定條件的頂點(diǎn)，并對(duì)由此產(chǎn)生的空洞重新三角化，從而達(dá)到簡(jiǎn)化模型的目的［48］。該算法首先將網(wǎng)格中的頂點(diǎn)劃分為簡(jiǎn)單頂點(diǎn)、復(fù)雜頂點(diǎn)、邊界頂點(diǎn)、拐點(diǎn)和內(nèi)部邊界頂點(diǎn)，然后根據(jù)相鄰頂點(diǎn)擬合局部切平面，計(jì)算頂點(diǎn)到擬合切平面的距離。若距離小于指定閾值，則刪除該頂點(diǎn)，對(duì)刪除頂點(diǎn)后所遺留的空洞進(jìn)行局部三角剖分，壓縮過(guò)程中不能改變模型的拓?fù)潢P(guān)系。此后，Schroeder對(duì)算法進(jìn)行了改進(jìn)，通過(guò)剪切、縫合等操作，使得算法在構(gòu)建LOD模型的過(guò)程中可以實(shí)現(xiàn)拓?fù)潢P(guān)系的修改［49］。

重新布點(diǎn)法基本思想是首先確定簡(jiǎn)化模型中的頂點(diǎn)個(gè)數(shù)，按照一定的規(guī)則將一些頂點(diǎn)插入原始模型中，形成新舊模型共存的模型，然后刪除原始模型中的點(diǎn)，對(duì)刪除頂點(diǎn)后的空洞進(jìn)行三角化，得到新頂點(diǎn)構(gòu)成的簡(jiǎn)化模型［50］。該算法中新點(diǎn)的分布采用排斥力算法，即先隨機(jī)分布新點(diǎn)，然后計(jì)算新點(diǎn)間的排斥力，根據(jù)排斥力在網(wǎng)格上移動(dòng)這些新點(diǎn)，使它們重新分布。排斥力的大小與新點(diǎn)間的距離、新點(diǎn)所在三角面片的曲率、面積等有關(guān)。

頂點(diǎn)聚合法的基本思想是通過(guò)空間劃分將模型中的頂點(diǎn)劃分為一系列頂點(diǎn)簇，然后把簇內(nèi)的點(diǎn)集聚合為一個(gè)頂點(diǎn)。該操作不依賴于原始模型的拓?fù)潢P(guān)系，僅與其幾何信息有關(guān)。最早的頂點(diǎn)聚類方法是均勻頂點(diǎn)聚類方法，該算法根據(jù)頂點(diǎn)的重要性對(duì)模型的頂點(diǎn)進(jìn)行分類，并將模型所在的空間按用戶定義的大小剖分為若干個(gè)規(guī)則格網(wǎng)，把構(gòu)成模型的所有頂點(diǎn)劃分到相應(yīng)的子格網(wǎng)單元中，遍歷劃分的格網(wǎng)單元，按照一定的規(guī)則（如距離單元內(nèi)所有頂點(diǎn)的加權(quán)平均距離）選擇可以代表整個(gè)格網(wǎng)單元中所有頂點(diǎn)的聚合頂點(diǎn)，最終得到由代表性頂點(diǎn)構(gòu)成的LOD模型［51］。Luebke等通過(guò)建立空間自適應(yīng)八叉樹(shù)剖分對(duì)上述算法進(jìn)行了改進(jìn)［52，53］。Low等提出利用立方體、球等任意簡(jiǎn)單的形狀作為空間剖分的基本單元，并將單元的中心定位于單元內(nèi)重要度最高的頂點(diǎn)，對(duì)于同時(shí)被包含在多個(gè)單元內(nèi)的頂點(diǎn)，根據(jù)其與各單元中心的距離遠(yuǎn)近進(jìn)行分配［54］。

區(qū)域合并算法通過(guò)合并表面模型中的相鄰面片以達(dá)到降低模型復(fù)雜度的目的。其中的超面算法是比較經(jīng)典的區(qū)域合并算法，該算法基于共面準(zhǔn)則把表面模型分割成連通區(qū)域，分別用多邊形面片代替各個(gè)區(qū)域，并對(duì)多邊形面片的邊界進(jìn)行簡(jiǎn)化，最后重新生成三角化多邊形面片［55，56］。

邊折疊法是一個(gè)迭代的化簡(jiǎn)算法，它按照一定的準(zhǔn)則刪除三角網(wǎng)中的邊并重構(gòu)三角網(wǎng)，以達(dá)到化簡(jiǎn)模型的目的。邊折疊可以在化簡(jiǎn)過(guò)程中形成自然的層次結(jié)構(gòu)，便于多分辨率模型的構(gòu)建。Hoppe最先提出了邊折疊化簡(jiǎn)方法，該方法綜合考慮了頂點(diǎn)數(shù)目、近似表達(dá)誤差以及網(wǎng)格結(jié)構(gòu)優(yōu)化，可以獲得非常好的結(jié)果，但運(yùn)算效率較低，后續(xù)研究主要集中在如何提高邊折疊的效率［57］。Ronfard等相繼提出了新的邊折疊的判別標(biāo)準(zhǔn)［58－62］。

三角形折疊法也是一種迭代化簡(jiǎn)方法。該方法先將滿足折疊條件的三角面片的三個(gè)頂點(diǎn)合并為一個(gè)頂點(diǎn)，然后刪除退化的三角面片。一次三角形折疊相當(dāng)于兩次邊折疊，因此三角形折疊的效率要優(yōu)于邊折疊。Hamann首先提出了基于三角形折疊的表面LOD模型構(gòu)建算法，該算法是基于三角形三個(gè)頂點(diǎn)曲率和三角形的形狀確定三角形權(quán)值，權(quán)值最低的三角形最先被折疊為一個(gè)頂點(diǎn)［63］。Isler以頂點(diǎn)的重要度決定基本操作算子（邊折疊或三角形折疊），以三角形的視覺(jué)重要度確定三角形折疊順序［64］。周昆利用折疊后的新點(diǎn)與被折疊三角形相關(guān)的三角形集合中各三角形所在平面的距離最大值的倒數(shù)作為權(quán)值，確定三角形的折疊順序［65］。

小波方法利用小波的多分辨率分析特性（Multi-Resilution Analysis，MRA），將模型分解為擬合域（即化簡(jiǎn)后的模型）和細(xì)節(jié)域。Lounsbery最早將小波方法應(yīng)用于三維表面模型化簡(jiǎn)，他將具有分割連通性的曲面進(jìn)行了小波分解［66，67］。此后，Eck等提出了將任意曲面轉(zhuǎn)換為分割連通性的方法，使得MRA可以應(yīng)用于任意形狀的三維模型［68］。

2.2 三維表面模型的調(diào)度與傳輸策略

雖然網(wǎng)格化簡(jiǎn)方法可以有效降低三維表面模型的數(shù)據(jù)量，但在處理海量數(shù)據(jù)時(shí)依然不能滿足繪制效率和用戶交互的要求，需與LOD、漸進(jìn)傳輸?shù)葍?yōu)化策略相配合，實(shí)現(xiàn)三維表面模型的調(diào)度與傳輸。

視點(diǎn)相關(guān)的LOD通過(guò)區(qū)域視覺(jué)重要度來(lái)定義，可以根據(jù)需要對(duì)局部格網(wǎng)區(qū)域有選擇地進(jìn)行加密或者簡(jiǎn)化，使得視覺(jué)重要度比較高的區(qū)域利用較高的分辨率表示。Gross在地形渲染中提出了地形表面模型的自適應(yīng)視相關(guān)LOD表示法，并定義了用于改變局部區(qū)域模型質(zhì)量的小波空間濾波算子［69］。Lindstrom等針對(duì)大數(shù)據(jù)量的地形渲染也提出了類似的方法［70－72］。Wang等設(shè)計(jì)并實(shí)現(xiàn)了一種具有拓?fù)浔３痔匦缘淖赃m應(yīng)視相關(guān)LOD模型的動(dòng)態(tài)構(gòu)建及實(shí)時(shí)更新方法［73］。

漸進(jìn)網(wǎng)格（Progressive Mesh，PM）技術(shù)通過(guò)記錄迭代TIN的化簡(jiǎn)過(guò)程形成化簡(jiǎn)模型和增量數(shù)據(jù)的形式，通過(guò)化簡(jiǎn)的逆向過(guò)程逐步恢復(fù)網(wǎng)格，實(shí)現(xiàn)網(wǎng)格的漸進(jìn)傳輸［74］。Pajarola等進(jìn)一步提出了壓縮漸進(jìn)網(wǎng)格算法，在傳輸之前對(duì)數(shù)據(jù)進(jìn)行壓縮［75，76］;Southern等結(jié)合視點(diǎn)相關(guān)傳輸方法進(jìn)一步提高了漸進(jìn)傳輸 效 率［77，78］。漸 進(jìn) 幾 何 壓 縮 （Progressive Geometry Compression，PGC）通過(guò)對(duì)規(guī)則或者半規(guī)則網(wǎng)格進(jìn)行小波變換，并在各個(gè)子帶的小波系數(shù)間建立零樹(shù)結(jié)構(gòu)，進(jìn)行零樹(shù)編碼生成漸進(jìn)壓縮碼流，在碼流的任意位置截?cái)?，解碼后可以獲得原始模型的一個(gè)近似表示［79］。

由以上研究可以看出，三維表面模型的化簡(jiǎn)與壓縮的核心是通過(guò)某種判別規(guī)則從模型中刪除頂點(diǎn)、邊或者三角形等幾何單元，并對(duì)刪除后模型進(jìn)行空洞填補(bǔ)處理，最后通過(guò)迭代式的化簡(jiǎn)及其逆向過(guò)程從而實(shí)現(xiàn)模型的漸進(jìn)傳輸。漸進(jìn)網(wǎng)格技術(shù)確立了三維表面模型漸進(jìn)傳輸?shù)幕痉椒?，?jīng)過(guò)多年發(fā)展已成為三維數(shù)據(jù)壓縮與傳輸?shù)慕?jīng)典算法。

3 結(jié)論

目前，漸進(jìn)傳輸已經(jīng)成為解決海量空間數(shù)據(jù)與網(wǎng)絡(luò)用戶交互、快速響應(yīng)之間矛盾的基本方法。雖然影像/柵格的漸進(jìn)傳輸已經(jīng)得到比較好的解決，但矢量數(shù)據(jù)的漸進(jìn)傳輸問(wèn)題尚未得到真正的解決。通過(guò)與三維表面模型漸進(jìn)傳輸?shù)难芯繉?duì)比，矢量數(shù)據(jù)漸進(jìn)傳輸研究需要克服如下問(wèn)題：

（1）明確矢量地理數(shù)據(jù)漸進(jìn)傳輸?shù)哪繕?biāo)與定位。當(dāng)前大量研究將矢量地理數(shù)據(jù)的漸進(jìn)傳輸與制圖綜合相聯(lián)系，試圖應(yīng)用制圖綜合的相關(guān)技術(shù)解決漸進(jìn)傳輸問(wèn)題。但制圖綜合的首要目的是生產(chǎn)滿足制圖需求的多比例尺地圖，而矢量地理數(shù)據(jù)漸進(jìn)傳輸?shù)氖滓繕?biāo)是在保證可視化結(jié)果正確的前提下，降低網(wǎng)絡(luò)負(fù)載，提升用戶的交互操作體驗(yàn)效果。這兩種技術(shù)存在應(yīng)用需求方面的差異，因此需要針對(duì)矢量數(shù)據(jù)漸進(jìn)傳輸?shù)哪繕?biāo)需求，設(shè)計(jì)相關(guān)算法。

（2）平衡矢量數(shù)據(jù)化簡(jiǎn)算法效率與拓?fù)潢P(guān)系保持之間的依賴性。矢量地理數(shù)據(jù)化簡(jiǎn)是漸進(jìn)傳輸?shù)幕A(chǔ)，但是當(dāng)前無(wú)論是多要素制圖綜合還是單要素幾何化簡(jiǎn)都在純幾何層次考慮問(wèn)題，算法需要大量的浮點(diǎn)運(yùn)算，難以保證效率。僅對(duì)單個(gè)地理要素進(jìn)行化簡(jiǎn)，難以維持要素間的拓?fù)潢P(guān)系;但考慮要素間的拓?fù)潢P(guān)系保持問(wèn)題，則又勢(shì)必極大地增加計(jì)算量。新的算法設(shè)計(jì)關(guān)鍵在于確定矢量數(shù)據(jù)化簡(jiǎn)與拓?fù)潢P(guān)系保持的平衡點(diǎn)，尋找新的控制結(jié)構(gòu)，解除兩者之間的依賴。

（3）設(shè)計(jì)新型的數(shù)據(jù)結(jié)構(gòu)，降低數(shù)據(jù)冗余和存儲(chǔ)的復(fù)雜性。當(dāng)前的相關(guān)算法都是基于樹(shù)的數(shù)據(jù)結(jié)構(gòu)，需要指針維護(hù)層次關(guān)系，還需要額外的存儲(chǔ)空間，無(wú)法真正實(shí)現(xiàn)無(wú)冗余傳輸。同時(shí)樹(shù)結(jié)構(gòu)與矢量地理數(shù)據(jù)的關(guān)系數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)難融合，實(shí)際應(yīng)用困難。因此需要尋找多分辨率之間的插入隱含關(guān)系，將增量數(shù)據(jù)的插入位置隱含在數(shù)據(jù)流中，實(shí)現(xiàn)增量數(shù)據(jù)的無(wú)冗余傳輸。

［1］BUTTENFIELD B P.Transmitting vector geospatial data across the Internet［EB/OL］.Proceeding GIScience′02.http：//www.springerlink.com/content/4kgffqdnmk962brv/fulltext.pdf.2011－09－27.

［2］BERTOLOTTO M，EGENHOFER M J.Progressive vector transmission［EB/OL］.7th ACM Symposium on Advances in Geographic Information Systems，1999.http：//delivery.acm.org/10.1145/330000/320172/p152-bertolotto.pdf ip＝137.189.162.186＆CFID＝44877011＆CFTOKEN＝80335071＆＿＿acm＿＿＝1317107472＿fcb8f0aa11cfa6c579111a684300ad9e.2011－09－27.

［3］BERTOLOTTO M，EGENHOFER M J.Progressive transmission of vector map data over the World Wide Web［J］.GeoInformatica，2001，5（5）：345－373.

［4］BERTOLOTTO M.Geometric Modeling of Spatial Entities at Multiple Levels of Resolution［D］.University of Genova，1998.

［5］楊必勝，李清泉.World Wide Web（WWW）上矢量地圖數(shù)據(jù)的多分辨率傳輸算法［J］.測(cè)繪學(xué)報(bào)，2005，34（4）：355－360.

［6］VISVALINGAM M，WHYATT J D.Line generalization by repeated elimination of points［J］.Cartographic，1993，30（1）：46－51.

［7］AI T H，LI Z L，LIU Y L.Progressive transmission of vector data based on changes accumulation model developments［EB/OL］.11th International Symposium on Spatial Data Handling 2005.http：//www.springerlink.com/content/u371gh8w85865mkm/fulltext.pdf.2011－09－27.

［8］CECCONI A，WEIBEL R.Map generalization for on-demand web mapping［EB/OL］.GIScience 2000.http：//citeseerx.ist.psu.edu/viewdoc/download;jsessionid＝ 85FD7EF9788A744D815 CFCE6A21BD8A7？doi＝10.1.1.90.9161＆rep＝rep1＆type＝pdf.2011－09－27.

［9］DAVID C C，MARIO M T，ANSELMO C，et al.Aservice-oriented architecture for progressive transmission of maps［EB/OL］.IX Brazilian Symposium on GeoInformatics.http：//www.geoinfo.info/geoinfo2007/papers/S5P2.pdf.2011－09－27.

［10］DOUGLAS D H，PEUKER T K.Algorithms for the reduction of the number of points required to represent aline or its caricature［J］.The Canadian Cartographer，1973，10（2）：112－122.

［11］VISVALINGAM M，WHYATT J D.Line generalization by repeated elimination of points［J］.Cartographic Journal，2003，30（1）：46－51.

［12］WANG Z，MULLER J C.Line generalization based on analysis of shape characteristics［J］.Cartography and Geographic Information Science，1998，25（1）：3－15.

［13］YANG B S，PURVES R S，WEIBEL R.Implementation of progressive transmission algorithms for vector map data in webbased visualization［A］.Proceedings XXth ISPRS Congress，Commission IV，2001.25－31.

［14］YANG B S.A multi-resolution model of vector map data for rapid transmission over the internet［J］.Computers ＆ Geosciences，2005，31（5）：569－578.

［15］YANG B S，PURVES R S，WEIBEL R.Efficient transmission of vector data over the internet［J］.International Journal of Geographical Information Science，2007，21（2）：215－237.

［16］任應(yīng)超，李文雯，楊崇俊.一種用于漸進(jìn)傳輸?shù)亩喾直媛是€模型［J］.計(jì)算機(jī)工程，2008，34（8）：25－28.

［17］LI Z L，OPENSHAW S.Linear feature′s self-adapted generalization algorithm based on impersonality generalized natural law［J］.Translation of Wuhan Technical University of Surveying and Mapping，1994（1）：49－58.

［18］朱鯤鵬，武芳，王輝連.Li-Openshaw算法的改進(jìn)與評(píng)價(jià)［J］.測(cè)繪學(xué)報(bào)，2007，36（4）：450－456.

［19］SAUX E.B-spline functions and wavelets for cartographic line generalization［J］.Cartography and Geographic Information Science，2003，30（1）：33－50.

［20］吳凡.基于小波分析的線狀特征數(shù)據(jù)無(wú)級(jí)表達(dá)［J］.武漢大學(xué)學(xué)報(bào)（信息科學(xué)版），2004，29（6）：488－491.

［21］WANG Y H，ZHU C Q.The vector relief data compression based on the mulit-band wavelet［J］.Science of Surveying and Mapping，2003，28（3）：66－68.

［22］朱長(zhǎng)青，王玉海，李清泉，等.基于小波分析的等高線數(shù)據(jù)壓縮模型［J］.中國(guó)圖象圖形學(xué)報(bào)（A輯），2004，9（7）：841－845.

［23］王玉海，朱長(zhǎng)青.基于小波分析的線狀要素壓縮優(yōu)化的綜合性研究［J］.武漢大學(xué)學(xué)報(bào)（信息科學(xué)版），2007，32（7）：630－632.

［24］GUO Q S.A progressive line simplification algorithm［J］.Wuhan Technical University of Surveying and Mapping，1998（1）：52－56.

［25］艾廷華，郭仁忠，劉耀林.曲線彎曲深度層次結(jié)構(gòu)的二叉樹(shù)表達(dá)［J］.測(cè)繪學(xué)報(bào)，2001，30（4）：343－348.

［26］王橋，吳紀(jì)桃.制圖綜合方根規(guī)律模型的分形擴(kuò)展［J］.測(cè)繪學(xué)報(bào)，1996，25（2）：104－109.

［27］王橋，吳紀(jì)桃.一種新分維估值方法作為工具的自動(dòng)制圖綜合［J］.測(cè)繪學(xué)報(bào)，1996，25（1）：10－16.

［28］POORTEN V D，JONES C B.Customisable line generalization using Delauney triangulation［EB/OL］.Proceedings of the 19th ICA conference in Ottawa，1999.http：//www.comp.glam.ac.uk/pages/staff/pmvander/.2011－09－27.

［29］杜維，艾廷華，徐崢.一種組合優(yōu)化的多邊形化簡(jiǎn)方法［J］.武漢大學(xué)學(xué)報(bào)（信息科學(xué)版），2004，29（6）：548－550.

［30］DUTTON G，BUTTENFIELD B P.Scale change via hierarchical coarsening：Cartographic properties of quaternary triangular meshes［A］.Proc.16th Int.Cartographic Conference［C］.1993.847－862.

［31］DUTTON G.Digital map generalization using a hierarchical coordinate system［A］.Proc.Auto Carto 13.（Seattle，WA）Bethesda，MD：ACSM/ASPRS，1997.367－376.

［32］DUTTON G.Scale，sinuosity and point selection in digital line generalization［J］.Cartography and Geographic Information Science，1999，26（1）：33－53.

［33］WANG P T，DOIHARA T，LU W.Spatial generalization：An adaptive lattice model based on spatial resolution［EB/OL］.Symposium on Geospatial Theory，Processing and Applications，2002.http：//www.isprs.org/proceedings/XXXIV/part4/pdfpapers/291.pdf.2011－09－27.

［34］WANG P T，DOIHARA T，LU W，et al.A resolution-driven generalization approach for linear and areal object［EB/OL］.Geoscience and Remote Sensing Symposium.http：//ieeexplore.ieee.org/stamp/stamp.jsp？tp＝＆arnumber＝1294431.2011－09－27.

［35］DOIHARA T，WANG P T，LU W.An adaptive lattice model and its applications to map simplification［EB/OL］.Symposium on Geospatial Theory，Processing and Applications，2002.http：//www.isprs.org/proceedings/XXXIV/part4/pdfpapers/301.pdf.2011－09－27.

［36］OOSTEROM P V.The reactive-tree：A storage structure for a seamless，scaleless geographic database［A］.Auto-Carto 10［C］.1991.393－407.

［37］OOSTEROM P V.A storage structure for a multi-scale database：The reactive-tree［J］.Computers，Environment and Urban Systems，1992，16（3）：239－247.

［38］OOSTEROM P V.Reactive Data Structure for Geographic In-formation Systems［M］.Oxford University Press，1994.

［39］李愛(ài)勤.無(wú)縫空間數(shù)據(jù)組織及其多比例尺表達(dá)與處理研究［D］.武漢大學(xué)，2001.

［40］OOSTEROM P V.The GAP-tree，an approach to on-the-fly map generalization of an area partitioning［A］.MULLER J C，LAGRANGE J P，WEIBEL R.GIS and Generalization：Methodology and Practice［C］.Taylor ＆ Francis，London，1995.120－133.

［41］田鵬，鄭扣根，張引，等.基于C-Tree的無(wú)級(jí)比例尺GIS多邊形綜合技術(shù)［J］.中國(guó)圖象圖形學(xué)報(bào)（A輯），2001，6（8）：765－770.

［42］BALLARD D H.Strip trees：A hierarchical representation for curves［J］.ACM Communications.1981，24（5）：310－321.

［43］OOSTEROM P V.A reactive data structure for geographic information systems［EB/OL］.Auto-Carto 9，1989.http：//www.mapcontext.com/autocarto/proceedings/auto-carto-9/pdf/a-reactive-data-structure-for-geographic-information-systems.pdf.2011－09－27.

［44］OOSTEROM P V.Reactive Data Structures for Geographic Information Systems［D］.Leiden University，1990.

［45］JONES C B，ABRAHAM I M.Line generalization in a global cartographic database［J］.Cartographica，1987，24（3）：32－45.

［46］毋河海.基于多叉樹(shù)結(jié)構(gòu)的曲線綜合算法［J］.武漢大學(xué)學(xué)報(bào)（信息科學(xué)版），2004，29（6）：479－483.

［47］任應(yīng)超，李文雯，楊崇俊.一種用于漸進(jìn)傳輸?shù)亩喾直媛是€模型［J］.計(jì)算機(jī)工程，2008，34（8）：25－28.

［48］SCHROEDER W J，ZARGE J A，LORENSEN W E.Decimation of triangulation meshes［J］.Computer Graphics，1992，26（2）：65－70.

［49］SCHROEDER W J.A topology modifying progressive decimation algorithm［A］.Proceedings of Visualization′97［C］，IEEE Computer Society Press，1997.

［50］TURK G.Retiling polygonal surface［J］.Computer Graphics，1992，26（2）：55－64.

［51］ROSSIGUAC J，BORREL P.Multi-resolution 3D approximation for rendering complex scenes［A］.FALCIDIENO B，KUNII T.Geometric Modeling in Computer Graphics［C］.1993.455－465.

［52］LUEBKE D.Hierarchical structures for dynamic polygonal simplification［A］.SIGGRAPH′96［C］.1996.96－106.

［53］LUEBKE D，ERIKSON C.View-dependent simplification of arbitrary polygonal environments［A］.ACM Computer Graphics，31（Proc.of SIGGRAPH′97）［C］.1997.199－208.

［54］LOW K L，TAN T S.Model simplification using vertex-clustering［A］.COHEN M.Proceedings of 1997 Symposium on Interactive 3D Graphics［C］.1997.75－82.

［55］KALVIN A D，TAYLOR R H.Superfaces：Polyhedral approximation with bounded error［A］.Medical Imaging：Image Capture，F(xiàn)ormatting and display，SPIE［C］.1994，2164：2－13.

［56］KALVIN A D，TAYLOR R H.Superfaces：Polyhedral mesh simplification with bounded error［J］.IEEECG＆A，1996，16（3）：64－77.

［57］HOPPE H，DEROSE T，DUCHAMP T，et a1.Mesh optimization［J］.Computer Graphics，1993，27（SIGGRAPH′93）：19－26.

［58］RONFARD R，ROSSIGNAC J.Full-range approximation of triangulated polyhedral［A］.Proceedings of EUROGRAPH′96［C］.1996.67－76.

［59］GARLAND M，HECKBERT P S.Surface simplification using quadric error metrics［A］.SIGGRAPH′97［C］.1997.209－216.

［60］LINDSTROM P，TURK G.Fast and memory efficient polygo-nal simplification［A］.ROBERT M.Proceedings of IEEE Visualization′98［C］.1998.279－286.

［61］陶志良，潘志庚.復(fù)雜場(chǎng)景中動(dòng)態(tài)簡(jiǎn)化層次的構(gòu)造［J］.中國(guó)圖象圖形學(xué)報(bào)（A輯），1998，3（12）：1032－1036.

［62］盛業(yè)華，王永波，閭國(guó)年，等.一種基于邊收縮的3維表面模型數(shù)據(jù)壓縮算法［J］.中國(guó)圖象圖形學(xué)報(bào)，2007，12（1）：159－163.

［63］HAMANN B.A data reduction scheme for triangulated surface［J］.Computer Aided Geometric Design，1994，11（3）：197－214.

［64］ISLER V，LAU W H，GREEN M.Real-time multi-resolution modeling for complex virtual environments［EB/OL］.Proceedings of Virtual Reality Software and Technology′96.http：//www.cs.cityu.edu.hk/～rynson/papers/vrst96.pdf.2011－09－27.

［65］周昆，潘志庚，石教英.基于三角形折疊的網(wǎng)格簡(jiǎn)化算法［J］.計(jì)算機(jī)學(xué)報(bào)，1998，21（6）：506－513.

［66］LOUNSBERY M.Multiresolution Analysis for Surfaces of Arbitrary Topological Type［D］.University of Washington，1994.

［67］LOUNSBERY M，DEROSE T D，WARREN J.Multiresolution analysis for surfaces of arbitrary topological type［J］.ACM Trans.on Graphics，1997，16（1）：34－73.

［68］ECK M，DEROSE T，DUCHAMP T，et a1.Multiresolution analysis of arbitrary meshes［A］.ACM Computer Graphics（Proc.of SIGGRAPH′95）［C］.1995.173－182.

［69］GROSS M H，GATTI R，STAADT O.Fast multiresolution surface meshing［A］.NIELSON G M，SILVER D.IEEE Visualization′95 Proceedings，1995.135－142.

［70］LINDSTROM P，KOLLER D，RIBARSKY W，et a1.Real-time，continuous level of detail rendering of height fields［A］.Proc.SIGGRAPH′96［C］.1996.109－118.

［71］LINDSTROM P，PASCUCCI V.Visualization of large terrains made easy［A］.Proc.IEEE Visualization 2001［C］.2001.363－370.

［72］DUCHAINEAU M，WOLINSKY M，SIGETI D E，et a1.Roaming terrain：Real-time optimally adapting meshes［A］.Proc.IEEE Visualization′97［C］.1997.81－88.

［73］WANG Y B，SHENG Y H，ZHANG K，et a1.Efficient implementation of adaptive view-dependent mesh simplification［A］.Proceeding of SPIE，Geoinformatics′2007.Cartographic Theory and Models［C］.2007，16751：1－13.

［74］HOPPE H.Progressive meshes［A］.Proceedings of SIGGRAPH′96［C］.1996.99－108.

［75］PAJAROLA R，ROSSIGNAC J.Compressed progressive mesh［J］.IEEE Transactions on Visualization and Computer Graphics，2000，6（1）：79－93.

［76］ALLIEA P，DESBRUN M.Progressive compression for lossless transmission of triangle meshes［A］.Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques［C］.2001.195－202.

［77］SOUTHERN R，PERKINS S，BARRY S，et a1.A stateless client for progressive view-dependent transmission［A］.Proceedings of the Sixth International Conference on 3D Web Technology［C］.2001.43－50.

［78］KIM J，LEE S，KOBBELT L.View-dependent streaming of progressive meshes［A］.Proceedings of the Shape Modeling International 2004［C］.2004.209－220.

［79］KHODAKOVSKY A，SCHRODER P，SWELDENS W.Progressive geometry compression［A］.Computer Graphics Proceeding，Annual Conference Series，ACM SIGGRAPH［C］.2000.85－94.

An Overview on Progressive Transmission of Vector Spatial Data

WEN Yong－ning1，2，LV Guo－nian1，CHEN Min3
（1.KeyLaboratoryofVirtualGeographicEnvironment（MinistryofEducation），NanjingNormalUniversity，Nanjing210046;2.SuzhouIndustrialParkSurveyCO.LTD，Suzhou215021;3.InstituteofSpaceandEarth InformationScience，TheChineseUniversityofHongKong，ShatinH.K.，China）

The progressive transmission strategy is considered to be an effective way to balance contradiction between scheduling the massive spatial data and the real time user experience.Research on the progressive transmission of raster data is fairly sophisticated and mature，while various problems of the theory and technology of vector data′s progressive transmission are still required to be tackled.Aiming at promoting the research of vector data′s progressive transmission，and providing references for research of the distributed network transmission of massive spatial data，this paper focuses on leveraging and summarizing the complementary past and ongoing research of the multi-resolution expression and the progressive transmission of 2D vector data and 3D surface model data which is closely related to the progressive transmission of vector data.

spatial data;vector data;progressive transmission

P208

A

1672－0504（2011）06－0006－07

2011－07- 28;

2011－10－27

國(guó)家“863”重點(diǎn)課題子課題項(xiàng)目“基于廣域網(wǎng)的虛擬月球環(huán)境構(gòu)建研究”（2010AA122202）;國(guó)家自然科學(xué)基金項(xiàng)目“像素?zé)o損的矢量地理數(shù)據(jù)高效傳輸機(jī)制研究”（41001223）;江蘇高校優(yōu)勢(shì)學(xué)科建設(shè)工程資助項(xiàng)目

溫永寧（1977－），男，博士，講師，主要研究方向?yàn)樘摂M地理環(huán)境、3D GIS。E－mail：wenyn＠m(xù)sn.com