Edgebreaker: connectivity compression for triangle meshes

摘要

Edgebreaker is a simple scheme for compressing the triangle/vertexnincidence graphs (sometimes called connectivity or topology) ofnthree-dimensional triangle meshes. Edgebreaker improves upon the storagenrequired by previously reported schemes, most of which can guaranteenonly an O(t log(t)) storage cost for the incidence graph of a mesh of tntriangles. Edgebreaker requires at most 2t bits for any meshnhomeomorphic to a sphere and supports fully general meshes by usingnadditional storage per handle and hole. For large meshes, entropy codingnyields less than 1.5 bits per triangle. Edgebreaker's compression andndecompression processes perform identical traversals of the mesh fromnone triangle to an adjacent one. At each stage, compression produces annop-code describing the topological relation between the current trianglenand the boundary of the remaining part of the mesh. Decompression usesnthese op-codes to reconstruct the entire incidence graph. BecausenEdgebreaker's compression and decompression are independent of thenvertex locations, they may be combined with a variety ofnvertex-compressing techniques that exploit topological information aboutnthe mesh to better estimate vertex locations. Edgebreaker may be used toncompress the connectivity of an entire mesh bounding a 3D polyhedron ornthe connectivity of a triangulated surface patch whose boundary need notnbe encoded. The paper also offers a comparative survey of the rapidlyngrowing field of geometric compression