Grow & Fold: Compression of Tetrahedral Meshes

Standard representations of irregular finite element meshes combine vertex data (sample coordinates and node values) and connectivity (tetrahedronvertex 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. 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. However, as our experiments with a prototype implementation show, the increase of the storage 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 reference..