Edgebreaker
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.
Keywords for this software
References in zbMATH (referenced in 50 articles )
Showing results 1 to 20 of 50.
Sorted by year (- Götschel, Sebastian; von Tycowicz, Christoph; Polthier, Konrad; Weiser, Martin: Reducing memory requirements in scientific computing and optimal control (2015)
- Zhao, Jie-Yi; Tang, Min; Tong, Ruo-Feng: Connectivity-based segmentation for GPU-accelerated mesh decompression (2012)
- Bonichon, Nicolas; Gavoille, Cyril; Hanusse, Nicolas: An information-theoretic upper bound on planar graphs using well-orderly maps (2011)
- Castelli Aleardi, Luca; Devillers, Olivier: Explicit array-based compact data structures for triangulations (2011)
- Lyuu, Yuh-Dauh; Ma, Tak-Man; Ti, Yen-Wu: Linear-time compression of 2-manifold polygon meshes into information-theoretically optimal number of bits (2011)
- Cheng, Shyi-Chyi; Kuo, Chen-Tsung; Wu, Da-Chun: A novel 3D mesh compression using mesh segmentation with multiple principal plane analysis (2010)
- Ivrissimtzis, Ioannis: Effects of noise on quantized triangle meshes (2010)
- Lewiner, Thomas; Lopes, Hélio; Medeiros, Esdras; Tavares, Geovan; Velho, Luiz: Topological mesh operators (2010)
- Tu, Shih-Chun; Tai, Wen-Kai; Isenburg, Martin; Chang, Chin-Chen: An improved data hiding approach for polygon meshes (2010)
- Yamanaka, Katsuhisa; Nakano, Shin-Ichi: A compact encoding of plane triangulations with efficient query supports (2010)
- Castelli Aleardi, Luca; Fusy, Éric; Lewiner, Thomas: Schnyder woods for higher genus triangulated surfaces, with applications to encoding (2009)
- Qi, Yue; Yang, Shen; Cai, Su; Hou, Fei; Shen, Xukun; Zhao, Qinping: A method of 3D modeling and codec (2009)
- Aleardi, L.Castelli; Devillers, O.; Schaeffer, G.: Succinct representations of planar maps (2008)
- Lu, Zhe-Ming; Li, Zhen: Dynamically restricted codebook-based vector quantisation scheme for mesh geometry compression (2008)
- Viaña, Raquel: Quick encoding of plane graphs in $\log _214$ bits per edge (2008)
- Aleardi, Luca Castelli; Devillers, Olivier; Schaeffer, Gilles: Optimal succinct representations of planar maps (2006)
- Blandford, Daniel K.; Blelloch, Guy E.; Kadow, Clemens: Engineering a compact parallel Delaunay algorithm in 3D (2006)
- Bonichon, Nicolas; Gavoille, Cyril; Hanusse, Nicolas; Poulalhon, Dominique; Schaeffer, Gilles: Planar graphs, via well-orderly maps and trees (2006)
- Poulalhon, Dominique; Schaeffer, Gilles: Optimal coding and sampling of triangulations (2006)
- Alliez, Pierre; Gotsman, Craig: Recent advances in compression of 3D meshes (2005)