Compression Hexahedral Volume Meshes

Martin Isenburg            Pierre Alliez

abstract:
Unstructured hexahedral volume meshes are of particular interest for visualization and simulation applications. They allow regular tiling of the three-dimensional space and show good numerical behaviour in finite element computations. Beside such appealing properties, volume meshes take up huge amounts of space when stored in a raw format. In this paper we present a technique for encoding connectivity and geometry of unstructured hexahedral volume meshes.

For connectivity compression, we extend the idea of coding with degrees as pioneered by Touma and Gotsman to volume meshes. Hexahedral connectivity is coded as a sequence of edge degrees. This naturally exploits the regularity of typical hexahedral meshes. We achieve compression rates of around 1.5 bits per hexahedron (bph) that go down to 0.18 bph for regular meshes. On our test meshes the average connectivity compression ratio is 1:162.

For geometry compression, we perform simple parallelogram prediction on uniformly quantized vertices within the side of a hexahedron. Tests show an average geometry compression ratio of 1:3.7 at a quantization level of 16 bits.

main contributions:

  • extending degree coding to volume mesh connectivity
  • using edge degrees rather than vertex degrees
  • maintaining edge slots on the active hull
  • exploiting the regularity found in hexahedral connectivity
  • identifying tetrahedral meshes as "naturally" irregular
  • showing that hexahedral geometry compresses better than tetrahedral geometry

  • publication:

  • [ia-chvm-02.pdf], Martin Isenburg, Pierre Alliez, Compressing Hexahedral Volume Meshes, Proceedings of Pacific Graphics 2002, pages 284-293, October 2002.
    ---> appeared also as a journal version in Graphical Models, Volume 65, Issue 4, pages 239-257, July 2003.
  • related publications:

  • [i-cpmcddp-02.pdf slides] Martin Isenburg, Compressing Polygon Mesh Connectivity with Degree Duality Prediction, Proceedings of Graphics Interface 2002, pages 161-170, May 2002.
  • [ia-cpmgpp-02.pdf slides] Martin Isenburg, Pierre Alliez, Compressing Polygon Mesh Geometry with Parallelogram Prediction, Proceedings of Visualization 2002, pages 141-146, October 2002.
  • downloads:

  • slides: chvm.ppt (8.9 MB)
  • interactive demo (including models): chvm_demo.zip (1.4 MB)
  • source code: chvm_src.zip (90 KB)
  • hindsights:
    The described data structure for compression is unnecessarily bloated. A more efficient implementation would separate the data structure into a static part that stores hexahedral connectivity and a dynamic part that maintains the hull. The described prediction for the position of the last vertex of a hexahedron (by far the most frequent case) should be replaced by the more efficient Lorenzo prediction. This improves geometry compression rates further and is already implemented in the available source code.

    funding:

  • This work was partly supported by the ARC-TeleGeo grant at INRIA, Sophia-Antipolis.