Out-of-Core Compression for Gigantic Polygon Meshes

Martin Isenburg      Stefan Gumhold

abstract:
Polygonal models acquired with emerging 3D scanning technology or from large scale CAD applications easily reach sizes of several gigabytes and do not fit in the address space of common 32-bit desktop PCs. In this paper we propose an out-of-core mesh compression technique that converts such gigantic meshes into a streamable, highly compressed representation. During decompression only a small portion of the mesh needs to be kept in memory at any time. As full connectivity information is available along the decompression boundaries, this provides seamless mesh access for incremental in-core processing on gigantic meshes. Decompression speeds are CPU-limited and exceed one million vertices and two million triangles per second on a 1.8 GHz Athlon processor.
A novel external memory data structure provides our compression engine with transparent access to arbitrary large meshes. This out-of-core mesh was designed to accommodate the access pattern of our region-growing based compressor, which - in return - performs mesh queries as seldom and as local as possible by remembering previous queries as long as needed and by adapting its traversal slightly. The achieved compression rates are state-of-the-art.

main contributions:

  • an external memory data structure that provides transparent access to connectivity and geometry of gigantic meshes
  • a method to construct this out-of-core mesh from an indexed mesh representation
  • a compression scheme that uses the out-of-core mesh to compress gigantic models in one piece
  • a streamable, highly compressed mesh format that allows decompression at over 2 million triangles per second
  • the concept of a processing sequence for high-speed, limited memory foot-print mesh computations with access to seamless connectivity
  • publication:

  • [ig-ooccgpm-03.pdf] Martin Isenburg, Stefan Gumhold, Out-of-Core Compression for Gigantic Polygon Meshes, Proceedings of SIGGRAPH'03, pages 935-942, July 2003.
  • related publications:

  • processing sequences (unpublished brain-storming draft, april 2003)
  • [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.
  • [il-sm-05.pdf slides] Martin Isenburg, Peter Lindstrom, Streaming Meshes, Proceedings of Visualization'05, pages 231-238, October 2005.
  • download:

  • interactive demo and compressed models oocc_demo.zip (6 MB)
  • slides: oocc.ppt (10 MB) (+ embedded videos)
  • the compressed lucy model at 16 bits: lucy_compressed_16bit.ply (28 MB)
  • the compressed david_1mm model at 16 bits: david_1mm_compressed_16bit.ply (44 MB) (*)
  • the compressed stmatthew model at 18 bits: stmatthew_compressed_18bit.ply (344 MB) (*)
  • a Windows MSVC6.0 project with lib and inc files for in-core compression oocc_api.zip (2 MB)
  • a Windows and Linux/IRIX API and source code for reading the compressed format.

    (*) The restricted models from Stanford's Digital Michelangelo Project are only available to verified licence holders.

    gigantic models:

  • Stanford's Digital Michelangelo Project
  • The Stanford 3D Scanning Repository
  • The 'power-plant' of UNC's Walkthru Group
  • Georgia-Tech's Large Geometric Model Archive
  • hindsights:
    When we started this work our main goal was to gain the ability to compress gigantic meshes with an out-of-core method into a highly compressed format from which they could then be decompressed with a small memory foot-print. For this we designed a mesh traversal that would keep the number of accesses to the out-of-core mesh to a minimum while driving the achieved compression to a maximum and---just like all previous works on mesh compression---we paid no attention what that would do to the ordering of triangles. In our streaming mesh work we realized that traversing the mesh triangles in a depth-first manner produces unnecessarily incoherent mesh layouts. Instead, the compressor should give all vertices a similarly long ``life-time'' on the compression boundary.
    Achieving coherence in the layout of the compressed mesh requires three changes to the traversal order of our out-of-core compressor. First, the traversal needs to advance along all boundaries simultaneously instead of operating exclusively on one boundary. One way of achieving this is to continue on the least recently advanced boundary whenever completing a loop around a boundary. Second, the adaptive traversal that jumps around the boundary in an attempt to avoid split operation needs to be replaced with a more coherence-preserving strategy. And third, once a non-manifold vertex has made its first appearance we can no longer just wait until the traversal runs into its other appearances. This can leave such vertices ``hanging'' for a long time, especially if they re-appear in separate mesh components that are not edge-connected. To reduce their ``life-time'' requires the start of an additional compression boundaries, making this probably the most complex change.

    relevant previous works: (in chronological order)

  • [crms-emmshm-03] "External Memory Management and Simplification of Huge Meshes", Paolo Cignoni, Claudio Rocchini, Claudio Montani, and Roberto Scopigno, to appear in IEEE Transactions on Visualization and Computer Graphics, 2003.
  • [gs-maess-02] "A Multiphase Approach to Efficient Surface Simplification", Michael Garland and Eric Shaffer, Visualization'02, pages 117-124, 2002.
  • [ia-cpmgpp-02] "Compressing Polygon Mesh Geometry with Parallelogram Prediction", Martin Isenburg and Pierre Alliez, Visualization'02, pages 141-146, 2002.
  • [dp-xfmfvdmem-02] "XFastMesh: Fast view-dependent meshing from external memory", Chris DeCoro and Renato Pajarola, Visualization'02, pages 363-370, 2002.
  • [scel-oocasvcg-02] "Out-of-Core Algorithms for Scientific Visualization and Computer Graphics", Claudio Silva, Yi-Jen Chiang, Jihad El-Sana, and Peter Lindstrom, Visualization'02 Course Notes, 2002.
  • [rlsts-ebscsh-02] "Edgebreaker: A Simple Compression for Surfaces with Handles", Jarek Rossignac, Hélio Lopes, Alla Safanova, Geovan Tavares, and Andrzej Szymczak, Technical Report GIT-GVU-02-03, 12 pages, 2002.
  • [pc-casmm-02] "Completely Adaptive Simplification of Massive Meshes", Prasun Choudhury and Benjamin Watson, Technical Report NWU-CS-02-09, 8 pages, 2002.
  • [lad-aatqmc-02] "Angle-Analyzer: A Triangle-Quad Mesh Codec", Haeyoung Lee, Pierre Alliez, and Mathieu Desbrun, Eurographics'02, pages 383-392, 2002.
  • [kg-octmgupt-02] "Optimized Compression of Triangle Mesh Geometry Using Prediction Trees", Boris Kronrod and Craig Gotsman, International Symposium on 3D Data Processing Visualization and Transmission, pages 602-608, 2002.
  • [i-cpmcddp-02] "Compressing Polygon Mesh Connectivity with Degree Duality Prediction", Martin Isenburg, Graphics Interface'02, pages 161-170, 2002.
  • [srk-prmcc-02] "Piecewise Regular Meshes: Construction and Compression", Andrzej Szymczak, Jarek Rossignac, and Davis King, Graphic Models 64(3-4), pages 183-198, 2002.
  • [kads-noce2mpm-02] "Near-Optimal Connectivity Encoding of 2-Manifold Polygon Meshes", Andrei Khodakovsky, Pierre Alliez, Mathieu Desbrun, and Peter Schröder, Graphic Models 64(3-4), pages 147-168, 2002.
  • [bmmrt-bdmmfp-02] "Building a Digital Model of Michelangelo's Florentine Pieta", Fausto Bernardini, Ioana Martin, Joshua Mittleman, Holly Rushmeier, and Gabriel Taubin, IEEE Computer Graphics and Applications 22(1), pages 59-67, 2002.
  • [s-oeelrtm-02] "Optimized Edgebreaker Encoding for Large and Regular Meshes", Andrzej Szymczak, Data Compression Conference'02, Poster, page 472, 2002.
  • [ls-mitlms-01] "A Memory Insensitive Technique for Large Model Simplification", Peter Lindstrom and Claudio Silva, Visualization'01, pages 121-126, 2001.
  • [sg-easmm-01] "Efficient Adaptive Simplification of Massive Meshes", Eric Shaffer and Michael Garland, Visualization'01, pages 127-134, 2001.
  • [hlk-clpm-01] "Compressing Large Polygonal Models", Jeffery Ho, Kuang-Chih Lee, and David Kriegman, Visualization'01, pages 357-362, 2001.
  • [mhs-oocbtdsps-01] "Out-of-Core Build of a Topological Data Structure from Polygon Soup", Sara McMains, Joseph Hellerstein, and Carlo Sequin, Solid Modeling'01, pages 171-182, 2001.
  • [rss-3dcmsect-01] "3D compression made simple: Edgebreaker on a Corner Table", Jarek Rossignac, Alla Safanova, and Andrzej Szymczak, Shape Modeling International'01, pages 278-283, 2001.
  • [ad-vdce3dm-01] "Valence-Driven Connectivity Encoding for 3D Meshes", Pierre Alliez and Mathieu Desbrun, Eurographics'01, pages 198-205, 2001.
  • [lk-vdctm-00] "Vertex Data Compression for Triangular Meshes", Eung-Seok Lee and Hyeong-Seok Ko, Pacific Graphics'00, pages 225-234, 2000.
  • [ec-emvdr-00] "External Memory View-Dependent Rendering", Jihad El-Sana and Yi-Jen Chiang, Eurographics'00, pages 139-150, 2000.
  • [l-oocslpm-00] "Out-of-Core Simplification of Large Polygonal Meshes", Peter Lindstrom, SIGGRAPH'00, pages 259-262, 2000.
  • [is-ff-00] "Face Fixer: Compressing Polygon Meshes with Properties", Martin Isenburg and Jack Snoeyink, SIGGRAPH'00, pages 263-270, 2000.
  • [p-pmlmat-00] "Progressive Meshes for Large Models of Arbitrary Topology", Chris Prince, Master Thesis, 9 pages, 2000.
  • [kg-nmc-00] "Normal Mesh Compression", Andrei Khodakovsky and Igor Guskov, preprint, 2000.
  • [kss-pgc-00] "Progressive Geometry Compression", Andrei Khodakovsky, Peter Schröder, and Wim Sweldens, SIGGRAPH'00, pages 271-278, 2000.
  • [kg-scmg-00] "Spectral Compression of Mesh Geometry", Zachi Karni and Craig Gotsman, SIGGRAPH'00, pages 279-286, 2000.
  • [lpcrkpgadgsf-dmp-00] "The Digital Michelangelo Project", Marc Levoy, Kari Pulli, Brian Curless, Szymon Rusinkiewicz, Dave Koller, Lucas Pereira, Matt Ginzton, Sean Anderson, James Davis, Jeremy Ginsberg, Jonathan Shade, and Duane Fulk, SIGGRAPH'00, pages 131-144, 2000.
  • [gcts-ecnmpm-99] "Efficient Compression of Non-Manifold Polygonal Meshes", Andre Gueziec, Frank Bossen, Gabriel Taubin, and Claudio Silva, Visualization'99, pages 73-80, 1999.
  • [bpz-srcatmp-99] "Single resolution compression of arbitrary triangular meshes with properties", Chandrajit Bajaj, Valerio Pascucci, and GuoZhong Zhuang, Data Compression Conference'99, pages 247-256, 1999.
  • [bmrst-bpasr-99] "The Ball-Pivoting Algorithm for Surface Reconstruction", Fausto Bernardini, Joshua Mittleman, Holly Rushmeier, Claudio Silva, and Gabriel Taubin , IEEE Transactions on Visualization and Computer Graphics 5(4), pages 349-359, 1999.
  • [r-ebcctm-99] "Edgebreaker: Connectivity compression for triangle meshes", Jarek Rossignac, IEEE Transactions on Visualization and Computer Graphics 5(1), pages 47-61, 1999.
  • [gtlh-cspmscs-98] "Converting Sets of Polygons to Manifold Surfaces by Cutting and Stitching", Andre Gueziec, Gabriel Taubin, Francis Lazarus, and William Horn, Visualization'98, pages 383-390, 1998.
  • [gs-rtctmc-98] "Real-time Compression of Triangle Mesh Connectivity", Stefan Gumhold and Wolfgang Strasser, SIGGRAPH'98, pages 133-140, 1998.
  • [tg-tmc-98] "Triangle Mesh Compression", Costa Touma and Craig Gotsman, Graphics Interface'98, pages 26-34, 1998.
  • [tr-gctts-98] "Geometric compression through topological surgery", Gabriel Taubin and Jarek Rossignac, ACM Transactions on Graphics 17(2), pages 84-115, 1998.
  • [d-gc-95] "Geometry Compression", Michael Deering, SIGGRAPH'95, pages 13-20, 1995.