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

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

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

0 引言

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

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

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

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

1.1 區(qū)域聚合

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

1.2 利用最大法向量夾角進(jìn)行誤差度量

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

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

N1、N22個(gè)法向量的夾角θ的余弦值計(jì)算公式為:

進(jìn)行簡(jiǎn)化運(yùn)算時(shí),事先根據(jù)簡(jiǎn)化需求指定簡(jiǎn)化閾值Ct:

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

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

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

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

②聚合運(yùn)算函數(shù)

Step1:若分塊大小為1,即僅為一個(gè)柵格點(diǎn),則中止遞歸過(guò)程,存儲(chǔ)該點(diǎn)索引坐標(biāo)（u,v）;

否則:

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

Step3:若cosθmax＜=Ct,則聚合成功,中止遞歸過(guò)程,存儲(chǔ)該聚合區(qū)域的4個(gè)邊角點(diǎn)的索引坐標(biāo)（u,v）;

否則:

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

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

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

注:索引坐標(biāo)（u,v）為該點(diǎn)在原柵格數(shù)據(jù)中的行列號(hào)。

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

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

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

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

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

圖2 消除裂縫示意圖

2 實(shí)驗(yàn)結(jié)果及分析

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

Ct=1,則最大法向量夾角為0°,即簡(jiǎn)化時(shí)將共面的區(qū)域聚合為由4個(gè)項(xiàng)點(diǎn)表示的一個(gè)區(qū)域,與原地形相比無(wú)失真。

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

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

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

表1 實(shí)驗(yàn)數(shù)據(jù)

3 結(jié)束語(yǔ)

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

[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]李建軍,李俊山.基于特征的三維模型簡(jiǎn)化算法研究[J].系統(tǒng)仿真學(xué)報(bào),2007,19（11）:2434-2436.

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