結合視點變換的三維地形無縫繪制算法

楊 燕，王慧青，焦 越

東南大學 儀器科學與工程學院，南京210096

1 引言

隨著測繪領域采集技術和存儲技術的發展，獲得的三維地形數據規模越來越大。當前，國內外主要通過多分辨率技術[1-2]對地形數據進行精簡，實現海量三維地形渲染。但由于不同分辨率網格在邊界處存在層次差異，渲染過程中易出現裂縫，裂縫問題是多分辨率地形中必須解決的一個問題。

對于裂縫消除，傳統方法主要有裙帶算法和調整網格邊界頂點。裙帶算法[3-4]是為不同層級的地形網格在其邊緣處添加一個包圍體，當網格層次不一致時，由于該包圍體的存在，在視覺上可擋住裂縫。但裙帶算法為消除裂縫增加了較多的三角網格，且高度難以控制。調整網格邊界頂點[5-6]分為分裂較高層次網格和合并較低層次網格，該方法應用范圍最廣，但當相鄰網格層次差大于1時算法會變復雜。除以上兩種算法外，文獻[7]提出基于漸進網格的聚類層次模型，可有效消除裂縫。文獻[8]提出在相鄰地形交界處保證重合頂點獲取的高程值相同來實現無縫連接。文獻[9]提出通過構造曲線擬合函數控制不同層次網格頂點的布局從而消除因LOD產生的裂縫。文獻[10]提出根據線性差值算法修正四叉樹中互為鄰居關系的瓦片高程以消除地形裂縫。但這些方法都或多或少需要增加最終繪制的網格數量，且無法解決地形在相鄰層級間分辨率的突變問題。

鑒于以上分析，本文提出一種改進的基于視點的裂縫消除算法，通過CPU-GPU協同工作，根據精度要求完成數據的分層分塊，利用紋理映射技術生成LOD 精細模型，并根據視點動態調整頂點位置達到消除T型裂縫的目的。

2 地形數據預處理

2.1 CPU-GPU結合的模型構建方式

本文提出一種CPU-GPU[11-12]協同構網的方式，渲染流程如圖1 所示。整體框架包括CPU 模塊和GPU 模塊。首先將地形高度圖作為紋理數據，以二維數組的格式保存至GPU 中。在CPU 中，根據精度要求建立粗糙LOD模型[13-14]，每一個網格中只保存四個邊界頂點的坐標及其網格尺寸。然后通過視錐裁剪將符合要求的子節點隊列傳入GPU中。

圖1 CPU-GPU結合的渲染方式

在GPU中，利用高速處理器并行構建LOD模型，生成精細網格，再通過紋理映射技術對高度圖進行頂點采樣，獲取高程數據并映射到網格頂點上，實現從二維頂點到三維頂點的轉變。然后根據視點動態地調整頂點位置以實現裂縫消除，完成地形渲染。

這種利用CPU-GPU 結合生成多分辨率模型的方式，將構建精細網格的工作交給GPU，CPU中只需根據視點對子節點進行視錐裁剪，充分利用GPU 并行處理的能力，減輕CPU的負載。同時，GPU中有成百上千可高速并行工作的處理器核心，地形的網格構建和渲染工作交由GPU 并行處理，比在串行的CPU 上運行速率更快，可以節省整個系統中數據的處理時間。

2.2 地形數據組織及包圍盒構建

本文選擇DEM 數據作為高度數據，以規則格網方式組織地形數據。采用自頂向下的規則建立多分辨率四叉樹模型，模型中每塊地形邊長都需滿足(2n+1)×(2n+1)，以左上角為起點，對于右側和下方不滿足條件的地形塊，以無效數據填充。圖2（a）所示即為四叉樹LOD 模型的生成過程，根據每個節點的精度是否達到系統的閾值來判斷當前節點是否需要繼續剖分。如果剖分，則上一層的子節點是下一層的父節點，每個非葉子節點包含四個子節點。為了減少在CPU中計算每個頂點的具體坐標值以及構網的過程，將每個地形塊的具體三角化過程放入GPU中。每個子節點只保存四個特征頂點的坐標信息以及在世界坐標系中的尺寸，地形渲染時這些數據會一同傳入GPU。如圖2（a）所示，1、2、3、4即為地形子節點A的四個特征頂點。

圖2 地形數據分塊

GPU 中調用的渲染函數是限制本文算法性能的關鍵，每個子節點都必須調用一次渲染函數。如圖2 所示，輸入數據為圖2（a）中的某個子節點，在GPU中該節點被繼續分割成圖2（b）所示的(2n+1)×(2n+1)頂點（圖2（b）中n 取為3，子節點分割為9×9 頂點），這些頂點是繪制地形的最小單元。每個子節點中頂點個數達到65×65時，若繼續細分頂點，最終渲染的地形差異不大，但會產生數據冗余，如果少于9×9，將不足以表達地形的細節，因此地形子節點的個數需控制在9×9 至65×65之間，即n 需控制在3 至6 范圍內。假設n 取6，葉子節點最高處于m 層，整個地形的最高分辨率為(2m+6+1)×(2m+6+1)，考慮到本文的DEM 數據，葉子節點處于第8級時，地形的最高分辨率達到(214+1)×(214+1)，此時頂點的精度在五米左右，繼續對節點進行剖分，精度提升不大，但性能將有所降低。因此本文m 值最高取8，此刻渲染的地形精度已滿足要求。

在GPU中根據每個頂點的序列號獲取其三維坐標的方式如公式（1）所示。假設某個頂點對應的序列號為(i,j)，根據此序列號獲得其在x 軸和z 軸方向的實際坐標值，進而獲取其高程值：

其中，Xmin、Zmin為當前地形塊四個特征頂點中左上角的頂點坐標，heightmap 為獲取頂點高度的函數，l 為當前的頂點間隔。

在實時渲染時為了利用視錐體裁剪部分節點，可對地形塊構造包圍盒[15]。包圍盒的四個頂點取節點的四個特征頂點，坐標分別為(Xmin,Zmin)、(Xmin,Zmax)、(Xmax,Zmin)、(Xmax,Zmax)。包圍盒的高度Y 取該子節點區域內所有采樣點的最大高程值，為減少數據的訪問量，可用四個邊界頂點以及對角線交點中的最大值代替。

根據三個方向的坐標值構造包圍盒，該包圍盒對角線的長度為：

3 基于視點和GPU的LOD地形無縫繪制

在海量地形實時渲染時，由于相鄰網格細節層次不一致，導致高層次網格與層次較低的網格邊線不一致，在相鄰瓦片間產生空隙，致使在虛擬空間中漫游時出現裂縫的現象。如圖3 所示即為裂縫產生的示意圖。為了避免裂縫問題，保證畫面渲染的連貫性，消除裂縫必不可少。

圖3 裂縫產生示意圖

對裂縫進一步分析發現，在高層級節點中x 和z 方向序列號皆為偶數的頂點在低層級中被保存下來，這些頂點對裂縫無影響。但是在x 或z 方向序列號中出現奇數的頂點在低層級中不再存在，在相鄰地塊交界處，也是因為這些奇數序列的頂點才導致裂縫的產生。因此本文提出只要調整序列號為奇數的頂點的位置，使其在網格邊界處與序列號為偶數的頂點重合，即可消除裂縫。

相對于傳統的垂直裙帶法、增邊法（刪邊法）等方法，本文提出了一種改進的基于視點的動態調整頂點法處理裂縫，該算法在生成網格過程中直接處理網格的裂縫，無需添加多余的網格，也不需要限制相鄰層級層次差≤1。

3.1 基于視點和包圍盒的視錐裁剪

為了提高系統的性能，減少每次渲染的三角網數量，在繪制地形之前需要先剔除一部分網格。本文采用視錐體方式[16]，在向GPU 傳遞子節點時，只傳遞在視錐體范圍內的節點，其余節點一律舍棄。視錐體如圖4所示，它有六個面，本文假設每個面的法向量都指向視錐體內部，則可以確定六個裁剪方程：

對于某個頂點P，其坐標為(xp,yp,zp) ，該頂點到其中某個面的距離為：

此時計算出的距離Dis 是一個帶符號的變量，表示在平面的不同方向，若符號為正，表明點在平面正方向，反之，點在平面反方向。若頂點p 到六個面的距離中只要有一個是小于0，可判斷該頂點此時在視錐體外部，否則位于視錐體內部。

基于以上方法，判斷一個地形塊節點是否在視錐體內部，即判斷其包圍盒與視錐體的位置關系。首先可確定包圍盒對角線的距離為size，根據公式（4）計算包圍盒中心點到視錐體六個面的距離，若包圍盒中心點到某個裁剪面的距離Dis 小于-size/2，可判斷此時整個包圍盒都不在視錐體中，屬于不可見地塊。

基于以上分析，視錐體與包圍盒的關系可以分為以下三種：

（1）地形塊節點對應的包圍盒完全在視錐體內部，該節點屬于可見節點，可根據視點到節點中心點的距離判斷是否需要繼續剖分，如圖4中的包圍盒A所示。

（2）地形塊節點與當前視錐體存在交叉，認為該地形塊部分存在于視錐體內部，將根據距離因素判斷是否需要繼續剖分，若剖分，將依次判斷四個子節點是否在視錐體內部；否則該節點將被直接存入渲染隊列中，等待傳入GPU，如圖4中的包圍盒B所示。

（3）節點完全位于視錐體外部，舍棄該節點，如圖4中的包圍盒C所示。

圖4 視錐體構造

3.2 基于視點的LOD無縫繪制

在渲染地形節點前，為了明確最終哪些節點將被傳入GPU，需提前計算每個LOD 層級的節點覆蓋的最遠距離。由于本文采用的四叉樹結構，因此相鄰層級的節點之間分辨率差異為四倍，在線性方向上，分辨率差異為兩倍[17]。基于本文自頂向下創建網格模型的過程，在生成網格的過程中創建一個可視距離數組m_visibilitys。根據葉子節點最高層級為7 以及相鄰網格間線性分辨率差異為2倍，可計算出整個地形的最遠距離fardist ，根據該距離可計算出每個層級之間距離的遞增因子sec：

根據該遞增因子可獲得每一層級最終的可視距離：

地形渲染時，從根節點開始進行判斷，若該節點至視點的最小距離大于當前層級的可視距離，則認為該節點超出當前視點的可視距離，該節點不予繪制。若節點至視點的最小距離在當前層級和下一層級的可視距離范圍內，且節點在視錐體內，則將該節點添加至渲染隊列。若節點至視點的距離小于下一層級的可視距離，將對該節點進行剖分，并遞歸判斷其四個子節點。最終，所有需要被渲染的節點都保存在渲染列表中。

為了消除裂縫，在獲取每一層級葉子節點的可視距離時，同時會獲取該層級的調整范圍，渲染時每個頂點都需進行判斷，若頂點至視點的距離處于當前層級的調整范圍內，則該頂點將會相對原來的位置發生一定的偏移。每一層級的調整范圍為其中：

其中，mratio 為調節參數，根據該參數可以調節頂點從何處開始發生調整，假設該值設置為0.6，此刻變形區域占每個地形塊總體的比例將大于40%。

地形子節點被傳入GPU 中后生成地形模型，獲得每個頂點的實際坐標，根據每個頂點的實際坐標會判斷該頂點的位置是否調整，調整公式如下：

其中，x、z 為局部坐標轉換為世界坐標后的對應坐標值，dis 是當前頂點到視點的距離，clamp 函數保證返回值始終處于0-1 之間，frac 函數返回當前數值的小數部分，scale 為當前地形子節點的尺寸大小，griddim 為當前子節點將會在x、z 方向分割的頂點數，它是繪制地形的最小單元，morph 為當前節點的調整系數。從上述公式可以看出，頂點分為兩種情形：

（1）某個頂點到視點的距離小于當前可變距離的開始位置，即mstart ，此刻clamp 函數直接返回1，因此參數morph=0，此時頂點無需調節。

本文算法對頂點位置的調整過程如圖5所示。圖5（a）為高層級地形的一部分，離視點較近，頂點未偏移，圖5（d）為低層級的地形，位置緊挨高層級地形塊，圖5（b）、（c）和圖（a）處于同一層級，但由于圖5（b）、（c）中的頂點離視點越來越遠，因此其中序列號為1 和3 的頂點的位置相對于其原始位置發生了一定的調整，圖5（c）離視點的距離比圖5（b）更遠，頂點相對于其原始位置偏移的更多。在與圖5（d）的交界處，根據公式（8）和（9）可知，此時序列號為奇數的頂點將會與其相鄰的頂點重合，因此在邊界處的頂點都和圖5（d）重合，消除裂縫。實驗部分給出了最終的繪制效果，可以看出，最終繪制的地形不存在裂縫，且網格保持連續。

圖5 裂縫消除示意圖

通過上述可知，在相鄰層級的地形交界處，高層級地形中序列號為奇數的頂點相對原來的坐標已被調整，和序列號為偶數的頂點相重合。在邊界處，高層級地形塊的頂點和低層級頂點重合，裂縫被消除。該方法不僅能在生成網格的過程中直接消除裂縫，同時層級之間的過渡較為平緩，不會產生突變的現象。

4 實驗結果

為了驗證該算法的可行性，本文進行了相關實驗。實驗的硬件平臺CPU為Intel?Core?i5-3470 3.6 GHz，內存為8 GB，顯卡型號為NVIDIA GeForce GT 630，顯存為1 GB，開發工具為Visual Studio 2010，DirectX 9.0版本，該實驗渲染時的屏幕窗口大小為1 024×768。測試數據為來自云南省某縣級區域的DEM 數據，該地區地形主要為山區，區域范圍為90 km×40 km。四叉樹模型自頂向下分為八層。設計以下三個實驗來驗證本文中所描述的算法。

實驗1 不同調節參數mratio 控制下的地形實時渲染效果。

圖6（a）為mratio=1 時的地形，根據公式（10）可知，參數為1 時mstarti=mendi，morph=0，頂點位置未發生調整，渲染的地形呈現原始狀態，因此存在裂縫，圖6（b）是裂縫的放大示意圖。圖6（c）為mratio=0.8 時渲染的地形，從圖中可看出有部分網格發生了調整，且每一次調整的幅度較大，但由于此刻mratio=0.8，因此只有靠近邊界線的一部分頂點位置被調整，大部分頂點維持不變。圖6（d）為mratio=0.6 時渲染的地形，此刻位置發生偏移的頂點數量更多，只有部分頂點還維持不變，頂點間每次調整的幅度與0.8時相比明顯小了很多。

圖6 不同調節參數渲染的網格

以上實驗結果表明，本文的算法可以有效解決裂縫問題，此外當mratio 位于0.8至0.9之間時，既能保證大部分網格保持原樣，也能保證部分頂點發生動態偏移，在邊界處可消除裂縫。因此，mratio 取0.8 至0.9 范圍內的數值較為合適。

實驗2 在GPU中繪制每個子節點時選取四種網格尺寸進行對比。

表1為不同網格尺寸下渲染的三角形個數、GPU占用率以及幀速率對比。從表1 中可以看出當網格尺寸達到65×65 時，每一幀渲染的三角形個數接近百萬，但整體系統未出現卡頓現象。觀察GPU 的負載，雖然渲染的三角形個數不斷增加，但GPU的負載變化不大，始終維持在20%以內，且CPU的負載維持在10%左右。測試結果說明本文提出的CPU-GPU協同工作的渲染方式可以充分利用GPU的超高計算能力，降低CPU負載。

表1 不同網格尺寸的渲染結果對比

觀察幀速率可看出，幀速率始終維持在60幀左右，并未隨著三角網個數的增長而降低，完全滿足流暢性的需求，達到了實時渲染與數據調度的平衡。

實驗3 在相同的硬件環境下，將本文的裂縫消除算法與傳統的邊刪除裂縫消除技術進行了比較，采用的數據為根據柏林噪聲生成的地形數據。

圖7（a）為本文算法渲染的地形，圖7（b）為傳統LOD 技術渲染的地形，圖7（c）和圖7（d）為兩種方法裂縫處理的細節；表2為本文算法與邊刪除技術的一些參數對比。

圖7 本文算法與邊刪除技術的對比

表2 本文算法與邊刪除算法的技術對比

實驗結果表明，邊刪除技術對層級之間的要求較高，需控制層次差不超過1，對于不符合要求的地形塊需不斷進行剖分，產生數據冗余，且該算法中網格模型的生成等一系列工作都是在CPU 中完成，因此繪制階段CPU 負載在45%左右。本文算法對相鄰地塊層級無限制，在繪制階段對于CPU 占有率低于10%，幾乎無占用。此外兩種算法的幀速率都穩定在60 f/s 左右，但本文平均繪制的三角網個數大于邊刪除法，說明本文的算法可以較好地保持地形的基本地貌特征。

5 結束語

本文在分析常規方式消除LOD模型中的裂縫的基礎上，提出一種基于視點的裂縫實時消除算法。該方法在數據預處理階段根據精度要求生成粗糙的LOD 模型，并構造相應的包圍盒；然后利用視錐裁剪和紋理映射技術生成精細的網格模型；最后根據視點動態調整頂點位置以實現T 型裂縫的消除。此外，本文采用CPUGPU協同工作的方式，將大量工作從CPU移植到GPU，提升了整個系統性能。實驗結果表明，本文提出的方法不需任何額外的補丁，地形的層次差不受限制，即可在生成地形的過程中將裂縫刪除，每次渲染的三角網個數可達到百萬級別，適用于海量地形。