**Sung-Soo Kim, Yang-Soo Kim, Mi-Gyung Cho, Hwan-Gue
Cho**

Graphics Application Laboratory,

Department of Computer Science,

Pusan National University,

Kum-Jung-Ku, Pusan 609-735, Korea.

E-mail: {sskim, yskim, mgcho, hgcho}@pearl.cs.pusan.ac.kr

**ABSTRACT**

In this paper we introduce a new compression
technique for a large triangulated terrain using Delaunay triangulation.
Our compression technique decomposes a triangulated mesh into two parts.
One is a point set whose connecting structure is defined implicitly by
Delaunay edges. The other is the set of edges which cannot be recovered
by the implicit Delaunay triangulation rule. Thus we only need to keep
the whole vertex coordinates and a few edges which is not included in the
Delaunay edges. For the vertex coordinate, we apply "entropy coding" given
by \cite{Costa}, and we store only the edges not included in Delaunay
triangulation.

In experiments, we prepared several TIN data
set with various resolutions, which were generated by five typical
algorithms for terrain simplification. Those algorithms include progressive
meshing, vertex decimation and incremental greedy insertion etc. We found
that most of terrain triangulations are quite similar( = nearly 93%) to
the plane-projected Delaunay triangular mesh. This experimental work shows
that more than 93% edges of a common terrain data is included in Delaunay
triangulation. By exploiting this result, we can compress the common terrain
data by 1.2 bits per vertex. Another advantage of our Delaunay compression
approach is that we can reconstruct the original terrain structure locally,
since we can easily determine if an edge is included in Delaunay
edges by observing only a few local surrounding vertices.

**Keywords: **Data Compression, Delaunay Triangulation, Terrain Modeling