Canonical Triangulation of a Graph, with a Coding Application - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport Année : 2004

Canonical Triangulation of a Graph, with a Coding Application

Olivier Devillers

Résumé

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.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-5231.pdf (726.89 Ko) Télécharger le fichier
Loading...

Dates et versions

inria-00070765 , version 1 (19-05-2006)

Identifiants

  • HAL Id : inria-00070765 , version 1

Citer

Luca Castelli Aleardi, Olivier Devillers. Canonical Triangulation of a Graph, with a Coding Application. RR-5231, INRIA. 2004, pp.24. ⟨inria-00070765⟩
166 Consultations
295 Téléchargements

Partager

Gmail Facebook X LinkedIn More