Grow & Fold: Compression of Tetrahedral Meshes

Standard representations of irregular #nite element meshes combine vertex data #sample coordinates and node values# and connectivity #tetrahedronvertex incidence#. Connectivity speci#es how the samples should be interpolated. It may be encoded for each tetrahedron as four vertex-references, 1 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 de#ned by the tree, we avoid the need to store tetrahedron-vertex references,..