楊 燕，王慧青，焦 越

東南大學(xué) 儀器科學(xué)與工程學(xué)院，南京210096

1 引言

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

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

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

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

2.1 CPU-GPU結(jié)合的模型構(gòu)建方式

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

圖1 CPU-GPU結(jié)合的渲染方式

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

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

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

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

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

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

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

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

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

根據(jù)三個方向的坐標(biāo)值構(gòu)造包圍盒，該包圍盒對角線的長度為：

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

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

圖3 裂縫產(chǎn)生示意圖

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

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

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

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

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

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

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

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

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

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

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

圖4 視錐體構(gòu)造

3.2 基于視點的LOD無縫繪制

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

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

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

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

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

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

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

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

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

圖5 裂縫消除示意圖

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

4 實驗結(jié)果

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

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

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

圖6 不同調(diào)節(jié)參數(shù)渲染的網(wǎng)格

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

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

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

表1 不同網(wǎng)格尺寸的渲染結(jié)果對比

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

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

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

圖7 本文算法與邊刪除技術(shù)的對比

表2 本文算法與邊刪除算法的技術(shù)對比

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

5 結(jié)束語

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