Proceedings: GI 2006

Streaming compression of tetrahedral volume meshes

Martin Isenburg, Peter Lindstrom, Stefan Gumhold, Jonathan Shewchuk

Proceedings of Graphics Interface 2006: Québec, Québec, Canada, 7-9 June 2006, 115-121

  • BibTex

    author = {Isenburg, Martin and Lindstrom, Peter and Gumhold, Stefan and Shewchuk, Jonathan},
    title = {Streaming compression of tetrahedral volume meshes},
    booktitle = {Proceedings of Graphics Interface 2006},
    series = {GI 2006},
    year = {2006},
    issn = {0713-5424},
    isbn = {1-56881-308-2},
    location = {Qu{\'e}bec, Qu{\'e}bec, Canada},
    pages = {115--121},
    numpages = {7},
    publisher = {Canadian Human-Computer Communications Society},
    address = {Toronto, Ontario, Canada},


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.