A Caltech Library Service

Near-Optimal Connectivity Encoding of 2-Manifold Polygon Meshes

Khodakovsky, Andrei and Alliez, Pierre and Desbrun, Mathieu and Schröder, Peter (2002) Near-Optimal Connectivity Encoding of 2-Manifold Polygon Meshes. Graphical Models, 64 (3-4). pp. 147-168. ISSN 1524-0703. doi:10.1006/gmod.2002.0575.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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 the 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 or face regularity if present. When the mesh exhibits perfect face regularity (e.g., a pure triangle or quad mesh) 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 two bits per edge in the worst case.

Item Type:Article
Related URLs:
URLURL TypeDescription ItemTechnical Report
Desbrun, Mathieu0000-0003-3424-6079
Schröder, Peter0000-0002-0323-7674
Additional Information:The work reported here was supported in part by the NSF (ACI-9721349, DMS-9872890, ACI-9982273, EEC-9529152, CCR-0133983). Other support was provided by Intel, Microsoft, Alias|Wavefront, Pixar, and the Packard Foundation. Additional thanks to Olivier Devillers for many discussions on the number-of-splits issue, and Craig Gotsman for access to his coder. The datasets are courtesy of Viewpoint Datalabs, Martin Isenburg, Digital Michelangelo Project, Stanford University, Cyberware, Headus, Hugues Hoppe, and The Scripps Research Institute.
Funding AgencyGrant Number
David and Lucile Packard FoundationUNSPECIFIED
Issue or Number:3-4
Record Number:CaltechAUTHORS:20230210-546014000.1
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:119209
Deposited By: George Porter
Deposited On:10 Feb 2023 23:34
Last Modified:10 Feb 2023 23:34

Repository Staff Only: item control page