Near-Optimal Connectivity Encoding of 2-Manifold Polygon Meshes - Archive ouverte HAL Access content directly
Reports Year : 2002

Near-Optimal Connectivity Encoding of 2-Manifold Polygon Meshes

Pierre Alliez
Mathieu Desbrun
Peter Schröder
  • Function : Author


Encoders for triangle mesh connectivity based on enumeration of vertex valences are among the best reported to date. They are both simple to implement and report the best compressed file sizes for a large corpus of test models. Additionally they have recently been shown to be near-optimal since they realize the Tutte entropy bound for all planar triangulations. In this paper we introduce a connectivity encoding method which extends these ideas to 2-manifold meshes consisting of faces with arbitrary degree. The encoding algorithm exploits duality by applying valence enumeration to both the primal and dual mesh in a symmetric fashion. It generates two sequences of symbols, vertex valences and face degrees, and encodes them separately using two context-based arithmetic coders. This allows us to exploit vertex and/or face regularity if present. When the mesh exhibits perfect face regularity (, a pure triangle or quad mesh) and/or perfect vertex regularity (valence six or four respectively) the corresponding bit rate vanishes to zero asymptotically. For triangle meshes, our technique is equivalent to earlier valence driven approaches. We report compression results for a corpus of standard meshes. In all cases we are able to show coding gains over earlier coders, sometimes as large as 50. Remarkably, we even slightly gain over coders specialized to triangle or quad meshes. A theoretical analysis reveals that our approach is near-optimal as we achieve the Tutte entropy bound for arbitrary planar graphs of 2 bits per edge in the worst case.
Fichier principal
Vignette du fichier
RR-4575.pdf (1.11 Mo) Télécharger le fichier

Dates and versions

inria-00072013 , version 1 (23-05-2006)


  • HAL Id : inria-00072013 , version 1


Andrei Khodakovsky, Pierre Alliez, Mathieu Desbrun, Peter Schröder. Near-Optimal Connectivity Encoding of 2-Manifold Polygon Meshes. RR-4575, INRIA. 2002. ⟨inria-00072013⟩
119 View
316 Download


Gmail Facebook Twitter LinkedIn More