Technical Reports

The ICICS/CS Reading Room

UBC CS TR-99-10 Summary

Mesh Collapse Compression, November 15, 1999 Martin Isenburg and Jack Snoeyink, 10 pages

Efficiently encoding the topology of triangular meshes has recently been the subject of intense study and many representations have been proposed. The sudden interest in this area is fueled by the emerging demand for transmitting 3D data sets over the Internet (e.g. VRML). Since transmission bandwidth is a scarce resource, compact encodings for 3D models are of great advantage. In this report we present a novel algorithm for encoding the topology of triangular meshes. Our encoding algorithm is based on the edge contract operation, which has been used extensively in the area of mesh simplification, but not for efficient mesh topology compression. We perform a sequence of edge contract and edge divide operations that collapse the entire mesh into a single vertex. With each edge contraction we store a vertex degree and with each edge division we store a start and an end symbol. This uniquely determines all inverse operations. For meshes that are homeomorphic to a sphere, the algorithm is especially simple. Surfaces of higher genus are encoded at the expense of a few extra bits per handle.

If you have any questions or comments regarding this page please send mail to