Take a look at the new version of this page: [ beta version ]. Tell us what you think.

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.

REFERENCES

• 1: Pierre Alliez , Mathieu Desbrun, Progressive compression for lossless transmission of triangle meshes, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.195-202, August 2001 [doi>10.1145/383259.383281]
• 2: ALLIEZ, P., AND DESBRUN, M. 2001. Valence-driven connectivity encoding for 3D meshes. In Eurographics'01 Conference Proceedings, 480--489.
• 3: ANN. Version 0.2. A library for approximate nearest neighbor searching by D. Mount and S. Arya. University of Maryland.
• 4: Chandrajit L Bajaj , Valerio Pascucci , Guozhong Zhuang, Single Resolution Compression of Arbitrary Triangular Meshes with Properties, Proceedings of the Conference on Data Compression, p.247, March 29-31, 1999
• 5: Reuven Bar-Yehuda , Craig Gotsman, Time/space tradeoffs for polygon mesh rendering, ACM Transactions on Graphics (TOG), v.15 n.2, p.141-152, April 1996 [doi>10.1145/234972.234976]
• 6: BERNARDINI, F., MARTIN, I., MITTLEMAN, J., RUSHMEIER, H., AND TAUBIN, G. 2002. Building a digital model of michelangelo's florentine pieta. IEEE Computer Graphics and Applications 22, 1, 59--67.
• 7: Paolo Cignoni , Claudio Montani , Claudio Rocchini , Roberto Scopigno, External Memory Management and Simplification of Huge Meshes, IEEE Transactions on Visualization and Computer Graphics, v.9 n.4, p.525-537, October 2003 [doi>10.1109/TVCG.2003.1260746]
• 8: Daniel Cohen-Or , David Levin , Offir Remez, Progressive compression of arbitrary triangular meshes, Proceedings of the conference on Visualization '99: celebrating ten years, p.67-72, October 1999, San Francisco, California, United States
• 9: Michael Deering, Geometry compression, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.13-20, September 1995 [doi>10.1145/218380.218391]
• 10: Xianfeng Gu , Steven J. Gortler , Hugues Hoppe, Geometry images, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 11: André Guéziec , Gabriel Taubin , Francis Lazarus , William Horn, Converting sets of polygons to manifold surfaces by cutting and stitching, Proceedings of the conference on Visualization '98, p.383-390, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 12: André Guéziec , Frank Bossen , Gabriel Taubin , Claudio Silva, Efficient compression of non-manifold polygonal meshes, Proceedings of the conference on Visualization '99: celebrating ten years, p.73-80, October 1999, San Francisco, California, United States
• 13: Stefan Gumhold , Wolfgang Straßer, Real time compression of triangle mesh connectivity, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.133-140, July 1998 [doi>10.1145/280814.280836]
• 14: Jeffrey Ho , Kuang Chih Lee , David Kriegman, Compressing large polygonal models, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
• 15: Hugues Hoppe, Smooth view-dependent level-of-detail control and its application to terrain rendering, Proceedings of the conference on Visualization '98, p.35-42, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 16: Hugues Hoppe, Optimization of mesh locality for transparent vertex caching, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.269-276, July 1999 [doi>10.1145/311535.311565]
• 17: Martin Isenburg , Pierre Alliez, Compressing polygon mesh geometry with parallelogram prediction, Proceedings of the conference on Visualization '02, October 27-November 01, 2002, Boston, Massachusetts
• 18: Martin Isenburg , Jack Snoeyink, Face fixer: compressing polygon meshes with properties, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.263-270, July 2000 [doi>10.1145/344779.344919]
• 19: ISENBURG, M. 2002. Compressing polygon mesh connectivity with degree duality prediction. In Graphics Interface'02 Conference Proceedings, 161--170.
• 20: Zachi Karni , Craig Gotsman, Spectral compression of mesh geometry, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.279-286, July 2000 [doi>10.1145/344779.344924]
• 21: Andrei Khodakovsky , Peter Schröder , Wim Sweldens, Progressive geometry compression, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.271-278, July 2000 [doi>10.1145/344779.344922]
• 22: Andrei Khodakovsky , Pierre Alliez , Mathieu Desbrun , Peter Schröder, Near-optimal connectivity encoding of 2-manifold polygon meshes, Graphical Models, v.64 n.3/4, p.147-168, May/July 2002 [doi>10.1006/gmod.2002.0575]
• 23: KRONROD, B., AND GOTSMAN, C. 2002. Optimized compression of triangle mesh geometry using prediction trees. In Proceedings of International Symposium on 3D Data Processing Visualization and Transmission, 602--608.
• 24: Eung-Seok Lee , Hyeong-Seok Ko, Vertex Data Compression for Triangular Meshes, Proceedings of the 8th Pacific Conference on Computer Graphics and Applications, p.225, October 03-05, 2000
• 25: LEE, H., ALLIEZ, P., AND DESBRUN, M. 2002. Angle-analyzer: A triangle-quad mesh codec. In Eurographics'02 Conference Proceedings, 198--205.
• 26: Marc Levoy , Kari Pulli , Brian Curless , Szymon Rusinkiewicz , David Koller , Lucas Pereira , Matt Ginzton , Sean Anderson , James Davis , Jeremy Ginsberg , Jonathan Shade , Duane Fulk, The digital Michelangelo project: 3D scanning of large statues, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.131-144, July 2000 [doi>10.1145/344779.344849]
• 27: LI, J., AND KUO, C. C. 1998. A dual graph approach to 3D triangular mesh compression. In Proceedings of Intern. Conf. on Image Processing '98, 891--894.
• 28: Peter Lindstrom , Cláudio T. Silva, A memory insensitive technique for large model simplification, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
• 29: Peter Lindstrom, Out-of-core simplification of large polygonal models, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.259-262, July 2000 [doi>10.1145/344779.344912]
• 30: M. Mantyla, Introduction to Solid Modeling, W. H. Freeman & Co., New York, NY, 1988
• 31: Sara McMains , Joseph M. Hellerstein , Carlo H. Séquin, Out-of-core build of a topological data structure from polygon soup, Proceedings of the sixth ACM symposium on Solid modeling and applications, p.171-182, May 2001, Ann Arbor, Michigan, United States [doi>10.1145/376957.376977]
• 32: METI S. Version 4. A software package for partitioning unstructured graphs by G. Karypis and V. Kumar. University of Minnesota.
• 33: Renato Pajarola , Jarek Rossignac, Compressed Progressive Meshes, IEEE Transactions on Visualization and Computer Graphics, v.6 n.1, p.79-93, January 2000 [doi>10.1109/2945.841122]
• 34: ROSSIGNAC, J., AND BORREL, P. 1993. Multi-resolution 3d approximation for rendering complex scenes. In Modeling in Computer Graphics, 455--465.
• 35: Jarek Rossignac, Edgebreaker: Connectivity Compression for Triangle Meshes, IEEE Transactions on Visualization and Computer Graphics, v.5 n.1, p.47-61, January 1999 [doi>10.1109/2945.764870]
• 36: SILVA, C., CHIANG, Y., EL-SANA, J., AND LINDSTROM, P. 2002. Out-of-core algorithms for scientific visualization and computer graphics. In Visualization'02, Course Notes, Tutorial 4.
• 37: Andrzej Szymczak , Jarek Rossignac , Davis King, Piecewise regular meshes: construction and compression, Graphical Models, v.64 n.3/4, p.183-198, May/July 2002 [doi>10.1006/gmod.2002.0577]
• 38: Gabriel Taubin , Jarek Rossignac, Geometric compression through topological surgery, ACM Transactions on Graphics (TOG), v.17 n.2, p.84-115, April 1998 [doi>10.1145/274363.274365]
• 39: Gabriel Taubin , André Guéziec , William Horn , Francis Lazarus, Progressive forest split compression, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.123-132, July 1998 [doi>10.1145/280814.280834]
• 40: TOUMA, C., AND GOTSMAN, C. 1998. Triangle mesh compression. In Graphics Interface'98 Conference Proceedings, 26--34.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

Keywords:
external memory data structures, mesh compression, out-of-core algorithms, processing sequences, streaming meshes