Geometry compression of tetrahedral meshes using optimized prediction

In this paper we propose a novel geometry compression technique for volumetric datasets represented as tetrahedral meshes. We focus on a commonly used technique for predicting vertex geometries via a flipping operation using an extension of the parallelogram rule. We demonstrate that the efficiency of the flipping operation is dependent on the order in which tetrahedra are traversed and vertices are predicted accordingly. We formulate the problem of optimally (traversing tetrahedra and) predicting the vertices via flippings as a combinatorial optimization problem of constructing a constrained minimum spanning tree. We give heuristic solutions for this problem and show that we can achieve prediction efficiency very close to that of the unconstrained minimum spanning tree which is an unachievable lower bound. We also show significant improvements of our new geometry compression over the state-of-the-art flipping approach, whose traversal order does not take into account the geometry of the mesh.