基于四叉樹的LOD算法實(shí)現(xiàn)

1、一種基于自適應(yīng)動(dòng)態(tài)四叉樹的實(shí)時(shí)連續(xù)一種基于自適應(yīng)動(dòng)態(tài)四叉樹的實(shí)時(shí)連續(xù)LOD模型生成算法模型生成算法Page 2 所謂的LOD建模,其實(shí)質(zhì)就是采用一定的算法思想將原有的網(wǎng)格地形數(shù)據(jù)進(jìn)行重組,得到一種更加便于實(shí)時(shí)繪制使用的數(shù)據(jù)結(jié)構(gòu)。 Lindstrom提出的基于四叉樹的實(shí)時(shí)連續(xù)LOD動(dòng)態(tài)生成算法就是一種典型的實(shí)時(shí)LOD生成算法。 在利用四叉樹方法進(jìn)行LOD建模的過程中, 其關(guān)鍵就在于怎樣對原有的網(wǎng)格數(shù)據(jù)進(jìn)行四叉樹分層。Page 3 四叉樹分層方法是: 從整個(gè)完整的地形出發(fā),遞歸的把地形不斷的分割( Sub-divide)成相等的四個(gè)區(qū)域,分割的深度越大,則得到的分辨率越高。如圖所示是一個(gè)地形的四叉

2、樹表示,圖中每一個(gè)正方形為四叉樹的一個(gè)節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)保存了一定區(qū)域的信息包括: 經(jīng)緯度,中心點(diǎn)的高度,邊節(jié)點(diǎn)的高度等。地形四叉樹表示 Page 4 在進(jìn)行四叉樹分層的過程中需要注意以下幾點(diǎn): 首先,由于四叉樹分層是針對(21)(21)的規(guī)則網(wǎng)格而言的,所以我們所采用的數(shù)據(jù)格式應(yīng)盡量滿足(21)(21)的規(guī)則網(wǎng)格的要求,即網(wǎng)格數(shù)據(jù)必須是一間隔均勻的正方形區(qū)域。如果網(wǎng)格數(shù)據(jù)的大小不滿足該條件,則需要擴(kuò)展其幾何圖形,讓其大小盡可能接近(21)(21),擴(kuò)展部分的像素用空值填充。 其次，四叉樹中相鄰的兩個(gè)節(jié)點(diǎn)的層次最大不能相差1,否則在LOD模型連續(xù)拼接的地方就會出現(xiàn)裂縫。 其基本思路是: 先把地形一

3、分為四,用遞歸的方法對每個(gè)網(wǎng)格渲染。對每個(gè)網(wǎng)格,如果達(dá)到最高精度,則退出; 如果不在視野內(nèi),也退出。再對符合條件的網(wǎng)格遞歸下去。Page 5 所以針對以上基于四叉樹構(gòu)建LOD模型算法，具有可以改進(jìn)優(yōu)化的方面主要集中在以下幾點(diǎn)：1.在對地形節(jié)點(diǎn)進(jìn)行分析判斷是否需要進(jìn)一步細(xì)化劃分方面（節(jié)點(diǎn)評價(jià)機(jī)制）；2.將地形節(jié)點(diǎn)往四叉樹結(jié)構(gòu)存儲和高效訪問方面；3.為了實(shí)現(xiàn)當(dāng)視點(diǎn)較遠(yuǎn)時(shí), 分辨率較低, 當(dāng)視點(diǎn)較近時(shí), 分辨率較高這個(gè)特性而產(chǎn)生的動(dòng)態(tài)誤差問題；4.消除由于相鄰的網(wǎng)格因分割的程度不同而產(chǎn)生的裂縫問題；綜上問題我提出了：一種基于自適應(yīng)動(dòng)態(tài)四叉樹的實(shí)時(shí)連續(xù)LOD模型生成算法Page 6 把整個(gè)地形作為根結(jié)

4、點(diǎn)，然后從根結(jié)點(diǎn)出發(fā)判斷其是否滿足某種分割條件，若不滿足則不分割并作為葉子結(jié)點(diǎn)保存；否則把根結(jié)點(diǎn)遞歸地不斷分成相等的4個(gè)子結(jié)點(diǎn)區(qū)域，直到不能再分割為止，最后將所有葉子結(jié)點(diǎn)繪制渲染形成簡化結(jié)果。 分割的深度越大，得到的分辨率就越高，分割時(shí)使用結(jié)點(diǎn)評價(jià)函數(shù)對每個(gè)行結(jié)點(diǎn)進(jìn)行評價(jià)，如果該點(diǎn)精度已經(jīng)符合結(jié)點(diǎn)評價(jià)函數(shù)的要求，則不再進(jìn)行分割，否則繼續(xù)分割直到該結(jié)點(diǎn)符合結(jié)點(diǎn)評價(jià)函數(shù)的要求為止。 傳統(tǒng)的四叉樹分層結(jié)構(gòu)Page 7l四叉樹存儲和訪問機(jī)制l快速訪問四叉樹結(jié)點(diǎn)的基本思想是將存儲DEM （數(shù)字高程模型，是用一組有序數(shù)值陣列形式表示地面高程的一種實(shí)體地面模型）數(shù)據(jù)的四叉樹結(jié)點(diǎn)用 一維數(shù)組來表示 。主要用兩

5、種方法來提高四叉樹結(jié)點(diǎn)的訪問效率 , 其中一種是四叉樹結(jié)點(diǎn)數(shù)據(jù)在 一維數(shù)組中的存儲方式 ,另外一種則是訪問四叉樹結(jié)點(diǎn)數(shù)組的方式 。Page 8l 四叉樹結(jié)點(diǎn)的存儲方式 首先將二維的DEM轉(zhuǎn)化為一維方式組織，其基本原理是 : l 先將數(shù)據(jù)空間劃分成大小相同的網(wǎng)格 ,再根據(jù)一定的方法將這些網(wǎng)格編碼 , 使得每一個(gè)網(wǎng)格的標(biāo)號是唯一識別的 ,并能在一定程度上保持空間鄰近性 ,即相鄰網(wǎng)格的標(biāo)號也相鄰 ,以便使一個(gè)空間對象由一組網(wǎng)格組成 。l 再次，考慮到四叉樹結(jié)點(diǎn)的存儲順序通常用 二維空間填充曲線的方法來確定 , 因?yàn)?二維空間填充曲線不僅可以保證遍歷空間中的每個(gè)數(shù)據(jù)點(diǎn) , 而且填充曲線局部區(qū)段內(nèi)的數(shù)據(jù)

6、點(diǎn)在空間分布上也是相鄰的 。 Page 9 我這里采用著名的希爾伯特空間填充曲線來組織四叉樹結(jié)點(diǎn) ,因?yàn)橄柌刂档呐判蚰芎芎玫胤从晨臻g鄰近性 ,如圖給出了用希爾伯特空間填充曲線組織 DEM數(shù)據(jù)的初始幾步網(wǎng)格頂點(diǎn)的索引號 。 DEM數(shù)據(jù)經(jīng)過希爾伯特空間填充曲線組織后 , 它自頂向下 ,由粗到細(xì)地將各個(gè)分辨率的四叉樹結(jié)點(diǎn)存儲到了一個(gè)一維數(shù)組中 , 這種方法實(shí)際上是把單一分辨率的數(shù)據(jù)變換到多分辨率數(shù)據(jù)后再進(jìn)行排序 , 這在3維地形數(shù)據(jù)的可視化中是一種十分有效的數(shù)據(jù)組織方式 ,其使用戶能夠方便地訪問四叉樹結(jié)點(diǎn)數(shù)據(jù) Page 10l 四叉樹結(jié)點(diǎn)的訪問方式 四叉樹結(jié)點(diǎn)訪問有隔層四叉樹和嵌入四叉樹兩種常用

7、的方式 。 我在這里利用隔層四叉樹來快速訪問四叉樹結(jié)點(diǎn)數(shù)據(jù)的實(shí)現(xiàn)方法 。 隔層四叉樹是指在地形網(wǎng)格由粗往細(xì)的剖分過程中 , 把地形網(wǎng)格按層次分為白色四叉樹和黑色四叉樹兩種 , 而且每種均為一棵完全的四叉樹 。 這種黑白隔層表示頂點(diǎn)的方式是利用四叉樹的編碼 ,并根據(jù)父子結(jié)點(diǎn)關(guān)系推導(dǎo)出頂點(diǎn)索引號 ,再按照自上而下 、 由粗到細(xì)的方式存儲結(jié)點(diǎn) ,這樣就可以很容易地讀取所需的數(shù)據(jù)信息 。Page 11 為了保證空間數(shù)據(jù)的鄰接性 , 每一層的數(shù)據(jù)都需要保存 。 這樣就使得在空間位置上相近的頂點(diǎn)在內(nèi)存里面的存儲位置也相近 。 然后就可以通過如下公式求解結(jié)點(diǎn)的存儲位置 , 如父結(jié)點(diǎn) p的第 k 個(gè)孩子的存儲

8、順序?yàn)镃（p，k)= 4 p + k + m , k = 0, 1, 2, 3 其中 , m 是一個(gè)常數(shù) , 其取值取決于根結(jié)點(diǎn)的位置以及相鄰兩層的距離 。使用這種方法 , 可以使同一層所有頂點(diǎn)數(shù)據(jù)都放在一塊 。 如下圖所示為隔層四叉樹頭幾層結(jié)點(diǎn)訪問順序的示意圖 。Page 12l節(jié)點(diǎn)評價(jià)系統(tǒng)n在建立節(jié)點(diǎn)評價(jià)系統(tǒng)時(shí)，一般需要考慮兩個(gè)因素：一是視距的影響；二是地形本身粗糙程度的影響。n 視距標(biāo)準(zhǔn) 在實(shí)際的視覺效果中，模型的粗細(xì)程度不僅與視點(diǎn)位置有關(guān)系，跟視線方向也有關(guān)系。也就是距視點(diǎn)距離相等的節(jié)點(diǎn)，對著視點(diǎn)的節(jié)點(diǎn)細(xì)節(jié)層次應(yīng)該比其他節(jié)點(diǎn)的細(xì)節(jié)層次高。Page 13 如下圖為透視變換中各參數(shù)間的關(guān)系

9、示意 , 設(shè)視點(diǎn)的張角和投影平面的邊長分別為 和 L , 被投影線段的長度為 l , 視點(diǎn)與該線段中心的距離為 d , 設(shè)該線段與投影平面平行 ,顯然 ,此時(shí)線段在投影平面上的長度最長 ,則屏幕投影誤差公式為 其中 , k 為一可變系數(shù) , 可以通過它對系統(tǒng)性能進(jìn)行調(diào)整 , L 為結(jié)點(diǎn)覆蓋區(qū)域的邊長 , 為物體空間中的單位長度在投影平面上的像素?cái)?shù) , d 為視點(diǎn)到地形結(jié)點(diǎn)中心點(diǎn)的距離 , 為視角 , 為用戶容許像素誤差 ,e為四叉樹結(jié)點(diǎn)單元精度變化時(shí)產(chǎn)生誤差 。 從公式中可知 , 由于e和 d 隨著視點(diǎn)的變化會隨時(shí)改變 , 而在特定的屏幕投影誤差下 , 其他參數(shù)則可以視為常量 , Page 1

10、4 因此實(shí)際編程時(shí) , 采用如下公式評估視距誤差。設(shè)細(xì)化后邊點(diǎn)及中心點(diǎn)產(chǎn)生的誤差最大值為e ,則在實(shí)時(shí)漫游時(shí),網(wǎng)格細(xì)化的條件為emax d 其中, d為視點(diǎn)到該四叉樹結(jié)點(diǎn)的距離,為一與投影方式相關(guān)的常數(shù), 一般取 =/,為視錐角范圍內(nèi)投影面上的像素個(gè)數(shù);最后按照遞歸的方式遍歷四叉樹,當(dāng)四叉樹孩子結(jié)點(diǎn)滿足細(xì)化條件且該結(jié)點(diǎn)不是四叉樹的葉子結(jié)點(diǎn)時(shí),則該結(jié)點(diǎn)被細(xì)化,否則該結(jié)點(diǎn)不再細(xì)化,并設(shè)置標(biāo)志位 = false。Page 15l地形粗糙度標(biāo)準(zhǔn) 第二個(gè)需要考慮的是，地形本身粗糙程度的影響，在“崎嶇”的地帶，使用較細(xì)的層級分割節(jié)點(diǎn)“平坦”的地帶，則粗略些，同樣可以節(jié)省分割渲染時(shí)間。 如圖（a）所示是某一

11、節(jié)點(diǎn)在某種狀態(tài)下的剖分情形，首先考慮 4 個(gè)邊點(diǎn)因分割而產(chǎn)生的高度。其次應(yīng)考慮圖 （b）所示的 4 個(gè)子節(jié)點(diǎn)中心所產(chǎn)生的高度變化，這樣總共需考慮 9 個(gè)高度變化值（0，,8）。取這 9 個(gè)點(diǎn)處的高度最大值 Max（0，8）和最小值 Min（0，8），構(gòu)造 diff=Max（0,8）-Min（0，8），再構(gòu)造 r=e /diff 。于是，當(dāng) diff e，即 1/r時(shí)，邊長較大需進(jìn)一步分割。此處，是一個(gè)可調(diào)節(jié)的常數(shù)，稱為高度分辨率。Page 16l綜合考慮視距和地形粗糙度兩者的影響，得出節(jié)點(diǎn)分割最終的評價(jià)函數(shù)為 d為視點(diǎn)到節(jié)點(diǎn)的距離，e為四叉樹結(jié)點(diǎn)單元精度變化時(shí)產(chǎn)生的誤差，為物體空間中的單位長度

12、在投影平面上的像素?cái)?shù)，是高度分辨率 ，當(dāng)f 1 時(shí)，節(jié)點(diǎn)需要進(jìn)一步分割，否則不分割。redfPage 17l 拼接縫消除l拼接縫的形成l在運(yùn)用樹數(shù)據(jù)結(jié)構(gòu) 對地形進(jìn) 行多分辨 率表示時(shí) , 會出現(xiàn)天然的“裂縫” 現(xiàn)象 , 如圖所示 . 結(jié)點(diǎn) c2具有較高的分辨率 , 而與之相鄰的結(jié)點(diǎn) c1和c3 具有較低的分辨率 , 使得結(jié)點(diǎn)c1 ,c3與 c2, c3 連接處出現(xiàn)了未被覆蓋的區(qū)域 , 從而在地形繪制時(shí)就產(chǎn)生了“裂縫” .Page 18 拼接縫消除l常用的辦法有兩種：一種是在兩個(gè)不同分辨率節(jié)點(diǎn)之間加上一條邊,如圖1所示；另一種方法是在不同分辨率格網(wǎng)之間減去一條邊,如圖2所示。從理論上來說,第一種

13、方法更加全面,因?yàn)橄噜弮蓚€(gè)節(jié)點(diǎn)層次可以是任意級別,但是這樣實(shí)現(xiàn)起來比較復(fù)雜,繪制效率較低。第二種方法比較簡單,只要滿足相鄰節(jié)點(diǎn)層次差別不超過1就可以。這里采用第二種方法來進(jìn)行裂縫消除。加邊策略減邊策略不同分辨率節(jié)點(diǎn)Page 19 由于采用了地形分塊技術(shù),除了考慮同一塊地形內(nèi)部的接邊問題外,還必須考慮相鄰分塊地形之間的接邊問題。為此每個(gè)分塊地形節(jié)點(diǎn)定義了一個(gè)分割標(biāo)志區(qū),大小與地形節(jié)點(diǎn)相同,記錄該節(jié)點(diǎn)是否被分割,如圖所示。圖中,黑點(diǎn)表示需要繼續(xù)分割節(jié)點(diǎn),空心點(diǎn)表示不需要分割節(jié)點(diǎn)。分割緩沖區(qū)Page 20l為了保證相鄰節(jié)點(diǎn)分辨率不超過1,制定分割規(guī)則為如果當(dāng)前節(jié)點(diǎn)的上下左右4個(gè)節(jié)點(diǎn)都 已經(jīng)參與分割,并且當(dāng)前節(jié)點(diǎn)滿足分割公式要求,則本節(jié)點(diǎn) 才可參與分割否則,直接繪制本節(jié)點(diǎn)。對于每個(gè)分塊地形,初始節(jié)點(diǎn)都認(rèn)為是可分割節(jié)點(diǎn)。對于分割過程中的任意節(jié)點(diǎn),其上下左右節(jié)點(diǎn)坐標(biāo)如以下公式所示, 其中nRow,nCol 分別是當(dāng)