3D Compression Made Simple: Edgebreaker on a Corner-Table

Abstract

Edgebreaker is a simple technique for compressing 3D triangle meshes. We introduce here a new formulation, which leads to a simple implementation. We describe it in terms of a data structure, the Corner Table, which represents the connectivity of any manifold triangle mesh as two table of integers. 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 a parallelogram predictor. Entropy encoding reduces this cost in practice to less than a bit per triangle when the mesh is large. The detailed compression and decompression algorithms fit on a page. Through minor modifications, the Edgebreaker algorithm has been adapted to manifold meshes with holes and handles, to nontriangle meshes, and to non-manifold meshes. A Corner-Table implementation of these extensions will be described elsewhere.