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