Progressive geometry compression

ABSTRACT

We propose a new progressive compression scheme for arbitrary topology, highly detailed and densely sampled meshes arising from geometry scanning. We observe that meshes consist of three distinct components: geometry, parameter, and connectivity information. The latter two do not contribute to the reduction of error in a compression setting. Using semi-regular meshes, parameter and connectivity information can be virtually eliminated. Coupled with semi-regular wavelet transforms, zerotree coding, and subdivision based reconstruction we see improvements in error by a factor four (12dB) compared to other progressive coding schemes.

REFERENCES

• 1: Chandrajit L. Bajaj , Valerio Pascucci , Guozhong Zhuang, Progressive compressive and transmission of arbitrary triangular meshes, Proceedings of the conference on Visualization '99: celebrating ten years, p.307-316, October 1999, San Francisco, California, United States
• 2: Andrew Certain , Jovan Popovic , Tony DeRose , Tom Duchamp , David Salesin , Werner Stuetzle, Interactive multiresolution surface viewing, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.91-98, August 1996 [doi>10.1145/237170.237213]
• 3: [3] CIGNONI, P., ROCCHINI, C., AND SCOPIGNO, R. Metro: Measuring Error on Simplified Surfaces. Computer Graphics Forum 17, 2 (1998), 167-174.
• 4: 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
• 5: Geoffrey M. Davis , Sumit Chawla, Image Coding Using Optimized Significance Tree Quantization, Proceedings of the Conference on Data Compression, p.387, March 25-27, 1997
• 6: [6] DAVIS, G., AND NOSRATINIA, A. Wavelet-based Image Coding: An Overview. Applied Computational Control, Signals, and Circuits 1, 1 (1998).
• 7: Mathieu Desbrun , Mark Meyer , Peter Schröder , Alan H. Barr, Implicit fairing of irregular meshes using diffusion and curvature flow, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.317-324, July 1999 [doi>10.1145/311535.311576]
• 8: Ronald A. DeVore , Björn Jawerth , Bradley J. Lucier, Surface compression, Computer Aided Geometric Design, v.9 n.3, p.219-239, Aug. 1992 [doi>10.1016/0167-8396(92)90019-L]
• 9: Nira Dyn , David Levine , John A. Gregory, A butterfly subdivision scheme for surface interpolation with tension control, ACM Transactions on Graphics (TOG), v.9 n.2, p.160-169, April 1990 [doi>10.1145/78956.78958]
• 10: Matthias Eck , Tony DeRose , Tom Duchamp , Hugues Hoppe , Michael Lounsbery , Werner Stuetzle, Multiresolution analysis of arbitrary meshes, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.173-182, September 1995 [doi>10.1145/218380.218440]
• 11: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 12: Markus H. Gross , Oliver G. Staadt , Roger Gatti, Efficient Triangular Surface Approximations Using Wavelets and Quadtree Data Structures, IEEE Transactions on Visualization and Computer Graphics, v.2 n.2, p.130-143, June 1996 [doi>10.1109/2945.506225]
• 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: Igor Guskov , Wim Sweldens , Peter Schröder, Multiresolution signal processing for meshes, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.325-334, July 1999 [doi>10.1145/311535.311577]
• 15: Igor Guskov , Kiril Vidimče , Wim Sweldens , Peter Schröder, Normal meshes, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.95-102, July 2000 [doi>10.1145/344779.344831]
• 16: [16] HOPPE, H. Efficient Implementation of Progressive Meshes. Computers & Graphics 22, 1 (1998), 27-36.
• 17: [17] KING, D., AND ROSSIGNAC, J. Optimal Bit Allocation in 3D Compression. Tech. Rep. GIT-GVU-99-07, Georgia Institute of Technology, 1999.
• 18: [18] KOBBELT, L., VORSATZ, J., LABSIK, U., AND SEIDEL, H.-P. A Shrink Wrapping Approach to Remeshing Polygonal Surfaces. Computer Graphics Forum 18 (1999), 119-130.
• 19: Krasimir Kolarov , William Lynch, Compression of functions defined on surfaces of 3D objects, Proceedings of the Conference on Data Compression, p.281, March 25-27, 1997
• 20: Venkat Krishnamurthy , Marc Levoy, Fitting smooth surfaces to dense polygon meshes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.313-324, August 1996 [doi>10.1145/237170.237270]
• 21: Aaron W. F. Lee , Wim Sweldens , Peter Schröder , Lawrence Cowsar , David Dobkin, MAPS: multiresolution adaptive parameterization of surfaces, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.95-104, July 1998 [doi>10.1145/280814.280828]
• 22: [22] LEVOY, M. The Digital Michelangelo Project. In Proceedings of the 2nd International Conference on 3D Digital Imaging and Modeling, October 1999.
• 23: [23] LI, J., AND KUO, C. Progressive Coding of 3-D Graphic Models. Proceedings of the IEEE 86, 6 (1998), 1052-1063.
• 24: [24] LOOP, C. Smooth Subdivision Surfaces Based on Triangles. Master's thesis, University of Utah, Department of Mathematics, 1987.
• 25: Michael Lounsbery , Tony D. DeRose , Joe Warren, Multiresolution analysis for surfaces of arbitrary topological type, ACM Transactions on Graphics (TOG), v.16 n.1, p.34-73, Jan. 1997 [doi>10.1145/237748.237750]
• 26: [26] PAJAROLA, R., AND ROSSIGNAC, J. Compressed Progressive Meshes. Tech. Rep. GIT-GVU-99-05, Georgia Institute of Technology, 1999.
• 27: Sherman D. Riemenschneider , Zuowei Shen, Wavelets and pre-wavelets in low dimensions, Journal of Approximation Theory, v.71 n.1, p.18-38, Oct. 1992 [doi>10.1016/0021-9045(92)90129-C]
• 28: 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]
• 29: [29] ROSSIGNAC, J., AND SZYMCZAK, A. Wrap&Zip: Linear Decoding of Planar Triangle Graphs. Tech. Rep. GIT-GVU-99-08, Georgia Institute of Technology, 1999.
• 30: [30] SAID, A., AND PEARLMAN, W. A New, Fast, and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees. IEEE Transaction on Circuits and Systems for Video Technology 6, 3 (1996), 243-250.
• 31: Peter Schröder , Wim Sweldens, Spherical wavelets: efficiently representing functions on the sphere, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.161-172, September 1995 [doi>10.1145/218380.218439]
• 32: [32] SHAPIRO, J. Embedded Image-Coding using Zerotrees of Wavelet Coefficients. IEEE Transactions on Signal Processing 41, 12 (1993), 3445-3462.
• 33: Oliver G. Staadt , Markus H. Gross , Roger Weber, Multiresolution compression and reconstruction, Proceedings of the 8th conference on Visualization '97, p.337-ff., October 18-24, 1997, Phoenix, Arizona, United States
• 34: 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]
• 35: 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]
• 36: [36] TAUBIN, G., AND ROSSIGNAC, J., Eds. 3D Geometry Compression. No. 21 in Course Notes. ACM Siggraph, 1999.
• 37: [37] TOUMA, C., AND GOTSMAN, C. Triangle Mesh Compression. Graphics Interface '98 (1998), 26-34.
• 38: Denis Zorin , Peter Schröder , Wim Sweldens, Interpolating Subdivision for meshes with arbitrary topology, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.189-192, August 1996 [doi>10.1145/237170.237254]
• 39: Denis Zorin , Peter Schröder , Wim Sweldens, Interactive multiresolution mesh editing, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.259-268, August 1997 [doi>10.1145/258734.258863]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Signal processing systems

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Approximation of surfaces and contours; Wavelets and fractals

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.2 Compression (Coding)
          Subjects: Approximate methods
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Signal processing

General Terms:
Algorithms, Design, Measurement, Performance, Theory

Keywords:
compression algorithms, hierarchical representations, semi-regular meshes, signal processing, subdivision surfaces, wavelets, zerotree coding