inria-00070765, version 1
Canonical Triangulation of a Graph, with a Coding Application
Luca Castelli Aleardi 1Olivier Devillers
N° RR-5231 (2004)
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.
- 1 : GEOMETRICA (INRIA Sophia Antipolis)
- INRIA
- Domaine : Informatique/Autre
- Mots-clés : MESH COMPRESSION / CONNECTIVITY ENCODING / CANONICAL ORDERINGS / 3-CONNECTED PLANAR GRAPHS
- Référence interne : RR-5231
- inria-00070765, version 1
- http://hal.inria.fr/inria-00070765
- oai:hal.inria.fr:inria-00070765
- Contributeur : Rapport De Recherche Inria
- Soumis le : Vendredi 19 Mai 2006, 21:34:24
- Dernière modification le : Mercredi 31 Mai 2006, 14:24:25






Documents associés

Exporter