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

Hosted by Graphics & Media Lab. http://graphics.cs.msu.su

mailto: Webmaster