基于delaunay三角網(wǎng)的三維地形可視化仿真

徐祥龍，李光耀，譚云蘭,2，李 超

基于delaunay三角網(wǎng)的三維地形可視化仿真

徐祥龍1，*李光耀1，譚云蘭1,2，李 超1

(1. 同濟(jì)大學(xué)CAD研究中心，上海201804；2. 井岡山大學(xué)電子與信息工程學(xué)院，江西，吉安 343009)

針對在三維地形處理領(lǐng)域中存在的地形數(shù)據(jù)冗余，可視化處理效率不高，真實(shí)感效果不強(qiáng)的問題，提出一種基于delaunay三角網(wǎng)的三維地形生成技術(shù)及可視化仿真處理的方法。該方法將DEM數(shù)據(jù)轉(zhuǎn)化為TIN數(shù)據(jù)，然后用改進(jìn)的delaunay算法將TIN數(shù)據(jù)生成三角網(wǎng)來模擬地形。最后經(jīng)過紋理映射，光照及渲染，生成具有真實(shí)感的三維地形。同時(shí)給出了運(yùn)用VC++和OpenGL實(shí)現(xiàn)的三維真實(shí)感地形可視化仿真軟件。仿真試驗(yàn)表明：該方法能快速的處理地形高程數(shù)據(jù)，得到了直觀的真實(shí)感較強(qiáng)的三維地形模型。

Delaunay三角網(wǎng)；三維地形可視化；OpenGL

0 引言

長久以來，人們都是用二維地圖來描述地理信息，但在數(shù)字化和信息化的今天，隨著地理信息應(yīng)用領(lǐng)域的不斷拓展，傳統(tǒng)的二維地圖已滿足不了人們的需求，具有豐富地理信息的三維地形圖成為研究熱點(diǎn)。

地形可視化是指在計(jì)算機(jī)上根據(jù)數(shù)字地形模型(Digital Terrain Model，簡稱DTM)對地形數(shù)據(jù)進(jìn)行三維仿真顯示的技術(shù)。它涉及到計(jì)算機(jī)圖形學(xué)、測繪學(xué)、地理信息系統(tǒng)、虛擬現(xiàn)實(shí)等諸多學(xué)科，并可應(yīng)用在城市規(guī)劃、地形勘察、項(xiàng)目選址、路徑選取、災(zāi)害預(yù)測、軍事及游戲等各個(gè)方面[1]。因此，研究如何更好、更快的實(shí)現(xiàn)地形可視化是很有必要的。

本文從地形模擬的角度出發(fā)，對地形數(shù)據(jù)進(jìn)行處理，應(yīng)用改進(jìn)的Delaunay算法建立三維地形模型中的不規(guī)則三角網(wǎng)(TIN)，以此來模擬地形表面。并用VC++和OpenGL實(shí)現(xiàn)了具有三維真實(shí)感的地形可視化仿真軟件。

1 數(shù)字地形模型的生成

1.1 概述

針對不同的應(yīng)用目的，人們依據(jù)各種數(shù)據(jù)模型和算法建立了很多種地形可視化模型。對于規(guī)則格網(wǎng)RSG(Regular Square Grid): Lindstrom在1996年提出了一種對規(guī)則格網(wǎng)表示的地形模型進(jìn)行實(shí)時(shí)細(xì)節(jié)層次刪減和繪制的方法[2]；Mark等在1997年提出了“實(shí)時(shí)優(yōu)化自適應(yīng)網(wǎng)格”(Real-Time Optimally Adapting Meshes，簡稱ROAM)算法[3]。對于不規(guī)則三角網(wǎng)TIN(Triangulated Irregular Network): Shamos和Hoey在1975年提出了分割-合并的思想，并證明了在N個(gè)離散數(shù)據(jù)點(diǎn)中建立Delaunay三角網(wǎng)的時(shí)間復(fù)雜度至少為log[4]。Lawson在1976年提出的逐點(diǎn)插入法思路清晰簡單，容易編程實(shí)現(xiàn)[5]。徐青等提出了基于TIN的自適應(yīng)分塊算法，把傳統(tǒng)的分割------合并算法和三角網(wǎng)生長法結(jié)合在一起，并給出了相應(yīng)的地形簡化過程[6]。

1.2 數(shù)字地形模型(DTM)

數(shù)字地形模型(Digit Terrain Model)是地理信息系統(tǒng)中表達(dá)空間信息及三維可視化的一種重要模型，構(gòu)造數(shù)字地形模型的方法主要有兩類：一是基于規(guī)則分布數(shù)據(jù)點(diǎn)的柵格格網(wǎng)(Grid)；另一個(gè)是基于離散數(shù)據(jù)點(diǎn)的不規(guī)則三角網(wǎng)格TIN。它們都有各自的優(yōu)缺點(diǎn)：規(guī)則格網(wǎng)的拓?fù)潢P(guān)系簡單，構(gòu)造算法比較容易，空間操作及存儲(chǔ)方便，但是它的數(shù)據(jù)冗余較大，難以描述局部復(fù)雜地形特征；不規(guī)則三角網(wǎng)的優(yōu)點(diǎn)是數(shù)據(jù)冗余小，能較好的模擬地形并能描述比較復(fù)雜的地形細(xì)節(jié)，但是它的構(gòu)造算法比較復(fù)雜，空間操作及存儲(chǔ)不便。本文主要討論不規(guī)則三角網(wǎng)TIN的構(gòu)建算法。

構(gòu)建TIN的算法一般有三種[7]：分而治之算法、數(shù)據(jù)點(diǎn)逐次插入算法以及三角網(wǎng)生長算法。這些算法都是將數(shù)據(jù)點(diǎn)連接成網(wǎng)來模擬地形，其效率隨著數(shù)據(jù)點(diǎn)數(shù)量的增長呈指數(shù)級(jí)遞減，當(dāng)數(shù)據(jù)點(diǎn)數(shù)量很大時(shí)，效率很低。為了提高TIN的建網(wǎng)效率，本文在研究前人算法的基礎(chǔ)上，對Delaunay三角網(wǎng)的建網(wǎng)算法提出了一些改進(jìn)。

1.3 改進(jìn)的Delaunay三角網(wǎng)生成算法[8]

改進(jìn)算法采用逐點(diǎn)內(nèi)插算法，快速生成Delaunay三角網(wǎng)。因?yàn)榈匦螖?shù)據(jù)塊皆為方形，因此可計(jì)算出包圍矩形作為初始三角網(wǎng)，然后將其余點(diǎn)逐一插入，每插入一個(gè)點(diǎn)都用LOP局部優(yōu)化過程(Local Optimization Procedure)進(jìn)行優(yōu)化，保證生成的三角網(wǎng)是Delaunay三角網(wǎng)DTN(Delaunay Triangulated Network )。具體實(shí)現(xiàn)過程如下：

（1）遍歷所有地形點(diǎn)的坐標(biāo)，算出所有點(diǎn)的坐標(biāo)范圍，由此得到一個(gè)包圍所有點(diǎn)的矩形，連接一條矩形對角線，形成初始三角網(wǎng)。

（2）在基本三角網(wǎng)中插入一點(diǎn)P，根據(jù)P點(diǎn)坐標(biāo)調(diào)用FindTriangle()函數(shù)，找到包含P點(diǎn)的三角形T；

（3）連接P點(diǎn)與三角形T的三個(gè)頂點(diǎn)，生成三個(gè)新的三角形；

（4）使用LOP算法優(yōu)化三角網(wǎng)；

（5）重復(fù)步驟（2）到（4），直到所有的點(diǎn)都插入完畢。

經(jīng)過上述步驟，Delaunay三角網(wǎng)已經(jīng)生成，但算法運(yùn)行過程中涉及到兩個(gè)重要函數(shù)，分別是FindTriangle()函數(shù)和LOP()函數(shù)。

FindTriangle()函數(shù)：所有的三角形都存儲(chǔ)在一個(gè)vector容器中，它可以實(shí)現(xiàn)隨機(jī)存取，具有較快的訪問速度。每生成一個(gè)三角形就加入到這個(gè)容器中，因此新生成的三角形都在容器的末尾處。當(dāng)有新的點(diǎn)插入時(shí)，采用從尾至頭的順序查找三角形，有較大幾率落在尾部的新三角形中，從而提高查找效率。判斷點(diǎn)是否在三角形中可先判斷點(diǎn)是否落在包含三角形的矩形內(nèi)，若在可繼續(xù)采用向量法判斷是否在三角形內(nèi)部（如圖1所示）：

圖1 判斷點(diǎn)P是否在△ABC中

Fig. 1 If the point P inside the △ABC

LOP()函數(shù)：delaunay三角網(wǎng)中每插入一個(gè)點(diǎn)都會(huì)對當(dāng)前的三角形進(jìn)行修改，這個(gè)過程稱為LOP，可采用如下方法：

連接P點(diǎn)與三角形的三個(gè)頂點(diǎn)，生成三個(gè)新的三角形，這將導(dǎo)致一些非法邊，對每條邊執(zhí)行LOP操作，這樣會(huì)將這三個(gè)三角形變化為delaunay三角形，同時(shí)也會(huì)影響以P為頂點(diǎn)的其他三角形，應(yīng)繼續(xù)對P的對邊進(jìn)行LOP操作，直到所有的三角形都變?yōu)閐elaunay三角形，該算法時(shí)間復(fù)雜度為(log)[9]。圖2為此LOP算法的執(zhí)行過程：

圖2 插入點(diǎn)時(shí)三角網(wǎng)的優(yōu)化執(zhí)行過程

在LOP過程中，每插入一個(gè)點(diǎn)至多改變9個(gè)三角形[8]，因此算法效率是比較高的。

2 三維真實(shí)感地形可視化軟件的實(shí)現(xiàn)

2.1 三維地形可視化軟件的設(shè)計(jì)

三維地形可視化軟件的設(shè)計(jì)思想是對DEM數(shù)據(jù)進(jìn)行處理，按照改進(jìn)的Delaunay算法生成三角網(wǎng)，來模擬地形表面，然后通過紋理映射、光照及渲染，實(shí)現(xiàn)三維真實(shí)感地形。根據(jù)上述思路，軟件的技術(shù)路線和流程圖如圖3所示：

圖3 地形建模流程圖

2.2 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

本三維地形可視化軟件在Windows XP操作系統(tǒng)下采用VC++6.0及OpenGL開發(fā)，下面是系統(tǒng)中用到的一些關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)。對三角網(wǎng)中的三角形采用如下數(shù)據(jù)結(jié)構(gòu)

對于轉(zhuǎn)換DEM數(shù)據(jù)，系統(tǒng)采用Global Mapper軟件來實(shí)現(xiàn)，此軟件支持各種地形數(shù)據(jù)的讀取和轉(zhuǎn)換，限于篇幅，不再詳細(xì)介紹。

2.3 實(shí)驗(yàn)結(jié)果

本實(shí)驗(yàn)軟件在Windows XP SP3系統(tǒng)平臺(tái)下使用Visual C ++ 6.0和OpenGL 2.0搭建的軟件平臺(tái)，系統(tǒng)運(yùn)行的硬件環(huán)境：CPU：Intel Core 2 Duo E7300；內(nèi)存：2G；顯卡芯片組：GeForce 9800 GT。使用中國地區(qū)的地形數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)，實(shí)驗(yàn)結(jié)果如圖4、圖5所示：

圖4 中國西藏某山區(qū)，其中(a)是地形等高線圖，(b)是Delaunay三角網(wǎng)圖，(c)是經(jīng)過渲染的三維地形模型

圖5 中國浙江某地區(qū)，其中(a)是地形等高線圖，(b)是Delaunay三角網(wǎng)圖，(c)是經(jīng)過渲染的三維地形模型

上述兩地區(qū)地形模擬的時(shí)間效率如下：

表1 建網(wǎng)的時(shí)間效率

3 結(jié)論

本文主要針對三維地形顯示中的重要環(huán)節(jié)，用Delaunay三角網(wǎng)模擬地形的部分進(jìn)行詳細(xì)描述，并對Delaunay三角網(wǎng)的生成算法進(jìn)行了改進(jìn)。從實(shí)驗(yàn)結(jié)果看來，三維地形建立的效率得到了一定的提高，最后得到了真實(shí)感良好的三維地形模型。

[1] 王永明.地形可視化[J].中國圖像圖形學(xué)報(bào).2000.5A(6): 449-456.

[2]Lindstrom P, Koller D, Ribarsky W, et al. Turner. Real-Time Continuous Level of Detail Rendering of Height Fields[C].In:Proceedings of SIGGRAPH'96, 1996.

[3] Mark Duchaineau. ROAMing Tenain:Real-time optimally adap ting meshes[C].In: Proc.Visualization'97, 1997.

[4]Shamos M I, Hoey D. closet-point problems[C]. In: Proceedings of the 16th Annual Symposium on the Foundations of Computer Science, 1975: 151-162.

[5]Lawson C L. Software for c Surface interpolation. Mathematic Soft-ware III, J Rice ED[M]. New York: Academic Press, 1977: 61-194.

[6]徐青．基于自適應(yīng)分塊的TIN三角網(wǎng)生成算法[J]．中國圖像圖形學(xué)報(bào)，2000，5(6)：461-465．

[7]徐青.地形三維可視化技術(shù)[M].北京:測繪出版社,2000．

[8]賈瑞生,姜巖,孫紅梅,等.三維地形建模與可視化研究[J].系統(tǒng)仿真學(xué)報(bào),2006,18(1):330-332.

[9]Guibas L J, Knuth D E, Sharir M. Randomized Incremental Construction of Delaunay and Voronoi Diagrams[J]. Algorithmica, 1992(7): 381-413.

Research on 3D Terrain Visualization Based on Delaunay Triangulations Network

XU Xiang-long1，*LI Guang-yao1，TAN Yun-lan1,2，LI Chao1

(1. CAD Research Center of Tongji University, Shanghai 201804,China; 2. School of Electronic Information and Engineering，Jinggangshan University，Ji’an，Jiangxi 343009，China)

Aiming to the problem of data redundancy, low efficiency and not good-enough realistic in 3D terrain processing, we propose a method to generate3D terrain based on Delaunay triangulation. It converts the DEM data to TIN data and generates the triangulation by optimal Delaunay algorithm to model terrain. Finally, we generate high realistic 3D terrain model by texture mapping, lighting and rendering. We also build 3D terrain visualization software using VC++ and OpenGL at the same time. The simulation experiment shows that the method can process the terrain data quickly and get better effect 3D terrain model.

delaunay triangulation; 3D terrain visualization; openGL

TP391.41

A

10.3969/j.issn.1674-8085.2012.02.013

1674-8085(2012)02-0050-04

2012-01-15；

2012-02-22

國家863高技術(shù)研究發(fā)展計(jì)劃(2010AA122200)

徐祥龍(1988-)，男，山東臨沂人，碩士生，主要從事地形建模與仿真、圖形圖像處理研究(E-mail: xuxl6125@163.com);

*李光耀(1965-)，男，安徽安慶人，教授，博導(dǎo)，主要從事大規(guī)模城市建模與仿真、圖形圖像處理研究(E-mail: lgy@#edu.cn);

譚云蘭(1972-)，女，江西新干人，副教授，同濟(jì)大學(xué)在讀博士生，主要從事圖像處理，計(jì)算機(jī)圖形與科學(xué)可視化研究(E-mail: tanyunlan@163.com);

李 超(1979-)，男，安徽合肥人，博士生，主要從事圖像處理，月表地形仿真研究(E-mail: lic321@163.com).