基于區(qū)域聚合的柵格地形數(shù)據(jù)簡化算法

郭文普,王天寶,徐東輝,臧傳收

（1.第二炮兵工程學(xué)院,陜西 西安710025;2.第二炮兵駐孝感地區(qū)軍事代表室,湖北 孝感 432000;3.第二炮兵駐石家莊地區(qū)軍事代表室,河北 石家莊 050081）

0 引言

隨著遙感技術(shù)、計算機視覺、計算機圖形學(xué)等學(xué)科的發(fā)展,由航空航天攝影測量或其他測量手段獲取地形數(shù)據(jù)來生成具有高分辨率的三維地形模型已經(jīng)十分普遍。這些由上百萬或更多三角形面片表示的各種地形模型,滿足了人們對地形真實感所提出的越來越高的要求。但大數(shù)據(jù)量的三維場景重建對目前的圖形硬件而言,實現(xiàn)交互方式的實時繪制是十分困難的。因此,早在上世紀70年代,就提出了對三維網(wǎng)格數(shù)據(jù)進行簡化的思想,即用盡可能少的數(shù)據(jù)構(gòu)造原始模型的逼近模型。如文獻[1]中提出了一種頂點聚類算法,算法通過將網(wǎng)格分割成小塊,每一塊中的頂點聚合為一個新頂點來實現(xiàn)簡化。文獻[2]提出了一種區(qū)域合并算法。算法先將網(wǎng)格表面分成若干區(qū)域,然后將區(qū)域的邊界簡化成多邊形,最后對多邊形進行三角剖分,得到簡化網(wǎng)格。這些算法面向的應(yīng)用目的不同,各有優(yōu)點和不足之處。

目前地形的三維建模方式有很多,但總體上可以分為規(guī)則網(wǎng)格建模（如正方形）與不規(guī)則網(wǎng)格建模（如TIN,Triangulated Irregular Network）兩大類。規(guī)則網(wǎng)格建模由于數(shù)據(jù)結(jié)構(gòu)簡單而得到了較為廣泛的應(yīng)用,如常見的DEM（Digital elevation model）數(shù)據(jù)就采用了規(guī)則網(wǎng)格。在借鑒上述簡化思想的基礎(chǔ)上,針對規(guī)則網(wǎng)絡(luò)的地形數(shù)據(jù)提出了基于區(qū)域聚合的地形數(shù)據(jù)簡化算法。

1 區(qū)域聚合數(shù)據(jù)簡化算法

采用規(guī)則網(wǎng)格方法時,地形的分辨率相對固定,在地形平坦區(qū)域存在數(shù)據(jù)冗余的現(xiàn)象,如果能有效地消除這些冗余的數(shù)據(jù),則可在保持真實精度不變的情況下,簡化數(shù)據(jù)。從這一基本點出發(fā),該算法的設(shè)計思想與實現(xiàn)過程如下。

1.1 區(qū)域聚合

針對規(guī)則網(wǎng)格數(shù)據(jù)的特點,沒有采用其他文獻中常用的頂點聚類或區(qū)域合并算法,而是采用了區(qū)域聚合。即將共面或近似共面的若干地形柵格點用這組柵格點的邊界點代替,并進行三角剖分。

1.2 利用最大法向量夾角進行誤差度量

地形簡化的誤差度量是用來量化簡化前地形和簡化后地形的差異,引導(dǎo)地形數(shù)據(jù)簡化,從而使得簡化后的誤差在用戶允許誤差范圍之內(nèi)。如何確定所有頂點或三角面片的重要程度對簡化地形模型的擬真度影響很大。有些算法用點到平面的平均距離作為局部誤差度量來控制點的刪除,有些算法用曲率來計算頂點的重要程度,近年來還有算法采用了體積[3]作為度量誤差,本算法采用了三角面間最大法向量夾角余弦值作為簡化誤差度量。最大法向量夾角θmax,即一組地形柵格點所描述的地形面中每個三角面的法向量間最大的夾角,其余弦值為cosθmax。

由V1、V2、V33個頂點構(gòu)成的三角面的法向量計算公式為:

N1、N22個法向量的夾角θ的余弦值計算公式為:

進行簡化運算時,事先根據(jù)簡化需求指定簡化閾值Ct:

當(dāng)指定閾值夾角為0°,即Ct=1時,地形數(shù)據(jù)簡化為無失真的簡化。

1.3 遞歸算法實現(xiàn)

采用遞歸函數(shù)實現(xiàn)該地形數(shù)據(jù)簡化算法,以最常見的正方形柵格為例,初始地形聚合區(qū)域大小設(shè)置為32*32,算法過程可描述為:

①讀入柵格地形數(shù)據(jù),將柵格地形數(shù)據(jù)按32*32大小進行分塊,對每一塊地形數(shù)據(jù)分別進行后續(xù)的遞歸聚合運算;

②聚合運算函數(shù)

Step1:若分塊大小為1,即僅為一個柵格點,則中止遞歸過程,存儲該點索引坐標（u,v）;

否則:

Step2:計算分塊數(shù)據(jù)的最大法向量夾角θmax的余弦值cosθmax;

Step3:若cosθmax＜=Ct,則聚合成功,中止遞歸過程,存儲該聚合區(qū)域的4個邊角點的索引坐標（u,v）;

否則:

Step4:細化分塊,即將原分塊分成4小分塊,對該4小分塊分別調(diào)用聚合運算函數(shù);

③地形數(shù)據(jù)中,左側(cè)及下側(cè)條狀區(qū)域小于初始分塊區(qū)域大小的柵格點不作簡化處理,直接存儲這些柵格點索引坐標（u,v）;

經(jīng)上述過程運算后,則可得到簡化后的存留的柵格地形數(shù)據(jù)的索引坐標。

注:索引坐標（u,v）為該點在原柵格數(shù)據(jù)中的行列號。

1.4 簡化后地形數(shù)據(jù)的繪制

利用簡化后存留的柵格地形數(shù)據(jù)的索引坐標和原始柵格地形數(shù)據(jù),求出簡化后每個柵格點的真實坐標（x,y,z）,這樣就得到了原地形數(shù)據(jù)經(jīng)簡化運算后的一系列散列點。此時,對這些散列點的繪制,一種作法是采用Delaunay三角化過程,構(gòu)造不規(guī)則三角形網(wǎng)TIN（Triangulated Irregular Network）,從而實現(xiàn)繪制。這種作法存在2個主要的缺陷,一是TIN的生成過程復(fù)雜,二是結(jié)構(gòu)存貯量大。

分析簡化算法流程,不難發(fā)現(xiàn)這些散列點每4個點即可構(gòu)成一個平面（斜面）,可直接進行三角剖分進行繪制,不需要進行Delaunay三角化,圖1為繪制的線框圖。

圖1 存在地形裂縫的格網(wǎng)

很明顯,這種繪制方法存在著大量的地形裂縫,這些地形裂縫存在于每個初始子塊及簡化時細分的子塊間。消除了這些地形裂縫,就可以實現(xiàn)簡化后地形數(shù)據(jù)的繪制了,圖2給出了消除子塊間地形裂縫的示意圖,算法實現(xiàn)時利用存留散列點的坐標索引（u,v）構(gòu)造地形裂縫間的三角面片即可。

圖2 消除裂縫示意圖

2 實驗結(jié)果及分析

采用的實驗數(shù)據(jù)為常州地區(qū)3塊1km*1km的規(guī)則格網(wǎng)地形數(shù)據(jù),柵格精度為1m,分別設(shè)置閾值Ct=1與Ct=0.985進行簡化實驗。

Ct=1,則最大法向量夾角為0°,即簡化時將共面的區(qū)域聚合為由4個項點表示的一個區(qū)域,與原地形相比無失真。

Ct=0.985,則最大法向量夾角為10°,即聚合區(qū)域的面片間夾角均不小于170°。圖3列出了其中一塊地形數(shù)據(jù),數(shù)據(jù)簡化前與用該算法簡化后的格網(wǎng)對比。

圖3 簡化前后的格網(wǎng)對比

由圖3（b）可以直觀地發(fā)現(xiàn),簡化后地形平坦的區(qū)域,用較少的數(shù)據(jù)表示,地形起伏變化大的區(qū)域,用較多的數(shù)據(jù)表示,呈現(xiàn)出多級精度的特點。表1給出了對3塊地形數(shù)據(jù)簡化的相應(yīng)實驗數(shù)據(jù),其中簡化后頂點數(shù)包括原地形數(shù)據(jù)中左側(cè)及下側(cè)條狀區(qū)域小于初始分塊區(qū)域大小的柵格點?？梢钥闯鰧@3塊地形數(shù)據(jù),即使是不失真的簡化,頂點簡化率仍高達85%以上。其中主要原因在于這3塊地形數(shù)據(jù)相對平坦,最高海拔12m,最低海拔1m,且精度很高,1m分辨率,因此數(shù)據(jù)冗余量大,簡化效果好;另一原因在于算法本身通過遞歸過程實現(xiàn)了不同分塊大小的區(qū)域聚合,最大聚合區(qū)域為32*32,最小聚合區(qū)域為4*4。對于山區(qū)地帶地形起伏變化大的數(shù)據(jù),適當(dāng)調(diào)整閾值Ct,也可以取得較好的簡化效果。

表1 實驗數(shù)據(jù)

3 結(jié)束語

對于高精度、大范圍海量地形數(shù)據(jù)快速三維可視化的研究一直是眾多研究者關(guān)注的問題,目前的研究熱點是動態(tài)細節(jié)層次模型[4-5]（Level of Detail,LOD）。本算法與之相比,優(yōu)勢體現(xiàn)在一是數(shù)據(jù)結(jié)構(gòu)簡單、存儲量小、易于實現(xiàn);二是精度可控,對于DEM映射DOM紋理的應(yīng)用還可以有效保留地形紋理坐標;三是更適用于地形數(shù)據(jù)的預(yù)處理,將三維地形動態(tài)繪制的壓力部分轉(zhuǎn)移。同時,本算法也存在一定的局限性,即僅限于規(guī)則柵格數(shù)據(jù)的簡化與三維繪制,不適用于TIN結(jié)構(gòu)的地形。從總體來說,本算法對于地形快速繪制有一定的實用性。

[1]ROSSIGNAC J,BORREL P.Multi-resolution 3D Approximations for Rendering Complex Scenes[C]//In B.Falcidieno and T.Kunii,editors,Modeling in Computer Graphics:Methods and Applications,1993:455-465.

[2]KALVIN A,TAYLOR R.Superfaces:PolygonalMesh Simplification with Bounded Error[J].IEEE Computer Graphics and Application,1996,16（3）:64-77.

[3]ZHU Yuanchen.Uniform RemeshingwithanAdaptive Domain:A New Scheme for View-dependent Level-of-Detail rendering of Meshes[J].IEEE Transactions on visualization and computer graphics.2005,11（3）:306-316.

[4]李建軍,李俊山.基于特征的三維模型簡化算法研究[J].系統(tǒng)仿真學(xué)報,2007,19（11）:2434-2436.

[5]朱軍,龔建華.大規(guī)模地形實時繪制算法[J].地理與地理信息科學(xué),2005,21（2）:24-27.