Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published February 10, 2023 | Accepted Version
Report Open

Near-Optimal Connectivity Encoding of 2-Manifold Polygon Meshes


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.

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.

Attached Files

Accepted Version - cit-asci-tr151.pdf


Files (639.3 kB)
Name Size Download all
639.3 kB Preview Download

Additional details

August 19, 2023
January 15, 2024