Edgebreaker: A simple and effective 3D Geometry Compression technique for Triangle Meshes

Edgebreaker is a compression technique developed under the National Science Foundation grant 9721358 by Prof. Rossignac and his colleagues and students at the GVU Center in the College of Computing of the Georgia Institute of Technology.

Edgebreaker was developed to improve upon the Topological Surgery 3D compression scheme, invented and patented by Jarek Rossignac and Gabriel Taubin at IBM. The Topological Surgery approach was adopted as the foundation of the current MPEG-4 standard for 3D compression and has received an IBM award for the Best 1998 Computer Science Paper co-authored by an IBM employee.

The Edgebreaker approach is not patented. Its implementation is extremely simple and efficient. The source code for the compression and decompression is publicly available. It uses the Corner Table representation (OV format), which may be genertedfrom other file formats using 3D Object Converter.

Edgebreaker is a finite state machine that walks from one triangle onto an adjacent one in a spiral. At each step it encodes whether the tip vertex and the left and right neighbors of the current triangle have already been visited. It encodes the complete connectivity of the triangle mesh in the clers string, a sequence of symbols, one per triangle, from the set {C,L,E,R,S}. A trivial, fixed code guarantees 2.0 bits per triangle encoding for the connectivity of any manifold triangle mesh without holes or handles. More efficient codes and various extensions for meshes with holes and handles have been published.

The original Edgebreaker paper is the first to propose a guaranteed, low, linear storage cost compression for zero-genus meshes. It also proposes extensions to more general topologies. It has received the Sigma Xi Award for the Best Paper published by a Georgia Tech faculty in 1999.

"Edgebreaker: Connectivity compression for triangle meshes", J. Rossignac. IEEE Transactions on Visualization and Computer Graphics, Vol. 5, No. 1, pp. 47-61, January - March 1999. (PDF)

A variable length coding and a simpler and faster decompression for CLERS strings were developed by Prof. Rossignac and Dr. Andrzej Szymczak,who was then a PhD student in the Math Department and now is a faculty member in the College of Computing at Georgia Tech. The improved coding reduces storage below 1.0 bit per triangle for larger meshes.

"Wrap&Zip decompression of the connectivity of triangle meshes compressed with Edgebreaker", J. Rossignac and A. Szymczak, Journal of Computational Geometry, Theory and Applications, Volume 14, Issue 1-3, pp. 119-135, November 1999. (PDF)

The implementation of the Edgebreaker compression and decompression technique has been considerably simplified through the use of the Corner Table data structure, which stores the connectivity using an array of two integers per corner: V[c] references the vertex of corner c and O[c] references the opposite corner. All other references used to visit the adjacent corners of the triangle mesh are computed from V and O when needed. The details and the pseudocode (PDF) of the publicly available implementation are discussed in the following paper.

"3D compression made simple: Edgebreaker on a Corner Table", J. Rossignac, A. Safanova, A. Szymczak, Shape Modeling International Conference, Genoa, Italy May 2001. (PDF)

This simplified implementation has been extended to support meshes with an arbitrary number of handles and with zero or one bounding loop (or hole).

"Edgebreaker: A Simple Compression Algorithm for Surfaces with Handles", Helio Lopes, Jarek Rossignac, Alla Safonova, Andrzej Szymczak and Geovan Tavares. Computers&Graphics International Journal, Vol. 27, No. 4, pp. 553-567, 2003. (PDF)

To simplify the extension to meshes with holes, triangle meshes with several holes should be preprocessed, so that all holes except the largest are plugged with triangle fans. Transmitting the IDs of the dummy central vertices of these fans allows the client to identify all the incident triangles and delete them to restore the holes.

The vertex locations are predicted using the parallelogram prediciton (originally suggested by Touma and Gotsman) and adapted to different configurations. The geometric predictor has recently been used to predict both the geometry and the connectivity and is a natural extension of EdgeBreaker and of the Cut-Border Machine, developed by Gumhold and Strasser.

"Delphi Encoding: Improving Edgebreaker by Geometry based Connectivity Prediction", Volker Coors and Jarek Rossignac. April 2003. GVU Tech. Report GIT-GVU-03-30. (PDF)

When the original connectivity does not need to be preserved, the triangle mesh may be resampled to produce a more regular approximating mesh. When combined with EdgeBreaker, this approach reduces storage cost to a fraction of a bit per triangle for both the connectivity and the geometry.

"SwingWrapper: Retiling Triangle Meshes for Better Compression", Marco Attene, Bianca Falcidieno, Michela Spagnuolo and Jarek Rossignac. ACM Transactions in Graphics, Volume 22, No. 4, pp. 982Ð996, October 2003. GVU Tech. Report GIT-GVU-02-04. (pdf)

The sharp edges and smooth surfaces may be automatically recovered during decompression, thus reducing the error.

"Sharpen&Bend: Recovering curved edges in triangle meshes produced by feature-insensitive sampling", Marco Attene, Bianca Falcidino, Michela Spagnuolo, Jarek Rossignac. GVU Tech. Report GIT-GVU-03-34.  (pdf)

A different resampling approach was also proposed. It splits the triangles into 6 sets, based on their oritentation. Each set is reampled using a 2D array of axis-alinged rays. The connectivity within each set and across sets is seamlessly compressed using a modified version of EdgeBreaker.

"Piecewise Regular Meshes: Construction and Compression", A. Szymczak, J. Rossignac, and D. King. Graphical Models, Volume 64, pp.183-198, May 2002. (pdf)

EdgeBreaker has been extended to the compression of quadrialteral meshes

"Connectivity Compression for Irregular Quadrilateral Meshes", Davis King, Jarek Rossignac. 1999. GVU Tech. Report GIT-GVU-99-36. (pdf)

and of  tetrahedral meshes.

"Grow&Fold: Compression of Tetrahedral Meshes", Andrzej Szymczak and Jarek Rossignac. Proc. ACM Symposium on Solid Modeling, pp. 54-64, June 1999. GVU Tech. Report GIT-GVU-99-02.(pdf)

EdgeBreaker has been combined with a space-time geometric predictor for the compression of 3D animations.

"Dynapack: Space-Time compression of the 3D animations of triangle meshes with fixed connectivity", L. Ibarria and J. Rossignac. ACM SIGGRAPH/Eurographics Symposium on Computer Animation, pp. 126-135, San Diego, July 2003.  GVU Tech. Report GIT-GVU-03-08. (pdf)

These and a few other 3D compression approaches are reviewed in the following chapter:

"Surface simplification and 3D geometry compression", Jarek Rossignac. Chapter 54 in Handbook of Discrete and Computational Geometry (second edition), CRC Press, Editors: J. E. Goodman and J. O'Rourke. 2003.  (pdf)