??? 摘 要： 介紹了對(duì)傳統(tǒng)的實(shí)時(shí)優(yōu)化自適應(yīng)網(wǎng)格算法" title="實(shí)時(shí)優(yōu)化自適應(yīng)網(wǎng)格算法">實(shí)時(shí)優(yōu)化自適應(yīng)網(wǎng)格算法的改進(jìn)。首先根據(jù)金字塔思想" title="金字塔思想">金字塔思想，對(duì)大數(shù)據(jù)量地形及紋理數(shù)據(jù)進(jìn)行分層分塊預(yù)處理，對(duì)每塊數(shù)據(jù)進(jìn)行細(xì)節(jié)層次處理，并建立統(tǒng)一的空間位置索引，存入磁盤。然后應(yīng)用緩沖區(qū)機(jī)制及多線程思想，結(jié)合該算法，渲染了北京市懷柔水庫三維地形，并進(jìn)行網(wǎng)絡(luò)實(shí)時(shí)漫游，效果理想。
??? 關(guān)鍵詞： 實(shí)時(shí)優(yōu)化自適應(yīng)網(wǎng)格算法? 金字塔思想? 細(xì)節(jié)層次
?
??? 三維場(chǎng)景的實(shí)時(shí)渲染技術(shù)一直是計(jì)算機(jī)圖形學(xué)中研究的熱點(diǎn)，其應(yīng)用領(lǐng)域十分廣泛，如GIS系統(tǒng)、飛行模擬系統(tǒng)、VR系統(tǒng)、視頻游戲以及數(shù)字地球技術(shù)等[1]。特別是隨著數(shù)字地球概念的提出，大規(guī)模數(shù)字高程模型的實(shí)時(shí)可視化技術(shù)顯得尤為重要。然而，龐大的數(shù)據(jù)集對(duì)于目前的圖形硬件設(shè)備仍存在極大的壓力[2]。因此，眾多學(xué)者對(duì)細(xì)節(jié)層次LOD(Level Of Details)這一真正的三維地形渲染技術(shù)進(jìn)行了深入的研究，也得出了許多經(jīng)典的LOD算法，如：連續(xù)LOD(CLOD)、ROAM LOD和分塊LOD（Chunk LOD）等[3]。其中，實(shí)時(shí)優(yōu)化自適應(yīng)網(wǎng)格算法ROAM(Real Time Optimally Adapting Meshes)LOD，以其簡單和可擴(kuò)展性的特點(diǎn)成為地形渲染中廣泛應(yīng)用研究的算法[4]。根據(jù)該算法，本文提出基于金字塔思想改進(jìn)的ROAM算法，以期進(jìn)一步提高大規(guī)模地形實(shí)時(shí)可視化的效率。
1 傳統(tǒng)ROAM算法
1.1 算法思想
??? ROAM描述了一個(gè)基于二元三角樹結(jié)構(gòu)的法則，它包含一個(gè)預(yù)處理過程和幾個(gè)實(shí)時(shí)處理階段。預(yù)處理過程對(duì)三角形二叉樹" title="二叉樹">二叉樹從底至頂進(jìn)行嵌套的、觀察依賴的誤差范圍計(jì)算[4]。其基本思想是：在對(duì)地形進(jìn)行三維渲染時(shí)，依據(jù)視點(diǎn)的位置和視線的方向等多種因素，對(duì)表示地形表面的三角形片元進(jìn)行一系列的基于三角形二叉剖分的分裂與合并，最終形成和原始表面近似且無縫無疊的簡化連續(xù)三角化表面[2]。
1.2 二叉三角樹
??? ROAM算法中的基本數(shù)據(jù)單元就是等腰直角三角形片元，通過從其直角頂點(diǎn)到斜邊遞歸" title="遞歸">遞歸的二叉剖分，形成具有層次結(jié)構(gòu)的二叉三角樹，如圖1所示[5]。其根結(jié)點(diǎn)T(Va,V0,V1)定義為最初的等腰直角三角形，此時(shí)層次L為0。當(dāng)層次L為1時(shí)，將根結(jié)點(diǎn)三角形T分割為T0和T1，分割是遞歸進(jìn)行的，直至達(dá)到希望的細(xì)節(jié)層次[5]。二叉三角樹采用SBinTree結(jié)構(gòu)保存，同時(shí)存儲(chǔ)五個(gè)最基本的數(shù)據(jù)，它們構(gòu)成合并與增加三角形操作的基礎(chǔ)，也是LOD得以實(shí)現(xiàn)的關(guān)鍵所在。每一個(gè)二叉三角樹通過這五個(gè)元素同它周圍的二叉三角樹產(chǎn)生聯(lián)系，只要一個(gè)樹的結(jié)構(gòu)發(fā)生變化，必將影響到整個(gè)地形塊的變動(dòng)[6]，如圖2所示。二叉三角樹數(shù)據(jù)結(jié)構(gòu)如下：
??? struct SBinTree
??? {
????????SBinTree *LeftChild;??//左子樹
??? SBinTree *RightChild;??//右子樹
??? SBinTree *BaseNeighbor;??//底鄰接區(qū)
??? SBinTree *LeftNeighbor;??//左鄰接區(qū)
??? SBinTree *RightNeighbor;?//右鄰接區(qū)
??? }
?
?
1.3 分裂與合并
??? 評(píng)價(jià)體系是決定三角形分裂與合并的標(biāo)準(zhǔn)，評(píng)價(jià)體系與視點(diǎn)的距離和地形本身的粗糙程度兩個(gè)因素有關(guān)。離視點(diǎn)越遠(yuǎn)、地形越平坦，二叉三角樹越淺，就需要對(duì)三角形進(jìn)行合并；反之則進(jìn)行分裂。
??? 分裂與合并是實(shí)現(xiàn)ROAM算法的基本操作。為了避免在分裂與合并的過程中出現(xiàn)裂縫和T形三角形，在操作時(shí)必須記錄三角形片元的拓?fù)潢P(guān)系并動(dòng)態(tài)更新其拓?fù)潢P(guān)系。圖3為二叉三角樹的分裂與合并示意圖[5]。圖中T被分裂為T0和T1，由于其底鄰接區(qū)TB與T位于同一鉆石形中，因此TB也被分裂為TB0和TB1。
?
??? 如果三角形T與其底鄰接區(qū)TB不位于一個(gè)鉆石形中，就不能立即分裂T，必須首先強(qiáng)制分裂TB，依此遞歸遍歷整個(gè)網(wǎng)絡(luò)，直至找到兩個(gè)三角形位于同一鉆石形之中為止，如圖4所示[5]。
?
?
2 基于金字塔思想改進(jìn)的ROAM算法
2.1 算法基本原理
??? 傳統(tǒng)ROAM算法是根據(jù)評(píng)價(jià)體系將整個(gè)地形進(jìn)行LOD處理，三角形的分裂與合并均是在程序運(yùn)行中進(jìn)行的，而且對(duì)紋理數(shù)據(jù)一般都不加處理直接映射到地形數(shù)據(jù)上，這勢(shì)必增加內(nèi)存的開銷，影響運(yùn)行的速度。在大數(shù)據(jù)量三維地形漫游過程中，距離視點(diǎn)較近時(shí)，看到的只是屏幕內(nèi)的地形，無需處理整個(gè)地形；而距離稍遠(yuǎn)、較平坦的地形，只需用較低的細(xì)節(jié)層次便可以得到很好的渲染效果，而無需與陡峭的地形用相同的細(xì)節(jié)層次，即相同的視點(diǎn)距離、不同的地形塊，可以使用不同的分辨率加以顯示，而且地形數(shù)據(jù)大，紋理數(shù)據(jù)也會(huì)很大。基于此，本文提出基于金字塔思想改進(jìn)的ROAM算法，對(duì)三維地形數(shù)據(jù)以及紋理數(shù)據(jù)依金字塔思想進(jìn)行數(shù)據(jù)預(yù)處理，預(yù)處理分為兩步： 數(shù)據(jù)的分層分塊處理和塊內(nèi)的LOD處理。
??? 首先根據(jù)場(chǎng)景數(shù)據(jù)的大小，確定需要分的層數(shù)，上層分辨率小于下層，再從上層到下層進(jìn)行四叉樹剖分，如圖5所示[7]，由此各個(gè)不同層將由不同分辨率的地形塊組成；然后根據(jù)每一層每一塊的分辨率大小以及粗糙程度進(jìn)行LOD處理，直至把每一層的每一塊數(shù)據(jù)寫入磁盤，這些處理都是在渲染前完成。此方法相當(dāng)于建立了三維地形及紋理庫，將與特定區(qū)域相關(guān)的數(shù)據(jù)有效地組織起來，通過空間坐標(biāo)將可視范圍與其范圍內(nèi)的數(shù)據(jù)關(guān)聯(lián)起來，并分配統(tǒng)一的空間位置索引，以便快速調(diào)度三維庫中的數(shù)據(jù)，從而達(dá)到對(duì)整個(gè)地形的無縫漫游[7]。這對(duì)于地形的層次細(xì)節(jié)模型的實(shí)時(shí)建立有著重要的意義。在渲染時(shí)，以塊為單位，根據(jù)視點(diǎn)的位置，調(diào)出相應(yīng)的數(shù)據(jù)塊" title="數(shù)據(jù)塊">數(shù)據(jù)塊。距視點(diǎn)越遠(yuǎn)的地方，渲染的是層數(shù)越高（分辨率?。┑膲K，距視點(diǎn)越近的地方，渲染的則是層數(shù)越低（分辨率大）的塊。計(jì)算出需要渲染的塊后，進(jìn)入渲染管道，最后渲染出三維地形場(chǎng)景。
?
??? 此外，為了提高渲染效率，本文還利用了緩沖區(qū)機(jī)制和多線程調(diào)度的方法。因?yàn)槁瓮ǔＪ窃谀骋粓?chǎng)景的周邊進(jìn)行的，所以剛剛渲染完的數(shù)據(jù)不應(yīng)該立刻卸載，而是存入緩沖區(qū)內(nèi)，當(dāng)后臺(tái)線程獲得預(yù)渲染的數(shù)據(jù)塊，首先查找緩沖區(qū)，如果沒有則繼續(xù)搜索磁盤。
2.2 數(shù)據(jù)的LOD處理
??? 首先確定一個(gè)最大幾何誤差值δ，即觀看最清晰的場(chǎng)景所能接收的誤差。如果地形數(shù)據(jù)分為10層，則第9層數(shù)據(jù)分辨率最高，此時(shí)幾何誤差不超過δ，第8層幾何誤差不超過2δ，第7層幾何誤差不超過4δ，依此類推。
??? 在計(jì)算誤差時(shí)，并不存儲(chǔ)屏幕誤差值，而是存儲(chǔ)某層可以接收的誤差值，即存儲(chǔ)的是每個(gè)點(diǎn)能接收的層數(shù)。這樣做的好處就是能節(jié)省一定的內(nèi)存。因?yàn)檎`差的范圍很大，而層數(shù)是有限的，所以只需很少的字節(jié)來存儲(chǔ)層數(shù)即可。計(jì)算層數(shù)的公式為：
??? Level=|log2(δ+0.5)|
式中，δ為幾何誤差，對(duì)每個(gè)點(diǎn)做完誤差處理后，取塊數(shù)據(jù)內(nèi)點(diǎn)的最大誤差作為此塊數(shù)據(jù)能接收的誤差值。塊數(shù)據(jù)采用Block結(jié)構(gòu)來保存，其結(jié)構(gòu)如下：
??? struct Chunk
??? {
??? int chunkindex; ???? //塊的索引
??? int? eastindex, northindex, westindex, southindex; ?
???????????????????????????? //四個(gè)子節(jié)點(diǎn)的索引
??? unsigned char LOD_level;? ?? //所在的層數(shù)
??? short xindex,zindex;?????? ?? //塊在該層中的位置
??? short min_y,max_y;????? ????????? //該塊的最小高程以
??????????????????????????????????????????? 及最大高程
??? int mesh_pos;??? ?????? ??? //三角網(wǎng)數(shù)據(jù)的位置
??? }
2.3 應(yīng)用實(shí)例
??? 根據(jù)本文所述算法，在1.7GHz CPU、256MB內(nèi)存、32MB顯卡的計(jì)算機(jī)上，應(yīng)用VC++6.0以及OpenGL開發(fā)了2 049×2 049的DEM三維地形渲染的ActiveX控件，將此地形數(shù)據(jù)分為8層，在網(wǎng)絡(luò)上進(jìn)行實(shí)時(shí)漫游，其效果如圖6所示。幀率達(dá)到83fps，而應(yīng)用傳統(tǒng)的ROAM算法，幀率只有60fps。
?
??? 本文提出了一種基于金字塔思想改進(jìn)的ROAM算法。該算法的創(chuàng)新之處在于對(duì)大數(shù)據(jù)量地形及紋理數(shù)據(jù)進(jìn)行分層分塊預(yù)處理和塊內(nèi)LOD預(yù)處理的雙重預(yù)處理，并存入磁盤中，建立統(tǒng)一的空間索引，而且預(yù)處理均是在渲染前完成。當(dāng)程序運(yùn)行時(shí)只需不斷檢索加載數(shù)據(jù)，而且當(dāng)視點(diǎn)移動(dòng)很快時(shí)，CPU消耗也很低，不會(huì)增加系統(tǒng)負(fù)擔(dān)。渲染時(shí)又應(yīng)用了緩沖區(qū)機(jī)制和多線程思想，進(jìn)一步提高了渲染效率。為支持超大數(shù)據(jù)量的地形及紋理數(shù)據(jù)三維渲染提供了一種思想。目前筆者正在進(jìn)行此方面的深入研究。
參考文獻(xiàn)
[1] 黃超超,凌永順,呂相銀. ROAM動(dòng)態(tài)地形渲染算法研究[J]. 計(jì)算機(jī)仿真,2005,22(1):216-219.
[2] 周宏偉,楊平,陳琦. 實(shí)時(shí)地形可視化ROAM算法的分塊改進(jìn)[J]. 測(cè)繪通報(bào),2003,(8):61-63.
[3] 江流長. ROAM地形渲染算法的實(shí)現(xiàn)[J]. 農(nóng)業(yè)網(wǎng)絡(luò)信息,2006,(5):42-44.
[4] 涂超. ROAM算法原理及其應(yīng)用研究[J]. 遼寧工程技術(shù)大學(xué)學(xué)報(bào)，2003,22(2):176-179.
[5] DUCHAINEAU M, WOLINSKY M, SIGETI D E. Realtime optimally adapting meshes[J]. Proceedings of the Conference on Visualization, 1997:81-88.
[6] 解志剛,馬秋禾,趙金萍. 基于二叉樹結(jié)構(gòu)的地形分塊實(shí)時(shí)漫游的研究[J]. 海洋測(cè)繪,2004,24(5):35-38.
[7] 劉修國,張劍波. 基于DEM庫的地表模型實(shí)時(shí)簡化方法[J]. 小型微型計(jì)算機(jī)系統(tǒng),2004,25(2):280-282.