“QSplat: a multiresolution point rendering system for large meshes” by Rusinkiewicz and Levoy

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.

1. Aliaga, D., Cohen, J., Wilson, A., Baker, E., Zhang, H., Erikson, C., Hoff, K., Hudson, T., Stuerzlinger, W., Bastos, R., Whitton, M., Brooks, E, and Manocha, D. “MMR: An Interactive Massive Model Rendering System Using Geometric and Image-Based Acceleration,” Proc. Symposium on Interactive 3D Graphics, 1999.
2. AnimaTek International, Inc., “Caviar Technology,” Web page: http://www.animatek.com/products_caviar.htm
3. Arvo, J. and Kirk, D. “A Survey of Ray Tracing Acceleration Techniques,” An Introduction to Ray Tracing, Glassner, A. S. ed., Academic Press, 1989.
4. Certain, A., Popovi~, J, DeRose, T., Duchamp, T., Salesin, D., and Stuetzle, W. “Interactive Multiresolution Surface Viewing,” Proc. SIGGRAPH, 1996.
5. Chang, C., Bishop, G., and Lastra, A. “LDI Tree: A Hierarchical Representation for Image-Based Rendering,” Proc. SIGGRAPH, 1999.
6. 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.
7. Cook, R., Carpenter, L., and Catmull, E. “The Reyes Image Rendering Architecture,” Proc. SIGGRAPH, 1987.
8. Csuri, C., Hackathorn, R., Parent, R., Carlson, W., and Howard, M. “Towards an Interactive High Visual Complexity Animation System,” Proc. SIGGRAPH, 1979.
9. Curless, B. and Levoy, M. “A Volumetric Method for Building Complex Models from Range Images,” Proc. SIGGRAPH, 1996.
10. Deering, M. “Geometry Compression,” Proc. SIGGRAPH, 1995.
11. Duchaineau, M., Wolinsky, M., Sigeti, D,. Miller, M., Aldrich, C., and Mineev-Weinstein, M. “ROAMing Terrain: Real-time Optimally Adapting Meshes,” Proc. Visualization, 1997.
12. Eck, M., DeRose, T., Duchamp, T., Hoppe, H., Lounsbery, M., and Stuetzle, W. “Multiresolution Analysis of Arbitrary Meshes,” Proc. SIGGRAPH, 1995.
13. Funkhouser, T., Sdquin, C., and Teller, S. “Management of Large Amounts of Data in Interactive Building Walkthroughs,” Proc. Symposium on Interactive 3D Graphics, 1992.
14. Funkhouser, T. and Sdquin, C. “Adaptive Display Algorithm for Interactive Frame Rates During Visualization of Complex Virtual Environments,” Proc. SIGGRAPH, 1993.
15. Funkhouser, T. “Database Management for Interactive Display of Large Architectural Models,” Graphics Interface, 1996.
16. Greene, N., Kass, M., and Miller, G. “Hierarchical Z-buffer Visibility,” Proc. SIGGRAPH, 1993.
17. Grossman, J. and Dally, W. “Point Sample Rendering,” Proc. Eurographics Rendering Workshop, 1998.
18. Hoppe, H. “Progressive Meshes,” Proc. SIGGRAPH, 1996.
19. Hoppe, H. “View-Dependent Refinement of Progressive Meshes,” Proc. SIGGRAPH, 1997.
20. Hoppe, H. “Smooth View-Dependent Level-of-Detail Control and its Application to Terrain Rendering,” Proc. Visualization, 1998.
21. Huffman, D. “A Method for the Construction of Minimum Redundancy Codes,” Proc. IRE, Vol. 40, No. 9, 1952.
22. Kajiya, J. and Kay, T. “Rendering Fur with Three Dimensional Textures,” Proc. SIGGRAPH, 1989.
23. Krishnamurthy, V. and Levoy, M. “Fitting Smooth Surfaces to Dense Polygon Meshes,” Proc. SIGGRAPH, 1986.
24. Kumar, S., Manocha, D., Garrett, W., and Lin, M. “Hierarchical Back-Face Computation,” Proc. Eurographics Rendering Workshop, 1996.
25. Laur, D. and Hanrahan, P. “Hierarchical Splatting: A Progressive Refinement Algorithm for Volume Rendering,” Proc. SIGGRAPH, 1991.
26. 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.
27. Levoy, M., Pulli, K., Curless, B., Rusinkiewicz, S., Koller, D., Pereira, L., Ginzton, M., Anderson, S., Davis, J., Ginsberg, J., Shade, J., and Fulk, D. “The Digital Michelangelo Project: 3D Scanning of Large Statues,” Proc. SIGGRAPH, 2000.
28. Lindstrom, P. and Turk, G. “Fast and Memory Efficient Polygonal Simplification,” Proc. Visualization, 1998.
29. Luebke, D., and Erikson, C. “View-Dependent Simplification of Arbitrary Polygonal Environments,” Proc. SIGGRAPH, 1997.
30. Max, N. and Ohsaki, K. “Rendering Trees from Precomputed Z- buffer Views,” Proc. Eurographics Rendering Workshop, 1995.
31. Pajarola, R. and Rossignac, J. “Compressed Progressive Meshes,” Technical Report GIT-GVU-99-05, Georgia Institute of Technology, 1999.
32. Reeves, W. “Particle Systems – A Technique for Modeling a Class of Fuzzy Objects,” Proc. SIGGRAPH, 1983.
33. Rossignac, J. and Borrel, E “Multi-Resolution 3D Approximations for Rendering Complex Scenes,” Geometric Modeling in Computer Graphics, 1993.
34. Rubin, S. M. and Whitted, T. “A 3-Dimensional Representation for Fast Rendering of Complex Scenes,” Proc. SIGGRAPH, 1980.
35. Samet, H. Applications of Spatial Data Structures, Addison-Wesley, 1990.
36. Shirman, L. and Abi-Ezzi, S. “The Cone of Normals Technique for Fast Processing of Curved Patches,” Proc. Eurographics, 1993.
37. Swan, J., Mueller, K., M611er, T., Shareef, N., Crawfis, R., and Yagel, R. “An Anti-Aliasing Technique for Splatting,” Proc. Visualization, 1997.
38. Taubin, G. and Rossignac, J. “Geometric Compression Through Topological Surgery,” ACM Trans. on Graphics, Vol. 17, No. 2, 1998.
39. Teller, S. and Sdquin, C. “Visibility Preprocessing for Interactive Walkthroughs,” Proc. SIGGRAPH, 1991.
40. Westover, L. “Interactive Volume Rendering,” Proc. Volume ~”- sualization Workshop, University of North Carolina at Chapel Hill, 1989.
41. Yemez, Y. and Schmitt, E “Progressive Multilevel Meshes from Octree Particles,” Proc. 3D Digital Imaging and Modeling, 1999.
42. Zhang, H. and Hoff, K. “Fast Backface Culling Using Normal Masks,” Proc. Symposium on Interactive 3D Graphics, 1997.