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 metadatas

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/inria-00070765
Contributor : Rapport de Recherche Inria <>
Submitted on : Friday, May 19, 2006 - 9:34:24 PM
Last modification on : Saturday, January 27, 2018 - 1:31:34 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

332

Files downloads

244