ＰＣ平臺下海量地形的分頁調度和實時渲染

摘 要:結合內存調度技術和場景渲染策略，提出了一種對海量網格和紋理數據進行分割和分頁調度的算法，通過調度算法使海量數據分批進入內存并實現實時卸載，在分頁的基礎上進行分塊實時渲染。實驗結果表明該算法取得了很好的效果。

關鍵詞:分頁調度; 地形塊; 渲染; 實時加/卸載; 幾何紋理貼圖

中圖分類號:TP391.9文獻標志碼:A

文章編號:1001-3695(2009)09-3575-03

doi:10.3969/j.issn.1001-3695.2009.09.109

Massive landscape paging scheuling andreal-time rendering strategy on PC platform

ZHOU Ke， CHEN Lei-ting， HE Ming-yun

(School of Computer Science Engineering， University of Electronic Science Technology of China， Chengdu 610054， China)

Abstract:With the combination of the memory scheduling technique and scene rendering strategy， this paper presented an algorithm for massive data’s partitioning and paging scheduling. The data’s load/unload was a batching processing. Based on paging scheduling， implemented a real-time tiling rendering method. The experimental results show the efficiency of the algorithm.

Key words:paging scheduling; tile; rendering; real-time load/unload; GeoMipMaping

近年來，海量三維地形在戰場仿真、三維網絡游戲、地理信息系統以及飛行駕駛模擬等領域中的應用越來越廣泛。但是，海量地形的渲染數據量是非常驚人的，這就需要對龐大的地形數據進行合適的調度，改變以往一次性將全部地形數據資源加載到內存的方法。一次性加載大量數據會在程序初始化時極大地增加加載響應時間，并在程序運行中占用大部分內存資源。由于外總線傳輸速率與內總線速率相比非常緩慢，數據在內、外存之間拷貝的效率與外總線速率密切相關。CPU的等待時間可能會隨著數據量的增大而增加。分頁加載模式極大地減少了等待時間，采取使用“誰”就加載“誰”的方法，加載一次只占用少量的I/O時間;同時采用預加載策略，把那些可能馬上會被使用的頁面數據也部分加載至內存，這樣既滿足了效率的提高，又實現了漫游不同頁面之間的平滑過渡。

采用分頁調度管理模式，只將當前(或未來短時間內)需要的頁面加載到內存中。經過分割處理后的地形高度數據圖被放入地形分頁數組中，與經過分割的地形紋理等資源數組綁定。這時，以單個頁面為單位的資源組的加載方式將比之前的一次性資源加載方式更節省內存資源，也減少了等待時間。

本文提出的分頁調度策略實現了動態加載地形頁面和基于幾何紋理貼圖的LOD(level of detail，層次細節)的結合，大大優化了一次性調度策略并顯著提高了渲染幀率。理論上，本方法可以實現海量地形數據的實時渲染。基于本方法實現的演示程序，使用了含有復雜地形的16 385×16 385個采樣點的高度圖來產生分頁地形，取得了不錯的渲染效果。

1 分頁調度策略

本文提出的策略方法的核心思想是對海量地形數據進行空間頁面(page)劃分，將地形網格頂點數據劃分為多個page，每個page又包含若干地形塊。Page是地形數據調度的基本單位，每一個地形頁面對應一個材質(material)，并定義了紋理的大小和多重紋理的混合方式。Tile則是地形LOD的基本單位，它負責管理幾何LOD。Page和tile是一種抽象的層次邏輯關系，它們的實際頂點信息和索引頂點信息則保存在可渲染體(renderable)中。Renderable包含實際的vertex/index信息，它實際上是地形tile的幾何表示，與tile是對應關系。地形數據的結構劃分如圖1所示。

在程序的運行過程中，是通過場景攝像機在地形場景中漫游，因此，能看見場景中的哪一部分是由當前的場景攝像機提供的位置和可視范圍等信息決定的。系統根據當前攝像機參數，在每幀作出是否加載或卸載地形頁面的決策(圖2):加載那些將要進入可視區的頁面數據，卸載那些遠離觀察者視點的頁面數據。對于使用過的地形紋理圖片則根據時間就近原則，保存那些可能被重復使用的數據。

1.1 數據結構劃分

整個地形數據被劃分成若干page，每一個page都是場景樹的一個節點，它們的索引值被保存于一個地形頁面二維索引數組(terraPageTable)中，每一個page將會保存自己的X、Z方向索引值:tablex、tablez。Page還會保存自己的上、下、左、右四個鄰居索引，這些索引存儲在鄰居數組(pageNeighbors)里面。同時，page還將知道自己包含了多少個tile，所以它會維護一個整型變量(numberTiles)用來存儲tile的個數。另外，由于需要被實時調度，page的狀態信息也是必不可少的，主要有inited(已初始化)、preloaded(就緒)、textureload(已紋理化)、loaded(已加載)、unloaded(已卸載)。

根據以上幾種狀態，創建四個用于方便調度的地形頁面隊列:加載隊列(qPageLoad)、就緒隊列(qPagePreLoad)、紋理化隊列(qTextureLoad)和卸載隊列(qUnLoad)。相應的地形塊tile也有自己的隊列，即加載隊列(qTileLoad)、就緒隊列(qTilePreLoad)和卸載隊列(qTileUnLoad)。

1.2 動態加載的算法描述

整個地形page的調度就是基于以上隊列的。當應用程序啟動，場景初始化完成后，首先加載第一個page。可以通過當前場景攝像機的位置cameraPos來獲取當前page在二維索引數組中的索引值和page本身的渲染數據并立即顯示，同時將頁面加入qPageLoad隊列中。當加載首個page完成后，開始加載視點周圍的page，并填充qPageLoad和qPagePreLoad隊列。填充隊列的操作每一幀進行一次，這樣可以避免單幀加載過多數據而導致的幀沖擊。

根據當前場景攝像機位置，判斷視點周圍page的狀態，從而進行相應隊列操作的算法描述如下:

a)確定一個相機最遠視距閾值cameraThreshold。上一幀攝像機位置為lastPos，當前位置為pos。如果cameraThreshold<|lastPos.x-pos.x|或cameraThreshold<|lastPos.z-pos.z|并且lastPos不等于pos，表明視點發生了改變，并且在閾值之內，此時需要進行page更新。

(a)獲取當前page以及屬于該page的tiles，并獲取page的索引值。

(b)如果page在qTextureLoad中，則將之移除，并加入到qPageLoad。

(c)更新場景相機位置。

b)如果這一幀攝像機移動出上一幀所在的范圍，及oldPage不等于page，則需要通知page的鄰居們，以確定它們應該屬于qPageLoad還是qPagePreLoad。定義場景中x、z方向page的初始加載數目和最終加載數目分別為iniX(iniZ)、finX(finZ)，初始預加載數目和最終預加載數目為preIniX(preIniZ)、prefinX(prefinZ)。

(a)在preIni到prefin的范圍內逐個取出page，再獲取每個page的索引值。

(b)判斷該page是否在qPageLoad中，如沒有則再判斷該page的索引是否介于iniX(iniZ)與finX(finZ)之間，如是則加入到qPageLoad隊列中。

(c)否則判斷是否在qTextureLoad或qPagePreLoad中，如都沒有，則將其加入到就緒隊列qPagePreLoad中。

c)更新所有已加載的page。

(a)更新攝像機視錐體，以便重新獲取攝像機位置(cameraPos)。通過當前索引與ini和fin比較，通知在范圍內的page進行更新。判斷光照、紋理等是否需要更新，是則更新。

(b)范圍外的page不再更新。

d)根據當前相機位置來加載與page相應的頂點數據renderables的集合。

(a)根據當前的cameraPos，對qTileLoad隊列中的tile進行視點—tile由近及遠排序。

(b)依次取出每一個tile作為地形場景子節點，并與它的實際頂點信息體renderable綁定。

(c)設置當前tile的鄰居索引值。

基于漫游視點的地形頁面動態加載如圖3所示。

1.3 垃圾回收算法

以上的算法模型包含了整個頁面加載的全部過程，即填充加載隊列、就緒隊列和紋理化隊列的全過程。下面要實現的就是頁面卸載算法。

a)檢查qPageLoad隊列中的Page是否應該被卸載。在本算法模型中，設置一個計數器timeUntouched。當計數器大于0時，表明該page在最近幾幀被使用過;當計數器小于等于0時，表明page使用過期，應該被收回。同時設置一個touch操作，每進行一次touch()，就是把timeUntouched計數器重置為初始值。當系統初始化，進行就緒隊列和紋理化隊列加載，加載qPageLoad隊列時都要進行一次計數器重置，而每進行一次untouch()操作則將計數器減一。檢查page是否應該被卸載，就是檢查計數器的值，將計數器值小于等于0的page卸載。

b)同樣檢查qPagePreLoad和qTextureLoad，卸載那些需要被回收的page。

上述回收算法采用的計數器方法有效地對加載/卸載的執行次數進行了限制，就是說只加載/卸載那些應該被執行該操作的page，這樣就把數據操作對程序性能的影響減到最低，使顯示幀率大幅提高。

1.4 調度策略的實現價值

a)對龐大的地形數據進行了分割，便于分批加載的實現。

b)Page、tile和renderable三個邏輯層次結構使地形頁面的索引值與實際的頂點信息和頂點索引信息分離開來，極大地減少了無謂的數據加載，可以節省很多CPU時間和內存容量。

c)加載page以幀為單位分批進行。以不同的page、tile狀態為依據執行不同隊列的填充，只加載那些應該被加載的page，從而構成了一條數據調度流水線，使地形渲染平穩進行，減少了對幀率的沖擊。

d)使用了智能的垃圾回收機制，最近最少使用算法使狀態轉換和無謂卸載減到最低，節省了CPU時間。

2 分塊實時渲染

前面介紹過，地形塊tile是對地形網格更細級別的劃分，一個地形page就是由一個N×N的tile矩陣構成的。Tile同時是地形LOD的基本單位。

在page被加載的同時，它包含的tile和與之對應的rende-rable也同時被加載到內存當中。此時內存中的地形數據仍然是比較龐大的。如果圖形顯卡直接對所有細節進行渲染，三維數據幾何復雜度仍然太高，這就需要在不影響視覺效果的前提下降低數據的幾何復雜度，減少圖形系統實時處理的圖形數量，提高渲染效率。當前，LOD模型是業界廣泛采用的地形幾何數據簡化方法，GeoMipMap算法就是其中一種LOD模型。

本文在tile層次上實施GeoMipMap(幾何紋理貼圖) LOD算法。GeoMipMap算法是Willem de Boer 根據紋理Mip貼圖的概念提出的。紋理Mip貼圖預先計算一系列縮小的紋理圖(1/2、1/4等)，稱為Mip貼圖。在生成紋理時，不同距離的三角形用最接近屏幕尺寸的Mip圖貼圖。根據這個概念，Willem de Boer把整個地形場景在xz平面上進行分塊(block)，如用65×65的block把1025×1025的地形表示為16×16個block。每個分塊可用不同分辨率的網格模型來描述，在同一分塊內，網格模型的分辨率相同，采用隔行采樣的方式生成不同分辨率的網格。

利用此算法要解決的一個問題是:兩個不同分辨率tile相鄰接時會產生幾何裂紋和間隙，這樣會破壞地形連續性。最好的解決方案是改變高細節網格的連接，使其與低細節網格無縫地混合。簡單地說，已經有高細節網格和低細節網格(圖4(a))，只需要重構高細節網格，使其與低細節網格整齊連接即可。只要在高細節網格中跳過一個頂點，就可以保證兩個網格無縫連接不會有間隔，即高細節網格中有一些頂點不用，但結果不會很明顯。

3 實驗和分析結果

本文的成果應用于國家“863”計劃基金項目網絡游戲內容創作平臺的地形編輯器系統當中。采用了由噪聲函數生成的高度圖創建的超大規模地形數據，地形數據被分割為多個1025×1025的page，每個page包含16×16個65×65的tile。在地形中漫游，FPS分別達到了30 fps和110 fps。

實驗結果運行的平臺為:P4 雙核 2.6 GHz CPU，nVidia 8600GT 256 MB顯卡，2 GB內存。實驗效果圖如圖5所示。

實驗結果表明，本文提出的海量地形分頁調度策略和分塊幾何紋理貼圖LOD較好地解決了海量網格數據的實時渲染，這種層次化的調度實現了大量數據的平滑加載，使大規模地形的渲染效率有了很大的提高。

參考文獻:

[1]胡斌，江南，劉琛，等 .基于粗粒度分頁和細粒度分片的大地形動態調度機制研究[J].計算機應用， 2006， 26(Z1):4-7.

[2]李惠，翟磊，林誠凱，等 .一種超大規模地形的實時渲染方法[J].系統仿真學報， 2004， 16(4):736-739.

[3]SPEARS Ⅲ V L. Terrain level of detail in first person-ground perspective simulations[D]. California:Naval Post Graduate School Monterey， 2002.

[4]HOPPE H.Smooth view-dependant level-of-detail control and its application to terrain rendering[EB/OL].(1998). http://research.micorsof.tcom/～hoppe/.

[5]LINDSTROM P， HODGES L F， FAUST N. Real-time， continuous level of detail rendering of height fields[C]// Proc of ACM SIGGRAPH. 1996: 109-118.

[6]趙友兵，石教英，周驥，等.一種大規模地形的快速漫游算法[J].計算機輔助設計與圖形學學報，2002， 14(7):624-628.

[7]馬照亭，潘懋，胡金星，等. 一種基于數據分塊的海量地形快速漫游方法[J].北京大學學報:自然科學版，2004， 40(4):619-625.