Edgebreaker swMATH ID: 4117 Software Authors: Rossignac; Georgia Institute of Technology; National Science Foundation Description: Edgebreaker is a simple technique for compressing three-dimensional triangle meshes. We introduce here a new formulation of Edgebreaker, which leads to a very simple implementation. We describe it in terms of a simple data structure, which we call the Corner Table. It represents the connectivity of any manifold mesh as two tables, V and O, such that for a corner c, which is the association of a triangle with a vertex, V[c] is an integer reference to the vertex of c and O[c] is an integer reference to the opposite corner. For meshes that are homeomorphic to a sphere, Edgebreaker encodes these two tables with less than 2 bits per triangle. It compresses vertex locations using Touma and Gottsman’s parallelogram predictor. We also present a new decompression, inspired by the Wrap&Zip decompression technique developed in collaboration with Andrzej Szymczak. We call it Zip&Wrap, because it works in the inverse direction from Wrap&Zip and zips cracks in the reconstructed mesh sooner. The detailed source code for the compression and the decompression algorithms fits on a single page. A further improvement of the codebook of Edgebreaker, developed with Davis King, guarantees no more than 1.73 bits per triangle for the connectivity. Entropy encoding reduces this cost in practice to less than a bit per triangle when the mesh is large. Through minor modifications, the Edgebreaker algorithm has been adapted to manifold meshes with holes and handles, to non-triangle meshes, and to non-manifold meshes. A Corner-Table implementation of these will be described elsewhere. Homepage: http://www.gvu.gatech.edu/~jarek/edgebreaker/eb/ Related Software: 2D triangulations; Metro; LEDA; CGAL; ECLIPSE; HexaShrink; MRST; Matlab; Kaskade7; revolve; apcluster; APCluster; OpenMesh; zfp; SIFT; MESH; Qsplat; Miniball Cited in: 46 Publications all top 5 Cited by 93 Authors 5 Rossignac, Jarek R. 4 Schaeffer, Gilles 4 Snoeyink, Jack Scott 4 Szymczak, Andrzej 3 Bonichon, Nicolas 3 Castelli Aleardi, Luca 3 Devillers, Olivier 3 Gavoille, Cyril 3 Hanusse, Nicolas 3 Isenburg, Martin 2 Alliez, Pierre 2 Blandford, Daniel K. 2 Blelloch, Guy E. 2 Cho, Youngsong 2 Gavrilova, Marina L. 2 Gotsman, Craig 2 Kadow, Clemens 2 Kim, Deok-Soo 2 Kim, Donguk 2 King, Davis 2 Kumar, Vipin 2 Lewiner, Thomas 2 Lu, Hsueh-I 2 Poulalhon, Dominique 2 Tan, Chih Jeng Kenneth 2 Taubin, Gabriel 1 Aleardi, L. Castelli 1 Antonini, Marc 1 Bartholdi, John J. III 1 Bossen, Frank 1 Bouard, Lauriane 1 Cai, Su 1 Cardoze, David E. 1 Cheng, Shyi-Chyi 1 Chiang, Yi-Ting 1 Chizat, Lénaïc 1 Chor, Benny 1 Desbrun, Mathieu 1 Duval, Laurent 1 Fellows, Michael Ralph 1 Fusy, Éric 1 Gervasi, Osvaldo 1 Goldsman, Paul 1 Götschel, Sebastian 1 Gu, Xianfeng 1 Guéziec, André 1 Hoppe, Hugues 1 Hou, Fei 1 Ivrissimtzis, Ioannis P. 1 Juedes, David W. 1 Kettner, Lutz 1 Khodakovsky, Andrei 1 Kronrod, Boris 1 Kuo, Chen-Tsung 1 Laganà, Antonio 1 L’Ecuyer, Pierre 1 Li, Zhen 1 Lin, Ching-Chi 1 Lindstrom, Peter G. 1 Lopes, Hélio 1 Lu, Zheming 1 Lyuu, Yuh-Dauh 1 Ma, Tak-Man 1 Medeiros, Esdras 1 Mun, Youngsong 1 Nakano, Shin-ichi 1 Ochotta, Tilo 1 Payan, Frédéric 1 Peyrot, Jean-Luc 1 Polthier, Konrad 1 Praun, Emil 1 Qi, Yue 1 Safonova, Alla 1 Saupe, Dietmar 1 Schneider, Sébastien 1 Schröder, Peter 1 Shen, Xukun 1 Silva, Cláudio T. 1 Sohler, Christian 1 Tavares, Geovan 1 Ti, Yen-Wu 1 Velho, Luiz 1 Viaña, Raquel 1 Von-Tycowicz, Christoph 1 Wang, Yalin 1 Weiser, Martin 1 Wu, Da-Chun 1 Wu, Tian-Sheng 1 Yamanaka, Katsuhisa 1 Yang, Shen 1 Yang, Shi-Nine 1 Yau, Shing-Tung 1 Zhao, Qinping all top 5 Cited in 20 Serials 6 Computational Geometry 4 Graphical Models 2 Information Processing Letters 2 Lecture Notes in Computer Science 1 Applied Mathematics and Computation 1 Theoretical Computer Science 1 Operations Research Letters 1 Computer Aided Geometric Design 1 Graphs and Combinatorics 1 Algorithmica 1 Discrete & Computational Geometry 1 The Visual Computer 1 CAD. Computer-Aided Design 1 International Journal of Computational Geometry & Applications 1 Pattern Recognition 1 Computer Graphics Forum 1 Computational Geosciences 1 Communications in Information and Systems 1 Science in China. Series F 1 Signal, Image and Video Processing all top 5 Cited in 8 Fields 32 Computer science (68-XX) 13 Numerical analysis (65-XX) 9 Combinatorics (05-XX) 3 Information and communication theory, circuits (94-XX) 2 General and overarching topics; collections (00-XX) 2 Convex and discrete geometry (52-XX) 1 Calculus of variations and optimal control; optimization (49-XX) 1 Geophysics (86-XX) Citations by Year