去LoD層級約束的海量三維地形裂縫實時消除算法

劉振東，李成名，武鵬達，劉 坡

(中國測繪科學研究院，北京 100830)

隨著遙感測繪數(shù)據(jù)采集、數(shù)據(jù)存儲技術(shù)的發(fā)展，地形數(shù)據(jù)規(guī)模越來越大，地形之上承載的建筑物模型、視頻、管線等數(shù)據(jù)日益豐富。對于大范圍、大場景下的地形來說，既要對其豐富的細節(jié)進行逼真的顯示，又要盡可能地減少計算量，為場景中其他對象騰出渲染時間和空間，因此，研究海量三維地形的實時渲染技術(shù)具有重要意義。當前，國內(nèi)外主要采取視點相關(guān)的連續(xù)LoD(level of detail)[1-2]技術(shù)對地形數(shù)據(jù)進行簡化，然而，由于LoD技術(shù)中存在細節(jié)層次差異，不同層級的相鄰地形網(wǎng)格邊界上網(wǎng)格點的高程值并不完全一致，導致地形實時渲染過程中會出現(xiàn)地形裂縫。裂縫問題是LoD技術(shù)中一個必須解決的關(guān)鍵問題[3]。

傳統(tǒng)的地形裂縫處理方法嘗試通過調(diào)整網(wǎng)格邊界頂點、附加補丁、模板分解等幾個方面解決該問題。調(diào)整網(wǎng)格邊界頂點法[4]出現(xiàn)較早，主要通過在裂縫處為較高層次網(wǎng)格添加頂點或在較低層次網(wǎng)格中刪除相應(yīng)頂點的方式，使不同層次的對應(yīng)節(jié)點具有相同高度，從而消除裂縫。這類算法使用范圍廣，但CPU運算量大，對LoD層級跨度要求高。垂直邊緣法(vertical skirt)[5-6]是一種典型的附加補丁算法，通過為每個地形網(wǎng)格的四周添加垂直向下的“裙邊”，以“裙邊”充當補丁去遮擋視覺上的裂縫。但該方法會額外繪制地形面片，當進行大場景地形實時渲染時，會給計算機帶來不小的負擔，同時在接縫處容易造成地形垂直顯示，破壞真實地形高度變換規(guī)律。限制性四叉樹算法[8-10]通過確定頂點約束關(guān)系解決地形裂縫問題，然而該算法僅考慮了相鄰層次節(jié)點的約束關(guān)系，因此，同樣存在層級跨度低、地形陡峭處的三維真實感表現(xiàn)力不夠的問題。

整體而言，傳統(tǒng)的地形裂縫消除方法在實現(xiàn)海量三維地形數(shù)據(jù)實時渲染時，通常會存在運算量大、渲染效率低、瓦片層次跨度小等問題。鑒于此，本文在分析地形四叉樹組織方式及地形LoD控制規(guī)則的基礎(chǔ)上，提出一種去LoD層次跨度約束的海量三維地形裂縫實時消除算法。

1 帶有鄰居關(guān)系的地形四叉樹結(jié)構(gòu)

當相鄰地形網(wǎng)格的LoD層次等級不相同時，網(wǎng)格邊界處的分辨率不一致則很可能造成地形裂縫。因此，實現(xiàn)地形裂縫消除的關(guān)鍵在于運用四叉樹數(shù)據(jù)結(jié)構(gòu)對地形進行LoD動態(tài)實時繪制時，能夠?qū)Φ匦尉W(wǎng)格節(jié)點的鄰近關(guān)系進行準確地識別及判斷。為此，本文首先建立包含邊鄰居與角鄰居的地形四叉樹結(jié)構(gòu)，即對傳統(tǒng)地形四叉樹增加以下約束：

(1) 地形網(wǎng)格節(jié)點簡稱為瓦片(Tile)，如圖1中的A1、A2等，瓦片以所在LoD層級、所在的列號、所在的行號作為唯一編碼，即Tilecode=(LoD，TileX，TileY)，且每個瓦片包含M×M個頂點(M為瓦片某邊上的網(wǎng)格點數(shù)，且為正整數(shù))。

(2) 地形四叉樹中，沒有“父親”的節(jié)點稱為根節(jié)點，如圖1中的節(jié)點C1，沒有“孩子”的節(jié)點稱為葉節(jié)點，如圖1中的節(jié)點C2、C6、C7等。

圖1 四叉樹地形結(jié)構(gòu)

(3) 以某一瓦片為中心、空間關(guān)系為依據(jù)，將其周圍瓦片劃分為邊鄰居、角點鄰居兩大類。其中邊鄰居類可分為：左邊鄰居(LN)、上邊鄰居(UN)、右邊鄰居(RN)、下邊鄰居(DN)。角點鄰居類可分為：左上角鄰居(LUN)、右上角鄰居(RUN)、右下角鄰居(RDN)、左下角鄰居(LDN)，如圖2所示。

(4) 四叉樹結(jié)構(gòu)中，依據(jù)“父親”節(jié)點、“孩子”節(jié)點之間的空間關(guān)系，將位于“父親”節(jié)點左上角的“孩子”節(jié)點命名為LUChild、右上角的“孩子”節(jié)點命名為RUChild、右下角“孩子”節(jié)點命名為RDChild、左下角“孩子”瓦片命名為LDChild。

圖2 瓦片的鄰居關(guān)系

特別說明，算法將只尋找LoD小于或等于當前瓦片的鄰居，并將其存儲在當前瓦片中。因為此時正處于地形四叉樹動態(tài)重構(gòu)階段，瓦片會更新裂分、合并狀態(tài)，這是一種狀態(tài)極不穩(wěn)定的階段，該階段無法確定繪制時瓦片的顯示鄰居。

2 地形裂縫實時消除算法

2.1 瓦片間鄰居關(guān)系及其狀態(tài)判斷

鄰居信息的動態(tài)更新處理是地形裂縫消除的關(guān)鍵步驟。本文根據(jù)葉節(jié)點自身特性，將鄰居信息的動態(tài)更新處理分為裂分葉節(jié)點鄰居信息處理算法和合并葉節(jié)點鄰居信息處理算法兩個模塊。前者處于渲染幀的更新階段，后者處于渲染幀的資源調(diào)出階段。

瓦片間鄰居信息的判斷依賴于瓦片的空間位置關(guān)系，為便于計算，為瓦片的各個邊、角方位鄰居信息設(shè)置更新標識(Dirty)，Dirty具有休眠及激活兩種狀態(tài)。

2.1.1 裂分葉節(jié)點鄰居信息及其狀態(tài)確認

判斷裂分葉節(jié)點位于“父親”瓦片的方位，根據(jù)所在方位及空間位置關(guān)系，識別該瓦片的鄰居信息。以左上角“孩子”瓦片(LUChild)為例，邊及角點的鄰居判斷方式如下：

邊鄰居及其狀態(tài)確認。因裂分葉節(jié)點為左上角“孩子”瓦片，因此它的右邊鄰居和下邊鄰居和當前瓦片屬于同一“父親”節(jié)點，在同一層級LoD中分辨率相同，故將當前瓦片的右邊、下邊及其右邊鄰居的左邊、下鄰居的上邊的裂縫消除Dirty標識，設(shè)置為休眠狀態(tài)；左邊鄰居和上邊鄰居與當前瓦片不屬于同一“父親”節(jié)點，則首先找到其“父親”節(jié)點的左邊鄰居和上邊鄰居，進而計算當前瓦片的左邊鄰居和上邊鄰居，將關(guān)聯(lián)瓦片相應(yīng)邊的裂縫消除Dirty標識，設(shè)置為激活狀態(tài)。

角點鄰居及其狀態(tài)確認原理與邊鄰居及其狀態(tài)確認原理相似，在此不再贅述。

2.1.2 合并葉節(jié)點鄰居信息及其狀態(tài)確認

因4個“孩子”節(jié)點要合并成一個“父親”節(jié)點，則需依次更新4個“孩子”鄰居節(jié)點的鄰居信息。這里同樣以左上角“孩子”瓦片(LUChild)為例進行說明。

(1) 邊鄰居及其狀態(tài)確認。因右邊和下邊鄰居和當前瓦片LUChild屬于同一“父親”，且三者被同時合并，因此這兩個鄰居瓦片的鄰居信息不作處理；如果左邊鄰居(LN)、上邊鄰居(UN)存在且與當前瓦片的LoD層級相同，則4個“孩子”節(jié)點合并后，其LN、UN的鄰居信息會發(fā)生變化，將LN的右邊鄰居、UN的下邊鄰居設(shè)置為LUChild的“父親”節(jié)點，若LN、UN有“孩子”節(jié)點則需遞歸更新相關(guān)聯(lián)的邊鄰居信息，同時將相應(yīng)邊Dirty標識設(shè)為激活狀態(tài)。

(2) 角點鄰居及其狀態(tài)確認。與邊鄰居及其狀態(tài)確認原理相似，因右下角鄰居與當前瓦片屬于同一“父親”節(jié)點，因此此鄰居瓦片的鄰居信息不作處理；根據(jù)空間位置關(guān)系，如果左上角鄰居(LUN)存在且與當前瓦片的LoD層級相同，則應(yīng)將LUN的右下角鄰居設(shè)置為LUChild的“父親”節(jié)點，若LUN有“孩子”節(jié)點則需遞歸更新相關(guān)聯(lián)的角點鄰居信息；如果右上角鄰居(RUN)或左下角鄰居(LDN)存在且與當前瓦片的LoD層級相同，因二者與LUChild的“父親”節(jié)點在空間位置上并不是角點鄰居關(guān)系(如圖2中瓦片O與UN2)，則二者需將相關(guān)聯(lián)的角鄰居設(shè)置為空，同樣若RUN、LDN有“孩子”節(jié)點則需遞歸更新相關(guān)聯(lián)的角點鄰居信息。

2.2 去層次跨度約束裂縫消除算法

從根節(jié)點開始遍歷地形四叉樹的每個節(jié)點，探索需要消除的瓦片范圍。根據(jù)視點相關(guān)的LoD控制規(guī)則，遍歷瓦片判斷其是否為新增瓦片。對于屬于葉節(jié)點的新增瓦片，確認其鄰居瓦片及其Dirty狀態(tài)，若Dirty為激活狀態(tài)則表明該瓦片存在裂縫可能，為此，本文提出去層次跨度約束裂縫消除算法。其基本思想為：以單個瓦片為處理單元，根據(jù)地形裂縫僅出現(xiàn)在瓦片邊界處的特點，順序處理瓦片的4條邊和4個角點，通過線性插值方法使處在不同層級的鄰近瓦片的節(jié)點高程值與處理瓦片對應(yīng)節(jié)點的高程值保持一致。下面以某一瓦片的左邊處理過程為例，詳細闡述具體步驟：

步驟1：根據(jù)動態(tài)更新的瓦片鄰居信息，探索當前瓦片的左邊鄰居節(jié)點(葉節(jié)點)。假設(shè)當前瓦片節(jié)點為N，節(jié)點N的左鄰居信息數(shù)組為Lvec[](左邊鄰居可能有多種情況，如圖3所示，但處理過程一致)。為找出三維地形場景中瓦片N的左邊鄰居，遍歷Lvec[]數(shù)組中的成員，判斷每個成員是否有“孩子”節(jié)點，有則將該成員右上、右下兩個“孩子”節(jié)點LChild1、LChild2賦給當前節(jié)點N，作為N的左鄰居，同時繼續(xù)按上述步驟進行遞歸處理LChild1、LChild2，直至到葉節(jié)點，將其記錄至鄰居數(shù)組LYvec[]。在設(shè)置了N的左鄰居后，同時將該左鄰居的右鄰居設(shè)置為N。

圖3 瓦片左邊鄰居節(jié)點情況

步驟2：遍歷左邊鄰居數(shù)組LYvec[]，進行消除運算。若LYvec[]中僅有1個節(jié)點，則表明左邊鄰居與當前瓦片N的LoD相等，二者在邊界上的頂點關(guān)系是嚴格一一對應(yīng)的，如圖4所示，則可直接遍歷邊界上的每一個頂點，判斷二者的高程值是否相等，不相等則以瓦片N作為基準，將其頂點的高程值賦值給鄰居對應(yīng)的頂點；若LYvec[]中僅有2個節(jié)點，且瓦片N與鄰居節(jié)點的LoD相差1，則二者在邊界上的頂點關(guān)系如圖5所示，鄰居瓦片兩個格網(wǎng)的長度與瓦片N的一個格網(wǎng)的長度相等，此時對瓦片N的頂點進行等距離線性插值運算，得到瓦片N邊界上兩節(jié)點的中點高程值，并將該高程值賦給鄰居頂點；若LYvec[]有4個節(jié)點，且瓦片N與鄰居節(jié)點的LoD相差n(n>1)，則二者在邊界上的頂點關(guān)系如圖6(n=2)所示，說明鄰居瓦片兩個格網(wǎng)的長度是瓦片N的一個格網(wǎng)長度的1/n，此時計算出瓦片N中距離鄰居瓦片最近的網(wǎng)格點，并將瓦片N的格網(wǎng)邊上等距離分為2n個節(jié)點，利用線性插值算法得出每一個節(jié)點的高程，將該高程值賦給鄰居頂點。

圖4 LoD層級相等

圖5 LoD層級相差為1

圖6 LoD層級相差為2

本文提出的地形裂縫實時消除算法不需控制相鄰節(jié)點之間的層級差，以實現(xiàn)去層級跨度約束的裂縫消除，而且該方法不需額外繪制地形面片，可以保持起伏的地形地貌。

3 試驗與分析

本文依托中國測繪科學研究院研制的NewMap軟件平臺，嵌入提出的地形裂縫消除算法，以四川省典型山區(qū)地形數(shù)據(jù)為例對本方法進行效果驗證。其中，高程數(shù)據(jù)來源于SRTM，經(jīng)緯度范圍為97.5°—108.5°E，26.2°—34.1°N，水平分辨率為90 m，豎直分辨率為0.1 m；影像數(shù)據(jù)來源于國際科學數(shù)據(jù)服務(wù)平臺Landsat陸地衛(wèi)星遙感影像數(shù)據(jù)。試驗的硬件環(huán)境為：CPU Pentium Dual Core E5300 2.60 GHz，內(nèi)存1.96 GB，顯卡NVIDIA GeForce 6800。高程、影像四叉樹金字塔依托NewMap TerrainPublish軟件進行構(gòu)建，金字塔大小分別為15.76、63.34 GB。

依據(jù)本文算法進行瓦片間裂縫消除試驗的部分效果如圖7所示，其中圖7(a)為裂縫消除前三維地形可視化畫面；圖7(b)為裂縫消除后的可視化結(jié)果。對比兩幅圖片可以發(fā)現(xiàn)，本文算法在保證地形裂縫正確且完全消除的同時，能夠很好地再現(xiàn)高低起伏的三維地形。

圖7 本文算法裂縫消除前后對比

在瓦片裂縫處理時間上，首先測試了任意選擇的某一視點下裂縫處理的瓦片數(shù)量及每個瓦片處理時間，如圖8所示。從圖中可以看出，單個瓦片的處理時間最小值為0.021 ms，最大值為0.15 ms；其次，隨機選擇某一路徑漫游進行測試，從圖9可以看出，每幀處理的瓦片數(shù)量基本維持在1～20個瓦片數(shù)，處理時間最小值為0.03 ms，最大值為0.74 ms。因此，結(jié)合圖8、圖9可知，每一幀裂縫消除的總時間最多不超過1 ms，消耗時間很少。

圖8 單個瓦片裂縫處理時間

圖9 漫游路徑下裂縫處理時間

與前文中提到的裙邊算法進行比較，由于本文算法是修改瓦片裂縫范圍內(nèi)的頂點高程值，因此不會產(chǎn)生多余的補丁，減少率為100%；從線框模式也可以看出裂縫消除后的瓦片網(wǎng)格并沒有增加多余的三角面片。

4 結(jié) 語

本文提出了去LoD層級約束的海量三維地形裂縫實時消除算法，在四叉樹地形表示結(jié)構(gòu)和LoD控制規(guī)則的基礎(chǔ)上，利用四叉樹結(jié)構(gòu)及父子節(jié)點間隱含的鄰居關(guān)系，實現(xiàn)了地形裂縫的實時消除。以四川省典型山區(qū)地形數(shù)據(jù)為試驗案例，進行了地形裂縫消除算法驗證。試驗結(jié)果表明，本文算法不需任何額外的“補丁”，而且瓦片層次跨度不受限制，在能正確消除裂縫的前提下最大限度地再現(xiàn)了起伏的真實感三維地形地貌，同時裂縫消除效率較高。總體而言，本文提出的識別模型較優(yōu)于常見地形裂縫消除方法且操作簡單、便于計算，更適用于海量地形的可視化表達與分析。