Streaming Compression of Tetrahedral Volume Meshes

Martin Isenburg      Peter Lindstrom      Stefan Gumhold      Jonathan Shewchuk

abstract:
Geometry processing algorithms have traditionally assumed that the input data is entirely in main memory and available for random access. This assumption does not scale to large data sets, as exhausting the physical memory typically leads to IO-inefficient thrashing. Recent works advocate processing geometry in a ``streaming'' manner, where computation and output begin as soon as possible. Streaming is suitable for tasks that require only local neighbor information and batch process an entire data set.

We describe a streaming compression scheme for tetrahedral volume meshes that encodes vertices and tetrahedra in the order they are written. To keep the memory footprint low, the compressor is informed when vertices are referenced for the last time (i.e. are finalized). The compression achieved depends on how coherent the input order is and how many tetrahedra are buffered for local reordering. For reasonably coherent orderings and a buffer of 10,000 tetrahedra, we achieve compression rates that are only 25 to 40 percent above the state-of-the-art, while requiring drastically less memory resources and less than half the processing time.

main contributions:

  • compression (not just decompression) of tetrahedral meshes in a streaming manner
  • writing and reading of compressed, irregular grids becomes user-transparent
  • practical independence of mesh size. scales to very large inputs
  • local instead of global reordering for connectivity compression
  • detailed analysis of different geometry prediction rules
  • support for preserving the original order of tetrahedra (if needed)
  • the first benchmark rates, timings, and implementation for streaming compression of tet meshes

  • publications:

  • [il-sctvm-06.pdf] Martin Isenburg, Peter Lindstrom, Stefan Gumhold, Jonathan Shewchuk, Streaming Compression of Tetrahedral Volume Meshes, Proceedings of Graphics Interface 2006, pages 115-121, June 2006.
  • related publications:

  • [ils-sctm-05.pdf slides] Martin Isenburg, Peter Lindstrom, Jack Snoeyink, Streaming Compression of Triangle Meshes, Proceedings of 3rd Symposium on Geometry Processing, pages 111-118, July 2005.
  • [ils-lcpfpg-05.pdf slides] Martin Isenburg, Peter Lindstrom, Jack Snoeyink, Lossless Compression of Predicted Floating-Point Geometry, in Computer-Aided Design, Volume 37, Issue 8, pages 869-877, July 2005.
  • download: (updated on January 23th, 2010)

  • compressor and decompressor software and demo: sctvm_demo.zip (17 MB)
  • source code: sv_api.zip (8 MB)