Grow & fold: compressing the connectivity of tetrahedral meshes

Computer-Aided Design, Elsevier, Vol 32, pp.527-537, 2000

MESHING
RESEARCH
CORNER

A. Szymczaka
Fraunhofer IGD, Rundeturmstrasse 6, D-64283 Darmstadt, Germany
E-mail address: aszymcza@igd.fhg.de (A. Szymczak). J. Rossignac
Graphics, Visualization & Usability Center, College of Computing, Georgia Institute of Technology, Atlanta, GA 30332-0280, USA

Abstract
Standard representations of irregular finite element meshes combine vertex data (sample coordinates and node values) and connectivity (tetrahedron-vertex incidence). Connectivity specifies how the samples should be interpolated. It may be encoded as four vertex-references for each tetrahedron, which requires 128m bits where m is the number of tetrahedra in the mesh. Our 'Grow & Fold' format reduces the connectivity storage down to 7 bits per tetrahedron: three of these are used to encode the presence of children in a tetrahedron spanning tree; the other four constrain sequences of 'folding' operations, so that they produce the connectivity graph of the original mesh. Additional bits must be used for each handle in the mesh and for each topological 'lock' in the tree. However, as our experiments with a prototype implementation show, the increase of the sto.rage cost due to this extra information is typically no more than 1-2%. By storing vertex data in an order defined by the tree, we avoid the need to store tetrahedron-vertex references and facilitate variable length coding techniques for the vertex data. We provide the details of simple, loss-less compression and decompression algorithms and discuss a way of decreasing the storage cost to about 6 bits per tetrahedron.