HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

Canonical Triangulation of a Graph, with a Coding Application

Luca Castelli Aleardi 1 Olivier Devillers
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : For compression of 3D meshes, we propose an algorithm to encode the transformation of a polygonal mesh into a triangular mesh, getting a full coder by combination with a triangular coder. In this way, we benefit of the possibility of choosing a triangular coder relevant for a particular kind of mesh. Let $G$ be a $3$-connected simple planar graph with $e$ edges. We introduce a special type of triangulation $T_G$ of $G$, based on the canonical orderings of this class of graphs. We show how to reconstruct the original graph starting from its canonical triangulation $T_G$, using only the face degrees of $G$: this detriangulation phase takes linear time and requires at most $e+o(e)$ bits. Our canonical coding of the detriangulation of $G$ can be combined with any triangulation coder to obtain a full coder of the connectivity of any genus $0$ polygonal mesh.
Document type :
Reports
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/inria-00070765
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Friday, May 19, 2006 - 9:34:24 PM
Last modification on : Friday, February 4, 2022 - 3:19:35 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:52:21 PM

Identifiers

  • HAL Id : inria-00070765, version 1

Collections

Citation

Luca Castelli Aleardi, Olivier Devillers. Canonical Triangulation of a Graph, with a Coding Application. RR-5231, INRIA. 2004, pp.24. ⟨inria-00070765⟩

Share

Metrics

Record views

156

Files downloads

238