基于四叉樹孤立分割和屏幕誤差的地形LOD算法

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

關鍵詞： 虛擬現實；四叉樹；屏幕誤差；裂隙；細節層次模型

中圖分類號： P208文獻標志碼： 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

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

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

圖1RSG的空間分塊

Fig.1Partition of RSG in space

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

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

圖2地形瓦片的依次分割

Fig.2Division of terrain tile in sequence

瓦片內部的孤立分割按照四叉樹層次結構遞歸進行（可將整個瓦片看作四叉樹根結點），當同一層次的所有結點都根據精度評價標準判斷是否需要繼續分割以后，再進行下一層次的判斷和分割.因此，當前結點的裂隙同樣也只可能出現在與上鄰和左鄰結點的鄰接處.1.3結點精度評價標準1.3.1保守性幾何誤差

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

圖3保守性幾何誤差的計算

Fig.3Calculation of conservative geometric error

（1） 葉結點的幾何誤差（l=n，其中，l為當前四叉樹結點的層次，n為四叉樹的總深度）.

葉結點實時繪制時所需要的頂點均為原始格網點，因此幾何誤差為0.

（2） 非葉結點的幾何誤差（l=n-1）.

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

（3） 非葉結點的幾何誤差（l∈[1，n-2]）.

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

1.3.2保守性屏幕誤差

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

圖4透視投影變換原理

Fig.4Transfer principle of perspective projection

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

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

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

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

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

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

變換式（3），有

dcos β

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

設當前瓦片內某一結點Na的分割層次為l，從渲染鏈表中可以方便地判斷同層次的上鄰Nb和左鄰Nc的分割情況，即是否達到了精度要求，是否需要繼續分割.

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

針對這3種情況，需根據當前結點的可能分割情況和相鄰結點分割后的情況區別對待：對情況（1） ，若Na需要繼續分割，不需添加拆分點；若不需要繼續分割，則在相鄰結點公共邊界中點處，在Na中添加拆分點.對情況（2），若Na需要繼續分割，在相鄰結點公共邊界中點處，在鄰結點中添加拆分點；若不需要繼續分割，則不需添加拆分點.對情況（3），鄰結點向上追溯至待繪制的層次，然后在公共邊界上根據層次關系在鄰結點中添加拆分點.

圖5四叉樹相鄰結點的分割情況

Fig.5Dividing condition of adjacent quadtree nodes

瓦片之間的分割沒有關聯，因此，裂隙完全由當前瓦片的邊界結點分割情況決定，見圖6.

圖6相鄰瓦片間的裂隙消除

Fig.6Elimination of cracks between adjacent terrain tiles

其中，Ta為當前瓦片，Tb和Tc為其上鄰和左鄰，由于相鄰瓦片邊界結點的分割層次不同，在點C、D、E、H和J處出現裂隙.邊界結點的分割層次有2種情況：（1） Ta邊界結點分割層深大于Tc邊界結點的分割層深，此時的裂隙點如C、D、E所示；（2） Ta邊界結點分割層深小于Tb邊界結點的分割層深，此時的裂隙點如H、J所示.

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

需要說明的是，裂隙消除在每一幀實時進行，臨時添加的拆分點和高程值的變化并不會改變原始RSG瓦片和四叉樹結點的結構.

2實驗及分析實驗1：不同屏幕誤差閾值控制下的地形實時自適應表達.

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

從單幀運行時間看，算法完全可以保證地形的實時動態顯示.不過，盡管利用較小的屏幕誤差閾值可以得到更精細的顯示效果，但這是以犧牲運行效率為代價的，有時也會得不償失，因此選擇適當的ε也是保證算法成功的關鍵.實驗表明，屏幕上2～3個像素的變化不易引起層次切換跳躍感帶來的視覺不適.

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

Fig.73D rendering controlled by different screen errors

表1不同屏幕誤差閾值控制下的相關運行參數

Tab.1Related parameters controlled by different screen errors

地形

范圍預處理

時間/s屏幕

誤差ε原始三角形

個數P實時繪制

三角形個數RRP/%實時繪制

結點個數單幀繪制

時間/s1 025×1 02591.2514322 097 1527 2260.348260.01610 6330.501 2160.01917 2510.821 9800.023

實驗2：基于瓦片分割和孤立分割的大規模地形實時自適應表達.

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

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

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

圖8大規模地形實時三維表達

Fig.83D rendering of largescale terrain可見區域即可.

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

為了比較本文算法和常規算法的不同，對該實驗數據進行結點依賴的四叉樹分割，但10 h后預處理仍未結束.這主要是因為原始數據的四叉樹層深為211，結點達∑11k=14k個之巨，再加上大量的參數計算，即使高性能電腦也無法順利運行.而本文算法中的四叉樹孤立分割是針對單個地形瓦片，數據量小，而且實時運行階段多線程動態調度的瓦片數有限，對速度不會有大的影響，故單幀運行時間可以保持在0.03 s以內.

表2大規模地形實時表達運行參數

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

地形

范圍幀

序預處理

時間/s分割后

總瓦片數可見瓦

片數原始三角形

個數P實時繪制

三角形個數RRP/%單幀繪制

時間/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結論采用四叉樹孤立分割和保守性屏幕誤差實現了大規模地形實時自適應LOD表達，獲得以下主要結論：

（1） 四叉樹孤立分割消除了結點間的依賴關系，地形各區域可以依據自身誤差確定合適的細節層次，而不受相鄰區域分割層次的限制.

（2） 屏幕誤差評價標準從根本上解決了層次切換帶來的視覺跳躍感，一般來說，屏幕上2～3個像素的變化不易引起視覺不適.

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

致謝：作者感謝華北水利水電學院高層次人才科研啟動項目（201206）的資助，感謝審稿專家及編輯提出的寶貴意見.參考文獻：[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]印桂生，陳懷友，張菁，等. 基于九宮格的累進LOD地形繪制算法[J]. 西南交通大學學報，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]王源，劉建永，江南，等. 視點相關實時LOD地形模型動態構網算法[J]. 測繪學報，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.

（下轉第677頁）[8]李勝，龔俊峰，劉學慧，等. 超大規模地形場景的高性能漫游[J]. 軟件學報，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]鄭順義，鄧德彥. 基于三角網無縫拼接的三維重建[J]. 武漢大學學報.信息科學版，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控制與內外存調度的大型三維點云數據繪制[J]. 計算機輔助設計與圖形學學報，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]馬照亭，潘懋，胡金星，等. 一種基于數據分塊的海量地形快速漫游方法[J]. 北京大學學報：自然科學版，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]張小虎，卲永社，葉勤. 基于自適應四叉樹的地形LOD算法[J]. 計算機應用，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.