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)