大規(guī)模虛擬地形數(shù)據(jù)多線程異步調度算法

任子健，陳 璐

(1.中車青島四方機車車輛股份有限公司國家高速動車組總成工程技術研究中心,山東 青島 266111；2.中國海洋大學信息科學與工程學院,山東 青島 266100)

0 引 言

大規(guī)模地形的繪制是虛擬自然場景的重要組成部分，雖然地形環(huán)境仿真的研究已經有較長的歷史，但海量地形數(shù)據(jù)的存儲和調度仍然是虛擬現(xiàn)實領域的研究重點和難點。在進行局部小范圍地形的可視化時，高程數(shù)據(jù)和影像數(shù)據(jù)的數(shù)據(jù)量較小，一般不會超過1 GB，計算機可以一次性地載入全部地形數(shù)據(jù)并進行處理和渲染。但在大規(guī)模地形環(huán)境下，地形的數(shù)據(jù)量隨著分辨率的增加成指數(shù)級增長，可以達到TB級甚至PB級。即使不斷地提高計算機的硬件水平，也很難實現(xiàn)海量地形數(shù)據(jù)的組織、存儲、管理、調度和實時繪制。因此，如何利用計算機有限的處理能力實現(xiàn)海量地形數(shù)據(jù)實時調度和渲染已成為一個需要面對的重要問題。

1 大規(guī)模地形數(shù)據(jù)組織與存儲管理

1.1 分層分塊組織策略

在進行虛擬場景的繪制時可以將原始高精度的數(shù)據(jù)全部載入，以保證場景的細節(jié)完整性。但根據(jù)人眼觀察物體的經驗可知，人眼難以看清距離視點較遠區(qū)域的細節(jié)。因此可以設想，在虛擬環(huán)境中進行物體的繪制時，可以由遠及近采用不同的細節(jié)層次。而細節(jié)的精細程度，可以用等級的概念進行量化，等級可以根據(jù)視點與物體之間的距離進行計算，這就是LOD模型的基本思想。金字塔模型是一種多分辨率層次模型[2]，其概念跟LOD模型的思想非常穩(wěn)合。圖1所示為地形影像數(shù)據(jù)金字塔示意圖，圖中不同層級影像所代表的地理區(qū)域范圍相同，而圖像分辨率逐層降低，形式上如金字塔一般。

圖1 地形影像和高程金字塔結構

理論上金字塔各層的分辨率應該是連續(xù)變化的，但實際上沒有必要也很難做到分辨率的連續(xù)性。四叉樹網格兼具結構網格和非結構網格的特性，一方面具有結構網格的正交性特點，另一方面具有非結構網格的靈活性特點，便于網格的自適應化[8]。因此，本文采用傳統(tǒng)的四叉樹結構進行金字塔模型多分辨率網格劃分，如圖2所示。地形數(shù)據(jù)分為DOM影像數(shù)據(jù)和DEM高程數(shù)據(jù)2類。DOM數(shù)據(jù)為圖像格式，而原始DEM數(shù)據(jù)為規(guī)則格網數(shù)據(jù)。由于OpenGL紋理流水線讀入紋理數(shù)據(jù)的速度非常快，因此為了提高DEM數(shù)據(jù)的讀取速度，本文將DEM數(shù)據(jù)處理為32位圖像進行存儲，其中每個DOM瓦片塊分辨率設置為256×256，每個DEM瓦片塊分辨率設置為257×257。

圖2 地形影像和高程數(shù)據(jù)四叉樹結構

隨著層級劃分的增高，地形數(shù)據(jù)總量將以指數(shù)級增長。由于操作系統(tǒng)的限制，海量數(shù)據(jù)的移動、更新、查看會非常困難。文獻[9]采用了一種Scene Graph(SG)的數(shù)據(jù)組織結構對地形金字塔數(shù)據(jù)進行組織，SG中并不存儲實際的地形數(shù)據(jù)，只是作為一個數(shù)據(jù)的屬性描述，在地形渲染時直接讀取內存進行數(shù)據(jù)索引。當數(shù)據(jù)量較大時，SG文件直接讀取內存會占用較大的系統(tǒng)資源，數(shù)據(jù)檢索效率也會極大地下降。本文采用文獻[4]中的方法對切割后的瓦片數(shù)據(jù)進行了再次的數(shù)據(jù)組織。對于空間上連續(xù)的256×256個瓦片數(shù)據(jù)，將其存儲在一個Blockdata文件中，而索引信息存儲在一個對應的Blockindex文件中。Blockindex文件順序存儲瓦片在Blockdata文件中的數(shù)據(jù)偏移量，Blockdata文件順序存儲瓦片數(shù)據(jù)本身及每個瓦片的長度值。Blockdata和Blockidex文件按照所在層級和編號進行命名。這樣通過瓦片的級別、編號就可以讀取相應的瓦片數(shù)據(jù)。通過這種緊湊型的數(shù)據(jù)組織方式，海量瓦片數(shù)據(jù)的更新、遷移和創(chuàng)建將更加方便和快速。

1.2 基于Hilbert填充曲線的存儲優(yōu)化策略

虛擬仿真環(huán)境中的空間數(shù)據(jù)往往是多維數(shù)據(jù)，并且任何一維都不存在一種排序可以完全反映數(shù)據(jù)之間的空間鄰近性，使用傳統(tǒng)方法劃分并存儲空間數(shù)據(jù)會割裂空間記錄之間的內在聯(lián)系，使空間上相鄰的數(shù)據(jù)對象被劃分到不同的存儲空間上[10]。虛擬環(huán)境中進行交互漫游時，往往需要進行實時空間查詢，讀取當前視點及周圍相鄰區(qū)域的空間數(shù)據(jù)。如果空間相鄰的數(shù)據(jù)分布在相隔較遠的不同磁盤頁面中，磁盤的磁頭在讀取數(shù)據(jù)時就需要移動較大的距離，從而增加硬盤尋道時間，降低了空間數(shù)據(jù)的調度效率。并且空間上鄰近的數(shù)據(jù)若存放在不同的Blockdata文件中，當進行連續(xù)數(shù)據(jù)讀取時，系統(tǒng)需要頻繁打開不同文件，這會造成很大的系統(tǒng)開銷。因此，理想的數(shù)據(jù)存儲方式是讓空間上相鄰的數(shù)據(jù)在外存儲器中的邏輯地址也保持相鄰。

對于虛擬環(huán)境中的多維數(shù)據(jù)，通過平面投影可以降維成二維形式。外存中的數(shù)據(jù)一般是線性存儲結構，可以通過一維索引進行檢索。虛擬地形數(shù)據(jù)從三維表達到一維索引的過程可以用空間填充曲線映射方法表示。空間填充曲線又稱為Peano曲線，是一種重要的近似表示方法，它將空間劃分為一個個的網格，對每個網格進行唯一編碼。這樣多維空間數(shù)據(jù)就可以映射到對應投影位置的網格當中，最后降維成一維形式。普通的關系數(shù)據(jù)無法對多維數(shù)據(jù)直接進行查詢，通過使用空間填充曲線對空間實體數(shù)據(jù)集進行降維處理，映射到一維空間進行編碼，就可以重復利用已有的B-樹索引、Hash索引、Bitmap索引等技術針對一維空間進行查詢。理想的空間映射方法是：在多維空間中聚集的空間實體，經過填充曲線編碼以后，在一維空間中是仍然是聚集的[11]。常見的空間填充曲線有：Gray碼填充曲線、row-wise曲線、Z-order曲線和Hilbert曲線等。Abel和Mark等人認為Z-order曲線和Hilbert曲線非常適合多維空間數(shù)據(jù)的存儲[12]。其中Z-order曲線編碼簡單，但Hilbert曲線具有更好的聚集能力。將空間數(shù)據(jù)用Hibert填充曲線填充和編碼，然后將混合層數(shù)據(jù)按Hibert值升序存放到磁盤上，這樣在查詢某一網格數(shù)據(jù)時，可以認為其Hilbert碼相鄰的數(shù)據(jù)被訪問的概率非常大，因此可對其磁盤上邏輯地址相鄰的網格塊進行預讀，這樣可以減少數(shù)據(jù)調度的I/O次數(shù)，從而提高數(shù)據(jù)訪問效率[11]。因此本文采用Hilbert空間填充曲線進行數(shù)據(jù)的存儲優(yōu)化。圖3為Hilbert曲線1～4階填充示意圖，高階曲線填充圖可以由低階曲線填充圖按照反射和旋轉的方法迭代生成[13]。

圖3 Hilbert曲線1～4階填充示意圖

從圖3中可以看出，Hilbert曲線的填充原理跟本文基于四叉樹的瓦片劃分方式十分吻合，完全可以按照Hilbert曲線填充方式對每個地形瓦片進行編碼，最后在外存中按照Hilbert編碼值升序順序存儲瓦片數(shù)據(jù)。具體到本文中，地形瓦片數(shù)據(jù)是以Blockdata和Blockindex為存儲單位進行存儲的，每個Blockdata和Blockindex都由256×256(即24×24)個瓦片數(shù)據(jù)組成。因此，采用8階Hilbert曲線進行編碼和填充即可覆蓋到每個Blockdata和Blockindex中所有的瓦片數(shù)據(jù)。

2 大規(guī)模地形數(shù)據(jù)實時調度

2.1 基于IOCP的地形數(shù)據(jù)異步調度

當?shù)匦螖?shù)據(jù)量較大時，無法一次性載入到計算機內存中，這就需要研究大規(guī)模地形數(shù)據(jù)的實時調度機制。數(shù)據(jù)的“載入+卸載”過程即為數(shù)據(jù)調度過程[14]。海量數(shù)據(jù)的實時調度需要將當前視景體內所需渲染的數(shù)據(jù)讀到內存和顯存當中，而過期的數(shù)據(jù)要及時地卸載，以此保證系統(tǒng)的性能平衡、渲染的流暢和穩(wěn)定。本文設計了基于IOCP的異步策略進行大規(guī)模地形數(shù)據(jù)的實時調度，實現(xiàn)了I/O操作及數(shù)據(jù)加卸載的合理運作。數(shù)據(jù)的加卸載主要通過對瓦片數(shù)據(jù)添加引用計數(shù)來實現(xiàn)，引用計數(shù)為1進行加載操作，引用計數(shù)為0進行卸載操作。如圖4所示為地形瓦片數(shù)據(jù)的調度流程，具體步驟如下：

1)對地形環(huán)境進行空間查詢，其中通過視錐裁剪確定當前幀需要渲染的地形瓦片，通過預測確定在接下來的漫游中需要渲染的地形瓦片。將視錐裁剪和預測確定的瓦片放入當前幀空間查詢瓦片隊列。

2)對當前幀空間查詢瓦片隊列進行遍歷，對于新的瓦片引用計數(shù)初始化為0，然后對每個瓦片的引用計數(shù)加1。此時瓦片的引用計數(shù)有1和2這2種可能。引用計數(shù)為1的為空間查詢后新出現(xiàn)的瓦片，引用計數(shù)為2的是上一幀就已存在的瓦片。對瓦片的引用計數(shù)進行判斷，值為1轉向步驟5，否則進行下一個瓦片塊的處理。

3)當前幀空間查詢瓦片隊列遍歷結束后，接著遍歷上一幀空間查詢瓦片隊列，將此隊列中每個瓦片塊的引用計數(shù)減1。此時隊列中瓦片的引用計數(shù)有0和1這2種值。引用計數(shù)為0說明此瓦片已不再需要，此時更新瓦片塊鏈表，將該數(shù)據(jù)從內存中刪除。引用計數(shù)為1，說明此瓦片同時出現(xiàn)在當前幀和上一幀所需要的集合里，數(shù)據(jù)可以直接從內存中拿來使用。接著進行下一瓦片塊的處理。

4)上一幀空間查詢瓦片隊列遍歷結束后，保存當前結果集，本次地形數(shù)據(jù)調度結束。

5)更新瓦片塊鏈表，并發(fā)送I/O請求到輔線程，輔線程通過直接內存訪問技術從外存中讀取數(shù)據(jù)到內存并進行初始化。

6)由于數(shù)據(jù)讀取和場景漫游渲染在不同線程中進行，剛讀入到內存的數(shù)據(jù)可能已經不在當前幀空間查詢所需要的隊列里了。因此，瓦片塊I/O讀取完成之后需要判斷瓦片塊引用計數(shù)是否為0，如果為0，則更新瓦片塊鏈表，將該數(shù)據(jù)從內存中刪除。此時輔線程數(shù)據(jù)處理結束。

上述步驟中提到的預測數(shù)據(jù)是指不在當前視錐范圍內，但可能出現(xiàn)在接下來視錐范圍內的數(shù)據(jù)?？梢酝ㄟ^當前漫游方向、速度和渲染幀速等計算需要預加載的瓦片數(shù)據(jù)，具體可以參考文獻[15]中的方法，這里不做詳細介紹。在三維可視化程序中，常用的相機漫游方式所使用的空間查詢會有局部重復的特征[16]。因此，在數(shù)據(jù)調度過程中有些數(shù)據(jù)會不斷地被加載、卸載，影響系統(tǒng)性能。通過建立合理的地形數(shù)據(jù)緩存策略，將暫時不需要渲染的預加載數(shù)據(jù)和不斷被重復加、卸載的這部分數(shù)據(jù)放到緩存中管理，可以提高系統(tǒng)運行效率和數(shù)據(jù)的利用率。本文采用LRU緩存算法進行緩存策略設計，緩存結構采用文獻[11,16]中的設計，本文不再贅述。

圖4 地形瓦片數(shù)據(jù)調度流程

在數(shù)據(jù)調度過程中，I/O隊列用來接收主線程發(fā)送過來的I/O請求，輔線程從I/O隊列中提取I/O請求并進行數(shù)據(jù)的讀取。I/O請求的發(fā)送和接收采用異步模式，即當進程將I/O請求發(fā)送到I/O隊列之后，不等待I/O請求的完成，立即返回執(zhí)行后續(xù)程序，大大提高了系統(tǒng)數(shù)據(jù)調度的效率。I/O隊列中的I/O請求處理具有優(yōu)先級。從用戶的心理感知來說，場景由近及遠載入和繪制更容易獲得良好的視覺體驗。而如果按照瓦片數(shù)據(jù)的距離遠近進行排序，必然會大幅增加計算時間，降低系統(tǒng)效率。因此本文按照瓦片LOD等級進行粗略的排序，瓦片LOD等級越高則越優(yōu)先進行I/O請求處理，這樣就基本上滿足了近處場景先載入，遠處場景延遲載入的設計需求。

2.2 基于IOCP線程池的多線程管理

在輔線程數(shù)據(jù)處理階段，采用IOCP的線程池機制進行線程的管理。IOCP的線程池在系統(tǒng)啟動時預先創(chuàng)建好多個子線程，線程的數(shù)目取CPU數(shù)目×2+2[17]。這些子線程一般處于休眠狀態(tài)，當有新的I/O請求時，系統(tǒng)會自動激活一個空閑線程給I/O請求使用。I/O請求完成后該線程回歸線程池并處于休眠狀態(tài)。如果當前沒有空閑線程，則I/O隊列處于等待狀態(tài)，一直等到空閑線程出現(xiàn)為止，如圖5所示。這樣的分配和處理方式比在I/O請求時臨時創(chuàng)建線程更加有效，可以大大提高線程操作的性能和系統(tǒng)的穩(wěn)定性，并且易于管理和控制，較好地實現(xiàn)了系統(tǒng)的負載平衡。

圖5 地形瓦片數(shù)據(jù)調度線程池結構

3 性能分析對比

為了對本文地形數(shù)據(jù)調度算法的性能進行評估，本文選取單線程同步I/O算法與本文算法進行對比分析(地形繪制效果如圖6所示)。為了驗證實驗的有效性，分別對比了2種算法的平均數(shù)據(jù)吞吐量和時間復雜度。實驗的硬件平臺為Intel Core i5-3570K 3.40 GHz處理器，Nvidia GeForce GTX 650顯卡(顯存1 GB)、4 GB內存。首先，以數(shù)據(jù)總量為6 GB的青島市25 km×20 km范圍地形數(shù)據(jù)為測試數(shù)據(jù)，隨機選取了5條漫游路線，在相同視點高度下，以相同速度在三維地形場景中漫游，然后記錄漫游過程中的平均數(shù)據(jù)吞吐量。然后，選擇6 GB，3 GB，1 GB，500 MB和200 MB這5種不同數(shù)據(jù)量的地形數(shù)據(jù)按2種不同算法進行數(shù)據(jù)讀取，統(tǒng)計了算法執(zhí)行總時間。測試結果如表1所示，通過實驗對比分析可以看出，本文算法數(shù)據(jù)實時調度性能優(yōu)異，較單線程同步I/O算法具有更高的數(shù)據(jù)加載速度。

圖6 地形繪制效果

表1 本文算法與單線程同步I/O算法的性能對比

算 法平均數(shù)據(jù)吞吐算法量/(MB/s)算法執(zhí)行總時間/s路線1路線2路線3路線4路線5數(shù)據(jù)量6GB數(shù)據(jù)量3GB數(shù)據(jù)量1GB數(shù)據(jù)量500MB數(shù)據(jù)量200MB單線程同步I/O算法7．88．48．97．38．1716．2345．6114．651．119．5本文算法79．882．186．676．880．770．134．311．35．62．2

4 結束語

近年來，隨著虛擬現(xiàn)實技術的快速發(fā)展，在實際應用中對虛擬地形環(huán)境的規(guī)模和數(shù)據(jù)精度要求越來越高。因此，本文提出了一種面向大規(guī)模虛擬地形環(huán)境的實時數(shù)據(jù)調度算法。首先，在傳統(tǒng)的四叉樹數(shù)據(jù)組織方法基礎上對海量地形瓦片數(shù)據(jù)進行二次組織，并且通過基于Hilbert填充曲線的方法進行了數(shù)據(jù)的存儲優(yōu)化，提高了數(shù)據(jù)更新、遷移和調度的效率。此外，設計了基于IOCP的地形數(shù)據(jù)異步調度機制，實現(xiàn)了海量地形數(shù)據(jù)的高效管理和快速調度。由實驗結果可知，本文算法具有較高的性能優(yōu)勢，適用于大規(guī)模虛擬地形環(huán)境的實時繪。

[1] Zhao Xuesheng, Bai Jianjun, Chen Jun, et al. A seamless visualization model of the global terrain based on the QTM[C]// Proceedings of the 16th International Conference on Advances in Artificial Reality and Tele-Existence. 2006:1136-1145.

[2] 杜瑩. 全球多分辨率虛擬地形環(huán)境關鍵技術的研究 [D]. 鄭州:解放軍信息工程大學, 2005.

[3] Zhang Liqiang, Yang Chongjun, Liu Suhong, et al. Effective techniques for interactive rendering of global terrain surfaces[J]. IEEE Geoscience and Remote Sensing Letters, 2005,2(2):215-219.

[4] Ren Zijian, Ma Cunyong, Huo Peng, et al. Real-time rendering of global multiple-resolution inlaid terrain based on tessellation[J]. Journal of Computational Information Systems, 2015,10(16):5899-5909.

[5] Lebiedz J, Mieloszyk K, Wiszniewski B. Real terrain visualisation with a distributed PC-Cluster[C]// International Conference on Parallel Processing and Applied Mathematics. 2005:349-356.

[6] Hsieh T J, Kuester F, Hutchinson T. Parallel terrain rendering using a cluster of computers[J]. Journal of the Chinese Institute of Engineers, 2013,36(2):212-223.

[7] Olanda R, Pérez M, Ordua J M, et al. Terrain data compression using wavelet-tiled pyramids for online 3D terrain visualization[J]. International Journal of Geographical Information Science, 2014,28(2):407-425.

[8] 關卓威,張曄. 臨近空間平臺下地形四叉樹優(yōu)化分割算法[J]. 南京航空航天大學學報, 2015,47(1):59-63.

[9] 張立民,閆文君. 基于GPU的大規(guī)模地形數(shù)據(jù)繪制算法[J]. 計算機與現(xiàn)代化, 2012(1):145-150.

[10] 周艷,朱慶,張葉廷. 基于Hilbert曲線層次分解的空間數(shù)據(jù)劃分方法[J]. 地理與地理信息科學, 2007,23(4):13-17.

[11] 馬純永. 城域景觀VRGIS一體化仿真平臺研究與實現(xiàn) [D]. 青島:中國海洋大學, 2010.

[12] Abel D J, Mark D M. A comparative analysis of some two-dimensional orderings[J]. International Journal of Geographical Information System, 1990,4(1):21-31.

[13] 陸鋒,周成虎. 一種基于Hilbert排列碼的GIS空間索引方法[J]. 計算機輔助設計與圖形學學報, 2001,13(5):424-429.

[14] 劉向南. 海量城市三維模型網絡異步調度與實時渲染算法研究[D]. 青島:中國海洋大學, 2015.

[15] 王海玲. 虛擬自然場景建模與繪制關鍵技術研究[D]. 哈爾濱：哈爾濱工程大學, 2013.

[16] 周圣川. 大規(guī)模城市場景圖形圖像混合建模與無損渲染技術[D]. 青島:中國海洋大學, 2014.

[17] 王早. 基于IOCP機制的代理模型與負載均衡算法研究[D]. 武漢:武漢科技大學, 2005.