摘要： 為解決靜態(tài)和動(dòng)態(tài)細(xì)節(jié)層次模型存在的數(shù)據(jù)冗余度大、精度判斷標(biāo)準(zhǔn)單一和層次切換跳躍感強(qiáng)的問題，提出了基于四叉樹孤立分割和屏幕誤差的地形LOD（level of detail）算法.采用該算法，針對于規(guī)則格網(wǎng)，通過地形瓦片分割和數(shù)據(jù)預(yù)處理減少實(shí)時(shí)階段計(jì)算量，利用四叉樹孤立分割消除結(jié)點(diǎn)間依賴關(guān)系，并構(gòu)建保守性屏幕誤差評價(jià)標(biāo)準(zhǔn)以弱化視覺跳躍感，最后采用添加拆分點(diǎn)和高程平均值法消除相鄰?fù)咂徒Y(jié)點(diǎn)間裂隙.實(shí)驗(yàn)結(jié)果表明：該算法能較好解決常規(guī)方法中存在的問題；可滿足大規(guī)模地形實(shí)時(shí)三維顯示的要求；實(shí)時(shí)顯示計(jì)算量小，幀速可保持在0.03 s以內(nèi).

關(guān)鍵詞： 虛擬現(xiàn)實(shí)；四叉樹；屏幕誤差；裂隙；細(xì)節(jié)層次模型

中圖分類號： P208文獻(xiàn)標(biāo)志碼： ALOD Algorithm of Terrain Based on Conservative

Screen Error and Isolated Division of QuadtreeZHANG Junfeng，YAO Zhihong

（School of Resource and Environment， North China University of Water Resources and Electric Power， Zhengzhou 450011， China）

Abstract：In order to deal with the problems of enormous data redundancy， single evaluation standard of precision and strong scene of jumping at level switch in static and dynamic level of detail models， an algorithm for regular square grid was proposed. This algorithm reduces the complex computation in realtime expression through terrain tile partition and data preprogressing， and eliminates dependencies between nodes using isolated division of quadtree. By building up an evaluation standard based on conservative screen error， jumping feeling is weakened greatly. Finally， cracks between adjacent tiles and nodes are eliminated easily by adding split points and averaging elevation value. Experiment results show that this algorithm has abilities to overcome the shortcoming of the conventional methods and meets the requirements of 3D realtime expression of largescale terrain. Furthermore， amount of calculation for realtime display is small and frame speed is within 0.03 s.

Key words：virtual reality； quadtree； screen error； crack； level of detail model

地形三維場景的實(shí)時(shí)快速顯示是虛擬現(xiàn)實(shí)的基礎(chǔ)內(nèi)容，也是關(guān)鍵的核心環(huán)節(jié)之一[1]，在一般硬件條件下如何實(shí)現(xiàn)實(shí)時(shí)動(dòng)態(tài)顯示一直是一個(gè)重點(diǎn)研究領(lǐng)域，細(xì)節(jié)層次模型（level of detail，LOD）就是其中的典型代表算法.從LOD提出到現(xiàn)在，靜態(tài)LOD是最常用的方法，它多基于金字塔結(jié)構(gòu)或瓦片結(jié)構(gòu)離散生成若干個(gè)精細(xì)度不同的模型副本供實(shí)時(shí)調(diào)用[25]，簡單是其最大優(yōu)點(diǎn)，但模型切換時(shí)視覺跳躍感較強(qiáng)，且在單一時(shí)刻分辨率處處相同，數(shù)據(jù)冗余度很大.針對靜態(tài)LOD的缺點(diǎn)，動(dòng)態(tài)LOD通過自下而上或自上而下的遍歷順序，依據(jù)一定的誤差規(guī)則確定分割或合并次序，地形顯示自由度大，數(shù)據(jù)冗余度較小[69].但由于采用結(jié)點(diǎn)依賴關(guān)系消除裂隙，導(dǎo)致相鄰區(qū)域的結(jié)點(diǎn)層次相互影響，且算法較復(fù)雜，難以用于大規(guī)模地形可視化.另外，各類算法多采用高程幾何差衡量表達(dá)精度，盡管簡單快捷，但隨意性較大，不能很好消除視覺跳躍感.

基于此，作者從規(guī)則格網(wǎng)（regular square grid，RSG）入手，提出了一種快速、高效的自適應(yīng)LOD顯示新算法.該算法采用孤立的四叉樹層次分割方式，使LOD的級別“不受限”，即當(dāng)前地形區(qū)域依據(jù)誤差大小自動(dòng)選擇合適的LOD級別而不受相鄰區(qū)域分割層次的限制，同時(shí)，利用優(yōu)化的預(yù)處理策略和保守性屏幕誤差評價(jià)標(biāo)準(zhǔn)，以減少實(shí)時(shí)階段計(jì)算量，并極大弱化了視覺跳躍感；最后，通過添加拆分點(diǎn)和高程平均值法消除不同LOD層次間的裂隙.1算法設(shè)計(jì)1.1地形瓦片分割及數(shù)據(jù)預(yù)處理為了四叉樹層次分割的方便，RSG的空間分塊要求每一個(gè)地形瓦片包含（2n+1）×（2n+1）個(gè)頂點(diǎn)（不足部分用空值補(bǔ)齊）.同時(shí)，為了后續(xù)瓦西南交通大學(xué)學(xué)報(bào)第48卷第4期張俊峰等：基于四叉樹孤立分割和屏幕誤差的地形LOD算法片間裂隙的處理，要求相鄰?fù)咂蚕?行和1列頂點(diǎn).規(guī)則格網(wǎng)分塊見圖1，圖中9×9的地形被分為4個(gè)5×5的地形瓦片.

圖1RSG的空間分塊

Fig.1Partition of RSG in space

地形實(shí)時(shí)動(dòng)態(tài)顯示的重要指標(biāo)是運(yùn)行速度，算法利用視距和幾何誤差的屏幕投影確定每一幀每個(gè)區(qū)域的LOD級別，視點(diǎn)對于每一幀是不同的，不能夠提前預(yù)知，而結(jié)點(diǎn)的幾何誤差則是固定不變的，因此，提前計(jì)算實(shí)時(shí)階段所需要的參數(shù)是提高顯示速度的關(guān)鍵.針對該問題，算法采用自上而下的四叉樹分割和自下而上的參數(shù)計(jì)算相結(jié)合的預(yù)處理策略.預(yù)處理針對每一個(gè)地形瓦片，采用四叉樹結(jié)構(gòu)按照層次順序得到每一層的各個(gè)結(jié)點(diǎn)，并計(jì)算相關(guān)參數(shù)供實(shí)時(shí)調(diào)用.預(yù)處理的目的僅是得到所有四叉樹結(jié)點(diǎn)及其參數(shù)，而具體需要利用哪些結(jié)點(diǎn)以及裂隙的消除方法，則在可視化階段實(shí)時(shí)判斷.1.2四叉樹孤立分割孤立分割針對的是單一地形瓦片，每個(gè)瓦片內(nèi)的四叉樹結(jié)點(diǎn)依據(jù)精度評價(jià)標(biāo)準(zhǔn)獨(dú)立分割，而不考慮相鄰?fù)咂屯咂瑑?nèi)相鄰結(jié)點(diǎn)的分割層次.當(dāng)結(jié)點(diǎn)滿足精度要求后，將其編號置入渲染列表中等待繪制.當(dāng)所有結(jié)點(diǎn)都滿足精度要求時(shí)，該瓦片區(qū)域整體滿足精度要求，然后依次進(jìn)行下一個(gè)可見瓦片的分割.通過孤立分割，每個(gè)結(jié)點(diǎn)區(qū)域都可以根據(jù)視距及自身的地形起伏情況確定分割層次，從而較好地保持地形模擬逼真度，避免由于結(jié)點(diǎn)間依賴關(guān)系導(dǎo)致的數(shù)據(jù)冗余或精度降低.

整個(gè)可見地形區(qū)域的分割按照自左向右、自上而下的順序進(jìn)行，如圖2所示.設(shè)原始大規(guī)模RSG數(shù)據(jù)按行列分割為m×n個(gè)地形瓦片，在實(shí)時(shí)顯示階段的某一時(shí)刻，視點(diǎn)E可見的瓦片集合A={b11，b12，…，b33}，此時(shí)僅需依次對這些可見瓦片進(jìn)行四叉樹孤立分割，并同步考慮瓦片之間和瓦片內(nèi)部的裂隙出現(xiàn)的位置以及消除方法.如對b22分割時(shí)，由于上鄰b12和左鄰b21先于其分割，而下鄰b32和右鄰b23還未分割，因此能夠判斷的瓦片間裂隙僅在b22與b12、b21的鄰接處出現(xiàn).不過，隨著分割的進(jìn)行，當(dāng)分割b32和b23時(shí)，就可以進(jìn)行相應(yīng)的瓦片間裂隙判斷了.

圖2地形瓦片的依次分割

Fig.2Division of terrain tile in sequence

瓦片內(nèi)部的孤立分割按照四叉樹層次結(jié)構(gòu)遞歸進(jìn)行（可將整個(gè)瓦片看作四叉樹根結(jié)點(diǎn)），當(dāng)同一層次的所有結(jié)點(diǎn)都根據(jù)精度評價(jià)標(biāo)準(zhǔn)判斷是否需要繼續(xù)分割以后，再進(jìn)行下一層次的判斷和分割.因此，當(dāng)前結(jié)點(diǎn)的裂隙同樣也只可能出現(xiàn)在與上鄰和左鄰結(jié)點(diǎn)的鄰接處.1.3結(jié)點(diǎn)精度評價(jià)標(biāo)準(zhǔn)1.3.1保守性幾何誤差

保守性幾何誤差要求采用父結(jié)點(diǎn)模擬地形所產(chǎn)生的最大幾何誤差必須大于采用子結(jié)點(diǎn)模擬地形所產(chǎn)生的最大幾何誤差.只有這樣，才能保證當(dāng)父結(jié)點(diǎn)精度滿足一定閾值時(shí)，所有子結(jié)點(diǎn)必然也滿足精度要求.采用自下而上逐層遞增的計(jì)算方式，設(shè)結(jié)點(diǎn)N1、N2、N3和N4為同層次的4個(gè)葉結(jié)點(diǎn)，N為相應(yīng)的父結(jié)點(diǎn)，Pi（i=1，2，…，25）為原始格網(wǎng)點(diǎn)，如圖3所示.幾何誤差的計(jì)算有以下3種情況：

圖3保守性幾何誤差的計(jì)算

Fig.3Calculation of conservative geometric error

（1） 葉結(jié)點(diǎn)的幾何誤差（l=n，其中，l為當(dāng)前四叉樹結(jié)點(diǎn)的層次，n為四叉樹的總深度）.

葉結(jié)點(diǎn)實(shí)時(shí)繪制時(shí)所需要的頂點(diǎn)均為原始格網(wǎng)點(diǎn)，因此幾何誤差為0.

（2） 非葉結(jié)點(diǎn)的幾何誤差（l=n-1）.

父結(jié)點(diǎn)N實(shí)時(shí)繪制時(shí)用到的9個(gè)頂點(diǎn)Pi（i=1，2，…，9）均屬于原始格網(wǎng)點(diǎn)，不存在插值誤差，但與采用子結(jié)點(diǎn)N1、N2、N3和N4表達(dá)地形的區(qū)別在于，頂點(diǎn)Pj（j=10，11，…，25）處的高程值是插值產(chǎn)生的，這必然與原始格網(wǎng)的高程值有一定誤差.若用Zj表示原始高程值，Zj′表示相應(yīng)位置的內(nèi)插高程值，則頂點(diǎn)Pj的高程誤差ΔZj=Zj-Z′j，最終可取max（ΔZj）為采用結(jié)點(diǎn)N繪制地形所產(chǎn)生的幾何變形.

（3） 非葉結(jié)點(diǎn)的幾何誤差（l∈[1，n-2]）.

該層次結(jié)點(diǎn)的誤差受兩方面的影響：一是相對于子結(jié)點(diǎn)表達(dá)地形引起的誤差，二是子結(jié)點(diǎn)本身的誤差.為了滿足保守性，可取二者的最大值作為結(jié)點(diǎn)的最終幾何誤差.

1.3.2保守性屏幕誤差

三維顯示中，所有物體最終都要投影在視平面上渲染，因此可以認(rèn)為屏幕誤差是影響視覺感受最重要的指標(biāo).在地形可視化中，屏幕誤差指近似網(wǎng)格與原始網(wǎng)格的幾何誤差在屏幕上投影的變形程度，若將該誤差限制在一定范圍內(nèi)，就可以從根本上解決由于LOD層次切換帶來的跳躍感，并將視覺感受維持在可控且適宜的范圍內(nèi).根據(jù)透視投影變換原理，離視點(diǎn)越遠(yuǎn)的物體，在屏幕上的投影越小，反之則越大，其原理如圖4所示.

圖4透視投影變換原理

Fig.4Transfer principle of perspective projection

設(shè)視點(diǎn)的可見角度為α，投影平面的高度為h，世界坐標(biāo)系與屏幕坐標(biāo)系單位長度之比為λ，屏幕誤差閾值為ε.對于幾何誤差為en的結(jié)點(diǎn)，若其中心點(diǎn)到視點(diǎn)的距離為d，且中心點(diǎn)在視線向量上，則按空間幾何關(guān)系，en投影到屏幕上的像素誤差

es=hλen2dtan（α/2） .（1）

進(jìn)一步考慮投影向量與視線方向夾角的影響，設(shè)二者夾角為β，修正式（1）后，得到完整的屏幕誤差投影公式：

es=hλencos β2dtan（α/2） .（2）

實(shí)時(shí)顯示時(shí)，每一幀的視點(diǎn)位置是不同的，對于具體的某一結(jié)點(diǎn)，其屏幕誤差也隨時(shí)改變，式（2）較為復(fù)雜，勢必影響運(yùn)算速度.根據(jù)式（2），某一結(jié)點(diǎn)的分割條件為

hλencos β2dtan（α/2）>ε，（3）

變換式（3），有

dcos β

式（4）中，在投影體參數(shù)和屏幕誤差閾值一定的情況下，后半部分是定值，且可在預(yù)處理中提前計(jì)算，因此實(shí)時(shí)階段僅需計(jì)算視距d以及夾角β，就可以快速確定是否需要細(xì)分.同時(shí)，由于結(jié)點(diǎn)的幾何誤差en滿足保守性質(zhì)，因此在視距一定的情況下，屏幕誤差es也是保守的.另外，為了簡化計(jì)算，也可假設(shè)屏幕誤差不受投影方向的影響，即不考慮夾角β.這樣雖然可能會(huì)導(dǎo)致偏離視線的結(jié)點(diǎn)也需要繼續(xù)分割，從而帶來一定的數(shù)據(jù)冗余，卻可減少實(shí)時(shí)計(jì)算量.1.4地形瓦片內(nèi)部和瓦片之間的裂隙消除三維顯示的某一時(shí)刻需要依次對每個(gè)可見瓦片進(jìn)行四叉樹孤立分割，由于結(jié)點(diǎn)的分割并不受制于相鄰結(jié)點(diǎn)和瓦片的分割層次，因此瓦片內(nèi)部的結(jié)點(diǎn)與相鄰結(jié)點(diǎn)間可能存在裂隙.同樣，瓦片邊界上的結(jié)點(diǎn)與相鄰?fù)咂g也可能存在裂隙，這些裂隙均需在實(shí)時(shí)繪制時(shí)消除.

設(shè)當(dāng)前瓦片內(nèi)某一結(jié)點(diǎn)Na的分割層次為l，從渲染鏈表中可以方便地判斷同層次的上鄰Nb和左鄰Nc的分割情況，即是否達(dá)到了精度要求，是否需要繼續(xù)分割.

Nb和Nc可能出現(xiàn)的分割情況有3種：（1） 需要繼續(xù)分割到l+1層，如圖5（a）所示；（2） 在l層已達(dá)到精度要求不需要繼續(xù)分割，如圖5（b）所示；（3） 在l層之前就已經(jīng)達(dá)到精度要求，如圖5（c）所示.

針對這3種情況，需根據(jù)當(dāng)前結(jié)點(diǎn)的可能分割情況和相鄰結(jié)點(diǎn)分割后的情況區(qū)別對待：對情況（1） ，若Na需要繼續(xù)分割，不需添加拆分點(diǎn)；若不需要繼續(xù)分割，則在相鄰結(jié)點(diǎn)公共邊界中點(diǎn)處，在Na中添加拆分點(diǎn).對情況（2），若Na需要繼續(xù)分割，在相鄰結(jié)點(diǎn)公共邊界中點(diǎn)處，在鄰結(jié)點(diǎn)中添加拆分點(diǎn)；若不需要繼續(xù)分割，則不需添加拆分點(diǎn).對情況（3），鄰結(jié)點(diǎn)向上追溯至待繪制的層次，然后在公共邊界上根據(jù)層次關(guān)系在鄰結(jié)點(diǎn)中添加拆分點(diǎn).

圖5四叉樹相鄰結(jié)點(diǎn)的分割情況

Fig.5Dividing condition of adjacent quadtree nodes

瓦片之間的分割沒有關(guān)聯(lián)，因此，裂隙完全由當(dāng)前瓦片的邊界結(jié)點(diǎn)分割情況決定，見圖6.

圖6相鄰?fù)咂g的裂隙消除

Fig.6Elimination of cracks between adjacent terrain tiles

其中，Ta為當(dāng)前瓦片，Tb和Tc為其上鄰和左鄰，由于相鄰?fù)咂吔缃Y(jié)點(diǎn)的分割層次不同，在點(diǎn)C、D、E、H和J處出現(xiàn)裂隙.邊界結(jié)點(diǎn)的分割層次有2種情況：（1） Ta邊界結(jié)點(diǎn)分割層深大于Tc邊界結(jié)點(diǎn)的分割層深，此時(shí)的裂隙點(diǎn)如C、D、E所示；（2） Ta邊界結(jié)點(diǎn)分割層深小于Tb邊界結(jié)點(diǎn)的分割層深，此時(shí)的裂隙點(diǎn)如H、J所示.

兩種情況的共性是Tb和Tc都已完成分割，不可能在其邊界上添加拆分點(diǎn)，因此只能通過改變當(dāng)前瓦片的邊界高程值或在其上添加拆分點(diǎn)消除裂隙.對情況（1），用高程平均值法，令C、D、E點(diǎn)的高程為點(diǎn)A和B對應(yīng)邊的線性插值，則插值后的C、D、E點(diǎn)必定在邊AB上，從而消除了裂隙.對情況（2），在Ta中添加拆分點(diǎn)H、J，通過將△OFG拆分為△OFH、△OHI、△OIJ和△OJG消除裂隙.

需要說明的是，裂隙消除在每一幀實(shí)時(shí)進(jìn)行，臨時(shí)添加的拆分點(diǎn)和高程值的變化并不會(huì)改變原始RSG瓦片和四叉樹結(jié)點(diǎn)的結(jié)構(gòu).

2實(shí)驗(yàn)及分析實(shí)驗(yàn)1：不同屏幕誤差閾值控制下的地形實(shí)時(shí)自適應(yīng)表達(dá).

屏幕誤差閾值ε控制三維顯示的精度和時(shí)間，設(shè)定的閾值越小，要求的精度越高.實(shí)驗(yàn)針對已有大小為1 025×1 025的RSG數(shù)據(jù)，不進(jìn)行瓦片分割，通過調(diào)整ε，得到不同精度下的地形顯示效果（圖7），表1為相應(yīng)的運(yùn)行參數(shù).從表1可見，隨著ε的減小，實(shí)時(shí)繪制所需的三角形數(shù)目不斷增加，也就是說，越來越多的地形區(qū)域需要細(xì)分到葉結(jié)點(diǎn)層次才能達(dá)到精度要求.利用孤立分割和屏幕誤差可以從根本上保留地形的細(xì)部特征，在平緩區(qū)域多采用低級別結(jié)點(diǎn)，只有在影響視覺感受的地方才自動(dòng)增加表達(dá)層次，因此線框圖中不少相鄰區(qū)域的結(jié)點(diǎn)層次差異較大.

從單幀運(yùn)行時(shí)間看，算法完全可以保證地形的實(shí)時(shí)動(dòng)態(tài)顯示.不過，盡管利用較小的屏幕誤差閾值可以得到更精細(xì)的顯示效果，但這是以犧牲運(yùn)行效率為代價(jià)的，有時(shí)也會(huì)得不償失，因此選擇適當(dāng)?shù)摩乓彩潜ＷC算法成功的關(guān)鍵.實(shí)驗(yàn)表明，屏幕上2～3個(gè)像素的變化不易引起層次切換跳躍感帶來的視覺不適.

圖7不同屏幕誤差閾值控制下的三維表達(dá)

Fig.73D rendering controlled by different screen errors

表1不同屏幕誤差閾值控制下的相關(guān)運(yùn)行參數(shù)

Tab.1Related parameters controlled by different screen errors

地形

范圍預(yù)處理

時(shí)間/s屏幕

誤差ε原始三角形

個(gè)數(shù)P實(shí)時(shí)繪制

三角形個(gè)數(shù)RRP/%實(shí)時(shí)繪制

結(jié)點(diǎn)個(gè)數(shù)單幀繪制

時(shí)間/s1 025×1 02591.2514322 097 1527 2260.348260.01610 6330.501 2160.01917 2510.821 9800.023

實(shí)驗(yàn)2：基于瓦片分割和孤立分割的大規(guī)模地形實(shí)時(shí)自適應(yīng)表達(dá).

實(shí)驗(yàn)采用大小為4 097×4 097的RSG數(shù)據(jù)，通過多次調(diào)整，選擇257×257作為瓦片分割大小，并利用四叉樹孤立分割和相關(guān)的內(nèi)外存調(diào)度、遮擋剔除等加速策略[1012]得到自適應(yīng)顯示效果，見圖8（第1～第6幀并不是漫游過程中流暢顯示時(shí)的連續(xù)幀，而是選擇的相隔較遠(yuǎn)的快照，以便體現(xiàn)算法效果），表2為相關(guān)運(yùn)行參數(shù).

為了更好表現(xiàn)瓦片分割和孤立分割的效果，令視點(diǎn)遠(yuǎn)離地面，并逐漸向后移動(dòng)，從而使單幀載入的瓦片數(shù)較多，且逐步增加，但即使在這種情況下仍然可以流暢運(yùn)行.

在程序初始階段，需要一次性載入大量地形瓦片，導(dǎo)致第1幀時(shí)間較長，不過，由于前后幀之間包含有較多重疊區(qū)，因此只需要利用多線程增量更新

圖8大規(guī)模地形實(shí)時(shí)三維表達(dá)

Fig.83D rendering of largescale terrain可見區(qū)域即可.

實(shí)時(shí)顯示時(shí)，根據(jù)孤立分割深度的不同，分別采用添加拆分點(diǎn)或高程平均值法消除裂隙.從實(shí)時(shí)繪制的三角形個(gè)數(shù)看，在一定的屏幕誤差（ε=3）條件下，LOD和加速算法大大減輕了系統(tǒng)的運(yùn)行負(fù)擔(dān).

為了比較本文算法和常規(guī)算法的不同，對該實(shí)驗(yàn)數(shù)據(jù)進(jìn)行結(jié)點(diǎn)依賴的四叉樹分割，但10 h后預(yù)處理仍未結(jié)束.這主要是因?yàn)樵紨?shù)據(jù)的四叉樹層深為211，結(jié)點(diǎn)達(dá)∑11k=14k個(gè)之巨，再加上大量的參數(shù)計(jì)算，即使高性能電腦也無法順利運(yùn)行.而本文算法中的四叉樹孤立分割是針對單個(gè)地形瓦片，數(shù)據(jù)量小，而且實(shí)時(shí)運(yùn)行階段多線程動(dòng)態(tài)調(diào)度的瓦片數(shù)有限，對速度不會(huì)有大的影響，故單幀運(yùn)行時(shí)間可以保持在0.03 s以內(nèi).

表2大規(guī)模地形實(shí)時(shí)表達(dá)運(yùn)行參數(shù)

Tab.2Related parameters for 3D rendering of largescale terrain

地形

范圍幀

序預(yù)處理

時(shí)間/s分割后

總瓦片數(shù)可見瓦

片數(shù)原始三角形

個(gè)數(shù)P實(shí)時(shí)繪制

三角形個(gè)數(shù)RRP/%單幀繪制

時(shí)間/s4 097×4 09712345610.698256（16×16）12914115116016916933 554 43284 6110.252.7512 110 6890.330.0212 141 4310.420.0192 170 1410.510.0222 184 7100.550.0212 192 3110.570.017

3結(jié)論采用四叉樹孤立分割和保守性屏幕誤差實(shí)現(xiàn)了大規(guī)模地形實(shí)時(shí)自適應(yīng)LOD表達(dá)，獲得以下主要結(jié)論：

（1） 四叉樹孤立分割消除了結(jié)點(diǎn)間的依賴關(guān)系，地形各區(qū)域可以依據(jù)自身誤差確定合適的細(xì)節(jié)層次，而不受相鄰區(qū)域分割層次的限制.

（2） 屏幕誤差評價(jià)標(biāo)準(zhǔn)從根本上解決了層次切換帶來的視覺跳躍感，一般來說，屏幕上2～3個(gè)像素的變化不易引起視覺不適.

（3） 結(jié)合內(nèi)外存多線程調(diào)度、視域裁剪和遮擋剔除等輔助加速策略，實(shí)時(shí)運(yùn)行階段的計(jì)算量和數(shù)據(jù)冗余度都很小，能夠滿足大規(guī)模地形三維快速顯示的需要，幀速可維持在0.03 s以內(nèi).

致謝：作者感謝華北水利水電學(xué)院高層次人才科研啟動(dòng)項(xiàng)目（201206）的資助，感謝審稿專家及編輯提出的寶貴意見.參考文獻(xiàn)：[1]LI Xuanying. A hybrid algorithm for terrain simplification[D]. Vancouver： The University of British Columbia， 2003： 2538.

[2]PAJAROLA R. Large scale terrain visualization using the restricted quadtree triangulation[C]∥Proceedings of 1998 International Conference on Visualization. Washington D C： IEEE Computer Society， 1998： 1926.

[3]PFEIFER N. A subdivision algorithm for smooth 3D terrain models[J]. ISPRS Journal of Photogrammetry and Remote Sensing， 2005， 59（3）： 115127.

[4]RENATO P. Fastmesh： efficient viewdependent meshing[C]∥Proceedings of 2001 International Conference on Computer Graphics and Applications. Washington D C： IEEE Computer Society， 2001： 2230.

[5]印桂生，陳懷友，張菁，等. 基于九宮格的累進(jìn)LOD地形繪制算法[J]. 西南交通大學(xué)學(xué)報(bào)，2010，45（3）： 411417.

YIN Guisheng， CHEN Huanyou， ZHANG Jing， et al. Progressive LOD terrain rendering algorithm based on nine palaces[J]. Journal of Southwest Jiaotong University， 2010， 45（3）： 411417.

[6]LOSASSO F， HOPPE H. Geometry clipmaps： terrain rendering using nested regular grids[J]. ACM Transactions on Graphics， 2004， 23（3）： 769776.

[7]王源，劉建永，江南，等. 視點(diǎn)相關(guān)實(shí)時(shí)LOD地形模型動(dòng)態(tài)構(gòu)網(wǎng)算法[J]. 測繪學(xué)報(bào)，2003，32（1）： 4752.

WANG Yuan， LIU Jianyong， JIANG Nan， et al. A dynamic triangulation algorithm for the viewdependent and realtime LOD model of terrain[J]. Acta Geodaetica et Cartographica Sinica， 2003， 32（1）： 4752.

（下轉(zhuǎn)第677頁）[8]李勝，龔俊峰，劉學(xué)慧，等. 超大規(guī)模地形場景的高性能漫游[J]. 軟件學(xué)報(bào)，2006，17（3）： 535545.

LI Sheng， GONG Junfeng， LIU Xuehui， et al. High performance navigation of very largescale terrain environment[J]. Journal of Software， 2006， 17（3）： 535545.

[9]鄭順義，鄧德彥. 基于三角網(wǎng)無縫拼接的三維重建[J]. 武漢大學(xué)學(xué)報(bào).信息科學(xué)版，2009，34（1）： 1519.

ZHENG Shunyi， DENG Deyan. 3D reconstruction based on seamless contiguity of TIN[J]. Geomatics and Information Science of Wuhan University， 2009， 34（1）： 1519.

[10]孟放，查紅彬. 基于LOD控制與內(nèi)外存調(diào)度的大型三維點(diǎn)云數(shù)據(jù)繪制[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2006，18（1）： 18.

MENG Fang， CHA Hongbin. Rendering of huge pointsampled geometry based on LOD control and outofcore techniques[J]. Journal of ComputerAided Design Computer Graphics， 2006， 18（1）： 18.

[11]馬照亭，潘懋，胡金星，等. 一種基于數(shù)據(jù)分塊的海量地形快速漫游方法[J]. 北京大學(xué)學(xué)報(bào)：自然科學(xué)版，2004，40（4）： 619625.

MA Zhaoting， PAN Mao， HU Jinxing， et al. A fast walkthrough method for massive terrain based on data block partition[J]. Acta Scientiarum Naturalium Universitatis Pekinensis， 2004， 40（4）： 619625.

[12]張小虎，卲永社，葉勤. 基于自適應(yīng)四叉樹的地形LOD算法[J]. 計(jì)算機(jī)應(yīng)用，2009，29（9）： 25962598.

ZHANG Xiaohu， SHAO Yongshe， YE Qin. New LOD method based on adaptive quadtree terrain in visualization[J]. Journal of Computer Applications， 2009， 29（9）： 25962598.