1、基于梯形格網的矢量地圖動態 LOD渲染方法“地圖是人類文化的杰作，它融科學、藝術于一體，作為描述、研究人類生存環境的一種信息載體是人類生產與生活中不可缺少的一種工具。”這是陳述彭院士為中國地圖學 年鑒作序的開場語。Taylor也曾指出當涉及應用人腦來識別空間聯系中的模式與相互關系時，地圖學的認知方法是唯一的過程”。地圖存在于我們生活的方方面面，應用廣泛且己經產生了巨大的社會效應和經濟效益，其重要性不言而喻。地圖是地圖可視化的結果，地圖可視化作為現代地圖學的核心一直是三維GIS的研究熱點。地圖可視化將電子設備的視覺傳輸能力和人類的視覺思維能力協同起來，將復雜多樣的空間信息轉化為圖形圖像并進行交互

2、處理， 為人們直觀地觀察地理現象及分析和探索地理規律提供了有力的工具。隨著計算機技術和圖形硬件的發展，利用計算機技術來輔助制作電子地圖逐漸成為主流趨勢。上世紀80年代科學計算可視化己被提出并迅速發展，其理論和方法對空間信息的表達和分析產生了重要影響。國際地圖制圖協會于1995 年成立了一個地圖可視化委員會，并與計算機圖形學會開始了 “ Carto-Project”， 研究項目，該項目使圖形學技術有效地應用在地理學及地圖學領域，為空間信息可視化提供了良好的技術支撐。隨著云計算、物聯網、基于位置的服務等技術的飛速發展，使得數據的種類和存儲規模以前所未有的速度增長。數據的規模化效應給地圖可視化帶來了

3、極大的挑戰，傳統地圖可視化方式上的變革正在醞釀和發生。21 世紀以來隨著社會經濟文化的進步，大眾對于地圖的需求也日益提高，人們不再滿足于二維地圖的抽象表達。隨著虛擬現實、增強現實等計算機圖形學技術的飛速發展，數字地球、虛擬地理環境、虛擬地理場景相繼被提出，可視化逐步由二維圖形的抽象表達發展至三維空間的逼真展示。在解決大規模空間數據實時繪制的問題上，國內外學者進行了廣泛而深入的研究，主要集中在空間索引優化、LOD可見域裁剪和渲染方法優化等多個方面。其中，LOD方法改變了 圖形質量越精細越好”的片面觀點，在保證繪制效果的基礎上有效地控制復雜場景的數據簡化，在實時圖形繪制、交互式可視化和虛擬現實等領

4、域有著廣泛的應用。在GIS領域，采用LOD進行大規模地理場景的實時渲染己經 成為最普遍的解決方案。然而，現有的多數矢量地圖動態LOD繪制方法在原始數據結構上進行簡化，再剖分為圖形API 支持的基礎圖元類型，海量且實時的剖分計算和速率敏感的顯存IO過程導致了其渲染效率低下；矢量地圖靜態LOD繪制方法則受限于有限的存儲空間和極 長的預處理時間。而且，現有的矢量地圖LOD繪制方法多是針對二維場景下矢量地圖的渲染，沒有考慮到投影方式對地圖簡化的影響，不適用于二三維一體化渲染。傳統的軟件地圖渲染方法依靠中央處理器的性能進行可視化渲染，其有限的計算能力導致地圖渲染效率低下，難以滿足大數據時代下海量空間信息

5、快速呈現的要求。自NVIDIA公司創造性地推出GPU以來，其高效的浮點運算能力和數倍于CPU的顯存帶寬使得以往由 CPU負責處理的幾何變換、光照計算、圖形及紋理計算等復雜計算全部轉移至GPU 上進行。隨著圖形處理器性能的大幅度提高和可編程特性的發展，計算機處理圖形的速度和質量得到了極大提升，圖形流水線的某些處理階段和算法從CPU向GPU轉移以加速圖形的渲染，充分開發GPU資源，已成為近年來計算機圖形學領域的研究熱點。同樣，在GIS領域利用GPU加速地圖渲染己經成為地圖可視化的發展趨勢，GPU性能的提升和可編程特性的發展為提高地圖的渲染效率和渲染質量提供了新的技術手段。充分利用GPU的性能，結合

6、LOD技術進行大規模數據的實時渲染已經成為矢量地圖優化渲染的重要方向。矢量地圖渲染方法的優化是現代地圖學一個重要的研究方向。人們對于矢量數據渲染需求是源源不斷的，空間數據的海量性和地理場景的復雜性使得單純依靠圖形硬件的計算能力遠遠不能滿足數據實時性渲染的需求，所以研究矢量地圖的加速渲染技術是十分必要的。本文的研究意義主要體現在以下兩個方面:(1)提高矢量地圖LOD繪制方法繪制效率針對現有透視投影下矢量地圖動態 LOD渲染方法存在的問題，設計一種視投影下矢量 地圖動態LOD渲染方法用以提高矢量地圖 LOD繪制方法的繪制效率，同時為三維場景下的 矢量地圖的渲染提供一種新的解決方案。(2)為非瓦片式

7、的地圖服務提供新的技術途徑現有柵格瓦片技術無法更改地圖的樣式，矢量瓦片可以更改樣式但繪制效率相對柵格瓦片效率降低。瓦片式地圖受限于計算機存儲空間的大小和極長的切片時間，層級之間具有跳躍感且沒有考慮投影方式的影響。本文方法考慮到投影方式的影響并對矢量幾何要素進行實時簡化，為非瓦片式地圖服務提供了新的技術途徑，為大規模數據可視化提供了新的思路。在地圖學與GIS領域，點符號、線符號、面符號是矢量地圖的三種基礎表達方式。因點 幾何要素不存在自身簡化，因此本文主要研究線，面幾何要素的動態LOD繪制方法。矢量地圖LOD繪制涉及三個主要的可視化操作：簡化，剖分與渲染。其中，針對LOD繪制中簡化的操作， 國內

8、外學者已經進行了廣泛而深入的研究。模型簡化的實質是一個信息壓縮的問題，即從組成模型的有序集合里選擇一個子集，在規定的精度范圍內，此子集從內容上可以盡可能的反映原集合，而在數據量上盡可能的減少。常見的簡化機制包括頂點聚類、增量式刪除、采樣和自適應細分等方法，基本的簡化算法都是通過這四種機制的結合或者變形進行實現的。針對本文的研究，以下將從線幾何要素的LOD繪制方法和面幾何要素的LOD繪制方法兩方面進行介紹。 1線幾何要素LOD繪制方法線幾何要素的LOD繪制一般通過簡化算法或LOD模型獲取簡化結果，再對簡化結果進行渲染。 線幾何要素的簡化算法一般采用增量式刪除法或采樣法。這些算法從幾何特征的角度出

9、發進行簡化，它們都能較好的保留幾何要素的圖形特征和空間分布特征。針對線幾何要素的簡化，國內外學者展開了不同的研究。以下， 本文從 Douglas-Peucker 算法 , Li-Openshaw算法、漸進式算法及這些算法的改進和線LOD模型分別進行介紹。(1) Douglas-Peucker 算法及其改進Douglas-Peucker 算法是一種增量式刪除的折線簡化算法，算法的基本思路是將曲線的首尾點相連，計算其余點至首尾點連線的垂直距離的最大值，若最大距離小于設定閾值即誤差度量則舍去兩端點之間的所有節點;若最大距離不小于設定閾值則保留此節點，以首尾點與此節點相連生成兩個新的線段，對其重復上述

10、的操作，直至線段上只有兩個節點為止。 Douglas-Peucker 算法采用從整體到局部的思維方式，是最具代表性的空間圖形綜合方法，可以有效地對折線進行簡化并保留其幾何特征，但此算法簡化過程中要素的拓撲關系發生變化可能會導致要素產生自相交。之后，Peucker和Douglas通過檢測凹坑、峰值、脊、溝壑和斷裂將Douglas-Peucker算法用效的應用在地形的簡化上。針對簡化的效率問題，Hershberger和 Snoeyink 提出了一種基于路徑凸包的方法加速了Douglas-Peucker 算法的效率，并分析了其最壞時候的運行情況。針對如何避免自相交的問題，Guibas證明了 Doug

11、las-Peucker算法中如何避免自相交是一個非確定多項式問題，針對 NP-hard 問題的求解一般采用窮舉法或采用確定性算法，采用窮舉法可以很容易得到結果但耗時極長，但確定性算法極難被找到。 Saalfelds設計了一種檢測拓撲一致性的簡單規則，通過添加簡單測試進行自相交判斷解決了簡化的折線自身及與相鄰要素潛在的拓撲沖突問題，但檢測效率不高。基于逐點前進法提出了一種改進的DP算法，極大地提高了算法的效率。不同于Saalfelds采用的凸包測試，Wu詳細分析自相交與折線星形區域的關系，通過分解折線為化星形子集并進行判斷來避免要素的自相交，提高了自相交判斷的效率。針對三維要素簡化的問題，基于二

12、維Douglas-Peucker算法提出了三維 Douglas-Peueker算法，良好的解決了三維離散點的綜合問題。 ( 2) Li-Openshaw 算法及其改進Li-Openshaw 算法是一種采樣式的折線簡化算法，Li-Openshaw 算法基于自然現實實現，算法的基本思想是通過圓在原始曲線上滑動對曲線進行重采樣，控制圓的大小獲取不同尺度下的簡化效果，可以有效的進行線要素的多尺度的簡化，但沒有考慮曲線上局部極大值點或圓與曲線的多個節點相交導致的異常情況。基于重心算法對Li-Openshaw 算法進行改進，這種方法在實現和簡捷性方面都取得了較好的效果，曲線光滑程度較為理想。改進 Li-O

13、penshaw算法， 通過局部極大值點識別彎曲并對彎曲進行細分用以簡化，同時依據構造曲線節點順序判斷相交的多個節點中初次出現的節點從而避免異常，解決了 Li-Openshaw 算法中失真和異常。在 Li-Openshaw 算法的基礎上，使用Nyquist-shannon 采樣理論采用六邊形的剖分對線要素進行采樣以簡化操作，此方法保持了要素更多的形態特征，適用于制圖線的簡化但預處理時間較長。結合Douglas-Peucker算法和Li-Openshaw算法提出一種顧及空間關系的線簡化方法， 通過對建立的全局簡化方法的使用有效地降低了曲線的復雜度，且顧及了線要素整體的空間關系。（3）漸進式簡化算法

14、漸進式簡化算法是一種增量式刪除的簡化方法，從局部到整體進行簡化，如可以通過使用距離控制、角度控制或者面積控制依次對幾何要素的頂點、邊進行簡化操作，最終完成整個要素的簡化。Visvalingam。和Whyatt使用面積作為度量因子對節點剔除，提出了一種線 要素的點剔除簡化方法，可以有效地保留線要素的幾何形態特征并進行簡化。通過線結構中的極值點、拐點、 凸點和單調區間建立線要素的分層結構，提出了一種從局部到整體的漸進方法可以有效進行線要素的簡化，同時考慮了空間拓撲關系避免了要素的自相交。通過剝皮算法， 將線要素以二叉樹進行組織依據彎曲程度實現對線要素的高效簡化。通過節點偏移量，以單調鏈求交的方式對

15、線要素進行簡化實現了線要素的有效簡化。（4）線要素LOD模型針對線要素的LOD模型研究，國內外學者己經提出了多種LOD數據結構如：Strip-Tree、Multi -Scale Line Tree Arc-Tree 和 Binary Line Generalisation Tree（BLGTree）等。Strip-Tree 和 Arc-Tree 解決了任意曲線存儲的問題卻不適用于簡單多段線的存儲。針對多段線的有效存儲問題，提出了 Multi -ScaleLine Tree,它是一個多向樹并引入了離散數量的細節層次，樹中的節點可以有任意數量的子項，實現了多段線的靜態LOD存儲。基于Douglas

16、和Peucker）的線性推廣算法的BLGTree是一個可變比例的線數據結構，BLGTree可以依據閾值動態的獲取簡 化后的線數據，解決了可變比例尺的存儲與動態檢索問題。但 Strip-Tree, Arc-Tree, Multi -ScaleLine Tree和B LGTree都是針對單個要素的存儲，不能用于多個對象的空間組織（索引，聚類），因此只能解決簡化和存儲的部分問題。為避免數據存儲冗余而設計的第一批多尺度矢量數據結構之一是反應性（BinarySpace Partitioning, BSP洶，它支持空間組織和多層次細節展示但它一個靜態的LOD 結構。 Van Oosterom 提出的反應樹

17、是第一個支持地圖對象的空間組織以及多個尺度存儲的動態矢量數據結構。反應樹（The Reactive-Tree磔R樹擴展，反應樹可以有效的表達對象的重要性級別，重要性程度高的對象在樹結構中相應存儲得更高，這使得重要性高的對象更易于訪問，而且反應樹且支持對象的插入與刪除。分析可知，現有線要素LOD繪制方法著重于對幾何要素數據的簡化而沒有慮繪制操作。幾何要素的簡化主要采用增量式刪除或重采樣的方式進行，增量式刪除在原始數據結構進行簡化， 重采樣則會產生新的頂點數據。針對矢量地圖中線幾何要素渲染的需求，線幾何要素必須被剖分成圖形API 支持的基礎圖元，再賦以顏色或者紋理完成線幾何要素的繪制。依據現有的方

18、法，繪制過程中大量的剖分計算導致現有方法在促進矢量地圖的LOD繪制上顯得有心無力。2面幾何要素LOD繪制方法面幾何要素（多邊形）的LOD繪制實現的直接解決方案是將多邊形邊界劃分為多個段，然后使用線的簡化算法對多邊形進行簡化，最終進行繪制操作。針對多邊形幾何模型LOD繪制過程中的簡化操作，國內外學者己經進行了諸多研究，主要有增量式刪除法和采樣法。以下，本文分別進行對上述方法進行詳細的介紹與分析。（ 1 ）增量式刪除增量式刪除方法即每次根據用戶指定的簡化準則在原始模型上選擇一個點進行刪除，對相關區域進行重新組織。這個簡化準則可能僅判斷頂點能否刪除也可能對模型質量的影響給出一個量化的值（誤差度量），

19、通過誤差度量完成對節點剔除、邊折疊或半邊折疊。針對節點剔除的處理，一般使用上文中描述的線簡化算法如DP算法或漸進式簡化算法。提出了一種經典網格簡化算法，首先通過將頂點的分類確定頂點是否可以進行刪除，再依據閾值對頂點進行刪除最終重新三角化，但算法的簡化質量不高。Cohen 提出了簡化信封算法，通過建立信封表面來控制模型頂點的刪除，簡化質量較好但空間開銷巨大，需要對簡化的表面進行重新三角化。針對非平面數據，采用頂點刪除的方法一般難以保證物體表面的光滑，簡化后的結果表面較為粗糙。邊折疊方法則是通過邊的移除操作和相關頂點的合并操作完成，會產生新的頂點，其中以漸進網格方法作為代表。漸進網格方法通過引入邊

20、折疊策略使漸進格網能夠高效地為任意的三角形網格動態創建連續分辨率數據狀態，極大地提高了渲染效率。Qlism 算法則采用二次誤差度量（Quadric Error Metrics, QEM） 表示頂點到平面幾何的距離平方和進行度量誤差，算法在渲染速度與簡化質量之間達到了極大的平衡，可以實現空洞的閉合和物體的合并。半邊折疊方法不同于邊折疊方法，半邊折疊方法通過頂點位置移動和邊移除完成，不產生新的頂點，存儲和運算相對邊折疊方法較低。詳細分析了頂點移除方法、邊折疊方法和半邊折疊方法的區別，驗證了半邊折疊方法的優越性。基于半邊折疊方法提出了一種網格簡化的通用框架，用以支持研究人員定義不同的簡化準則進行簡化

21、操作，在簡化質量和簡化效率上都取得了較好的效果。提出一種實時的漸進網格生成算法，使用堆排序算法將邊折疊的計算成本排序成二叉樹并定義了只考慮局部信息的簡化操作，算法速度得到了很大提升。依據頂點在鄰域的尖銳程度判斷原始節點的重要性提出一種保持特征的格網簡化算法，算法實現簡單且簡化效率較高。分析可知，節點剔除方法需要對簡化后的模型進行三角化操作，效率較低; 邊折疊和半邊折疊方法則著重于高度詳細的幾何模型，適用于如地形數據等特定的GIS數據結構卻沒有考慮到矢量數據的簡化，導致這些方法在促進矢量地圖LOD繪制的能力上顯得不足。（ 2）采樣法采樣法即通過抽取點或生成新的頂點模擬初始模型，試圖通過擬合模型來

22、近似表達原始模型， 采樣法主要研究如何將采樣點合理的分布在表面上以保留原始模型的更多特征。使用規則格網劃分模型，判斷格網內頂點的重要程度，通過選取重要程度較高的點代表柵格中的頂點從而完成模型的簡化，但其簡化質量不高。通過聚類的方式對將頂點的集合采用聚類后的頂點進行代替，該算法運算速度快，簡化效率有所提高。提出基于混合矢量的光柵的方法同時考慮了制圖簡化和渲染。該方法采用GPU緩存來有效地創建 Voronoi圖，以通過像素顏色檢查來輔助多邊形邊界的簡化。由于Voronoi 圖和像素顏色檢查可以通過硬件進行加速，這種方法對于簡化多邊形邊界非常有效，但此方法沒有考慮多邊形填充不適用于矢量地圖的渲染且沒

23、有處理自相交的問題。使用幀緩存技術改進了混合矢量的光柵方法，實現了大規模矢量數據的快速簡化，同時使用模板緩存剔除了Voronoi 圖因自相交而重疊的區域，解決了原有方法存在的自相交問題。（ 3）面要素LOD 模型面要素的LOD模型國內外學者己經進行了諸多研究。基于DP算法提出了一種稱為二叉線性綜合樹（BLGTree）的數據結構，它遞歸地將線劃分為多段線并將多段線組織成二叉樹用于拓撲保持，可以高效地獲取多個尺度的面要素簡化結果。基于R樹結構提出反應樹的存儲結構，實現動態LOD區域劃分。GAP-Tree GAP-Tree是一種廣義區域劃分方法，它通過分層組織區域的手段對面要素進行劃分完成了多尺度下面要素的構建。此外， 針對數據存儲的冗余和碎片化，國內外學者提出了若干對GAP-Tree的改進如tGap-Tree和流暢tGap-Tree,流暢 tGap-Tree 可以用以支持三維數據的快速瀏覽。另外，由于圖形簡