一種基于自適應動態四叉樹的實時連續LOD模型生成算法所謂的LOD建模,其實質就是采用一定的算法思想將原有的網格地形數據進行重組,得到一種更加便于實時繪制使用的數據結構。Lindstrom提出的基于四叉樹的實時連續LOD動態生成算法就是一種典型的實時LOD生成算法。在利用四叉樹方法進行LOD建模的過程中,其關鍵就在于怎樣對原有的網格數據進行四叉樹分層。四叉樹分層方法是:從整個完整的地形出發,遞歸的把地形不斷的分割(Sub-divide)成相等的四個區域,分割的深度越大,則得到的分辨率越高。如圖所示是一個地形的四叉樹表示,圖中每一個正方形為四叉樹的一個節點。每個節點保存了一定區域的信息包括:經緯度,中心點的高度,邊節點的高度等。地形四叉樹表示在進行四叉樹分層的過程中需要注意以下幾點:首先,由于四叉樹分層是針對(2?＋1)×(2?＋1)的規則網格而言的,所以我們所采用的數據格式應盡量滿足(2?＋1)×(2?＋1)的規則網格的要求,即網格數據必須是一間隔均勻的正方形區域。如果網格數據的大小不滿足該條件,則需要擴展其幾何圖形,讓其大小盡可能接近(2?＋1)×(2?＋1),擴展部分的像素用空值填充。其次，四叉樹中相鄰的兩個節點的層次最大不能相差1,否則在LOD模型連續拼接的地方就會出現裂縫。其基本思路是:先把地形一分為四,用遞歸的方法對每個網格渲染。對每個網格,如果達到最高精度,則退出;如果不在視野內,也退出。再對符合條件的網格遞歸下去。所以針對以上基于四叉樹構建LOD模型算法，具有可以改進優化的方面主要集中在以下幾點：在對地形節點進行分析判斷是否需要進一步細化劃分方面（節點評價機制）；將地形節點往四叉樹結構存儲和高效訪問方面；為了實現當視點較遠時,分辨率較低,當視點較近時,分辨率較高這個特性而產生的動態誤差問題；消除由于相鄰的網格因分割的程度不同而產生的裂縫問題；綜上問題我提出了：一種基于自適應動態四叉樹的實時連續LOD模型生成算法

把整個地形作為根結點，然后從根結點出發判斷其是否滿足某種分割條件，若不滿足則不分割并作為葉子結點保存；否則把根結點遞歸地不斷分成相等的4個子結點區域，直到不能再分割為止，最后將所有葉子結點繪制渲染形成簡化結果。分割的深度越大，得到的分辨率就越高，分割時使用結點評價函數對每個行結點進行評價，如果該點精度已經符合結點評價函數的要求，則不再進行分割，否則繼續分割直到該結點符合結點評價函數的要求為止。傳統的四叉樹分層結構四叉樹存儲和訪問機制快速訪問四叉樹結點的基本思想是將存儲DEM（數字高程模型，是用一組有序數值陣列形式表示地面高程的一種實體地面模型）數據的四叉樹結點用一維數組來表示。主要用兩種方法來提高四叉樹結點的訪問效率,其中一種是四叉樹結點數據在一維數組中的存儲方式,另外一種則是訪問四叉樹結點數組的方式。四叉樹結點的存儲方式首先將二維的DEM轉化為一維方式組織，其基本原理是:

先將數據空間劃分成大小相同的網格,再根據一定的方法將這些網格編碼,使得每一個網格的標號是唯一識別的,并能在一定程度上保持空間鄰近性,即相鄰網格的標號也相鄰,以便使一個空間對象由一組網格組成。

再次，考慮到四叉樹結點的存儲順序通常用二維空間填充曲線的方法來確定,因為二維空間填充曲線不僅可以保證遍歷空間中的每個數據點,而且填充曲線局部區段內的數據點在空間分布上也是相鄰的。

我這里采用著名的希爾伯特空間填充曲線來組織四叉樹結點,因為希爾伯特值的排序能很好地反映空間鄰近性,如圖給出了用希爾伯特空間填充曲線組織DEM數據的初始幾步網格頂點的索引號。

DEM數據經過希爾伯特空間填充曲線組織后,它自頂向下,由粗到細地將各個分辨率的四叉樹結點存儲到了一個一維數組中,這種方法實際上是把單一分辨率的數據變換到多分辨率數據后再進行排序,這在3維地形數據的可視化中是一種十分有效的數據組織方式,其使用戶能夠方便地訪問四叉樹結點數據四叉樹結點的訪問方式

四叉樹結點訪問有隔層四叉樹和嵌入四叉樹兩種常用的方式。我在這里利用隔層四叉樹來快速訪問四叉樹結點數據的實現方法。

隔層四叉樹是指在地形網格由粗往細的剖分過程中,把地形網格按層次分為白色四叉樹和黑色四叉樹兩種,而且每種均為一棵完全的四叉樹。這種黑白隔層表示頂點的方式是利用四叉樹的編碼,并根據父子結點關系推導出頂點索引號,再按照自上而下、由粗到細的方式存儲結點,這樣就可以很容易地讀取所需的數據信息。

為了保證空間數據的鄰接性,每一層的數據都需要保存。這樣就使得在空間位置上相近的頂點在內存里面的存儲位置也相近。然后就可以通過如下公式求解結點的存儲位置,如父結點p的第k個孩子的存儲順序為C（p，k)=4p+k+m,k=0,1,2,3

其中,m是一個常數,其取值取決于根結點的位置以及相鄰兩層的距離。使用這種方法,可以使同一層所有頂點數據都放在一塊。如下圖所示為隔層四叉樹頭幾層結點訪問順序的示意圖。節點評價系統在建立節點評價系統時，一般需要考慮兩個因素：一是視距的影響；二是地形本身粗糙程度的影響。視距標準

在實際的視覺效果中，模型的粗細程度不僅與視點位置有關系，跟視線方向也有關系。也就是距視點距離相等的節點，對著視點的節點細節層次應該比其他節點的細節層次高。如下圖為透視變換中各參數間的關系示意,設視點的張角和投影平面的邊長分別為α和L,被投影線段的長度為l,視點與該線段中心的距離為d,設該線段與投影平面平行,顯然,此時線段在投影平面上的長度最長,則屏幕投影誤差公式為

其中,k為一可變系數,可以通過它對系統性能進行調整,L為結點覆蓋區域的邊長,λ為物體空間中的單位長度在投影平面上的像素數,d為視點到地形結點中心點的距離,α為視角,ε為用戶容許像素誤差,e為四叉樹結點單元精度變化時產生誤差。從公式中可知,由于e和d隨著視點的變化會隨時改變,而在特定的屏幕投影誤差下,其他參數則可以視為常量,因此實際編程時,采用如下公式評估視距誤差。設細化后邊點及中心點產生的誤差最大值為e,則在實時漫游時,網格細化的條件為emax

×λ>d其中,d為視點到該四叉樹結點的距離,λ為一與投影方式相關的常數,一般取λ=ω/φ,ω為視錐角φ范圍內投影面上的像素個數;最后按照遞歸的方式遍歷四叉樹,當四叉樹孩子結點滿足細化條件且該結點不是四叉樹的葉子結點時,則該結點被細化,否則該結點不再細化,并設置標志位=false。地形粗糙度標準

第二個需要考慮的是，地形本身粗糙程度的影響，在“崎嶇”的地帶，使用較細的層級分割節點“平坦”的地帶，則粗略些，同樣可以節省分割渲染時間。如圖（a）所示是某一節點在某種狀態下的剖分情形，首先考慮4個邊點因分割而產生的高度。其次應考慮圖（b）所示的4個子節點中心所產生的高度變化，這樣總共需考慮9個高度變化值（△0，…,△8）。取這9個點處的高度最大值Max（0，…，8）和最小值Min（0，…，8），構造diff=Max（0,…,8）-Min（0，…，8），再構造r=e/diff。于是，當diff<e×η，即1/r＜η時，邊長較大需進一步分割。此處，η是一個可調節的常數，稱為高度分辨率。綜合考慮視距和地形粗糙度兩者的影響，得出節點分割最終的評價函數為d為視點到節點的距離，e為四叉樹結點單元精度變化時產生的誤差，λ為物體空間中的單位長度在投影平面上的像素數，η是高度分辨率

，當f<1時，節點需要進一步分割，否則不分割。拼接縫消除拼接縫的形成在運用樹數據結構對地形進行多分辨率表示時,會出現天然的“裂縫”現象,如圖所示.結點c2具有較高的分辨率,而與之相鄰的結點c1和c3

具有較低的分辨率,使得結點c1,c3與c2,c3

連接處出現了未被覆蓋的區域,從而在地形繪制時就產生了“裂縫”.拼接縫消除常用的辦法有兩種：一種是在兩個不同分辨率節點之間加上一條邊,如圖1所示；另一種方法是在不同分辨率格網之間減去一條邊,如圖2所示。從理論上來說,第一種方法更加全面,因為相鄰兩個節點層次可以是任意級別,但是這樣實現起來比較復雜,繪制效率較低。第二種方法比較簡單,只要滿足相鄰節點層次差別不超過1就可以。這里采用第二種方法來進行裂縫消除。加邊策略減邊策略不同分辨率節點由于采用了地形分塊技術,除了考慮同一塊地形內部的接邊問題外,還必須考慮相鄰分塊地形之間的接邊問題。為此每個分塊地形節點定義了一個分割標志區,大小與地形節點相同,記錄該節點是否被分割,如圖所示。圖中,黑點表示需要繼續分割節點,空心點表示不需要分割節點。分割緩沖區為了保證相鄰節點分辨率不超過1,制定分割規則為如果當前節點的上下左右4個節點都已經參與分割,并且當前節點滿足分割公式要求,則本節點才可參與分割否則,直接繪制本節點。對于每個分塊地形,初始節點都認為是可分割節點。對于分割過程中的任意節點,其上下左右節點坐標如以下公式所示,

其中nRo