基于GeometryClipmap的三維地形可視化研究

殷青松　哈力木拉提·買買提

(新疆大學新疆多語種信息技術實驗室　新疆 烏魯木齊 830046)

?

基于GeometryClipmap的三維地形可視化研究

殷青松哈力木拉提·買買提

(新疆大學新疆多語種信息技術實驗室新疆 烏魯木齊 830046)

摘要隨著數字科技的廣泛應用和信息化普及的逐漸深入，實現地形的三維可視化的重要性日漸彰顯。但目前的普通PC內存容量無法容納海量的幾何數據和紋理數據。為解決這個問題并提高繪制的效率，采用Geometry Clipmap算法繪制地形，充分利用GPU以提高繪制效率，通過頂點紋理獲取各頂點高程值。同時，簡化了三角形條帶的組織方式，使用簡化的視錐體裁剪方法和動態確定繪制層數方法減少需要繪制的頂點數。根據特定層結構，提出數據更新的新方法(二進制定位法)減少視點移動時各幀的數據更新量。實驗結果表明，該方法使用很少的內存完成大規模地形繪制，且取得了較高的幀率，漫游流暢，保證了地形的真實感，能滿足大規模地形實時可視化的要求。

關鍵詞幾何剪切圖剪切圖地形可視化頂點紋理獲取圖形處理器

0引言

三維地形渲染從用途分類，主要有兩種方式：一種是人為設計各種地形并采用多種紋理素材。通過混合、拼接等操作實現地形的渲染[1,2]，這種方式常用于大型3D游戲等人為設計的虛擬環境渲染中。它的特點是高程和紋理人為合成設計，可重復利用，所以數據量小，比較容易實現。另一種是采用真實的高程數據和紋理(如通過衛星探測拍攝)來進行三維地形的渲染[3,4]。這種方式一般用于需要真實地形模擬的場合，如數字地球、軍事用途等。采用第二種方式實現三維地形渲染時，要處理的數據量相當大，一般內存容量不能一次容納這么多數據，所以此法對數據的加載和調度算法要求比較高，實現難度更大。為了減少數據的處理量，提高渲染速度，LOD(LevelofDetails)細節層級技術應運而生，產生了許多優秀的算法。LOD技術指根據物體模型的節點在顯示環境中所處的位置和重要度，決定物體渲染的資源分配，降低非重要物體的面數和細節度，從而獲得高效率的渲染運算。

從三維地形網格圖的實現方式來看，也主要可分為兩類：規則格網Grid模型[5]和不規則三角網TIN模型[6]。

近年來，隨著GPU的出現和迅速發展，GPU強大的數據處理能力尤其是對浮點型數據的處理能力極大地緩解了CPU的負擔，所以最大限度地利用GPU來渲染地形能夠使渲染速度大幅加快。相比TIN模型，具有規則結構的Grid模型在利用GPU提高效率方面明顯更具優勢。

由于傳統的LOD算法(如ROAM算法[7]、基于四叉樹的地形算法[8]等)需要實時地建立和修改網格結構，極大地依賴CPU，限制了繪制速度，所以近年來的研究都專注于面向GPU的LOD算法，Mipmap算法和收稿Clipmap算法[9]就是其中的佼佼者，極大地提高了繪制速度并節省了存儲空間。Clipmap算法比Mipmap算法復雜，但占用更少內存。

2004年Losasso和Hoppe提出了GeometryClipmap算法。這是一種基于視點的連續LOD方法，將地形看作是一張由高程數據組成的紋理圖像，采用Clipmap結構將地形幾何數據組織成嵌套的規則網格形式并進行繪制[10]。Asirvatham和Hoppe將GeometryClipmap結構每層數據分解成多個規則塊，并利用了顯卡的VTF(VertexTextureFetch頂點紋理獲取)新特性，提高了繪制速度[11]。康寧等使用“裙”的方法解決各層之間的裂縫問題，但數據精度仍有待提高[12]。袁建鋒等采取直接改變GeometryClipmap結構不同層邊界對應頂點高程的方法避免裂縫，減少了彌補裂縫的計算量，但仍會產生視覺不連續的情況[13]。王春通等過降低GeometryClipmap結構兩相鄰層中較精細層對應頂點高度值的方法，避免了裂縫的產生[14]。張浩等給出了一種不對稱GeometryClipmap結構，在構造GeometryClipmap結構時，不再以視點為中心，而是以視點偏移后得到的中心點為新的中心，并通過使用不對稱GeometryClipmap結構的更新方法，提高了原方法對網格的利用率[15]。Clasen等將GeometryClipmap結構擴展到球面[16]。

綜上所述，要使用面向GPU的Grid模型LOD算法模擬真實地形，GeometryClipmap算法無疑是一個很好的選擇。本文采用GeometryClipmap算法來實現三維地形網格的繪制，并利用SM3.0以后版本顯卡的VTF新特性使大繪制任務轉移到GPU中實現。采用了特定的GeometryClipmap層結構，并根據其特定結構優化了三角形條帶的組織方式，使用了簡化的視椎體裁剪方法，運用了隨視點高度動態調整Clipmap層數的方法，大大減少了需要繪制的頂點數。尤其是提出了與層結構對應的各層位置調整和數據更新方式——二進制定位法，以保證各層嵌套嚴密，并大大減少了數據更新量。

1Geometry Clipmap算法介紹

GeometryClipmap算法是Losasso和Hoppe提出的嵌套規則網格LOD算法。主要思想(如圖1所示)：把地形高程數據看做一張2D高程紋理圖，然后類似于Mipmap，將其過濾為不同分辨率的L層棱錐(相鄰的兩層中較精細層的行寬是較粗糙層行寬的兩倍)，但完整的棱錐太大，存儲器僅有的容量容納不下。所以算法在每層緩存一個數據大小都為n×n的窗口，各層窗口組成一個以視點為中心的嵌套的規則網格結構(最粗糙層的窗口恰好完全覆蓋當層棱錐)。由于較粗糙層中間部分會被較精細層覆蓋，所以渲染時除了最精細層全部渲染，其他層都只渲染一個口字型區域。由于只有最粗糙層窗口完全覆蓋了當層的棱錐，所以當視點移動時，只有最粗糙層窗口保持不變，其他各層窗口隨視點移動在各自所在的棱錐各層移動更新。

圖1　高程數據組織原理圖

最初的方法通過將每層的高程數據分別存入一個頂點緩沖區來實現，但這樣的方式需要大量CPU干涉。所以當顯卡具有頂點紋理新特性(即在頂點著色器中使用紋理的能力)時，將每層的高程數據存儲為一個2D紋理的方法成為更好的選擇，它能解放CPU，使大部分渲染任務都轉移到GPU上執行，利用GPU強大的浮點型數據運算能力，大大提高渲染的效率。

采用頂點紋理方式的實現方法為：將頂點坐標(x,y,z)分為單獨的兩部分：水平面位置(x,z)和高度值y坐標。前者可通過計算得知，存儲為常量數據。后者則從DEM文件中讀取出來并以單通道2D紋理形式保存在顯卡中，稱之為高程圖，并為每一層設置一個單獨的大小為n×n的高程圖。當視點移動時，這些高程圖也隨之更新。在頂點著色器中各層頂點通過VTF重新獲取保存在相應層紋理中的高程值。

2Geometry Clipmap算法具體實現

2.1Geometry Clipmap層結構設計

每層的邊大小n都為2k-1，這樣可以使層間邊界上的較粗糙的層的頂點位置剛好落在較精細層上的頂點上，有利于避免產生裂縫。

最精細層全部渲染，設置成一個整塊。

除最精細層外，其他層都只渲染一個口字型區域，分為18個區塊，如圖2所示。

圖2　Geometry Clipmap各層區塊劃分

可以把每層(最精細層除外)劃分為3種固定大小類型，共18個區塊。如圖2所示，三種區塊大小可固定表示為m×m(1至12白色區塊)，m×3(13至16灰色區塊)和(2m+1)×2(17、18黑色區塊)，其中m=(n+1)/4。這樣做的好處是我們可以利用固定的頂點序列及索引序列來組織三角形條帶，方便簡單地調用繪制函數把每層的網格結構繪制出來，而且還有利于后期的視錐體裁剪操作。

2.2獲取頂點坐標數據

對于水平面位置(x,z)部分，很容易實現，只需要定義一個大小為n×n×2(n×n個頂點，每個頂點水平位置有x和z兩個數據)的數組并可通過計算定初值。然后創建頂點數組對象VAO和頂點緩沖區，將數組存入頂點緩沖區，最后指定頂點屬性數組并啟用頂點屬性數組即可。

對于高度值y坐標部分，就相對要復雜點。首先需要從DEM文件中讀取高程數據。本文采用國際標準的USGS_DEM格式的DEM文件。按照該文件特定的存儲數據的格式，可以方便地將數據讀取出來，并以數組形式保存。然后就可以創建并綁定紋理，將數組中的高程值以單通道紋理方式保存于顯存中。具體步驟如下：

1) 創建紋理名稱；

2) 將紋理名稱綁定到二維紋理綁定點；

3) 指定二維紋理的寬高，設置為單通道，并指定構成二維紋理的數組；

4) 設置放大和縮小紋理過濾器的過濾方式為最近鄰過濾。

接著就可以通過VTF方式獲取高程值，具體方法為在頂點著色器中定義紋理采樣器，并通過頂點x、z位置坐標計算出紋理坐標。最后使用GLSL中的內置函數texture從高程紋理圖中采樣出高程值?？梢酝ㄟ^紋理數組與VTF結合的方式來獲取各層頂點的高程值。

2.3視錐體裁剪

顯而易見，地形繪制的頂點數量是相當大的，而視域內所見的區域通常只是整個地形的一部分。所以如果只讓GPU處理視域內頂點的數據，就可以大大減少計算量，提高繪制速度同時又不影響真實感。在調用draw函數前進行簡單的視錐體裁剪，就可以達到這個目的。將視錐體左右平面定為裁剪平面。每個m×m塊可以通過四個角中的兩個頂點是否在左右平面之間來判斷這個塊中是否有頂點在視錐體中，若有，則繪制這個塊，否則不繪制。這種方法使每層占絕大多數頂點的12個m×m塊平均減少到4個，且只需少量計算即可剔除大量不在視域內的塊，避免了CPU對每個頂點進行計算。

另外，若視點升得太高，距離精細層太遠，那么實際上精細層的精細表示是一種浪費?？筛鶕朁c距離精細層的距離動態決定Clipmap的層數。具體方法為如果視點到某層的距離大于0.4ngl(gl為各層相鄰頂點的間距)，則不繪制這層及更精細的層。此方法可在不影響顯示效果的前提下減少不必要的繪制開銷。

2.4繪制三角形條帶

在進行繪制時，使用頂點的索引序列和三角形條帶方法繪制，而不直接使用頂點坐標和單個三角形。這樣做的好處是可以大大節省存儲空間，并且更簡單易行。

一個頂點坐標包括3個浮點型數據，共12個字節；而一個索引則只需1個整型數據，只占4個字節，使用索引序列來繪制三角形占用內存明顯更少。如圖3中第一行條帶所示，10個頂點組成有8個三角形的三角形條帶。如果使用單個三角形方式繪制，每個三角形3個頂點，共需存儲3×8=24個頂點；而使用三角形條帶方式繪制則只需一個10個元素的頂點數組即可。在地形繪制這種需要繪制的頂點比較多的情況下，盡可能地利用頂點索引和三角形條帶來繪制，可以大大節省存儲空間。

圖3　組織三角形條帶的頂點索引序列

在繪制時使用組合繪制函數glMultiDrawElements繪制三角形條帶，與文獻[12]文獻[17]相比，這樣可以進一步地減少存儲的頂點數量，并簡化了索引序列的組織。如圖3所示，將三角形條帶第一行部分的索引序列加上頂點數10，就是第二行部分的索引序列，后面各行依此類推。

具體實現方法為：先創建并綁定索引緩沖區；然后按照各區塊的結構將索引組織成三角形條帶索引序列并存入索引數組；接著將數組保存在顯存的索引緩沖區中，最后調用glMultiDrawElements函數按照索引緩沖區中的索引序列繪制三角形條帶。

由于GeometryClipmap各層的結構是固定的，所以各不同區塊的索引數組都是固定的，并不隨每幀的數據更新變化而改變。相比文獻[12]和文獻[17]，這樣可以進一步節約CPU資源，提高繪制效率。

2.5數據更新

當視點移動時，各層也會相應地移動更新，但由于在相鄰各層之間，較粗糙層相鄰頂點間隔是較精細層相鄰頂點間隔的兩倍。各層的移動更新步調不一致，就會導致各層之間不能維護完整嚴密的嵌套層級結構。

圖2中所示第17、18區塊，叫做內部調整塊，通過對它的位置的調整，我們可以完美地解決各LOD層級更新的問題。

各層更新步驟以第18區塊為例，假定有1個無內部調整塊的精細層和三個帶內部調整塊的口字型區域層，如圖4所示。

圖4　各層位置更新方式

注：黑色的是各層的內部調整塊，灰色的是各層大小為m×3的塊，視點一步移動兩小格(即最小內部調整塊寬度)

如果各層第18區塊調整塊在左側標記為1，在右側標記為0，那么從外層到內層，調整塊初始位置為{0,1,0}。視點向右移動一步后各層調整塊位置變為{0，1，1}。再向右移動一步后各層調整塊位置變為{1,0，0}。由此可見，調整塊跟隨視點的變化規律恰恰類似于二進制數相加減：視點右移幾步，由調整塊初始位置構成的二進制數就加幾；反之，視點左移幾步，由調整塊初始位置構成的二進制數就減幾。根據得到的新二進制數的各位數值是1還是0，就可判斷各層的內部調整塊應該在左側還是在右側。第17區塊內部調整塊的調整方案與第18區塊的相同。

由此推出視點移動時，各層內部調整塊位置的計算方法——二進制定位法：

1) 設置兩個全局數組adjust1[]和adjust2[]，并以0和1為兩數組各元素初始值，以此分別確定z軸方向和x軸方向各層調整塊(即各層17、18區塊)初始位置序列。

2) 將步驟1)中的調整塊序列數組中各元素作為一個二進制數的各位，并將此二進制數轉化為十進制數。

3) 利用三角函數計算視點在z軸和x軸方向的分位移，從而得到視點在兩個方向的移動步數。

4) 將2)中得到的兩個十進制數分別加上3)中的在z軸、x軸方向的移動步數，得到兩個新的十進制數。

5) 用位移和按位與操作計算4)中得到的兩個新十進制數的二進制形式的各位，并以此更新1)中全局數組各元素的值，得到視點移動后各層的調整塊位置。

容易看出，當一個較粗糙層的調整塊位置改變時，它內部的所有更精細的層都會進行位置更新，而它所在的層以及所有更粗糙的層的位置都不變，也就不用更新數據。由于視點的移動是連續的，所以我們總是會更新較精細層的數據，而較粗糙層的數據總是很少更新。也就是說，我們總是只更新精細的幾個層的數據，而不是所有層的數據都更新，這樣可以明顯減少視點移動時各幀的數據更新量，從而提高繪制效率。

由于第17區塊可在上邊或下邊，第18區塊可在左邊或右邊(如圖2中的黑色區塊)，不像其他兩種區塊位置固定不變。所以，在繪制內部調整塊三角形條帶時，需要判斷各層的內部調整塊位置，根據其位置來確定它的頂點索引序列。另外，確定了較粗糙層的內部調整塊位置后，才能確定較精細層的位置，即各層的首頂點位置需要根據各層調整塊的位置算出。

3算法實現

3.1繪制階段流程圖

圖5　流程圖

3.2實驗環境及效果展示

實驗采用的地形高程和紋理數據來自PugetSound，地形繪制的范圍大小為16 256×16 256。采取n的大小為127，層數為8。每層127×127個數據，8層，每個數據為float型，占用內存僅127×127×8×4byte/1024≈504KB。

硬件和軟件環境如表1、表2所示。

表1　硬件環境表

表2　軟件環境表

令視點逐步升高，則所需繪制的Clipmap層數逐漸減少。由圖6可明顯看出，隨著繪制的層數減少，繪制時的幀率越來越大。

圖6　視點高度逐步升高時的平均幀率圖

由圖7可見GeometryClipmap的層層嵌套結構。相鄰兩層，外層頂點間距是內層的2倍。效果如圖8所示。

圖7　線框模式效果圖

圖8　紋理映射效果圖

4結語

本文利用了現代圖形卡的新特性，對大規模地形的繪制進行了研究。利用現代圖形卡的可編程特性和強大的計算能力將GeometryClipmap的繪制任務轉移到GPU上。利用現代圖形卡近年出現的VTF新特性完成了高程值的獲取。特別地，本文詳

細描述了各層的更新方式和內部調整塊的調整方案，解決了視點移動時各層如何更新和調整塊如何調整的問題，保證了各層之間結構嚴密吻合。使用簡易的視錐體裁剪方法和隨視點高度動態確定繪制的層數方法大大減少了繪制的計算量。實驗取得了較高的幀率，視點移動時畫面流暢，可以滿足大規模地形實時可視化的需求。

參考文獻

[1] 趙瑞斌,張燕玲,王繼東,等.特征控制下的多樣圖地形紋理合成算法[J].計算機工程,2012,38(10):197-199.

[2] 王繼東,趙瑞斌,龐明勇.基于特征草圖和分形插值的可控真實感地形合成[J].計算機應用,2013,33(2):519-542.

[3] 王響,雷小永,戴樹嶺.基于視點預測的大規模地形的實時渲染[J].系統仿真學報,2013,25(6):1202-1206.

[4] 李欽,戴樹嶺,趙永嘉,等.分塊LOD大規模地形實時渲染算法[J].計算機輔助設計與圖形學學報,2013,25(5):708-713.

[5] 陳希亮,曹雷,崔平.基于ROAM算法的實時地形可視化研究[J].計算機技術與發展,2013(1):243-247.

[6] 周雪梅,黎應飛.基于Bowyer-Watson三角網生成算法的研究[J].ComputerEngineeringandApplications,2013,49(6):198-200.

[7]DuchaineauM,WolinskyM,SigetiDE,etal.ROAMingterrain:real-timeoptimallyadaptingmeshes[C]//Proceedingsofthe8thConferenceonVisualization’97.IEEEComputerSocietyPress,1997:81-88.

[8]LindstromP,KollerD,RibarskyW,etal.Real-time,continuouslevelofdetailrenderingofheightfields[C]//Proceedingsofthe23rdannualconferenceonComputergraphicsandinteractivetechniques.ACM,1996:109-118.

[9]TannerCC,MigdalCJ,JonesMT.Theclipmap:avirtualmipmap[C]//Proceedingsofthe25thannualconferenceonComputergraphicsandinteractivetechniques.ACM,1998:151-158.

[10]LosassoF,HoppeH.Geometryclipmaps:terrainrenderingusingnestedregulargrids[J].ACMTransactionsonGraphics(TOG),2004,23(3):769-776.

[11]AsirvathamA,HoppeH.TerrainrenderingusingGPU-basedgeometryclipmaps[J].GPUgems,2005,2(2):27-46.

[12] 康寧,徐青,周楊,等.一種基于圖形硬件的海量地形實時可視化算法[J].系統仿真學報,2007,19(17):3988-3992.

[13] 袁建鋒,崔鐵軍,姚慧敏.一種基于GPU的大規模地形實時生成算法[J].海洋測繪,2009,29(1):35-38.

[14] 王春,馬純永,陳戈.基于GPGPU的海量山地地形數據的實時繪制算法[J].計算機應用,2009(8):2105-2108.

[15] 張浩.不對稱的GeometryClipmap算法[D].武漢:華中科技大學,2005.

[16]ClasenM,HegeHC.Terrainrenderingusingsphericalclipmaps[C]//ProceedingsoftheEighthJointEurographics/IEEEVGTCconferenceonVisualization.EurographicsAssociation,2006:91-98.

[17] 殷小靜,慕曉冬,陳琦.基于圖形硬件的海量地形可視化算法[J].火力與指揮控制,2013,37(11):61-64.

ON 3D TERRAIN VISUALISATION BASED ON GEOMETRY CLIPMAP

Yin QingsongHalmurat Mamat

(Xinjiang Laboratory of Multi-Language Information Technology,Xinjiang University,Urumqi 830046,Xinjiang,China)

AbstractWith the wide use of digital technology and the growing popularisation of informatisation, the importance of realising 3D terrain visualisation becomes increasingly clearer. But the normal PC memory capacities cannot accommodate massive geometric and texture data. To solve this problem and to guarantee the efficiency of drawing, we adopted the Geometry Clipmap algorithm to draw the terrain, made the full use of GPU to improve the efficiency of drawing, and obtained elevation values of every vertex through vertex textures. Meanwhile, we simplified the organisation mode of triangle strips, used the simplified view frustum clipping method and the dynamic rendering layers number determination method to reduce the number of vertexes to be drawn. Based on the structure of specific layer, we came up with the new method (binary positioning method) of data update to reduce data updating amount of each frame during the motion of viewpoint. Experimental results showed that the new algorithm completed the large-scale terrain rendering by using a little memory, and got a higher frame numbers with smooth roam, guaranteed the realistic display of terrain, and was able to meet the demand of real-time visualisation of large-scale terrain.

KeywordsGeometry ClipmapClipmapTerrain visualisationVertex texture fetch (VTF)GPU

收稿日期：2014-12-24。國家高技術研究發展計劃項目(2013AA 013702)。殷青松，碩士生，主研領域：計算機圖形學。哈力木拉提·買買提，教授。

中圖分類號TP391.9

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.06.049