Connectivity compression for non-triangular meshes by context-based arithmetic coding

ABSTRACT

In this article, we present an efficient algorithm for encoding the connectivity information of general polygon meshes. The algorithm is a single-resolution lossless compression method for meshes, mainly for non-triangular meshes. In comparison with the excellent algorithms previously proposed for non-triangular meshes, the new method highly improves the compression ratio by using a novel entropy coding method. By the method, Huffman coder is first applied, then a context-based arithmetic coder is employed to encode the Huffman codes.The new method also puts forward a novel mesh traversing method by which the traversal to each polygon face could be in multiple times, though encoding each face is still only once. In this new method, "jump" operations are added to replacing "split" operations commonly used in various existing connectivity compression algorithms. Much of the decoding time and space could be saved by using the new traversing method through taking advantage of a decoding scheme that the operator code could be immediately discarded as soon as it is decoded. Therefore, the decoding method could be well applied to the applications with online transmission and decoding. In another word, our algorithm has an advantage of parallel encoding and decoding. The algorithm is also capable of handling the meshes with holes.

REFERENCES

• 1: Alliez, P., Desbrun, M. 2001. Valence-Driven Connectivity Encoding for 3D Meshes. Euro graphics '01, 480--489.
• 2: Alliez, P., Gotsman C. 2003. Recent Advances in Compression of 3D Meshes. Symposium on Multiresolution in Geometric Modeling.
• 3: 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]
• 4: 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]
• 5: Isenburg, M. 2000. Triangle Strip Compression. Proceedings of Graphics Interface 2000, 197--204.
• 6: Isenburg, M., Snoeyink, J. 2000. Spirale Reversi: Reverse Decoding of EdgeBreaker Encoding. Proceedings of 12th Canadian Conference on Computational Geometry, 247--256.
• 7: 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]
• 8: Jong B. S., Lin, T. W., Yang, W. H., Tseng, J. L. 2004. Improved Edge-Based Compression for the Connectivity of 3D Models. IEICE Transactions on information & system, Vol. E87-No. 12, Dec. 2845--2854.
• 9: Bin-Shyan Jong , Wen-Hao Yang , Juin-Ling Tseng , Tsong-Wuu Lin, An Efficient Connectivity Compression for Triangular Meshes, Proceedings of the Fourth Annual ACIS International Conference on Computer and Information Science (ICIS'05), p.583-588, July 14-16, 2005 [doi>10.1109/ICIS.2005.29]
• 10: Andrei Khodakovsky , Pierre Alliez , Mathieu Desbrun , Peter Schröder, Near-optimal connectivity encoding of 2-manifold polygon meshes, Graphical Models, v.64 n.3/4, p.147-168, May/July 2002 [doi>10.1006/gmod.2002.0575]
• 11: Boris Kronrod , Craig Gotsman, Efficient coding of nontriangular mesh connectivity, Graphical Models, v.63 n.4, p.263-275, July 2001 [doi>10.1006/gmod.2001.0555]
• 12: Lee, H., Alliez, P., Desbrun M. 2002. Angle-Analyzer: a Triangle-Quad Mesh Codec. Eurographics'02 Conference Proceedings. 383--392.
• 13: Li, J., Kuo, C. C. 1998. A dual graph approach to 3D triangular mesh compression. Proceedings of the IEEE Inter-national Conference on Image Processing, Chicago, 1998.
• 14: Peng, J. L., Kuo, J. C. C. 2005. Technologies for 3D Mesh Compression: A Survey. Proceedings of ACM SIGGRAPH 2005, 609--616.
• 15: 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]
• 16: 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]
• 17: Rossigngac, J., Lopes, H., Safanova, A., Tavares, G., Szymczak, A. 2003. Edgebreaker: A Simple Compression for Surface with Handles. Computers & Graphics International Journal, Vol. 27, No.4, 553--567.
• 18: Szymczak, D., King, D., Rossignac, J. 2000. An EdgeBreaker Based Efficient Compression Scheme for Regular Meshes. Proceedings of 12th Canadian Conference on Computational Geometry, 53--68.
• 19: Taubin, G., Horn, W., Lazarus, F., Rossignac, J. 1998. Geometry Coding and VRML. Proceedings of the IEEE, 86(6), 1228--1243.
• 20: Touma, C., Gotsman, C. 1998. Triangle Mesh Compression. Proceedings of Graphics Interface 98, 26--34.
• 21: Wheeler, F. 1996. Adaptive Arithmetic Coding Source Code. http://www.cipr.rpi.edu/wheeler/ac

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques

Keywords:
connectivity compression, context-based arithmetic coder, decode, encode, meshes