Geometric compression through topological surgery

ABSTRACT

The abundance and importance of complex 3-D data bases in major industry segments, the affordability of interactive 3-D rendering for office and consumer use, and the exploitation of the Internet to distribute and share 3-D data have intensified the need for an effective 3-D geometric compression technique that would significantly reduce the time required to transmit 3-D models over digital communication channels, and the amount of memory or disk space required to store the models. Because the prevalent representation of 3-D models for graphics purposes is polyhedral and because polyhedral models are in general triangulated for rendering, this article introduces a new compressed representation for complex triangulated models and simple, yet efficient, compression and decompression algorithms. In this scheme, vertex positions are quantized within the desired accuracy, a vertex spanning tree is used to predict the position of each vertex from 2,3, or 4 of its ancestors in the tree, and the correction vectors are entropy encoded. Properties, such as normals, colors, and texture coordinates, are compressed in a similar manner. The connectivity is encoded with no loss of information to an average of less than two bits per triangle. The vertex spanning tree and a small set of jump edges are used to split the model into a simple polygon. A triangle spanning tree and a sequence of marching bits are used to encode the triangulation of the polygon. Our approach improves on Michael Deering's pioneering results by exploiting the geometric coherence of several ancestors in the vertex spanning tree, preserving the connectivity with no loss of information, avoiding vertex repetitions, and using about three fewer bits for the connectivity. However, since decompression requires random access to all vertices, this method must be modified for hardware rendering with limited onboard memory. Finally, we demonstrate implementation results for a variety of VRML models with up to two orders of magnitude compression.

REFERENCES

• 1: Esther M. Arkin , Martin Held , Joseph S. B. Mitchell , Steven Skiena, Hamilton Triangulations for Fast Rendering, Proceedings of the Second Annual European Symposium on Algorithms, p.36-47, September 26-28, 1994
• 2: BORREL, P., CHENG, K. S., DARMON, P., KIRCHNER, P., LIPSCOMB, J., MENON, J., MITTLEMAN, J., ROSSIGNAC, g., SCHNEIDER, B. O., AND WOLFE, B. 1995. The IBM 3D interaction accelerator (3DIX). Tech. Rep. RC 20302, IBM Research.
• 3: CAREY, R., BELL, G., AND MARRIN, C. 1997. The virtual reality modeling language. Tech. Rep. ISO/IEC DIS 14772-1, April. Available at http://www.vrml, org/Specifications/ VRML97/DIS.
• 4: 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]
• 5: Matthias Eck , Tony DeRose , Tom Duchamp , Hugues Hoppe , Michael Lounsbery , Werner Stuetzle, Multiresolution analysis of arbitrary meshes, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.173-182, September 1995 [doi>10.1145/218380.218440]
• 6: Thomas A. Funkhouser , Carlo H. Séquin, Adaptive display algorithm for interactive frame rates during visualization of complex virtual environments, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.247-254, September 1993 [doi>10.1145/166117.166149]
• 7: GUEZIEC, A. 1995. Surface simplification with variable tolerance. In Second Annual International Symposium on Medical Robotics and Computer Assisted Surgery (Baltimore, MD, Nov.).
• 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: Hugues Hoppe , Tony DeRose , Tom Duchamp , John McDonald , Werner Stuetzle, Surface reconstruction from unorganized points, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.71-78, July 1992
• 10: Hugues Hoppe , Tony DeRose , Tom Duchamp , John McDonald , Werner Stuetzle, Mesh optimization, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.19-26, September 1993 [doi>10.1145/166117.166119]
• 11: Alan D. Kalvin , Russell H. Taylor, Superfaces: Polygonal Mesh Simplification with Bounded Error, IEEE Computer Graphics and Applications, v.16 n.3, p.64-77, May 1996 [doi>10.1109/38.491187]
• 12: Donald E. Knuth, The Art of Computer Programming Volumes 1-3 Boxed Set, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 13: MASSEY, W. S. 1967. Algebraic Topology, An Introduction. Harcourt, Brace & World, Orlando, FL.
• 14: NEIDER, J., DAVIS, T., AND Woo, M. 1993. OpenGL Programming Guide. Addison-Wesley, Reading, MA.
• 15: William B. Pennebaker , Joan L. Mitchell, JPEG Still Image Data Compression Standard, Kluwer Academic Publishers, Norwell, MA, 1992
• 16: RONFARD, R. AND ROSSIGNAC, J. 1994. Triangulating multiply-connected polygons: A simple, yet efficient algorithm. In Proceedings of Eurographics '94 Computer Graphics Forum, (Oslo, Norway).
• 17: ROSSIGNAC, J. AND BORREL, P. 1993. Geometric Modeling in Computer Graphics. Springer Verlag, 455-465.
• 18: William J. Schroeder , Jonathan A. Zarge , William E. Lorensen, Decimation of triangle meshes, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.65-70, July 1992
• 19: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 20: Gabriel Taubin, A signal processing approach to fair surface design, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.351-358, September 1995 [doi>10.1145/218380.218473]
• 21: G. Taubin, Curve and surface smoothing without shrinkage, Proceedings of the Fifth International Conference on Computer Vision, p.852, June 20-23, 1995
• 22: TAUBIN, G., HORN, W. P., AND LAZARUS, F. 1997. The VRML compressed binary format proposal, June. Available at http ://www. research, ibm. com/vrml/binary.
• 23: TAUBIN, G., HORN, W. P., LAZARUS, F., AND ROSSIGNAC, J. 1998. Geometric coding and VRML. Proc. IEEE 86, 7 (Special issue on multimedia signal processing).
• 24: Gabriel Taubin , Tong Zhang , Gene H. Golub, Optimal Surface Smoothing as Filter Design, Proceedings of the 4th European Conference on Computer Vision-Volume I, p.283-292, April 15-18, 1996

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Algorithms, Standardization

Keywords:
3D mesh compression, VRML, geometry compression