Streaming Meshes

Martin Isenburg      Peter Lindstrom

abstract:
Recent years have seen an immense increase in the complexity of geometric data sets. Today's gigabyte-sized polygon models can no longer be completely loaded into the main memory of common desktop PCs. Unfortunately, current mesh formats do not account for this. They were designed years ago when meshes were orders of magnitudes smaller. Using such formats to store large meshes is inefficient and unduly complicates all subsequent processing.

We describe a streaming format for polygon meshes, which is simple enough to replace current mesh formats and more suitable for working with large data sets. Furthermore, it is an ideal input and output format for IO-efficient out-of-core algorithms that process meshes in a streaming, possibly pipelined, fashion. This paper chiefly concerns the underlying theory and the practical aspects of creating and working with this new representation. In particular, we describe desirable qualities for streaming meshes, methods for converting meshes from a traditional to a streaming format, and a novel technique for streaming on-the-fly compression.

The central theme of this paper is the issue of coherent and compatible orderings of the mesh vertices and polygons. We present metrics and diagrams that characterize the coherence of a mesh layout and suggest appropriate strategies for improving its ``streamability''. To this end, we outline several out-of-core algorithms for reordering meshes with poor coherence, and present results for a menagerie of well known and generally incoherent surface meshes.

main contributions:

  • the concept of a streaming format for polygonal meshes
  • a number of metrics for the coherency in existing mesh layouts - these help us decide how much work to put into coverting them to a streaming mesh
  • a set of out-of-core tools for converting meshes from a standard format into a streaming format
  • quantitative measures for the stream-quality of streaming meshes and how they affect different types of processing
  • the observation that popular stack-based mesh compressors systematically produce sub-optimal layouts
  • a scheme for streaming compression of meshes that preserves the stream-order

  • publication:

  • [il-sm-05.pdf], Martin Isenburg, Peter Lindstrom, Streaming Meshes, Proceedings of Visualization'05, pages 231-238, October 2005.
  • [ilgs-sfgd-05.pdf] (abstract), Martin Isenburg, Peter Lindstrom, Stefan Gumhold, Jack Snoeyink, Streaming Formats for Geometric Datasets, presented at the MASSIVE'05 workshop in Pisa, June 2005.
  • 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-sctm_abs-05.pdf] (abstract), Martin Isenburg, Peter Lindstrom, Jack Snoeyink, Streaming Compression of Triangle Meshes, presented as a sketch at SIGGRAPH'05, Los Angeles, August 2005.
  • [ilss-scdt-06.pdf slides], Martin Isenburg, Yuanxin Liu, Jonathan Shewchuk, Jack Snoeyink, Streaming Computation of Delaunay Triangulations, accepted to SIGGRAPH'06, July, 2006.
  • [ilgs-lmsps-03.pdf slides] Martin Isenburg, Peter Lindstrom, Stefan Gumhold, Jack Snoeyink, Large Mesh Simplification using Processing Sequences, Proceedings of Visualization'03, pages 465-472, October 2003.
  • [ig-ooccgpm-03.pdf slides] Martin Isenburg, Stefan Gumhold, Out-of-Core Compression for Gigantic Polygon Meshes, Proceedings of SIGGRAPH'03, pages 935-942, July 2003.
  • download: (updated on january 11th, 2010)

  • source code and programming API, including MSVC 6.0 project files: sm_api.zip (8 MB)
  • interactive demo software + models in streaming formats: sm_demo.zip (37 MB)
  • slides: sm.ppt (+ embedded videos)
  • algorithms that 'naturally' generate streaming meshes

  • [ilss-scdt-06.pdf], Martin Isenburg, Yuanxin Liu, Jonathan Shewchuk, Jack Snoeyink, Streaming Computation of Delaunay Triangulations, Proceedings of SIGGRAPH'06, pages 1049-1056, July, 2006.
  • [mips-evgsie-04.pdf] Ajith Mascarenhas, Martin Isenburg, Valerio Pascucci, Jack Snoeyink, Encoding Volumetric Grids For Streaming Isosurface Extraction, Proceedings of 3DPVT'04, pages 665-672, September 2004.
  • [jlsw-dchd-02] "Dual Contouring of Hermite Data", Tao Ju, Frank Losasso, Scott Schaefer, Joe Warren, SIGGRAPH'02 Conference Proceedings, 339-346, 2002.
  • [bpasr-bmrst-99] "The Ball-Pivoting Algorithm for Surface Reconstruction", Fausto Bernardini, Joshua Mittleman, Holly Rushmeier, Claudio Silva, Gabriel Taubin, IEEE Transactions on Visualization and Computer Graphics, 5(4):349-359, 1999.
  • [sm-gcaftta-98] "Greedy Cuts: An Advancing Front Terrain Triangulation Algorithm", Claudio Silva, Joseph Mitchell, Symposium on Geographic Information Systems, 137-144, 1998.
  • [lc-mc-87] "Marching cubes: A high resolution 3D surface construction algorithm", William Lorensen, Harvey Cline, SIGGRAPH'87 Conference Proceedings, 163-169, 1987.
  • ... more ...
  • algorithms that 'naturally' operate on streaming meshes

  • [ilgs-lmsps-03] "Large Mesh Simplification using Processing Sequences", Martin Isenburg, Peter Lindstrom, Stefan Gumhold, Jack Snoeyink, Visualization'03 Conference Proceedings, 465-472, 2003.
  • [wk-sadmm-03] "A Stream Algorithm for the Decimation of Massive Meshes", Jianhua Wu, Leif Kobbelt, Proceedings of Graphics Interface'03, 185-192, 2003.
  • ... more ...