Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

3D Mesh Compression

  • Chapter
Three-Dimensional Model Analysis and Processing

Part of the book series: Advanced Topics in Science and Technology in China ((ATSTC,volume 0))

Abstract

3D meshes have been widely used in graphics and simulation applications for representing 3D objects. They generally require a huge amount of data for storage and/or transmission in the raw data format. Since most applications demand compact storage, fast transmission and efficient processing of 3D meshes, many algorithms have been proposed in the literature to compress 3D meshes efficiently since the early 1990s [1]. Because most of the 3D models in use are polygonal meshes, most of the published papers focus on coding that type of data, which is composed of two main components: connectivity data and geometry data. This chapter discusses 3D mesh compression technologies that have been developed over the last decade, with the main focus on triangle mesh compression technologies.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 129.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
USD 169.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. P. Alliez and C. Gotsman. Recent advances in compression of 3D meshes. In: Proceedings of the Symposium on Multiresolution in Geometric Modeling, 2003.

    Google Scholar 

  2. J. L. Peng, C. S. Kim and C. C. Jay Kuo. Technologies for 3D mesh compression: A survey. Journal of Visual Communication and Image Representation, 2005, 16(6):688–733.

    Article  Google Scholar 

  3. ISO/IEC 14772-1. The Virtual Reality Modeling Language VRML. 1997.

    Google Scholar 

  4. G. Taubin, W. Horn, F. Lazaru, et al. Geometry coding and VRML. Proceedings of the IEEE, 1998, 96(6):1228–1243.

    Article  Google Scholar 

  5. G. Taubin and J. Rossignac. Geometric compression through topological surgery. ACM Trans. Graph., 1998, 17(2):84–115.

    Article  Google Scholar 

  6. ISO/IEC 14496-2. Coding of Audio-Visual Objects: Visual. 2001.

    Google Scholar 

  7. O. Devillers and P. Gandoin. Geometric compression for interactive transmission. In: Proceedings of the IEEE Conference on Visualization, 2000, pp. 319–326.

    Google Scholar 

  8. G. Taubin. 3D geometry compression and progressive transmission. EUROGRAPHICS—State of the Art Report, 1999.

    Google Scholar 

  9. D. Shikhare. State of the art in geometry compression. Technical Report, National Centre for Software Technology, India, 2000.

    Google Scholar 

  10. C. Gotsman, S. Gumhold and L. Kobbelt. Simplification and compression of 3D meshes. Tutorials on Multiresolution in Geometric Modelling, 2002.

    Google Scholar 

  11. J. Gross and J. Yellen. Graph Theory and Its Applications. CRC Press, 1998.

    Google Scholar 

  12. M. Deering. Geometry compression. ACM SIGGRAPH, 1995, pp. 13–20.

    Google Scholar 

  13. M. Chow. Optimized geometry compression for real-time rendering. IEEE Visualization, 1997, pp. 347–354.

    Google Scholar 

  14. E. M. Arkin, M. Held, J. S. B. Mitchell, et al. Hamiltonian triangulations for fast rendering. Visual Computation, 1996, 12(9):429–444.

    Google Scholar 

  15. F. Evans, S. S. Skiena and A. Varshney. Optimizing triangle strips for fast rendering. IEEE Visualization, 1996, pp. 319–326.

    Google Scholar 

  16. G. Turan. On the succinct representations of graphs. Discr. Appl. Math, 1984, 8:289–294.

    Article  MATH  MathSciNet  Google Scholar 

  17. C. L. Bajaj, V. Pascucci and G. Zhuang. Single resolution compression of arbitrary triangular meshes with properties. Comput. Geom. Theor. Appl., 1999, 14:167–186.

    MATH  MathSciNet  Google Scholar 

  18. C. Bajaj, V. Pascucci and G. Zhuang. Compression and coding of large CAD models. Technical Report, University of Texas, 1998.

    Google Scholar 

  19. C. Touma and C. Gotsman. Triangle mesh compression. In: Proceedings of Graphics Interface, 1998, pp. 26–34.

    Google Scholar 

  20. P. Alliez and M. Desbrun. Valence-driven connectivity encoding for 3D meshes. EUROGRAPHICS, 2001, pp. 480–489.

    Google Scholar 

  21. M. Schindler. A fast renormalization for arithmetic coding. In: Proceedings of IEEE Data Compression Conference, 1998, p. 572.

    Google Scholar 

  22. W. Tutte. A census of planar triangulations. Can. J. Math., 1962, 14:21–38.

    Article  MATH  MathSciNet  Google Scholar 

  23. C. Gotsman. On the optimality of valence-based connectivity coding. Computer Graphics Forum, 2003, 22(1):99–102.

    Article  Google Scholar 

  24. S. Gumhold and W. Straßer. Real time compression of triangle mesh connectivity. ACM SIGGRAPH, 1998, pp. 133–140.

    Google Scholar 

  25. S. Gumhold. Improved cut-border machine for triangle mesh compression. Paper presented at The Erlangen Workshop’99 on Vision, Modeling and Visualization, 1999.

    Google Scholar 

  26. J. Rossignac. Edgebreaker: connectivity compression for triangle meshes. IEEE Trans. Vis. Comput. Graph., 1999, 5(1):47–61.

    Article  Google Scholar 

  27. D. King and J. Rossignac. Guaranteed 3.67v bit encoding of planar triangle graphs. Paper presented at The 11th Canadian Conference on Computational Geometry, 1999, pp. 146–149.

    Google Scholar 

  28. S. Gumhold. New bounds on the encoding of planar triangulations. Technical Report WSI-2000-1, Wilhelm-Schickard-Institut f ür Informatik, University of T übingen, Germany, 2000.

    Google Scholar 

  29. J. Rossignac and A. Szymczak. Wrap and zip decompression of the connectivity of triangle meshes compressed with edgebreaker. Comput. Geom., 1999, 14(1–3):119–135.

    Article  MATH  MathSciNet  Google Scholar 

  30. M. Isenburg and J. Snoeyink. Spirale reversi: reverse decoding of the Edgebreaker encoding. Paper presented at The 12th Canadian Conference on Computational Geometry, 2000, pp. 247–256.

    Google Scholar 

  31. A. Szymczak, D. King and J. Rossignac. An Edgebreaker-based efficient compression scheme for regular meshes. In: Proceedings of 12th Canadian Conference on Computational Geometry, 2000, pp. 257–264.

    Google Scholar 

  32. M. Isenburg. Triangle strip compression. In: Proceedings of the Graphics Interface, 2000, pp. 197–204.

    Google Scholar 

  33. B. S. Jong, W. H. Yang, J. L. Tseng, et al. An efficient connectivity compression for triangular meshes. In: Proceedings of the Fourth Annual ACIS International Conference on Computer and Information Science (ICIS’05), 2005.

    Google Scholar 

  34. A. Guéziec, G. Taubin, F. Lazarus, et al. Converting sets of polygons to manifold surfaces by cutting and stitching. IEEE Visualization, 1998, pp. 383–390.

    Google Scholar 

  35. H. Hoppe. Progressive meshes. ACM SIGGRAPH, 1996, pp. 99–108.

    Google Scholar 

  36. H. Hoppe, T. DeRose, T. Duchamp, et al. Mesh optimization. ACM SIGGRAPH, 1993, pp. 19–25.

    Google Scholar 

  37. H. Hoppe. Efficient implementation of progressive meshes. Comput. Graph, 1998, 22(1):27–36.

    Article  Google Scholar 

  38. J. Popovic and H. Hoppe. Progressive simplicial complexes. ACM SIGGRAPH, 1997, pp. 217–224.

    Google Scholar 

  39. G. Taubin, A. Gueziec, W. Horn, et al. Progressive forest split compression. ACM SIGGRAPH, 1998, pp. 123–132.

    Google Scholar 

  40. G. Taubin. A signal processing approach to fair surface design. ACM SIGGRAPH, 1995, pp. 351–358.

    Google Scholar 

  41. R. Pajarola and J. Rossignac. Compressed progressive meshes. IEEE Trans. Vis. Comput. Graph., 2000, 6(1):79–93.

    Article  Google Scholar 

  42. N. Dyn, D. Levin and J. A. Gregory. A butterfly subdivision scheme for surface interpolation with tension control. ACM Trans. Graph., 1990, 9(2):160–169.

    Article  MATH  Google Scholar 

  43. D. Zorin, P. Schröder and W. Sweldens. Interpolating subdivision for meshes with arbitrary topology. ACM SIGGRAPH, 1996, pp. 189–192.

    Google Scholar 

  44. R. Pajarola and J. Rossignac. Squeeze: fast and progressive decompression of triangle meshes. In: Proceedings of Computer Graphics International Conference, 2000, pp. 173–182.

    Google Scholar 

  45. R. Pajarola. Fast Huffman code processing. Technical Report UCI-ICS-99-43, Information and Computer Science, UCI, 1999.

    Google Scholar 

  46. W. J. Schroeder, J. A. Zarge and W. E. Lorensen. Decimation of triangle meshes. ACM SIGGRAPH, 1992, pp. 65–70.

    Google Scholar 

  47. M. Soucy and D. Laurendeau. Multiresolution surface modeling based on hierarchical triangulation. Comput. Vis. Image Understand., 1996, 63(1):1–14.

    Article  Google Scholar 

  48. D. Cohen-Or, D. Levin and O. Remez. Progressive compression of arbitrary triangular meshes. IEEE Visualization, 1999, pp. 67–72.

    Google Scholar 

  49. P. Alliez and M. Desbrun. Progressive encoding for lossless transmission of triangle meshes. ACM SIGGRAPH, 2001, pp. 198–205.

    Google Scholar 

  50. J. Li and C. C. J. Kuo. Progressive coding of 3-D graphic models. In: Proc. of the IEEE, 1998, 86(6):1052–1063.

    Article  Google Scholar 

  51. C. Bajaj, V. Pascucci and G. Zhuang. Progressive compression and transmission of arbitrary triangular meshes. IEEE Visualization, 1999, pp. 307–316.

    Google Scholar 

  52. C. L. Bajaj, E. J. Coyle and K. N. Lin. Arbitrary topology shape reconstruction from planar cross sections. Graph. Models Image Proc., 1996, 58(6):524–543.

    Article  Google Scholar 

  53. T. S. Gieng, B. Hamann, K. I. Joy, et al. Constructing hierarchies for triangle meshes. IEEE Trans. Vis. Comput. Graph., 1998, 4(2):145–161.

    Article  Google Scholar 

  54. A. Gersho and R. M. Gray. Vector Quantization and Signal Compression. Kluwer Academic Publishers, 1992.

    Google Scholar 

  55. H. Lee, P. Alliez and M. Desbrun. Angle-analyzer: a triangle-quad mesh codec. In: Eurographics Conference Proceedings, 2002, pp. 383–392.

    Google Scholar 

  56. M. Isenburg and P. Alliez. Compressing polygon mesh geometry with parallelogram prediction. In: IEEE Visualization Conference Proceedings, 2002, pp. 141–146.

    Google Scholar 

  57. B. Kronrod and C. Gotsman. Optimized compression of triangle mesh geometry using prediction trees. In: Proceedings of 1st International Symposium on 3D Data Processing, Visualization and Transmission, 2002, pp. 602–608.

    Google Scholar 

  58. R. Cohen, D. Cohen-Or and T. Ironi. Multi-way geometry encoding. Technical Report, 2002.

    Google Scholar 

  59. D. Shikhare, S. Bhakar and S. P. Mudur. Compression of large 3D engineering models using automatic discovery of repeating geometric features. In: Proceedings of 6th International Fall Workshop on Vision, Modeling and Visualization, 2001.

    Google Scholar 

  60. P. M. Gandoin and O. Devillers. Progressive lossless compression of arbitrary simplicial complexes. ACM Trans. Graph., 2002, 21(3):372–379.

    Article  Google Scholar 

  61. O. Devillers and P. Gandoin. Geometric compression for interactive transmission. IEEE Visualization, 2000, pp. 319–326.

    Google Scholar 

  62. I. H. Witten, R. M. Neal and J. G. Cleary. Arithmetic coding for data compression. Commun. ACM, 1987, 30(6):520–540.

    Article  Google Scholar 

  63. J. Peng and C. C. J. Kuo. Geometry-guided progressive lossless 3D mesh coding with octree (OT) decomposition. ACM Trans. Graph., 2005, 24(3):609–616.

    Article  Google Scholar 

  64. N. S. Jayant and P. Noll. Digital Coding of Waveforms—Principles and Applications to Speech and Video. Prentice Hall, 1984.

    Google Scholar 

  65. Z. Karni and C. Gotsman. Spectral compression of mesh geometry. ACM SIGGRAPH, 2000, pp. 279–286.

    Google Scholar 

  66. Z. Karni and C. Gotsman. 3D mesh compression using fixed spectral bases. In: Proceedings of the Graphics Interface, 2001, pp. 1–8.

    Google Scholar 

  67. O. Sorkine, D. Cohen-Or and S. Toldeo. High-pass quantization for mesh encoding. In: Proceedings of Eurographics Symposium on Geometry Processing, 2003.

    Google Scholar 

  68. M. Lounsbery, T. D. Derose and J. Warren. Multiresolution analysis for surfaces of arbitrary topological type. ACM Transactions on Graphics, 1997, 16(1):34–73.

    Article  Google Scholar 

  69. A. Khodakovsky, P. Schröder and W. Sweldens. Progressive geometry compression. ACM SIGGRAPH, 2000, pp. 271–278.

    Google Scholar 

  70. A. W. F. Lee, W. Sweldens, P. Schröd er, et al. MAPS: multiresolution adaptive parametrization of surfaces. ACM SIGGRAPH, 1998, pp. 95–104.

    Google Scholar 

  71. C. Loop. Smooth subdivision surfaces based on triangles. Master’s Thesis, Department of Mathematics, University of Utah, 1987.

    Google Scholar 

  72. A. Said and W. A. Pearlman. A new, fast and efficient image codec based on set partitioning in hierarchical trees. IEEE Trans. Circuits Syst. Video Technol., 1996, 6(3):243–250.

    Article  Google Scholar 

  73. A. Khodakovsky and I. Guskov. Normal mesh compression. Geometric Modeling for Scientific Visualization, Springer-Verlag, 2002.

    Google Scholar 

  74. I. Guskov, K. Vidimce, W. Sweldens, et al. Normal meshes. ACM SIGGRAPH, 2000, pp. 95–102.

    Google Scholar 

  75. F. Payan and M. Antonini. Multiresolution 3D mesh compression. Proceedings of IEEE International Conference in Image Processing, 2002, pp. 245–248.

    Google Scholar 

  76. C. Parisot, M. Antonini and M. Barlaud. Optimal nearly uniform scalar quantizer design for wavelet coding. In: Proc. of SPIE VCIP Conference, 2002.

    Google Scholar 

  77. C. Parisot, M. Antonini and M. Barlaud. Model-based bit allocation for JPEG 2000. In: Proc. of EUSIPCO, 2002.

    Google Scholar 

  78. R. Chen, X. Luo and H. Xu. Geometric compression of a quadrilateral mesh. Computers and Mathematics with Applications, 2008, 56:1597–1603.

    Article  MATH  MathSciNet  Google Scholar 

  79. X. Gu, S. J. Gortler and H. Hoppe. Geometry images. ACM SIGGRAPH, 2002, pp. 355–361.

    Google Scholar 

  80. P. Sander, S. Gortler, J. Snyder, et al. Signal-specialized parametrization. Technical Report MSR-TR-2002-27, Microsoft Research, 2002.

    Google Scholar 

  81. E. Praun and H. Hoppe. Spherical parametrization and remeshing. ACM Trans. Graph., 2003, 22(3):340–349.

    Article  Google Scholar 

  82. H. Hoppe and E. Praun. Shape compression using spherical geometry images. In: N. Dodgson, M. Floater, M. Sabin (Eds.), Advances in Multiresolution for Geometric Modelling, Springer-Verlag, 2005, pp. 27–46.

    Google Scholar 

  83. Y. Linde, A. Buzo and R. M. Gray. An algorithm for vector quantizer design. IEEE Trans. Commun., 1980, 28(1):84–95.

    Article  Google Scholar 

  84. E. S. Lee and H. S. Ko. Vertex data compression for triangular meshes. In: Proceedings of the 8th Pacific Conference on Computer Graphics and Applications, 2000, pp. 225–234.

    Google Scholar 

  85. P. H. Chou and T. H. Meng. Vertex data compression through vector quantization. IEEE Trans. Vis. Comput. Graph., 2002, 8(4):373–382.

    Article  Google Scholar 

  86. U. Bayazit, O. Orcay, U. Konurand, et al. Predictive vector quantization of 3-D mesh geometry by representation of vertices in local coordinate systems. Journal of Visual Communication & Image Representation, 2007, 18(4):341–353.

    Article  Google Scholar 

  87. R. P. Rao and W. A. Pearlman. Alphabet-and entropy-constrained vector quantization of image pyramids. Opt. Eng., 1991, 30:865–872.

    Article  Google Scholar 

  88. Z. M. Lu, J. S. Pan and S. H. Sun. Efficient codevector search algorithm based on Hadamard transform. Electronics Letters, 2000, 36(16):1364–1365.

    Article  Google Scholar 

  89. Z. Li and Z. M. Lu. Fast codevector search scheme for 3D mesh model vector quantization. IET Electronics Letters, 2008, 44(2):104–105.

    Article  Google Scholar 

  90. C. D. Bei and R. M. Gray. An improvement of the minimum distortion encoding algorithm for vector quantization. IEEE Trans. Commun., 1985, 33(10):1132–1133.

    Article  Google Scholar 

  91. L. Guan and M. Kamel. Equal-average hyperplane partitioning method for vector quantization of image data. Pattern Recognition Letters, 1992, 13(10):693–699.

    Article  Google Scholar 

  92. H. Lee and L. H. Chen. Fast closest codevector search algorithms for vector quantization. Signal Processing, 1995, 43:323–331.

    Article  Google Scholar 

  93. Z. M. Lu and Z. Li. Dynamically restricted codebook based vector quantization scheme for mesh geometry compression. Signal Image and Video Processing, 2008, 2(3):251–260.

    Article  MATH  Google Scholar 

  94. S. W. Ra and J. K. Kim. Fast mean-distance-ordered partial codebook search algorithm for image vector quantization. IEEE. Transactions on Circuits and Systems-II, 1993, 40(9):576–579.

    Article  Google Scholar 

  95. Z. Li, Z. M. Lu and L. Sun. Dynamic extended codebook based vector quantization scheme for mesh geometry compression. Paper presented at The IEEE Third International Conference on Intelligent Information Hiding and Multimedia Signal Processing (IIHMSP2007), 2007, Vol. 1, pp. 178–181.

    Article  Google Scholar 

  96. S. Valette and R. Prost. Wavelet-based progressive compression scheme for triangle meshes: Wavemesh. IEEE Transactions on Visualizations and Computer Graphics, 2004, 10(2):123–129.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Aeronautics and Astronautics, Zhejiang University, Hangzhou, 310027, China

    Associate Prof. Faxin Yu, Dr. Hao Luo & Prof. Zheming Lu

Authors
  1. Associate Prof. Faxin Yu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dr. Hao Luo
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Prof. Zheming Lu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Prof. Pinghui Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

Copyright information

© 2010 Zhejiang University Press, Hangzhou and Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Yu, F., Luo, H., Lu, Z., Wang, P. (2010). 3D Mesh Compression. In: Three-Dimensional Model Analysis and Processing. Advanced Topics in Science and Technology in China, vol 0. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12651-2_2

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-12651-2_2

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-12650-5

  • Online ISBN: 978-3-642-12651-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics