TUTORIAL T3: Compression and Progressive Transmission of 3D Models

Jarek Rossignac, Georgia Institute of Technology

The current MPEG-4 standard for 3D compression is based on the award-winning Topological Surgery technique that Rossignac has co-invented at IBM. His more recent work on 3D compression, supported by the NSF, has resulted in a new 3D compression technique called Edgebreaker, for which Rossignac has received a SigmaXi Best Paper Award. A very simple and effective implementation of Edgebreaker is available at http://www.gvu.gatech.edu/~jarek/edgebreaker/eb. It uses Rossignac's Corner Table, which represents the connectivity of any manifold triangle mesh by two arrays of integers. Edgebreaker compresses the connectivity of meshes of T triangles down to about T bits. Its guaranteed cost of 1.8T bits holds the theoretical record for encoding planar triangle graphs.

Edgebreaker also supports more general triangle meshes with handles, holes, and non-manifold singularities. It has been adapted to quadrilateral and to more general polygonal meshes, further reducing the average storage cost per vertex. The Edgebreaker principle has also been applied to compress irregular tetrahedral meshes, such as those used for Finite Element Analysis. More recently, the Edgebreaker connectivity encoding has been combined with new geometric prediction schemes that improve the compression of vertex location and attributes. Some of the relevant publications on compression are available in electronic form from http://www.gvu.gatech.edu/~jarek/papers. Compression reduces the bit-count, but does not alter the complexity (triangle count) of the mesh. To further reduce the transmission time of 3D models and to accelerate their rendering, simplification and progressive transmission techniques are used. In the early 90's Rossignac has co-invented the simple, fast, and versatile vertex clustering simplification technique, which was used in several commercial products and has inspired numerous recent developments in 3D simplification. Later, in collaboration with Andrzej Szymczak and Renato Pajarola, he has developed simplification and compressed progressive transmission techniques for triangle and tetrahedral meshes. Finally, working with Ghassan Al-Regib and Yucel Altunbasak, he has recently developed unequal error protection mechanisms that maximize the expected quality of the model received over lossy channels.

The tutorial will cover these results in details, describing simple and practical data structures and algorithms for implementing them. The speaker will also put them in the broader context of the vast body of research in 3D simplification and compression.

back to SM'02