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

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

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

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

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

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

1 帶有鄰居關系的地形四叉樹結構

當相鄰地形網格的LoD層次等級不相同時，網格邊界處的分辨率不一致則很可能造成地形裂縫。因此，實現地形裂縫消除的關鍵在于運用四叉樹數據結構對地形進行LoD動態實時繪制時，能夠對地形網格節點的鄰近關系進行準確地識別及判斷。為此，本文首先建立包含邊鄰居與角鄰居的地形四叉樹結構，即對傳統地形四叉樹增加以下約束：

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

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

圖1 四叉樹地形結構

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

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

圖2 瓦片的鄰居關系

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

2 地形裂縫實時消除算法

2.1 瓦片間鄰居關系及其狀態判斷

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

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

2.1.1 裂分葉節點鄰居信息及其狀態確認

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

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

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

2.1.2 合并葉節點鄰居信息及其狀態確認

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

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

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

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

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

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

圖3 瓦片左邊鄰居節點情況

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

圖4 LoD層級相等

圖5 LoD層級相差為1

圖6 LoD層級相差為2

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

3 試驗與分析

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

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

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

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

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

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

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

4 結 語

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