Compression of geometric structures

The compression of geometric structures is quite a new field of research, lying between computational geometry and standard data compression.

The rapid growth of image synthesis applications makes necessary the manipulation and the exchange of geometric data in a fast and economical manner. In particular, the numerous possibilities given by the World Wide Web in the field of virtual reality can be dramatically restricted whithout a fast access to the data. This implies (especially for remote access through low bandwidth lines) that the geometrical data would be efficiently structured and compressed.

Since about 1995, several works have dealt with the coding of meshes (2 or 3-dimensional geometric scenes made of polygons), using for most of them the following approach: the vertices of the mesh are coded in an order such that it contains partially the topology of the mesh (that is to say the edges and the polygons). In the same time, some simple rules attempt to predict the position of the current vertex from the positions of its neighbours that have been previously coded.

Our works consists in developing new methods for geometric compression. In particular, we have designed an algorithm whose general principle is the following: the order of the vertices is used to compress their coordinates, and then the topology of the mesh is reconstructed from the vertices. This algorithm achieves compression factors that are slightly greater than those of the currently available algorithms, and moreover, it allows progressive and interactive transmission of the data.

Application to terrain models

The following pictures show the progressive transmission of a terrain model through our algorithm. For each stage of the transmission, we give the number of bits of accuracy over the coordinates of the mesh vertices and the compression factor achieved, which is the size of the raw original data divided by the size of the transmitted data. The last stage of the algorithm restore the original model (lossless compression). This model is available at GIS-VIS.
Accuracy: 4 bits, Compression factor: 41.8
Accuracy: 5 bits, Compression factor: 17.5
Accuracy: 6 bits, Compression factor: 9.0
Accuracy: 7 bits, Compression factor: 5.6
Accuracy: 8 bits, Compression factor: 4.0
Accuracy: 9 bits, Compression factor: 3.0
Accuracy: 14 bits (lossless compression), Compression factor: 1.6

Last modified: Thu Nov 4 16:00:55 MET 1999 P.-M. Gandoin Topics PRISME Homepage la même page en français