Face fixer: compressing polygon meshes with properties

ABSTRACT

Most schemes to compress the topology of a surface mesh have been developed for the lowest common denominator: triangulated meshes. We propose a scheme that handles the topology of arbitrary polygon meshes. It encodes meshes directly in their polygonal representation and extends to capture face groupings in a natural way. Avoiding the triangulation step we reduce the storage costs for typical polygon models that have group structures and property data.

REFERENCES

• 1: 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
• 2: 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
• 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: M. Denny and C. Sohler. Encoding a triangulation as a permutation of its point set. In Proc. of 9th Canadian Conf. on Comp. Geom., pages 39-43, 1997.
• 5: Francine Evans , Steven Skiena , Amitabh Varshney, Optimizing triangle strips for fast rendering, Proceedings of the 7th conference on Visualization '96, p.319-326, October 28-29, 1996, San Francisco, California, United States
• 6: Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
• 7: 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]
• 8: 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]
• 9: 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
• 10: Martin Isenburg , Jack Snoeyink, Spirale Reversi: Reverse decoding of the Edgebreaker encoding, University of British Columbia, Vancouver, BC, Canada, 1999
• 11: Kenneth Keeler , Jeffery Westbrook, Short encodings of planar graphs and maps, Discrete Applied Mathematics, v.58 n.3, p.239-252, April 7, 1995 [doi>10.1016/0166-218X(93)E0150-W]
• 12: D. King and J. Rossignac. Guaranteed 3.67v bit encoding of planar triangle graphs. In Proc. of 11th Canadian Conf. on Comp. Geom., pages 146-149,1999.
• 13: D. King, J. Rossignac, and A. Szymczak. Connectivity compression for irregular quadrilateral meshes. Technical Report TR-99-36,GVU, Georgia Tech, 1999.
• 14: D. G. Kirkpatrick. Optimal search in planar subdivisions. SIAMJournal of Com-puting, 12(1):28-35, 1983.
• 15: B. Kronrod and C. Gotsman. Efficient coding of non-triangular meshes. In Proc. of 16th Europ. Workshop on Computational Geometry, pages 24-26, 2000.
• 16: J. Li, C. C. Kuo, and H. Chen. Mesh connectivity coding by dual graph approach. Contribution Document MPEG98/m3530Tokyo, mar 1998.
• 17: R. Parajola and Rossignac. Compressed progressive meshes. Technical Report TR-99-05, GVU, Georgia Tech, 1999.
• 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: J. Rossignac and A. Szymczak. Wrap&zip: Linear decoding of planar triangle graphs. The Journal of ComputationalGeometry, Theory and Applications, 1999.
• 20: Jack Snoeyink , Marc J. van Kreveld, Linear-Time Reconstruction of Delaunay Triangulations with Applications, Proceedings of the 5th Annual European Symposium on Algorithms, p.459-471, September 15-17, 1997
• 21: D. M. Y. Sommerville. An Introductionto the Geometry of N Dimensions. Dutton Publications, New York, 1929.
• 22: 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]
• 23: G. Taubin, W.P. Horn, F. Lazarus, and J. Rossignac. Geometry coding and VRML. Proceedings of the IEEE, 86(6):1228-1243, 1998.
• 24: 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]
• 25: C. Touma and C. Gotsman. Triangle mesh compression. In Graphics Interface 98 Conference Proceedings, pages 26-34, 1998.
• 26: G. Turan. Succinct representations of graphs. Dis. Apl. Math., 8:289-294, 1984.
• 27: W.T. Tutte. A census of planar triangulations. Cnd. Jrn. Math., 14:21-38, 1962.
• 28: Viewpoint. Premier Catalog (2000 Edition) www.viewpoint.com.
• 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]
• 30: M. Woo, J. Neider, and T. Davis. Open GL Programming Guide. A.W., 1996.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations
  I.4 IMAGE PROCESSING AND COMPUTER VISION

General Terms:
Design, Measurement, Performance, Theory

Keywords:
connectivity encoding, mesh compression