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 ...