基于Diamond的ROAM算法研究*

王智利，寧 芊

（四川大學(xué) 電子信息學(xué)院，四川 成都 610065）

飛行模擬系統(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é)點指那些與當(dāng)前鉆石節(jié)點重疊，且細節(jié)層次較低的鉆石節(jié)點。父鉆石節(jié)點分為兩種：一種是位于對角線上的鉆石節(jié)點(圖2中的a0和a2),稱為祖先節(jié)點；另一種是只包含當(dāng)前鉆石節(jié)點的一部分，細節(jié)層次只比當(dāng)前鉆石節(jié)點的細節(jié)層次低一級，稱為父親節(jié)點。圖2中虛線標注的a1和a3即為這類節(jié)點，其中a1為右父親，a3為左父親。

孩子鉆石節(jié)點是那些與當(dāng)前鉆石節(jié)點部分重疊，并且細節(jié)層次比當(dāng)前鉆石節(jié)點高一級的鉆石節(jié)點，如圖3所示。當(dāng)前鉆石節(jié)點的4個孩子鉆石節(jié)點逆時針方向順序為 c0、c1、c2、c3。

鉆石節(jié)點與其父親與孩子之間用指針連接,表示為：d→ai,d→ci(i=0,1,2,3)。

1.1.2 訪問關(guān)鍵技術(shù)

渲染過程中經(jīng)常需要訪問相同細節(jié)層次的鄰居鉆石節(jié)點。假設(shè)d和d0是同一細節(jié)層次的鉆石節(jié)點，并且它們同時是d的右父親節(jié)點a1(指針表示為d→a1)的孩子。假設(shè) d是d→a1第 i(i=0,1,2,3)個孩子，索引表示為a1i，則按照逆時針方向，d0將是 d→a1的第(a1i+1)mod4個孩子。

算法實現(xiàn)過程中，相同細節(jié)層次的鉆石節(jié)點之間的訪問操作十分頻繁。為了提高訪問性能，可以將d作為其右父親 d→a1的第a1i個孩子和d作為其左父親d→a3的第 a3i個孩子的索引,將 a1i、a3i存儲在 d的數(shù)據(jù)結(jié)構(gòu)中。則：

通過c0對角線所在的邊訪問d0可以表示為：

細節(jié)層次增加時，需要為當(dāng)前鉆石節(jié)點增加孩子節(jié)點。為d增加孩子節(jié)點c=d→c0時，首先要判斷c的另外一個父親d0是否存在，如果不存在，則需要遞歸地將d0添加到其父親節(jié)點d→al的孩子節(jié)點中。新添加的孩子c有兩個父親 d和 d0，d是左父親還是右父親與 c的祖先a0的確定有關(guān)。由圖4可以看出，c的祖先有d→a0和 d→al,考慮到 c的父親 d的連接關(guān)系(d→a0)，c→a0取d→a1。接下來，按照逆時針方向，確定出 c的連接關(guān)系如下：

當(dāng)刪除一個鉆石節(jié)點時，如果當(dāng)前鉆石節(jié)點沒有孩子，則只需要將其左右父親中指向該鉆石節(jié)點的孩子指針置為空，表示如下：

如果當(dāng)前鉆石節(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]。

當(dāng)細節(jié)層次低于要求時，尋找分裂優(yōu)先隊列里優(yōu)先級最高的鉆石節(jié)點d，并分裂d，分裂操作如圖5所示。當(dāng)細節(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]提出了一種基于嵌套的世界空間范圍的節(jié)點誤差計算方法，該方法雖然精確，但計算復(fù)雜、速度慢。本文使用了一種基于視點與地形粗糙度的節(jié)點誤差計算方法。在基于視點的LOD算法中，節(jié)點的誤差主要由兩個因素決定：一是節(jié)點到視點的距離;另一個則是地形本身的粗糙程度[9]。

在基于鉆石節(jié)點的ROAM算法中，基本的數(shù)據(jù)結(jié)構(gòu)為鉆石節(jié)點，視點到觀察節(jié)點的距離可以用鉆石節(jié)點中心點的距離到視點距離來表示：

地形粗糙度采用鉆石節(jié)點中心點實際高程值與左右父親實際高程值的平均值計算。用公式表示如下：

實際渲染過程中，對地形的細化與地形粗糙度成正比，與視點到節(jié)點的距離成反比。同時本文還考慮到地形尺寸的影響，得到一個誤差計算公式：

其中MapSize為整個地形的尺寸;C為可調(diào)因子，可根據(jù)實際調(diào)節(jié)，以達到最佳渲染效果。

1.2.4 視錐體裁剪

包圍球的計算基于三角形面片，每個鉆石節(jié)點包括2個三角形。為每一個鉆石節(jié)點計算包圍球半徑時，需要計算鉆石節(jié)點中點分別到4個父親頂點的距離，選出最長的距離作為其包圍球半徑[6]。測試可見性時，將每個鉆石節(jié)點包圍球與視錐體6個平面進行測試，當(dāng)鉆石節(jié)點的包圍球位于視錐體內(nèi)時才進行渲染，以提高渲染速度。

2 算法實現(xiàn)流程

地形初始化之后，首先根據(jù)當(dāng)前視點渲染地形。渲染過程中,當(dāng)鉆石節(jié)點可見性發(fā)生變化時，需要根據(jù)節(jié)點誤差確定已變化的鉆石節(jié)點優(yōu)先級，并放入相應(yīng)的優(yōu)先隊列。當(dāng)判斷地形細節(jié)層次沒有達到要求時，將進行相應(yīng)的分裂或合并操作，由此產(chǎn)生新的鉆石節(jié)點并同樣需要判斷其可見性，然后根據(jù)可見性更新需要渲染的三角形列表，最后將所有需要渲染的三角形渲染到屏幕，渲染過程如圖7所示。

圖7 算法實現(xiàn)流程

3 實驗及分析

本文算法采用VC6.0++和OpenGL來實現(xiàn)。實驗仿真的DEM數(shù)據(jù)量大小為1025×1025。計算機配置為：Intel Celeron CPU 1.73GHz處理器，1GB內(nèi)存,ATI RADEON XPRESS 200M Series集成顯卡，Windows XP操作系統(tǒng)。

圖8所示為只考慮視點，不考慮粗糙度的地形時，鉆石節(jié)點在平坦和粗糙的地方均勻分布。圖9、圖10所示為使用了節(jié)點誤差公式之后的地形，當(dāng)粗糙度大或者距離視點近的地形采用更多的鉆石節(jié)點渲染。在節(jié)點誤差公式中可調(diào)因子C取值不同，而視點相同的情況下，地形顯示的細節(jié)層次不同。由結(jié)果可以看出，渲染當(dāng)前地形C取值為0.001時較為理想。

圖8 使用節(jié)點誤差公式前的地形

圖9 節(jié)點誤差公式C=0.001的地形

圖10 節(jié)點誤差公式C=0.003的地形

圖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.