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

楊 燕，王慧青，焦 越

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

1 引言

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

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

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

2 地形數(shù)據預處理

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

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

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

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

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

2.2 地形數(shù)據組織及包圍盒構建

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

圖2 地形數(shù)據分塊

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

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

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

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

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

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

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

圖3 裂縫產生示意圖

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

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

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

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

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

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

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

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

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

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

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

圖4 視錐體構造

3.2 基于視點的LOD無縫繪制

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

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

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

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

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

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

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

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

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

圖5 裂縫消除示意圖

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

4 實驗結果

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

實驗1 不同調節(jié)參數(shù)mratio 控制下的地形實時渲染效果。

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

圖6 不同調節(jié)參數(shù)渲染的網格

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

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

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

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

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

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

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

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

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

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

5 結束語

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