s'authentifier
version française rss feed

inria-00070765, version 1

Canonical Triangulation of a Graph, with a Coding Application

Luca Castelli Aleardi 1, Olivier 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.

  • 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
  • oai:hal.inria.fr:inria-00070765
  • Contributeur : 
  • Soumis le : Vendredi 19 Mai 2006, 21:34:24
  • Dernière modification le : Mercredi 31 Mai 2006, 14:24:25
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...