QSplat: a multiresolution point rendering system for large meshes

ABSTRACT

Advances in 3D scanning technologies have enabled the practical creation of meshes with hundreds of millions of polygons. Traditional algorithms for display, simplification, and progressive transmission of meshes are impractical for data sets of this size. We describe a system for representing and progressively displaying these meshes that combines a multiresolution hierarchy based on bounding spheres with a rendering system based on points. A single data structure is used for view frustum culling, backface culling, level-of-detail selection, and rendering. The representation is compact and can be computed quickly, making it suitable for large data sets. Our implementation, written for use in a large-scale 3D digitization project, launches quickly, maintains a user-settable interactive frame rate regardless of object complexity or camera position, yields reasonable image quality during motion, and refines progressively when idle to a high final image quality. We have demonstrated the system on scanned models containing hundreds of millions of samples.

REFERENCES

• Aliaga 99: Daniel Aliaga , Jon Cohen , Andrew Wilson , Eric Baker , Hansong Zhang , Carl Erikson , Kenny Hoff , Tom Hudson , Wolfgang Stuerzlinger , Rui Bastos , Mary Whitton , Fred Brooks , Dinesh Manocha, MMR: an interactive massive model rendering system using geometric and image-based acceleration, Proceedings of the 1999 symposium on Interactive 3D graphics, p.199-206, April 26-29, 1999, Atlanta, Georgia, United States [doi>10.1145/300523.300554]
• Animatek: AnimaTek International, Inc., "Caviar Technology," Web page: http://www.animatek.com/products_caviar.htm
• Arvo 89: James Arvo , David Kirk, A survey of ray tracing acceleration techniques, An introduction to ray tracing, Academic Press Ltd., London, UK, 1989
• Certain 96: Andrew Certain , Jovan Popovic , Tony DeRose , Tom Duchamp , David Salesin , Werner Stuetzle, Interactive multiresolution surface viewing, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.91-98, August 1996 [doi>10.1145/237170.237213]
• Chang 99: Chun-Fa Chang , Gary Bishop , Anselmo Lastra, LDI tree: a hierarchical representation for image-based rendering, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.291-298, July 1999 [doi>10.1145/311535.311571]
• Cline 88: Cline, H. E., Lorensen, W. E., Ludke, S., Crawford, C. R., and Teeter, B. C. "Two Algorithms for the Three-Dimensional Reconstruction of Tomograms," Medical Physics, Vol. 15, No. 3, 1988.
• Cook 87: Robert L. Cook , Loren Carpenter , Edwin Catmull, The Reyes image rendering architecture, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.95-102, August 1987
• Csuri 79: C. Csuri , R. Hackathorn , R. Parent , W. Carlson , M. Howard, Towards an interactive high visual complexity animation system, Proceedings of the 6th annual conference on Computer graphics and interactive techniques, p.289-299, August 08-10, 1979, Chicago, Illinois, United States
• Curless 96: 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]
• Deering 95: 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]
• Duchaineau 97: Mark Duchaineau , Murray Wolinsky , David E. Sigeti , Mark C. Miller , Charles Aldrich , Mark B. Mineev-Weinstein, ROAMing terrain: real-time optimally adapting meshes, Proceedings of the 8th conference on Visualization '97, p.81-88, October 18-24, 1997, Phoenix, Arizona, United States
• Eck 95: 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]
• Funkhouser 92: Thomas A. Funkhouser , Carlo H. Séquin , Seth J. Teller, Management of large amounts of data in interactive building walkthroughs, Proceedings of the 1992 symposium on Interactive 3D graphics, p.11-20, June 1992, Cambridge, Massachusetts, United States [doi>10.1145/147156.147158]
• Funkhouser 93: 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]
• Funkhouser 96: Thomas A. Funkhouser, Database management for interactive display of large architectural models, Proceedings of the conference on Graphics interface '96, p.1-8, May 1996, Toronto, Ontario, Canada
• Greene 93: Ned Greene , Michael Kass , Gavin Miller, Hierarchical Z-buffer visibility, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.231-238, September 1993 [doi>10.1145/166117.166147]
• Grossman 98: Grossman, J. and Dally, W. "Point Sample Rendering," Proc. Eurographics Rendering Workshop, 1998.
• Hoppe 96: 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]
• Hoppe 97: Hugues Hoppe, View-dependent refinement of progressive meshes, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.189-198, August 1997 [doi>10.1145/258734.258843]
• Hoppe 98: Hugues Hoppe, Smooth view-dependent level-of-detail control and its application to terrain rendering, Proceedings of the conference on Visualization '98, p.35-42, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• Huffman 52: Huffman, D. "A Method for the Construction of Minimum Redundancy Codes," Proc. IRE, Vol. 40, No. 9, 1952.
• Kajiya 89: J. T. Kajiya , T. L. Kay, Rendering fur with three dimensional textures, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.271-280, July 1989
• Krishnamurthy 96: Venkat Krishnamurthy , Marc Levoy, Fitting smooth surfaces to dense polygon meshes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.313-324, August 1996 [doi>10.1145/237170.237270]
• Kumar 96: Subodh Kumar , Dinesh Manocha , William Garrett , Ming Lin, Hierarchical back-face computation, Proceedings of the eurographics workshop on Rendering techniques '96, p.235-ff., December 1996, Porto, Portugal
• Laur 91: David Laur , Pat Hanrahan, Hierarchical splatting: a progressive refinement algorithm for volume rendering, Proceedings of the 18th annual conference on Computer graphics and interactive techniques, p.285-288, July 1991
• Levoy 85: Levoy, M. and Whitted, T. "The Use of Points as a Display Primitive," Technical Report TR 85-022, University of North Carolina at Chapel Hill, 1985.
• Levoy 00: 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]
• Lindstrom 98: 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
• Luebke 97: David Luebke , Carl Erikson, View-dependent simplification of arbitrary polygonal environments, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.199-208, August 1997 [doi>10.1145/258734.258847]
• Max 95: Max, N. and Ohsaki, K. "Rendering Trees from Precomputed Z- buffer Views," Proc. Eurographics Rendering Workshop, 1995.
• Pajarola99: Pajarola, R. and Rossignac, J. "Compressed Progressive Meshes," Technical Report GIT-GVU-99-05, Georgia Institute of Technology, 1999.
• Reeves 83: William T. Reeves, Particle systems—a technique for modeling a class of fuzzy objects, Proceedings of the 10th annual conference on Computer graphics and interactive techniques, p.359-375, July 25-29, 1983, Detroit, Michigan, United States
• Rossignac 93: Rossignac, J. and Borrel, E "Multi-Resolution 3D Approximations for Rendering Complex Scenes," Geometric Modeling in Computer Graphics, 1993.
• Rubin 80: Steven M. Rubin , Turner Whitted, A 3-dimensional representation for fast rendering of complex scenes, Proceedings of the 7th annual conference on Computer graphics and interactive techniques, p.110-116, July 14-18, 1980, Seattle, Washington, United States
• Samet 90: Hanan Samet, Applications of spatial data structures: Computer graphics, image processing, and GIS, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• Shirman 93: Shirman, L. and Abi-Ezzi, S. "The Cone of Normals Technique for Fast Processing of Curved Patches," Proc. Eurographics, 1993.
• Swan 97: J. Edward Swan, II , Klaus Mueller , Torsten Möller , Naeem Shareef , Roger Crawfis , Roni Yagel, An anti-aliasing technique for splatting, Proceedings of the 8th conference on Visualization '97, p.197-ff., October 18-24, 1997, Phoenix, Arizona, United States
• Taubin 98: 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]
• Teller 91: Seth J. Teller , Carlo H. Séquin, Visibility preprocessing for interactive walkthroughs, Proceedings of the 18th annual conference on Computer graphics and interactive techniques, p.61-70, July 1991
• Westover 89: Lee Westover, Interactive volume rendering, Proceedings of the 1989 Chapel Hill workshop on Volume visualization, p.9-16, May 1989, Chapel Hill, Noth Carolina, United States [doi>10.1145/329129.329138]
• Yemez 99: Yemez, Y. and Schmitt, E "Progressive Multilevel Meshes from Octree Particles," Proc. 3D Digital Imaging and Modeling, 1999.
• Zhang 97: Hansong Zhang , Kenneth E. Hoff, III, Fast backface culling using normal masks, Proceedings of the 1997 symposium on Interactive 3D graphics, p.103-ff., April 27-30, 1997, Providence, Rhode Island, United States [doi>10.1145/253284.253314]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms

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.3.6 Methodology and Techniques
          Subjects: Graphics data structures and data types
  I.4 IMAGE PROCESSING AND COMPUTER VISION

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
compression algorithms, level of detail algorithms, rendering systems, spatial data structures