王智利，寧 芊

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

飛行模擬系統(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)格動態(tài)地形渲染算法ROAM(Real—time Optimally Adapting Meshes)憑借其簡單性和可擴(kuò)展性成為解決海量高程數(shù)據(jù)地形可視化的常用方法[2];基于分塊的ROAM算法在處理大規(guī)模數(shù)據(jù)時(shí)取得了較好的渲染效率[3];基于金字塔思想的ROAM算法對大數(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)存儲三角形坐標(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)的更加對稱，使算法擁有更快的渲染速度，在三維系統(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ū)分的對角線 (對角線將鉆石節(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所示。

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

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

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

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

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

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

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

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

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

如果當(dāng)前鉆石節(jié)點(diǎn)有孩子，則需要對其孩子遞歸地執(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級細(xì)節(jié)層次，4個(gè)孩子位于1級細(xì)節(jié)層次。隨著渲染深度的增加，使得細(xì)節(jié)層次增加，需要渲染的鉆石節(jié)點(diǎn)數(shù)也增加。

每一個(gè)L級細(xì)節(jié)層次的鉆石節(jié)點(diǎn)在L-1級有2個(gè)父親節(jié)點(diǎn)，在L+1級有4個(gè)孩子節(jié)點(diǎn)。如果等級L的鉆石節(jié)點(diǎn)的對角線與坐標(biāo)軸平行/垂直，則等級L+1的鉆石節(jié)點(diǎn)的對角線就與坐標(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)先級，優(yōu)先級最高的鉆石節(jié)點(diǎn)位于隊(duì)列的最前端[6]。

當(dāng)細(xì)節(jié)層次低于要求時(shí)，尋找分裂優(yōu)先隊(duì)列里優(yōu)先級最高的鉆石節(jié)點(diǎn)d，并分裂d，分裂操作如圖5所示。當(dāng)細(xì)節(jié)層次高于要求時(shí)，尋找合并優(yōu)先隊(duì)列里優(yōu)先級最高的鉆石節(jié)點(diǎn)d，并合并d，合并操作如圖6所示。

1.2.3 節(jié)點(diǎn)誤差

傳統(tǒng)ROAM算法中，分裂與合并優(yōu)先級根據(jù)節(jié)點(diǎn)的空間誤差來確定，空間誤差越大，分裂優(yōu)先級越高，合并優(yōu)先級越小。參考文獻(xiàn)[5]和參考文獻(xiàn)[8]提出了一種基于嵌套的世界空間范圍的節(jié)點(diǎn)誤差計(jì)算方法，該方法雖然精確，但計(jì)算復(fù)雜、速度慢。本文使用了一種基于視點(diǎn)與地形粗糙度的節(jié)點(diǎn)誤差計(jì)算方法。在基于視點(diǎn)的LOD算法中，節(jié)點(diǎn)的誤差主要由兩個(gè)因素決定：一是節(jié)點(diǎn)到視點(diǎn)的距離;另一個(gè)則是地形本身的粗糙程度[9]。

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

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

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

其中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)先級，并放入相應(yīng)的優(yōu)先隊(duì)列。當(dāng)判斷地形細(xì)節(jié)層次沒有達(dá)到要求時(shí)，將進(jìn)行相應(yīng)的分裂或合并操作，由此產(chǎn)生新的鉆石節(jié)點(diǎn)并同樣需要判斷其可見性，然后根據(jù)可見性更新需要渲染的三角形列表，最后將所有需要渲染的三角形渲染到屏幕，渲染過程如圖7所示。

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

3 實(shí)驗(yàn)及分析

本文算法采用VC6.0++和OpenGL來實(shí)現(xiàn)。實(shí)驗(yàn)仿真的DEM數(shù)據(jù)量大小為1025×1025。計(jì)算機(jī)配置為：Intel Celeron CPU 1.73GHz處理器，1GB內(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í)較為理想。

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

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

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

圖9所示地形每秒渲染的三角形數(shù)目為5 049個(gè)，比圖8所示的10 893地形減少了一半左右，渲染幀率從110幀左右提高到200幀左右，并且所示地形基本保持一致。因此，綜合考慮視點(diǎn)與地形粗糙度，可以在提高地形渲染效率的同時(shí)，保持原有的地形地貌不變。

本文詳細(xì)闡述了鉆石節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)，對基于鉆石節(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)更加對稱的數(shù)據(jù)結(jié)構(gòu)更適于程序渲染。將其應(yīng)用到灌區(qū)三維系統(tǒng)建模中，實(shí)現(xiàn)三維地形地貌的快速渲染，是進(jìn)一步研究的重點(diǎn)。

[1]曹敏，楊長興，楊煉.大規(guī)模地形漫游中動態(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í)動態(tài)地形可視化研究[J].計(jì)算機(jī)與現(xiàn)代化，2011(5):57-60.