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

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

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


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

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

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

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

    本文詳細(xì)闡述了鉆石節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)，對(duì)基于鉆石節(jié)點(diǎn)的ROAM算法實(shí)現(xiàn)過程中的關(guān)鍵技術(shù)進(jìn)行了分析，并根據(jù)鉆石節(jié)點(diǎn)結(jié)構(gòu)特點(diǎn)，綜合考慮視點(diǎn)與地形粗糙度，提出了合理的節(jié)點(diǎn)誤差計(jì)算公式，最后用OpenGL和VC6.0++進(jìn)行了算法和公式有效性驗(yàn)證。實(shí)驗(yàn)結(jié)果表明，在使用本文提出的節(jié)點(diǎn)誤差公式計(jì)算之后，渲染效率大幅提高，完全滿足交互式漫游的需求。
    基于鉆石節(jié)點(diǎn)的ROAM算法與傳統(tǒng)的ROAM算法相比，鉆石節(jié)點(diǎn)更加對(duì)稱的數(shù)據(jù)結(jié)構(gòu)更適于程序渲染。將其應(yīng)用到灌區(qū)三維系統(tǒng)建模中，實(shí)現(xiàn)三維地形地貌的快速渲染，是進(jìn)一步研究的重點(diǎn)。
參考文獻(xiàn)
[1] 曹敏，楊長興，楊煉.大規(guī)模地形漫游中動(dòng)態(tài)LOD算法研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2008,18(10):187-189.
[2] 魏楠，江南.ROAM算法及其在地形可視化中的應(yīng)用[J].計(jì)算機(jī)工程與科學(xué)，2007,29(2):66-68.
[3] 侯能，黎展勞，韋婷. 基于分塊ROAM算法的設(shè)計(jì)與實(shí)現(xiàn)[J]. 科學(xué)技術(shù)與工程, 2011,11(26):6459-6462.
[4] 楊冠軍，陳洪，朱德海.基于金字塔思想改進(jìn)的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的實(shí)時(shí)動(dòng)態(tài)地形可視化研究[J].計(jì)算機(jī)與現(xiàn)代化，2011(5):57-60.