飛行模擬系統(tǒng)、VR系統(tǒng)、3D游戲及數(shù)字地球等都離不開大規(guī)模地形的實時渲染技術(shù)?？焖俣咝У劁秩镜匦问怯嬎銠C圖形學(xué)的研究熱點，也是三維系統(tǒng)建模的一個關(guān)鍵技術(shù)。

    近年來，真實感DEM數(shù)據(jù)來源豐富、數(shù)據(jù)量龐大、精度高，全分辨率顯示地形可行性已變得簡單易行。因此，模型簡化技術(shù)、多分辨率表示和LOD(Level of Detail)技術(shù)成為近年來研究的熱點[1]?；诙鄬哟渭毠?jié)的實時優(yōu)化自適應(yīng)網(wǎng)格動態(tài)地形渲染算法ROAM(Real—time Optimally Adapting Meshes)憑借其簡單性和可擴展性成為解決海量高程數(shù)據(jù)地形可視化的常用方法[2]; 基于分塊的ROAM算法在處理大規(guī)模數(shù)據(jù)時取得了較好的渲染效率[3];基于金字塔思想的ROAM算法對大數(shù)據(jù)量地形及紋理數(shù)據(jù)進行分層分塊預(yù)處理和塊內(nèi)LOD預(yù)處理，提高了渲染效率[4]。這些，都是基于傳統(tǒng)的ROAM算法進行的改進。傳統(tǒng)意義上的ROAM算法使用Triangle-Bintree實現(xiàn)存儲三角形坐標[5]。
    基于鉆石節(jié)點ROAM算法的基本數(shù)據(jù)結(jié)構(gòu)是鉆石節(jié)點。基本數(shù)據(jù)結(jié)構(gòu)的不同，使基于鉆石節(jié)點的ROAM算法在實現(xiàn)上與傳統(tǒng)ROAM算法存在極大的差異；數(shù)據(jù)結(jié)構(gòu)的更加對稱，使算法擁有更快的渲染速度，在三維系統(tǒng)建模中，有利于提高三維系統(tǒng)的運行效率。本文研究了實現(xiàn)鉆石節(jié)點的基本數(shù)據(jù)結(jié)構(gòu)及算法的關(guān)鍵技術(shù)，并將視點與地形復(fù)雜程序的節(jié)點誤差公式應(yīng)用到算法中，提升了算法渲染速度。
1 基于鉆石節(jié)點的ROAM算法介紹
1.1鉆石節(jié)點數(shù)據(jù)結(jié)構(gòu)
1.1.1基本數(shù)據(jù)結(jié)構(gòu)
    基本鉆石節(jié)點包括唯一一條用于區(qū)分的對角線(對角線將鉆石節(jié)點劃分為2個共斜邊的等腰直角三角形)、一個中心頂點C及其包圍球半徑R[6],如圖1所示。同時，每個鉆石節(jié)點有4個父鉆石節(jié)點和4個孩子鉆石節(jié)點，如圖2、圖3所示。

      對于每個鉆石節(jié)點來說，父鉆石節(jié)點指那些與當前鉆石節(jié)點重疊，且細節(jié)層次較低的鉆石節(jié)點。父鉆石節(jié)點分為兩種：一種是位于對角線上的鉆石節(jié)點(圖2中的a0和a2),稱為祖先節(jié)點；另一種是只包含當前鉆石節(jié)點的一部分，細節(jié)層次只比當前鉆石節(jié)點的細節(jié)層次低一級，稱為父親節(jié)點。圖2中虛線標注的a1和a3即為這類節(jié)點，其中a1為右父親，a3為左父親。


    如果當前鉆石節(jié)點有孩子，則需要對其孩子遞歸地執(zhí)行以上刪除操作[7]。
1.2 算法描述
1.2.1 地形數(shù)據(jù)管理
　　在基于鉆石節(jié)點的ROAM算法中，為使地形更快、更準確地渲染，高程數(shù)據(jù)大小要求為(2N+1)×(2N+1)。
　　本文使用原始數(shù)據(jù)大小為1025×1025的DEM高程數(shù)據(jù)，每個高程點均可視為一個鉆石節(jié)點的中心點。根鉆石節(jié)點的中心點位于(512，512)，且4個父節(jié)點位于地形塊的4個角。事實上，地形塊4個角上的節(jié)點并不是完整意義上的鉆石節(jié)點，稱為“偽鉆石節(jié)點”。引入“偽鉆石節(jié)點”只是為了體現(xiàn)算法的完整性。根鉆石節(jié)點的4個孩子鉆石節(jié)點中心點坐標為(0,512)、(512,0)、(1 024,512)、 (512,1 024)。根鉆石節(jié)點位于0級細節(jié)層次，4個孩子位于1級細節(jié)層次。隨著渲染深度的增加，使得細節(jié)層次增加，需要渲染的鉆石節(jié)點數(shù)也增加。
    每一個L級細節(jié)層次的鉆石節(jié)點在L-1級有2個父親節(jié)點，在L+1級有4個孩子節(jié)點。如果等級L的鉆石節(jié)點的對角線與坐標軸平行/垂直，則等級L+1的鉆石節(jié)點的對角線就與坐標軸形成45°夾角。在處理地形邊界時,將不存在的父鉆石節(jié)點指針設(shè)置為空。
1.2.2 雙隊列優(yōu)先
　    分裂與合并優(yōu)先隊列的引入，避免了ROAM算法每次渲染時都必須從根節(jié)點開始分裂，并且很好地利用了幀與幀之間的相關(guān)性，極大提升了ROAM算法的渲染速度[5]。基于鉆石節(jié)點的ROAM算法,在合并隊列與優(yōu)先隊列中保存的是鉆石節(jié)點的指針，并為每一個鉆石節(jié)點保存一個優(yōu)先級，優(yōu)先級最高的鉆石節(jié)點位于隊列的最前端[6]。
　    當細節(jié)層次低于要求時，尋找分裂優(yōu)先隊列里優(yōu)先級最高的鉆石節(jié)點d，并分裂d，分裂操作如圖5所示。當細節(jié)層次高于要求時，尋找合并優(yōu)先隊列里優(yōu)先級最高的鉆石節(jié)點d，并合并d，合并操作如圖6所示。

1.2.3 節(jié)點誤差
　    傳統(tǒng)ROAM算法中，分裂與合并優(yōu)先級根據(jù)節(jié)點的空間誤差來確定，空間誤差越大，分裂優(yōu)先級越高，合并優(yōu)先級越小。參考文獻[5]和參考文獻[8]提出了一種基

其中MapSize為整個地形的尺寸;C為可調(diào)因子，可根據(jù)實際調(diào)節(jié)，以達到最佳渲染效果。
1.2.4 視錐體裁剪
    包圍球的計算基于三角形面片，每個鉆石節(jié)點包括2個三角形。為每一個鉆石節(jié)點計算包圍球半徑時，需要計算鉆石節(jié)點中點分別到4個父親頂點的距離，選出最長的距離作為其包圍球半徑[6]。測試可見性時，將每個鉆石節(jié)點包圍球與視錐體6個平面進行測試，當鉆石節(jié)點的包圍球位于視錐體內(nèi)時才進行渲染，以提高渲染速度。
2 算法實現(xiàn)流程
　 地形初始化之后，首先根據(jù)當前視點渲染地形。渲染過程中,當鉆石節(jié)點可見性發(fā)生變化時，需要根據(jù)節(jié)點誤差確定已變化的鉆石節(jié)點優(yōu)先級，并放入相應(yīng)的優(yōu)先隊列。當判斷地形細節(jié)層次沒有達到要求時，將進行相應(yīng)的分裂或合并操作，由此產(chǎn)生新的鉆石節(jié)點并同樣需要判斷其可見性，然后根據(jù)可見性更新需要渲染的三角形列表，最后將所有需要渲染的三角形渲染到屏幕，渲染過程如圖7所示。

3 實驗及分析
　本文算法采用VC6.0++和OpenGL來實現(xiàn)。實驗仿真的DEM數(shù)據(jù)量大小為1 025×1 025。計算機配置為：Intel Celeron CPU 1.73 GHz處理器，1  GB內(nèi)存,ATI RADEON
XPRESS 200M Series集成顯卡，Windows XP操作系統(tǒng)。
    圖8所示為只考慮視點，不考慮粗糙度的地形時，鉆石節(jié)點在平坦和粗糙的地方均勻分布。圖9、圖10所示為使用了節(jié)點誤差公式之后的地形，當粗糙度大或者距離視點近的地形采用更多的鉆石節(jié)點渲染。在節(jié)點誤差公式中可調(diào)因子C取值不同，而視點相同的情況下，地形顯示的細節(jié)層次不同。由結(jié)果可以看出，渲染當前地形C取值為0.001時較為理想。
    圖9所示地形每秒渲染的三角形數(shù)目為5 049個，比圖8所示的10 893地形減少了一半左右，渲染幀率從110幀左右提高到200幀左右，并且所示地形基本保持一致。因此，綜合考慮視點與地形粗糙度，可以在提高地形渲染效率的同時，保持原有的地形地貌不變。

    本文詳細闡述了鉆石節(jié)點數(shù)據(jù)結(jié)構(gòu)，對基于鉆石節(jié)點的ROAM算法實現(xiàn)過程中的關(guān)鍵技術(shù)進行了分析，并根據(jù)鉆石節(jié)點結(jié)構(gòu)特點，綜合考慮視點與地形粗糙度，提出了合理的節(jié)點誤差計算公式，最后用OpenGL和VC6.0++進行了算法和公式有效性驗證。實驗結(jié)果表明，在使用本文提出的節(jié)點誤差公式計算之后，渲染效率大幅提高，完全滿足交互式漫游的需求。
    基于鉆石節(jié)點的ROAM算法與傳統(tǒng)的ROAM算法相比，鉆石節(jié)點更加對稱的數(shù)據(jù)結(jié)構(gòu)更適于程序渲染。將其應(yīng)用到灌區(qū)三維系統(tǒng)建模中，實現(xiàn)三維地形地貌的快速渲染，是進一步研究的重點。
參考文獻
[1] 曹敏，楊長興，楊煉.大規(guī)模地形漫游中動態(tài)LOD算法研究[J].計算機技術(shù)與發(fā)展，2008,18(10):187-189.
[2] 魏楠，江南.ROAM算法及其在地形可視化中的應(yīng)用[J].計算機工程與科學(xué)，2007,29(2):66-68.
[3] 侯能，黎展勞，韋婷. 基于分塊ROAM算法的設(shè)計與實現(xiàn)[J]. 科學(xué)技術(shù)與工程, 2011,11(26):6459-6462.
[4] 楊冠軍，陳洪，朱德海.基于金字塔思想改進的ROAM算法[J].電子技術(shù)應(yīng)用,2007,33(8):130-132.
[5] DUCHAINEAU M,WOLINSKY M,DAVID E,et al.ROAMing Terrain: real-time optimally adapting meshes[C]. Proceedings of the Conference on Visualization 97,1997.
[6] POLACK T. Focus on 3D terrain programming[M]. Premier Press, 2002.
[7] LOK M, MARK A. MEMBER D, et al. Realtime optimal adaptation for planetary geometry and texture:4-8 tile hierarchies[J]. IEEE Transactions on Visualization and Computer Graphics, 2005,11(2):6-8.
[8] LOSASSO F, HOPPE H. Geometry clipmaps: terrain rendering using nested regular grids[C]. ACM Siggraph, 2004.
[9] 王金， 楊克儉. 基于ROAM的實時動態(tài)地形可視化研究[J].計算機與現(xiàn)代化，2011(5):57-60.