Space-efficient terrain rendering using constrained Delaunay triangulation

Space-Ef?cient Terrain Rendering using

Constrained Delaunay Triangulation

Sung-Soo Kim,Jong-Hyun Park

Spatial Information Technology Center

ETRI(Electronics and Telecommunications Research Institute)

161Gajong-Dong,Yusong-Gu,Daejon305-350,South Korea

Abstract—This paper proposes a new terrain visualization technique as-

sociated with the conversion process from a contour-based data model to a

TIN model.

The main research related to processing these contour lines had been fo-

cused on interpolation methods to create the digital terrain model(DTM).

We introduce a novel approach for visualizing terrain by using contour line

data which is obtained from the digital elevation model(DEM).Our ap-

proach use the marching square algorithm to extract contour lines from

the DEM and classify contours into open coutours and closed contours to

calculate local minimum/maximum points.

To minimize the search space for calculating local minimum/maximum,

we construct the containment tree of the closed contour.Then we only

achieve an approximation procedure for calculating minimum/maximum

points at leaf nodes in the containment tree.Finally,we can easily recon-

struct the terrain by performing constrained Delaunay triangulation that

uses approximation points and contour data as inputs.

In the experiments,we compare our algorithm with DEM processing in

terms of the processing speed and data size.

I.I NTRODUCTION

Modern terrain data acquisition techniques provide huge

datasets that permit to represent terrain accurately.However,

high representation accuracy is paid for in terms of high costs

for storage and processing.One of objectives in handling GIS

data is how to handle the terrain data easily and ef?ciently,since

a common terrain?le is very large.

The digital elevation model(DEM)is used as important data

in various?elds such as country planning/management,engi-

neering works,environments,resources and military purpose.

The most popular method for acquiring a DEM is interpolation

method by using the vector map.We can acquire the elevation

data that have relatively equal accuracy in a short time and small

expense if we have vector map as a resource data.

Existent contour line data that is obtained from a paper map

is used in various applications,such as remote sensing and GIS

applications.The main research related to processing these con-

tour lines had been focused on interpolation methods to create

the digital terrain model(DTM).

II.R ELATED W ORKS

The research works concerning the contour data have been

focused on digitizing a map from a scanned terrain image and

DEM extraction through interpolation methods from contours.

Yamamoto proposed to extract from the map the elevation

symbols,the characters and the contour lines,and then a reg-

ularization process is used to create a DTM,by using the eleva-

tion dots as elevation constraints,and the contour lines only as

tangent constraints[4].

Yla-Jaaski proposed an automatic contour lines reconstruc-

tion sytstem based on the analysis of the V oronoi skeleton[3].

Although this system provides good results in most general

cases,it fails when the interruptions of the curves are too many

and/or too long.

Kim has proposed a new triangle mesh compression method

based on Delaunay Triangulation[1].The main feature of this

compression method is that almost90%of triangles are the same

as in Delaunay triangulation.

Hoppe introduced a new multiresolution model called Pro-

gressive Meshes(PM)[5].Progressive Meshes represent polyg-

onal objects as a small base mesh plus vertex-split transforma-

tions.Since the vertex splits can be added incrementally to the

model,a progressive representation results.

Touma has introduced a new triangle mesh compression

method that exploits the triangle marching structure[6].He uses

vertex connectivity codes for compressing triangulation.

Floriani et al.has proposed a simple and compact TIN com-

pression method,which based on traversing a TIN in a shelling

order[8].It sends each vertex once,and produces less than4.5

bits of connectivity information for each vertex.

One approach to visualize terrains is the use of DEM which is

interpolated from contours.However,this method requires huge

data size and a lot of processing speed for visualizing three-

dimensional terrain to user.

In this paper,we introduce novel approach for visualizing

terrain by using contour line data which is obtained from the

digital elevation model(DEM).Our research work concern-

ing the visualization of terrains focuses on techniques for data

management,fast real-time visualization and memory-usage

optimization.Our approach requires only local approxima-

tion/interpolation procedure of contours by using containment

tree instead of global interpolation procedure of contours.

III.T ERRAIN R ENDERING S YSTEM

In this section,we propose a new terrain reconstruction al-

gorithm for massive DEM data by using constrained Delaunay

triangulation.The basic idea of our algorithm is that we can

reconstruct a terrain by performing constrained Delaunay trian-

gulation for all contour lines in original DEM and interpolated

points at the peak or valley.

A.System Overview

The proposed system performs the following setps to visual-

ize a three-dimensional terrain.

1.extract contour data from a given input DEM through the

marching square algorithm.

2.classify extracted contours into open contours and closed

contours.

0-7803-7536-X/$17.00 (C) 2002 IEEE2441

3.construct the containment tree for closed contours.

4.calculate interpolation vertices from leaf nodes in the con-tainment tree.

5.render a terrain by performing constrained Delaunay triangu-lation of given contours and interpolated

points.

Fig.1.The pipeline of our proposed system

B.Contour Line Extraction and Classi?cation

A contour line is a map line connecting points representing places on the terrain surface that have the same elevation.We use the marching square algorithm to extract contour lines from a grid DEM.We de?ne the following data structure to manage contour lines.

struct CVertex {

?oat x,y;};

struct CContourList {

List VertexList;int Elevation;};

We classify contour lines into open contours and closed con-tours to minimize search space for calculating local minimum and maximum points.

De?nition 1:The open contour is de?ned as a graph which has no cycle consisting vertices in contour line.

The h,i,j and k in Fig.2(a)are examples of open contours.De?nition 2:The closed contour is de?ned as a graph which has cycle consisting vertices in contour line.

The B,C,D,E and F in Fig.2(a)are examples of closed contours.The main goal of this step is to minimize the search space by using classifying contours in order to con-structing tree at next step.The containment tree is a tree that constructs according to containment relation of MBR for each closed contour.In order to construct the containment tree,we should ?nd all MBR for each open contour.If an arbitrary MBR A (x min ,y min ,x max ,y max )contains MBR B (x min ,y min ,x max ,y max ),it should satisfy the following two conditions at the same time.

Ax min Bx max Ay min By max

We can easily construct the containment tree by using above two conditions.The Fig.2(b)shows a containment tree by using containment relation among closed contours.

A B

D E C F G

h i

j

k

(a)

Fig.2.An example of the containment tree

C.Local Points Approximation

We should approximate points by using local minimum or maximum points of closed contours to reconstruct a peak or val-ley of a terrain.The closed contour that has local minimum or maximum points is a leaf node in the containment tree.In other words,the closed contour which does not contain any other closed contour has local minimum or maximum points.These points exist in a peak or valley on a terrain.We use multilevel B-spline approximation method for calculating these points[2].Let ?={(x,y )|0≤x

Let φj be the value of the ij -th control point on lattice Φ,located at (i,j )for i =?1,0,...,m +1and j =?1,0,...,n +1.The approximation function f is de?ned in terms of these control points by

f (x,y )=

3 k =03 k =0

B k (s )B l (t )φ(i +k )(j +l )

where i = x ?1,j = y ?1,s =x ? x ,t =y ? y .

B k and B l are uniform cubic B-spline basis functions de?ned as

B 0(t )=(1?t )3/6B 1(t )=(3t 3?6t 2+4)/6B 2(t )=(?3t 3+3t 2+3t +1)/6

B 3(t )=(1?t 3)/6

where 0≤t <1.

The multilevel B-spline approximation is based on the B-spline approximation by incrementally re?ning the control grid reso-lution as shown in Algorithm 1.We perform approximation procedure for the classi?ed contour line data through this ap-proximation algorithm.

D.Constrained Delaunay Triangulation

A Delaunay triangulation is desirable for approximation be-cause of its general property that most of its triangles are nearly equiangular.Since the Delaunay triangulation is done over a set of points and does

not necessarily

conform to imposed boundary (?xed edges),the method can be forced to include the boundary

2442

Algorithm 1Multi-level B-spline Approximation Input :P ={(x c ,y c ,z c )}

Output:a control lattice hierarchy F 0,F 1,.,F k Step 1.(initialization )set k =0

Step 2.(obtain discrete point )P k ={x c ,y c ,?z c }

Step 3.(computation of f k )compute f k from P k by the B-spline approximation.

Step 4.(computation of elevation value )compute ?k +1z c =?k z c -f k (x c ,y c )for each data point.Reset k =k +1and go to step 2.

properly.This method is called Constrained Delaunay Triangu-lation .In this method,the pre-de?ned edges are in the triangu-lation and the empty circle property is modi?ed to apply only to points that can be seen from at least one edge of the triangle where the pre-de?ned edges are treated as opaque.

We perform a constrained Delaunay triangulation using whole input contour lines and interpolated points resulted from closed contours at leaf nodes in containment tree to render three-dimensional terrain surface.In other words,we construct Delau-nay triangulation which has input contour lines as edges in the terrain triangulation.

IV.E XPERIMENTAL R ESULTS

We have implemented our algorithm in C/C++,tested our non-optimized implementation on several datasets which is ob-tained from the U.S.Geological Survey (USCG).All experi-ments were conducted on a 850MHz Pentium III running Mi-crosoft Windows 2000.Our system had 512MB of RAM and a graphics accelerator based on the NVIDIA GeForce 256chip.Fig.3shows original terrain for the DEM

data.

(a)havasupai (178,308vertices)(b)powell (177,536vertices)

Fig.3.Original Terrains(DEM)

Fig.4and 5show results of a contour extraction and a terrain reconstruction.

Fig.4.Contour extraction and terrain reconstruction

Fig.5.Terrrain rendering results (time :3.61sec,4.55sec)

ec11f5b765ce05087632136dparison Results

V.C ONCLUSION

In this paper we have introduced a new terrain reconstruction algorithm for the massive DEM.We can minimize the compu-tation for interpolated point by applying only classi?ed closed contours instead of whole contours.

Our proposed system requires only a half of data size (points)of original DEM (see Fig.6).In the future,the implementation of the constrained Delaunay triangulation should be extended to optimize the triangle strip during the constrained Delaunay triangulation processes.And,we will improve the terrain ren-dering engine by ?nding contour strips in the triangulation.

R EFERENCES

[1]Sung-Soo Kim,Yang-Soo Kim,Mi-Gyung Cho,Hwan-Gue Cho,A Geo-metric Compression Algorithm for Massive Terrain Data using Delaunay Triangulation ,Proc.of WSCG ’99,pp.124-131,Feb.,1999.

[2]

Seungyong Lee,George Wolberg,and Sung Yong Shin,Scattered Data Interpolation with Multilevel B-Splines ,IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS,VOL.3,NO.3,JULY-SEPTEMBER 1997.

[3]J.Yla-Jaaski H.Ahonen,Knowledge based analysis of line drawing ,pp.774-777,The 6th Scandinavian Conference on Image Analysis,1989.[4]K.Yamamoto et al.,Symbol recognition and surface reconstruction from topographic map by parallel method ,pp.914-917,ICDAR,1993.

[5]Hugues Hoppe,Progressive Meshes ,SIGGRAPH ’96Proc.,pp.99-108,Aug.,1996.

[6]Costa Touma,Craig Gotsman,Triangle Mesh Compression ,Proc.of Graphics Interface ’98,pp.26-34,1998.

[7]

Michael Garland and Paul S.Heckbert,Fast

Polygonal Approximation

of Terrains and Height Fields ,CMU-CS 95-181,CS Dept.,Sept,1995.[8]

P.Magillo L.De Floriani,E.Puppo Compressing Triangulated Irregular Networks ,Geoinformatica 1,no.4,pp.67-88,2000.

2443

本文来源：https://www.bwwdw.com/article/vy9e.html