Compression techniques for distributed use of 3D data: an emerging media type on the internet

ABSTRACT

3D data is being processed in a number of application domains such as, engineering design, manufacture, architecture, bio-informatics, medicine, entertainment, commerce, science, defense, heritage, etc. The volume of 3D data that is being circulated on the Internet is increasing very rapidly. Adding to this trend further are new developments like availability of inexpensive 3D scanners and 3D graphics accelerators, sophisticated 3D gaming devices, and increasing use of 3D imaging in distributed collaborative work in virtually all domains like engineering, scientific research, education, entertainment, commerce, etc. Clearly like text, images, audio and video, 3D data is emerging as yet another media type that has to be processed and visualized. Transmission issues concerning 3D data are instrumental for the distributed use of 3D information. In this paper we identify the major requirements for remote interactive access to locationally distributed 3D data, and then briefly describe two new compressed 3D data transmission techniques, developed by the authors. The first technique is for triangulated models representing individual, complex 3D sculptured objects, while the second is for large architectural and engineering class of models, typically large assemblies of a few types of components. Both techniques have the properties of high compaction ratios, fast decompression and low decompression latency, making them very well suited for rapid distribution and retrieval of 3D data on the Internet.

REFERENCES

• 1: {1} P. Alliez and M. Desbrun. Valence-driven connectivity encoding of 3D meshes. In Eurographics 2001 Conference, pages 480-489, 2001.
• 2: {2} S. V. Babji. Advancing fan-front : An efficient compression technique for large 3d triangle meshes. Master's thesis, Department of Computer Science, Pondicherry University, India, February 2002.
• 3: Gill Barequet , Christian A. Duncan , Subodh Kumar, RSVP: A Geometric Toolkit for Controlled Repair of Solid Models, IEEE Transactions on Visualization and Computer Graphics, v.4 n.2, p.162-177, April 1998 [doi>10.1109/2945.694983]
• 4: Gill Barequet , Micha Sharir, Filling gaps in the boundary of a polyhedron, Computer Aided Geometric Design, v.12 n.2, p.207-229, March 1995 [doi>10.1016/0167-8396(94)00011-G]
• 5: Daniel R. Baum , Stephen Mann , Kevin P. Smith , James M. Winget, Making radiosity usable: automatic preprocessing and meshing techniques for the generation of accurate radiosity solutions, Proceedings of the 18th annual conference on Computer graphics and interactive techniques, p.51-60, July 1991
• 6: Mark de Berg , Katrin Dobrindt, On levels of detail in terrains, Proceedings of the eleventh annual symposium on Computational geometry, p.426-427, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220334]
• 7: {7} G. Butlin and C. Stops. CAD data repair. In Proceedings of the 5th International Meshing Roundtable, pages 7-12. Sandia National Laboratory, October 1996.
• 8: {8} L. Chiariglione. MPEG home page. http://www.cselt.it/mpeg.
• 9: {9} CoCreate. OneSpace: Virtual conference room for collaborative CAD. http://www.CoCreate.com, 2001.
• 10: {10} T. W. Consortium. The Virtual Reality Modeling Language. http://www.web3d.org, ISO/IEC 14772-1, September 1997.
• 11: Brian Curless , Marc Levoy, A volumetric method for building complex models from range images, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.303-312, August 1996 [doi>10.1145/237170.237269]
• 12: 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]
• 13: {13} V. J. DeLeon and H. R. Berry. VRND: Notre-Dame cathedral - globally accessible multi-user real-time virtual reconstruction. In Proceedings of Virtual Systems & MultiMedia (VSMM98), Ogaki, Gifu, Japan, November 1998.
• 14: {14} Discreet (Autodesk Inc.). 3DStudio MAX R4. http://www.discreet.com, 2000.
• 15: Jihad El-Sana , Amitabh Varshney, Topology Simplification for Polygonal Virtual Environments, IEEE Transactions on Visualization and Computer Graphics, v.4 n.2, p.133-144, April 1998 [doi>10.1109/2945.694955]
• 16: Gerald Farin, Curves and surfaces for computer aided geometric design (3rd ed.): a practical guide, Academic Press Professional, Inc., San Diego, CA, 1993
• 17: James D. Foley , Andries van Dam , Steven K. Feiner , John F. Hughes, Computer graphics (2nd ed. in C): principles and practice, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 18: {18} C. Gotsman, S. Gumhold, and L. Kobbelt. Simplification and compression of 3d meshes. In Proceedings of the European Summer School on Principles of Multiresolution in Geometric Modelling (PRIMUS ), Munich, pages 319-361, August 2001.
• 19: André Guéziec , Frank Bossen , Gabriel Taubin , Claudio Silva, Efficient compression of non-manifold polygonal meshes, Proceedings of the conference on Visualization '99: celebrating ten years, p.73-80, October 1999, San Francisco, California, United States
• 20: 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]
• 21: Igor Guskov , Wim Sweldens , Peter Schröder, Multiresolution signal processing for meshes, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.325-334, July 1999 [doi>10.1145/311535.311577]
• 22: Nikhilesh Haval, Three-Dimensional Documentation of Complex Heritage Structures, IEEE MultiMedia, v.7 n.2, p.52-56, April 2000 [doi>10.1109/93.848429]
• 23: {23} IBM Research (Visualization Group). VRML compressed binary format. http://www.research.ibm.com/vrml/binary/.
• 24: 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]
• 25: Martin Isenburg , Jack Snoeyink, Compressing the Property Mapping of Polygon Meshes, Proceedings of the 9th Pacific Conference on Computer Graphics and Applications, p.4, October 16-18, 2001
• 26: 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]
• 27: 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]
• 28: {28} D. King and J. Rossignac. Connectivity compression irregular quadrilateral meshes. Technical Report GIT-GVU-99-36, GVU Center, Georgia Tech., Atlanta, USA, 1999.
• 29: Rob Koenen, MPEG-4: multimedia for our time, IEEE Spectrum, v.36 n.2, p.26-33, Feb. 1999 [doi>10.1109/6.744873]
• 30: Marc Levoy , Kari Pulli , Brian Curless , Szymon Rusinkiewicz , David Koller , Lucas Pereira , Matt Ginzton , Sean Anderson , James Davis , Jeremy Ginsberg , Jonathan Shade , Duane Fulk, The digital Michelangelo project: 3D scanning of large statues, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.131-144, July 2000 [doi>10.1145/344779.344849]
• 31: Peter Lindstrom , David Koller , William Ribarsky , Larry F. Hodges , Nick Faust , Gregory A. Turner, Real-time, continuous level of detail rendering of height fields, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.109-118, August 1996 [doi>10.1145/237170.237217]
• 32: William E. Lorensen , Harvey E. Cline, Marching cubes: A high resolution 3D surface construction algorithm, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.163-169, August 1987
• 33: {33} F. Ltd. CADFix: A Product for CAD Data Exchange, Repair and Upgrade. http://www.fegs.co.uk, 1997.
• 34: M. Mantyla, Introduction to Solid Modeling, W. H. Freeman & Co., New York, NY, 1988
• 35: {35} S. Microsystems. Java3d API specification. http://java.sun.com/products/java-media/3D, June 1999.
• 36: Michael E. Mortenson, Geometric modeling, John Wiley & Sons, Inc., New York, NY, 1985
• 37: {37} M. Nelson. Data Compression Handbook. M & T Publishing, Inc., 1991.
• 38: {38} R. Pajarola and J. Rossignac. Compressed progressive meshes. Technical Report GIT-GVU-99-05, GVU Center, Georgia Tech., Atlanta, USA, 1999.
• 39: Les Piegl , Wayne Tiller, The NURBS book, Springer-Verlag, London, 1995
• 40: Greg Roelofs , Richard Koman, PNG: The Definitive Guide, O'Reilly & Associates, Inc., Sebastopol, CA, 1999
• 41: {41} M. A. Rosenman and J. S. Gero. Modelling multiple views of design objects in a collaborative CAD environment. Computer-aided Design, 28(3):193-205, 1996.
• 42: Jarek Rossignac, The 3D Revolution: CAD Access for All!, Proceedings of the 1997 International Conference on Shape Modeling and Applications (SMA '97), p.64, March 03-06, 1997
• 43: 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]
• 44: Jarek Rossignac , David Cardoze, Matchmaker: manifold BReps for non-manifold r-sets, Proceedings of the fifth ACM symposium on Solid modeling and applications, p.31-41, June 08-11, 1999, Ann Arbor, Michigan, United States [doi>10.1145/304012.304016]
• 45: M. Schindler, A Fast Renormalisation for Arithmetic Coding, Proceedings of the Conference on Data Compression, p.572, March 30-April 01, 1998
• 46: Dinesh Shikhare , Sushil Bhakar , Sudhir P. Mudur, Compression of Large 3D Engineering Models using Automatic Discovery of Repeating Geometric Features, Proceedings of the Vision Modeling and Visualization Conference 2001, p.233-240, November 21-23, 2001
• 47: 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]
• 48: {48} G. Taubin, W. Horn, F. Lazaurus, and J. Rossignac. Geometry coding and VRML. Proceedings of the IEEE, 86(6):1228-1243, 1998.
• 49: 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]
• 50: {50} C. Touma and C. Gotsman. Triangle mesh compression. In Proceeding of Graphics Interface 98, pages 26-34, June 1998.
• 51: Greg Turk , Marc Levoy, Zippered polygon meshes from range images, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.311-318, July 1994 [doi>10.1145/192161.192241]
• 52: {52} W.T. Tutte. A census of planar triangulations. Canad. J. Math., 14:21-38, 1962.
• 53: Gregory K. Wallace, The JPEG still picture compression standard, Communications of the ACM, v.34 n.4, p.30-44, April 1991 [doi>10.1145/103085.103089]
• 54: Peter Wayner, Compression algorithms for real programmers, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 55: {55} M. Woo, J. Neider, and T. Davis. OpenGL Programming Guide. Addison-Wesley Publishing Company, 1996.

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Network communication

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Web-based services

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Reliability