Progressive compression for lossless transmission of triangle meshes

ABSTRACT

Lossless transmission of 3D meshes is a very challenging and timely problem for many applications, ranging from collaborative design to engineering. Additionally, frequent delays in transmissions call for progressive transmission in order for the end user to receive useful successive refinements of the final mesh. In this paper, we present a novel, fully progressive encoding approach for lossless transmission of triangle meshes with a very fine granularity. A new valence-driven decimating conquest, combined with patch tiling and an original strategic retriangulation is used to maintain the regularity of valence. We demonstrate that this technique leads to good mesh quality, near-optimal connectivity encoding, and therefore a good rate-distortion ratio throughout the transmission. We also improve upon previous lossless geometry encoding by decorrelating the normal and tangential components of the surface. For typical meshes, our method compresses connectivity down to less than 3.7 bits per vertex, 40% better in average than the best methods previously reported [5, 18]; we further reduce the usual geometry bit rates by 20% in average by exploiting the smoothness of meshes. Concretely, our technique can reduce an ascii VRML 3D model down to 1.7% of its size for a 10-bit quantization (2.3% for a 12-bit quantization) while providing a very progressive reconstruction.

REFERENCES

• 1: P. Alliez and M. Desbrun. Valence-Driven Connectivity Encoding of 3D Meshes. In Eurographics Conference Proceedings, 2001.
• 2: 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]
• 3: Jean-Daniel Boissonnat , Frédéric Cazals, Smooth surface reconstruction via natural neighbour interpolation of distance functions, Proceedings of the sixteenth annual symposium on Computational geometry, p.223-232, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336208]
• 4: P. Cignoni, C. Rocchini, and R. Scopigno. Metro: Measuring Error on Simplified Surfaces. Computer Graphics Forum, 17(2):167-174, 1998.
• 5: 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
• 6: 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]
• 7: M. Denny and C. Sohler. Encoding a Triangulation as a Permutation of its Point Set. 9th Canadian Conference on Computational Geometry, pages 39-43, 1997.
• 8: 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
• 9: Michael Garland , Paul S. Heckbert, Simplifying surfaces with color and texture using quadric error metrics, Proceedings of the conference on Visualization '98, p.263-269, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 10: 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]
• 11: 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]
• 12: Hugues Hoppe, New quadric metric for simplifiying meshes with appearance attributes, Proceedings of the conference on Visualization '99: celebrating ten years, p.59-66, October 1999, San Francisco, California, United States
• 13: 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]
• 14: D. King and J. Rossignac. Guaranteed 3.67v bit Encoding of Planar Triangle Graphs. In Proceedings of the 11th Canadian Conference on Computational Geometry, pages 146-149, 1999.
• 15: Davis King , Jarek Rossignac, Optimal bit allocation in compressed 3D models, Computational Geometry: Theory and Applications, v.14 n.1-3, p.91-118, Nov. 1999 [doi>10.1016/S0925-7721(99)00025-5]
• 16: Leif Kobbelt, √3-subdivision, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.103-112, July 2000 [doi>10.1145/344779.344835]
• 17: Peter Lindstrom , Greg Turk, Fast and memory efficient polygonal simplification, Proceedings of the conference on Visualization '98, p.279-286, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 18: 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]
• 19: Renato B. Pajarola , Jarek Rossignac, SQUEEZE: Fast and Progressive Decompression of Triangle Meshes, Proceedings of the International Conference on Computer Graphics, p.173, June 19-24, 2000
• 20: 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]
• 21: Jarek Rossignac , Andrzej Szymczak, WRAP&Zip decompression of the connectivity of triangle meshes compressed with edgebreaker, Computational Geometry: Theory and Applications, v.14 n.1-3, p.119-135, Nov. 1999 [doi>10.1016/S0925-7721(99)00028-0]
• 22: M. Schindler, A Fast Renormalisation for Arithmetic Coding, Proceedings of the Conference on Data Compression, p.572, March 30-April 01, 1998
• 23: Jack Snoeyink , Marc van Kreveld, Good orders for incremental (re)construction, Proceedings of the thirteenth annual symposium on Computational geometry, p.400-402, June 04-06, 1997, Nice, France [doi>10.1145/262839.263025]
• 24: Andrzej Szymczak , Davis King , Jarek Rossignac, An edgebreaker-based efficient compression scheme for regular meshes, Computational Geometry: Theory and Applications, v.20 n.1-2, p.53-68, October 2001 [doi>10.1016/S0925-7721(01)00035-9]
• 25: 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]
• 26: G. Taubin, W. Horn, J. Rossignac, and F. Lazarus. Geometry Coding and VRML. In Proceedings of the IEEE, Special issue on Multimedia Signal Processing, volume 86(6), pages 1228-1243, june 1998.
• 27: G. Taubin and J. Rossignac. 3D Geometry Compression, 1999-2000. ACM SIGGRAPH Conference course notes.
• 28: C. Touma and C. Gotsman. Triangle Mesh Compression. In Graphics Interface 98 Conference Proceedings, pages 26-34, 1998.
• 29: Ian H. Witten , Radford M. Neal , John G. Cleary, Arithmetic coding for data compression, Communications of the ACM, v.30 n.6, p.520-540, June 1987 [doi>10.1145/214762.214771]

INDEX TERMS

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

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

General Terms:
Algorithms, Design, Performance

Keywords:
connectivity encoding, geometry encoding, levels of details, mesh decimation, progressive transmission, triangle mesh compression