Geometry-guided progressive lossless 3D mesh coding with octree (OT) decomposition

ABSTRACT

A new progressive lossless 3D triangular mesh encoder is proposed in this work, which can encode any 3D triangular mesh with an arbitrary topological structure. Given a mesh, the quantized 3D vertices are first partitioned into an octree (OT) structure, which is then traversed from the root and gradually to the leaves. During the traversal, each 3D cell in the tree front is subdivided into eight childcells. For each cell subdivision, both local geometry and connectivity changes are encoded, where the connectivity coding is guided by the geometry coding. Furthermore, prioritized cell subdivision is performed in the tree front to provide better rate-distortion (RD) performance. Experiments show that the proposed mesh coder outperforms the kd-tree algorithm in both geometry and connectivity coding efficiency. For the geometry coding part, the range of improvement is typically around 10%~20%, but may go up to 50%~60% for meshes with highly regular geometry data and/or tight clustering of vertices.

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, 480--489.
• 3: Alliez, P., and Gotsman, C. 2003. Recent advance in compression of 3d meshes. In Proceedings of the Symposium on Multiresolution in Geometric Modeling.
• 4: Marco Attene , Bianca Falcidieno , Michela Spagnuolo , Jarek Rossignac, SwingWrapper: Retiling triangle meshes for better edgebreaker compression, ACM Transactions on Graphics (TOG), v.22 n.4, p.982-996, October 2003 [doi>10.1145/944020.944022]
• 5: 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
• 6: Bajaj, C. L., Pascucci, V., and Zhuang, G. 1999. Single resolution compression of arbitrary triangular meshes with properties. Computational Geometry: Theory and Applications 14, 167--186.
• 7: Mario Botsch , Andreas Wiratanaya , Leif Kobbelt, Efficient high quality rendering of point sampled geometry, Proceedings of the 13th Eurographics workshop on Rendering, June 26-28, 2002, Pisa, Italy
• 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: Volker Coors , Jarek Rossignac, Delphi: geometry-based connectivity prediction in triangle mesh compression, The Visual Computer: International Journal of Computer Graphics, v.20 n.8-9, p.507-520, November 2004 [doi>10.1007/s00371-004-0255-1]
• 10: Olivier Devillers , Pierre-Marie Gandoin, Geometric compression for interactive transmission, Proceedings of the conference on Visualization '00, p.319-326, October 2000, Salt Lake City, Utah, United States
• 11: Pierre-Marie Gandoin , Olivier Devillers, Progressive lossless compression of arbitrary simplicial complexes, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 12: Gotsman, C., Gumhold, S., and Kobbelt, L. 2002. Simplification and compression of 3D meshes. In Tutorials on Multiresolution in Geometric Modelling.
• 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: Hugues Hoppe, Progressive meshes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.99-108, August 1996 [doi>10.1145/237170.237216]
• 15: 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]
• 16: Khodakovsky, A., and Guskov, I. 2000. Normal mesh compression. Preprint.
• 17: 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]
• 18: Laney, D., Bertram, M., Duchaineau, M., and Max, N. 2002. Multiresolution distance volumes for progressive surface compression. In Proceedings of the First International Symposium on 3D Data Processing, Visualization, and Transmission, 470--479.
• 19: Lee, H., Desbrun, M., and Schröder, P. 2003. Progressive encoding of complex isosurfaces. In ACM SIGGRAPH.
• 20: Li, J., and Kuo, C.-C. J. 1998. Progressive coding of 3-D graphic models. Proceedings of the IEEE 86, 6 (Jun), 1052--1063.
• 21: 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]
• 22: Peng, J., Kim, C.-S., and Kuo, C.-C. J. Technologies For 3D mesh compression: A survey, to appear in Journal of Visual Communication and Image Representation.
• 23: Jovan Popović , Hugues Hoppe, Progressive simplicial complexes, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.217-224, August 1997 [doi>10.1145/258734.258852]
• 24: Rossignac, J., and Borrel, P. 1993. Geometric Modeling in Computer Graphics. Springer-Verlag, Jul.
• 25: 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]
• 26: Dietmar Saupe , Jens-Peer Kuska, Compression of Isosurfaces, Proceedings of the Vision Modeling and Visualization Conference 2001, p.333-340, November 21-23, 2001
• 27: Dieter Schmalstieg , Gernot Schaufler, Smooth Levels of Detail, Proceedings of the 1997 Virtual Reality Annual International Symposium (VRAIS '97), p.12, March 01-05, 1997
• 28: 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]
• 29: 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]
• 30: 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]
• 31: Touma, C., and Gotsman, C. 1998. Triangle mesh compression. In Proceedings of Graphics Interface, 26--34.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.6 Segmentation
          Subjects: Region growing, partitioning

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.6 Segmentation
          Subjects: Pixel classification

General Terms:
Algorithms, Experimentation, Performance

Keywords:
3D geometry compression, mesh compression, non-manifold mesh, progressive lossless coding, triangle soup