GIT-GVU-99-02

Grow & Fold: Compression of Tetrahedral Meshes

Andrzej Szymczak
Jarek Rossignac

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 for each tetrahedron as four vertex-references, which together occupy 128 bits. For simple 3D meshes with a single scalar value per node, non-compressed vertex data occupies 14 times less storage. Our Grow & Fold format reduces the connectivity storage down to 7 bits per tetrahedron: 3 of these are used to encode the presence of children in a tetrahedron spanning tree; the other 4 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. By storing vertex data in an order defined by the tree, we avoid the need to store tetrahedron-vertex references, and facilitate variable coding techniques for the vertex data. We provide the details of simple, loss-less compression and decompression algorithms and describe implementation results.

Tetrahedral meshes, Grow & Fold, algorithms

PDF

Postscript