**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.

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.

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)*

*"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)*