任子健，陳 璐

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

0 引 言

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

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

1.1 分層分塊組織策略

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

圖1 地形影像和高程金字塔結(jié)構(gòu)

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

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

隨著層級劃分的增高，地形數(shù)據(jù)總量將以指數(shù)級增長。由于操作系統(tǒng)的限制，海量數(shù)據(jù)的移動、更新、查看會非常困難。文獻(xiàn)[9]采用了一種Scene Graph(SG)的數(shù)據(jù)組織結(jié)構(gòu)對地形金字塔數(shù)據(jù)進(jìn)行組織，SG中并不存儲實(shí)際的地形數(shù)據(jù)，只是作為一個數(shù)據(jù)的屬性描述，在地形渲染時直接讀取內(nèi)存進(jìn)行數(shù)據(jù)索引。當(dāng)數(shù)據(jù)量較大時，SG文件直接讀取內(nèi)存會占用較大的系統(tǒng)資源，數(shù)據(jù)檢索效率也會極大地下降。本文采用文獻(xiàn)[4]中的方法對切割后的瓦片數(shù)據(jù)進(jìn)行了再次的數(shù)據(jù)組織。對于空間上連續(xù)的256×256個瓦片數(shù)據(jù)，將其存儲在一個Blockdata文件中，而索引信息存儲在一個對應(yīng)的Blockindex文件中。Blockindex文件順序存儲瓦片在Blockdata文件中的數(shù)據(jù)偏移量，Blockdata文件順序存儲瓦片數(shù)據(jù)本身及每個瓦片的長度值。Blockdata和Blockidex文件按照所在層級和編號進(jìn)行命名。這樣通過瓦片的級別、編號就可以讀取相應(yīng)的瓦片數(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ù)會割裂空間記錄之間的內(nèi)在聯(lián)系，使空間上相鄰的數(shù)據(jù)對象被劃分到不同的存儲空間上[10]。虛擬環(huán)境中進(jìn)行交互漫游時，往往需要進(jìn)行實(shí)時空間查詢，讀取當(dāng)前視點(diǎn)及周圍相鄰區(qū)域的空間數(shù)據(jù)。如果空間相鄰的數(shù)據(jù)分布在相隔較遠(yuǎn)的不同磁盤頁面中，磁盤的磁頭在讀取數(shù)據(jù)時就需要移動較大的距離，從而增加硬盤尋道時間，降低了空間數(shù)據(jù)的調(diào)度效率。并且空間上鄰近的數(shù)據(jù)若存放在不同的Blockdata文件中，當(dāng)進(jìn)行連續(xù)數(shù)據(jù)讀取時，系統(tǒng)需要頻繁打開不同文件，這會造成很大的系統(tǒng)開銷。因此，理想的數(shù)據(jù)存儲方式是讓空間上相鄰的數(shù)據(jù)在外存儲器中的邏輯地址也保持相鄰。

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

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

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

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

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

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

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

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

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

4)上一幀空間查詢瓦片隊(duì)列遍歷結(jié)束后，保存當(dāng)前結(jié)果集，本次地形數(shù)據(jù)調(diào)度結(jié)束。

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

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

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

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

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

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

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

圖5 地形瓦片數(shù)據(jù)調(diào)度線程池結(jié)構(gòu)

3 性能分析對比

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

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

[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)境關(guān)鍵技術(shù)的研究 [D]. 鄭州:解放軍信息工程大學(xué), 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] 關(guān)卓威,張曄. 臨近空間平臺下地形四叉樹優(yōu)化分割算法[J]. 南京航空航天大學(xué)學(xué)報, 2015,47(1):59-63.

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

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

[11] 馬純永. 城域景觀VRGIS一體化仿真平臺研究與實(shí)現(xiàn) [D]. 青島:中國海洋大學(xué), 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]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報, 2001,13(5):424-429.

[14] 劉向南. 海量城市三維模型網(wǎng)絡(luò)異步調(diào)度與實(shí)時渲染算法研究[D]. 青島:中國海洋大學(xué), 2015.

[15] 王海玲. 虛擬自然場景建模與繪制關(guān)鍵技術(shù)研究[D]. 哈爾濱：哈爾濱工程大學(xué), 2013.

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

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