三維地形數據結構與調度研究進展?

袁松鶴靳海亮李留磊耿文軒

三維地形數據結構與調度研究進展?

袁松鶴靳海亮李留磊耿文軒

（河南理工大學測繪與國土信息工程學院焦作454000）

地形三維可視化技術是將能夠在二維平面中進行描述的以及無法在二維平面中顯示的地理空間信息轉換到三維環境中，并通過一定的規則將這些信息整合成為三維空間中的一個實體，人們可以通過三維地形可視化技術對事物內部深層次的關系和規律進行挖掘，提高研究成果的可靠性。論文將近幾年國內外學者針對三維地形數據的存儲和調度方面的研究進行了總結和歸納，對于今后研究該領域的技術具有一定的參考價值。

三維地形；三維可視化；Ogre3D；數據簡化：GPU

Class NumberP283

1引言

由于地形高程數據獲取方式越來越先進，地形數據的高程網格精度有了很大的提升，這將為構建高精度虛擬數字場景打下堅實的數據基礎。目前，要求所實現的三維地形場景的規模逐漸地變大，從小區域到城市、國家乃至全球都在建立仿真系統，因此海量增長的地形數據，這必然導致相應的數據存儲需求不能在現有計算機硬件條件上實現，為了使計算機的性能能夠滿足海量地形數據存儲的要求，國內外學者針對地形數據的存儲和調度進行了大量的研究。

2海量地形數據存儲與調度

Lindstrom提出了隔層四叉樹結構和交叉四叉樹結構［1］，通過四叉樹的數據組織方法對地形數據進行管理和繪制，并且利用∏型空間填充曲線法對數據進行重新排列，從而消除數據冗余，通過基于虛擬內存的管理方案，實現了內外存儲空間之間的數據調度。Lindstrom的算法是從所有的數據角度出發，用相對穩健和高效的操作系統來完成頁面動態調度操作。但是需要我們進一步研究的關鍵是，確定一種盡可能減少硬盤動態頁面調度的原始數據存儲方案和設計一種高效的快速確定硬盤中所需頂點位置的索引算法。

Falby是以觀察者視點的移動作為出發點，來進行分辨率選取與層次結構數據調度［2］。因此提出了更為直接的地形動態頁面調度系統。Pajarola以基于移動窗的方案來對地形塊進行調度，通過觀察視點的移動區域來對該區域的地形數據進行獲取計算，從而實現了增量式的地形數據調度［3］。但是也存在一些不足：如果視點在水平或者垂直方向上快速漫游或反復移動時，將會有“抖動”現象出現。如果視點向斜對角方向移動時，所需要傳輸的數據塊數將會增多，這樣會給服務器增加負荷量。唐桂文等［4］首先從金字塔影響、分片分塊的角度出發，組織三維地形數據，并在此基礎上開發了一種空間數據中間件，并通過該中間件對數據庫中的地形數據進行讀寫，實現了三維地形數據的存儲和調度。其優點是地形渲染速度完全達到了實時性的要求，但三維地形數據在存儲時間上比基于文件的管理方式要慢些。適用于基于Web應用的發展趨勢。

溫菊屏等［5］通過多通道圖形輸出地形漫游系統項目為基礎，來研究地形數據的分塊存儲以及動態調整策略，提出的地形數據組織和調度方案，解決了海量數據同計算機有限的硬件水平之間的矛盾，從而使三維地形場景的初始化時間得到了極大縮短，并使大規模連續三維地形的顯示更加平滑和連續。

蔣秉川等［6］基于體素的基本概念以及體素模型所實現的地形表達特點，結合Ogre3D實現了體素模型的三維地形可視化，為實現空間過程模擬建立統一的基于“體”的虛擬地理環境建立了重要的基礎。其優點是能較好地表示空間粒子之間的相互作用關系，適用于表達地理空間過程的動力學機制，進而實現對多尺度地理現象與過程的模擬、分析與預測因此在3DGMS（三維地學模擬信息系統）中應用廣泛。但關鍵問題是底層體素模型的設計，以及基于體素的地理空間表達。吳晨等［7］以傳統多動態地形數據采用磁盤存儲而導致的高頻存取的現勢性數據讀取效率過低的角度出發，提出了MongoDB數據庫支持下內外存儲結合的多時態海量地形數據存儲管理的優化方法，來滿足用戶可視化應用需求以及調度方面的要求，并進一步設計了MongoDB支持的時態數據自動分片以及索引的優化策略，進一步保證用戶所需現勢性數據在內存中快鎖撲捉。李光輝等［8］從大地形海量數據量的角度考慮，提出了地形多分辨率四叉樹模型，對該模型的定義和構成進行了簡單的介紹，構建了模型的具體存儲機制，設計了數據并行多線程調度機制，采用共享內存同步策略，進一步保證了數據處理的高效性和有序性。楊冰等［9］針對全球地形數據提出了一種正八面體球面四元三角的空間剖分方法，來解決兩極區域拼接變形問題。實現了全球模型的無縫拼接。該方法的優點采用了一種新穎的經緯度編碼方式，能夠實現對地形數據的快速檢索和調度，減少了CPU的計算量。但是仍需對海量地形數據壓縮存儲算法以及在實現一定要求的細節層次時精度不夠的問題仍需進一步研究。

岳利群、夏青等［10］結合海量地形數據的特點和實際渲染需求，提出了海量地形數據組織管理的五個影響因素以及五個因素之間的關系，這五個影響因素分別為LOD級別、視覺精度、數據索引速度、三維地形分析精度和系統管理便攜性。為了對地形基礎地形塊的屬性變化對地形繪制產生的影響進行測試，它們將DEM和紋理均設置為三種不同的屬性，從研究結果來看，五個因素的重要性不一樣，研究的順序也有先后，但是清楚表現出了數據組織管理的關鍵之處，五個因素共同提出有利于全面理解海量地形數據的組織管理方法，并且體現了各個要素之間相互交叉、融合和不能孤立存在與發展的特點。

楊靖宇、張永生等［11］以多用戶全球三維仿真為應用背景，研究P2P環境下海量數據的多點并行分發技術。通過依據地理空間的影像分塊、編碼協議和Tracker服務器所維護的資源擁有節點四叉樹索引列表，實現P2P網絡中的快速資源定位；利用基于數據預測、緩沖思想的優先下載策略和用戶節點間的直接數據交換，提高數據分發效率。最后，通過對現有的多用戶三維地形可視化系統進行改造試驗，證明該方法的有效性，但由于在多個用戶節點存在數據副本，可能會造成用戶對數據的非法獲取與任意篡改，因此需要進一步研究數據的安全性問題。

許文波、李莉等［12］首先利用CTS和Vegaprime軟件開發了一個大地形三維仿真系統。系統在對數據進行預處理之后，利用CTS軟件生成虛擬紋理和地形格網，并進行紋理映射。在Vega Prime下引用地形格網和虛擬紋理形成三維的海量大地形場景，并在此基礎上開發了基于MFC平臺的功能模塊，可以成為某些特定行業的三維電子沙盤。解決了在大區域尺度下海量地形數據漫游的難點，為三維仿真系統的研制與應用提供了參考價值。

左志權、陳媛［13］針對傳統四叉樹、八叉樹等數據結構，在解決對于大規模場景漫游存在的瓶頸問題，通過實施多級緩沖機制、采用動態LOD與顯存調度技術，以及引入多核CPU并行計算策略，最終構建出一套與數據大小無關的實時地形繪制算法。隨著數據量的不斷增大，平均繪制速率保持在30幀/s以上，比一般漫游速度高出2～3倍，這種解決方案在海量場景數據和渲染速度方面已取得較好效果，但該方案對計算機性能要求比較高，具有多核CPU并行計算能力。而且基于多核微機平臺的并行渲染系統目前還仍然在研究。

潘少明等［14］針對大規模地形漫游所采用的P2P機制沒有充分考慮數據的存儲特點和時效性，導致節點優選效率不高，服務的時效性不強等問題，提出了一種基于節點分組的P2P海量地形數據共享機制，對P2P節點進行按瓦片分域、按帶寬分組、組內按時效分級的模型。通過實驗原型系統的比較測試表明，本文方法的平均傳輸速率更高，時效性更強。但是其在基于P2P的影像傳輸方面，一是只考慮節點間的物理網絡關系或者只考慮節點的興趣信息，沒有根據空間影像的區域特性將兩者有效結合；二是對于臨近節點選擇方法，大多是基于隨機選擇的方式，缺少對較優鄰近節點和節點間歷史傳輸參數信息的考慮。

殷小靜等［15］針對海量數據存儲與計算機內存不足的問題，提出構建瓦片金字塔模型，并給出了瓦片大小的最優值，提出了一種高效的四叉樹瓦片索引方法，并采用最小二乘和算術編碼對瓦片進行單獨壓縮。最后從地形瓦片預裝載、雙緩存機制、多線程技術、內存優化等方面進行了交互機制優化，并采用Geometry Clipmaps算法進行了地形繪制，以及利用“過渡帶”的方法消除裂縫。實驗結果具有較好的渲染效果和較高的實時性，但是不適用對于動態的地形塊池，而且在實際應用中并沒有真正的減少內存。

李振舉、李學軍等［16］針對海量地形數據在HBase中管理效率不高的問題，提出一種四叉樹和Hilbert編碼相結合的設計思想。其優點提高了數據入庫的速度，降低了地形數據的查詢時間。并且設計了地形數據的物理存儲結構，只需通過行鍵即可調用相應區域的數據信息，方便了用戶的操作。但也存在一些不足，比如復雜的查詢，響應時間比較長。

楊瑩、李雪等［17］針對有效地對海量地形數據進行組織并實現可見數據在內外存之間的實時調度，由此設計了一種矩形二叉樹模型，其優點是能夠保證地形數據很好的連續性，從而降低了每幀訪問的數據量。這種無指針數據索引二叉樹編碼方式，大大降低了海量數據的調度次數，實現數據塊的準確定位。但該論文對地形的管理與繪制是基于細粒度層次細節模型的，即繪制單元為單個三角形，而且隨著GPU并行處理能力的提高，目前該方法并未大范圍實施。

3基于GPU的海量地形數據處理優勢

由于GPU的性能逐漸提高，GPU不僅具備高性能和高質量的圖形處理能力，還適用于通用計算，而且鑒于CPU與GPU之間帶寬的提高，以及GPU可編程能力的不斷強大，GPU逐漸替代CPU完成圖形軟件處理運算。實施基于GPU的地形渲染將極大的提高地形渲染效率。目前，國內對基于GPU的地形數據存儲和傳輸在進行深入地研究。

張兵強［18］為了解決海量數據在地形可視化中存儲和傳輸的壓力，通過構建地形數據多分辨率金字塔模型，采用一種基于塊的GPU實時解壓的高程數據無損壓縮和有損壓縮算法。該算法首先對地形塊數據進行線性預測，其次對高分辨率地形塊的預測誤差采用變長編碼定理，實現對高分辨率地形數據的無損壓縮，不會損失地形細節；而對低分辨率地形塊的預測誤差，采用有損的預測量化編碼，并將在GPU上的快速并行解壓處理流程展現出來。該算法的優點是隨著數據規模的不斷增大可以取得較高的壓縮率，但不足之處是地形塊誤差的計算量較大，耗費時間較長。

李浩等［19］為了充分發揮GPU的批量繪制的性能，提出了把它用在全球格網的快速繪制上。他們把地形數據通過重新編碼存儲在高度圖中，再結合ShaderModel3.0引入的頂點紋理拾取技術，在GPU中進行解碼，得到原始的DEM數據，避免了在CPU上執行頂點緩存的更新，降低了CPU的負擔，能達到實時繪制的要求。但是仍然存在許多問題，比如基于球體剖分會造成兩極的誤差很大，精確性存在差異不能滿足實際需要，仍需進一步研究基于橢球體的剖分。而且在網絡傳輸的及時性方面需要將網絡的帶寬考慮在內。

張立民等［20］針對大規模地形數據繪制的速度以及生成圖像清晰度的問題，從高度場形式的地形數據進行組織、LOD誤差選擇標準、裂縫以及突躍現象的處理、視錐體裁減等各個環節入手，提出合理的解決方案。其研究結果顯示該方法能夠充分利用GPU進行繪制，可以適用于大規模地形數據繪制。

曹巍等［21］提出利用GPU來對地形進行無縫渲染。本文在構建多層次地形網格時采用二叉樹的細分方法，用行、列標號來表示網格模型。首先，將高程數據轉化為便于GPU讀取的高程紋理圖，再通過頂點紋理提取（VTF）技術提取三維真實坐標進行渲染，同時，采用實時優化自適應網格（ROAM）算法的強制拆分法，通過相鄰地形塊控制在一定的等級上來消除裂縫。最后，為了減少向GPU傳遞的數據量，采用Triangle Strip方式進行渲染，使相鄰三角形中公共頂點坐標不必重復傳遞。從實驗分析來看，在保證渲染幀率較高的前提下同時也解決了地形裂縫的問題。但是對于兩等級相差較大的分塊來說該處理方法存在不足。因此王文博等［22］又在此基礎上提出了基于細分著色器的硬件無縫繪制方法。其基本思想是通過利用一種細分著色器進行地形網格細分的層次細節地形渲染算法，并針對外部細分因子對裂縫進行消除。而且通過將四叉樹結構存儲至頂點緩沖區，緩解了CPU與GPU的資源交換。其優點是不需要大量的細分模板，實時漫游甚至回讀過程，細分過程與可編程管線對映，更加順暢。而且能夠得到無縫的大規模地形。

李尚林等［23］提出了一種GPU網格生成的地形可視化方法來解決分塊LOD方法存在的數據傳輸瓶頸問題，并且通過一系列方法設計了一個全球地形可視化系統GTVS，用于全球高精度地形數據與多分辨率高清衛星影像數據的調度與渲染等，該方法的優點是降低了GPU和CPU的工作耦合性，對GPU進行了更友好的設計，但該方法也存在一些不足，比如對GPU的要求更高，必須要到達一定的顯卡支持，而求每個塊的邊界細分是有一定聯系的，故對塊邊界的誤差要求會比較嚴格。

4結語

長期以來，三維地形的可視化技術被廣泛應用于虛擬現實、三維游戲、戰場仿真、飛行模擬、電子地圖、地形漫游等方面的研究重點。通過對當前國內外相關研究的歸納分析，可以看出，當前國內外針對三位地形可視化技術的研究非常廣泛，尤其是基于分形理論的地形模擬非常盛行，但是還缺乏系統性和比較性，具體的實現算法還需要進一步的研究，而且全球地形可視化向著GPU的設計發展，系統將會讓更多的GPU資源用于發展，目前對于海量三維地形數據的高效快速地實時繪制和漫游顯示仍然面領著嚴峻的挑戰。無論是國內外的學者都將該問題作為研究重點。

［1］P Lindstrom，V Pascussi.Visualization of Large Terrains Made Easy［C］//Proceedings of the conference on Visual?ization'01，San Diego，2001.Washington，IEEE Comput?er Society Press：363-370.

［2］J S Falby，M J Zyda，DR Pratt，etal.NPSNET：Hierarchi?cal Data Structures for Realtime Three-dimensional Visu?al Simulation［J］.Computer Graphics，1993，17（1）：65-69.

［3］R Pajarola，M Antonijuan，R Lario.Quad TIN：Quadtree Based Triangulated Irregular Networks［C］//Proceedings of the conference on Visualization'02，Boston.Washing?ton，IEEE Computer Society，2002：95-102.

［4］唐桂文，張慶娟，王功明，等.基于三維GIS的海量地形數據存儲和調度的研究［J］.測繪科學，2008（3）：110-112，120.

TANG Guiwen，ZHANG Qingjuan，WANG Gongming，et al.Research of storage and schedule of huge terrain based on 3D GIS［J］.Science of Surveying and Mapping，2008（3）：110-112，120.

［5］溫菊屏，李利軍.大地形數據存儲和調度方法研究［J］.佛山科學技術學院學報（自然科學版），2007（4）：13-15.

WEN Juping，LI Lijun.Data storage and scheduling of the large-scale terrain［J］.Journalof Foshan University（Natu?ral Science Edition），2007（4）：13-15.

［6］蔣秉川，游雄，夏青.一種基于體素的三維地形可視化方法研究［J］.測繪通報，2013（3）：46-49.

JIANG Bingchuan，YOU Xiong，XIA Qing.Research on a Method of Voxel-based Three-dimensional Terrain Visu?alization［J］.Bulletin of Surveying and Mapping，2013（3）：46-49.

［7］吳晨，朱慶，張葉廷，等.基于MongoDB數據庫的多時態地形數據存儲管理優化方法［J］.地理信息世界，2014（4）：37-42.

WU Chen，ZHU Qing，ZHANG Yeting，et al.Storage Man?agement Optimization Method for Multi-Temporal Terrain Data Based on MongoDB Database［J］.Geomatics World，2014（4）：37-42.

［8］李光輝，邵偉，吳東亞.基于OSG的大地形并行快速調度問題研究［J］.系統仿真學報，2013（S1）：282-285，296.

LI Guanghui，SHAO Wei，WU Dongya.Research of Large Terrain Multithreading Fast Scheduling Based on OSG［J］. Journalof System Simulation，2013（S1）：282-285，296.

［9］楊冰，譚力恒，魏迎梅.基于連續球面剖分的全球地形數據組織模型［J］.系統仿真學報，2012（1）：150-153.

YANG Bing，TAN Liheng，WEI Yingmei.Global Terrain Data Model Based on Continuous Spherical Grid［J］.Jour?nalof System Simulation，2012（1）：150-153.

［10］岳利群，夏青，王洪威，等.大規模三維地形可視化中數據組織管理影響因素探討［J］.測繪科學，2010（5）：158-160.

YUE Liqun，XIA Qing，WANG Hongwei，et al.Research on the affect factor of data organization and management in large-scale terrain visualization［J］.Science of Survey?ing and Mapping，2010（5）：158-160.

［11］楊靖宇，張永生，蔡暢.多用戶全球三維仿真的數據組織與調度研究［J］.系統仿真學報，2011（9）：1896-1899.

YANG Jingyu，ZHANG Yongsheng，CAI Chang.Study of Data Organization and Scheduling Method in Multi-user Accessed Global 3D Visualization Application［J］.Jour?nalof System Simulation，2011（9）：1896-1899.

［12］許文波，李莉，周虹霞，等.海量地形三維仿真系統的設計與實現［J］.電子科技大學學報，2011（3）：418-423.

XU Wenbo，LI Li，ZHOU Hongxia，et al.The Design and Implemention ofa Large Area Terrain 3D Simulation Sys?tem［J］.Journal of University of Electronic Science and Technology of China，2011（3）：418-423.

［13］左志權，陳媛.TB級地形數據實時漫游核心算法研究［J］.中國圖象圖形學報，2010（9）：1411-1415.

ZUO Zhiquan，CHEN Yuan.Research on kernel algo?rithm of real-time rendering based on TB lever terrain data［J］.Journal of Image and Graphics，2010（9）：1411-1415.

［14］潘少明，喻占武，王浩.基于節點分組的P2P海量地形數據共享機制［J］.武漢大學學報（信息科學版），2009（6）：650-653.

PAN Shaoming，YU Zhanwu，WANG Hao.Massive Ter?rain Data Sharing in Pyramid Hierarchical Peer-to-Peer Networks［J］.Geomatics and Information Science of Wu?han University，2009（6）：650-653.

［15］殷小靜，慕曉冬，徐義文，等.海量地形數據的管理和交互策略優化［J］.計算機應用，2011（9）：2465-2467.

YIN Xiaojing，MU Xiaodong，XU Wenyi，etal.Optimized management and interactive strategy for massive terrain data.［J］.Journal of Computer Applications，2011（9）：2465-2467.

［16］李振舉，李學軍，謝劍薇，等.基于HBase的海量地形數據存儲［J］.計算機應用，2015（7）：1849-1853.

LI Zhenju，LIXuejun，XIE Jianwei，etal.Massive terrain data storage based on HBase［J］.Journal of Computer Applications，2015（7）：1849-1853.

［17］楊瑩，李雪，楊蕊.矩形二叉樹實現海量地形數據組織與管理［J］.計算機工程與應用，2009（20）：169-172.

YANG Ying，LI Xue，YANG Rui.Organization and man?agement of massive terrain dataset using rectangular bin?tree［J］.Computer Engineering and Applications，2009（20）：169-172.

［18］張兵強，姜本清，方君.GPU快速解壓的多分辨率地形高程數據壓縮算法［J］.計算機應用研究，2015（11）：3513-3517，3520.

ZHANG Bingqiang，JIANG Benqing，FANG Jun.Multi resolution terrain height field data compression for rapid GPU decoding［J］.Application Research of Computers，2015（11）：3513-3517，3520.

［19］李浩，相恒茂，孫久虎.基于GPU的全球地形數據加速繪制技術研究［J］.山東國土資源，2015（7）：59-64，71.

LI Hao，XIANG Hengmao，SUN Jiuhu.Research on Ac?celerated Rendering Technique of Global Terrain Based on GPU［J］.Land and Resources in Shandong Province，2015（7）：59-64，71.

［20］張立民，閆文君.基于GPU的大規模地形數據繪制算法［J］.計算機與現代化，2012（1）：145-150.

ZHANG Limin，YAN Wenjun.A Method of Real-time Rendering for Large Terrain Based on GPU［J］.Comput?er and Modernization，2012（1）：145-150.

［21］曹巍，段光耀.基于二叉樹和GPU的無縫地形場景渲染方法［J］.計算機應用，2012（9）：2548-2552.

CAO Wei，DUAN Guangyao.Seamless terrain rendering method based on binary tree and GPU［J］.Journal of Computer Applications，2012（9）：2548-2552.

［22］王文博，殷宏，解文彬，等.基于硬件細分的層次細節地形渲染算法［J］.計算機應用，2015（6）：1716-1719，1729.

WANG Wenbo，YIN Hong，XIE Wenbin，et al.Terrain rendering for level of detail based on hardware tessella?tion［J］.Journal of Computer Applications，2015（6）：1716-1719，1729.

［23］李尚林，鄭利平，張迎凱，等.GPU Tessellation全球地形可視化方法［J］.中國圖象圖形學報，2015（10）：1412-1421.

LI Shanglin，ZHENG Liping，ZHANG Yingkai，et al. GPU Tessellation method of global terrain visualization［J］.Journal of Image and Graphics，2015（10）：1412-1421.

Research Progress of 3D Terrain Data Structure and Scheduling

YUAN Songhe JIN Hailiang LILiulei GENG Wenxuan
（Schoolof Surveying and Land Information Engineering，Henan Polytechnic University，Jiaozuo 454000）

Three-dimensional（3D）Terrain visualization technology can transform geospatial information that can or can not described in the two-dimensional plane into 3D environment and integrate the information into an 3D entity by some rules.People can min Internalrelations and rules ofthings to improve reliability of research results by the technology.This paper summarizes and induces research achievements of recent years based on 3D data storage and scheduling by domestic and overseas scholars，which has a certain reference value for the future technology research in this field.

3D terrain，3D visualization，Ogre3D，data reduction，GPU

P283

10.3969/j.issn.1672-9722.2017.08.037

2017年2月9日，

2017年3月23日

國家自然科學基金項目：海量地形數據無冗余存儲模型及并行繪制研究（編號：41541011）資助。

袁松鶴，女，碩士研究生，研究方向：三維地形可視化。靳海亮，男，博士后，教授，碩士生導師，研究方向：三維地形可視化。