Spectral compression of mesh geometry

ABSTRACT

We show how spectral methods may be applied to 3D mesh data to obtain compact representations. This is achieved by projecting the mesh geometry onto an orthonormal basis derived from the mesh topology. To reduce complexity, the mesh is partitioned into a number of balanced submeshes with minimal interaction, each of which are compressed independently. Our methods may be used for compression and progressive transmission of 3D content, and are shown to be vastly superior to existing methods using spatial techniques, if slight loss can be tolerated.

REFERENCES

• 1: 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
• 2: N. Biggs. Alegbraic Graph Theory (2nd Ed.). Cambridge University Press, 1993.
• 3: Mike M. Chow, Optimized geometry compression for real-time rendering, Proceedings of the 8th conference on Visualization '97, p.347-ff., October 18-24, 1997, Phoenix, Arizona, United States
• 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: 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]
• 6: 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]
• 7: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 8: 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]
• 9: 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]
• 10: Martin Isenburg , Jack Snoeyink, Mesh Collapse Compression, Proceedings of the XII Brazilian Symposium on Computer Graphics and Image Processing, p.27-28, October 17-20, 1999
• 11: 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]
• 12: 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]
• 13: D. King and J. Rossignac. Guaranteed 3.67v bit encoding of planar triangle graphs. In Proceedings of 1 lth Canadian Conference on Computation Geometry, pp.146-149, 1999.
• 14: G. Karypis and V. Kumar. MeTiS: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices. Version 4.0, Univ. of Minnesota, Dept. of Computer Science, 1998. Available at http://wwwusers.cs.umn.edu/Nkarypis/metis/metis.html
• 15: Leif Kobbelt , Swen Campagna , Jens Vorsatz , Hans-Peter Seidel, Interactive multi-resolution modeling on arbitrary meshes, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.105-114, July 1998 [doi>10.1145/280814.280831]
• 16: P. Lancaster and M. Tismenetsky. The theory of matrices. (2nd Ed.), Academic Press, 1985.
• 17: J. Li and C.-C. Kuo, A dual graph approach to 3D triangular mesh compression, In Proceedings of the IEEE International Conference on Image Processing, Chicago, 1998.
• 18: 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]
• 19: David Salomon, Data compression: the complete reference, Springer-Verlag New York, Inc., New York, NY, 1997
• 20: Gabriel Taubin, A signal processing approach to fair surface design, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.351-358, September 1995 [doi>10.1145/218380.218473]
• 21: 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]
• 22: C. Touma and C. Gotsman. Triangle mesh compression. In Proceedings of Graphics Interface '98, pp. 26-34, 1998.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

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

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
  I.4 IMAGE PROCESSING AND COMPUTER VISION
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Signal processing

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

Keywords:
compression algorithms, signal processing