The randomized z-buffer algorithm: interactive rendering of highly complex scenes

ABSTRACT

We present a new output-sensitive rendering algorithm, the randomized z-buffer algorithm. It renders an image of an arbitrary three-dimensional scene consisting of triangular primitives by reconstruction from a dynamically chosen set of random surface sample points. This approach is independent of mesh connectivity and topology. The resulting rendering time grows only logarithmically with the numbers of triangles in the scene. We were able to render walkthroughs of scenes of up to 10¹⁴ triangles at interactive frame rates. Automatic identification of low detail scene components ensures that the rendering speed of the randomized z-buffer cannot drop below that of conventional z-buffer rendering. Experimental and analytical evidence is given that the image quality is comparable to that of common approaches like z-buffer rendering. The precomputed data structures employed by the randomized z-buffer allow for interactive dynamic updates of the scene. Their memory requirements grow only linearly with the number of triangles and allow for a scene graph based instantiation scheme to further reduce memory consumption.

REFERENCES

• 1: Appel, A.: Some Techniques for Shading Mashine Renderings of Solids. In: Proceedings of the Spring Joint Computer Conference, 37-45, 1968.
• 2: James Arvo , David Kirk, A survey of ray tracing acceleration techniques, An introduction to ray tracing, Academic Press Ltd., London, UK, 1989
• 3: Bern, M., Eppstein, D., Gilbert, J.: Provably good mesh generation. In: Proc. 31 st Annu. IEEE Sympos. Found. Compt. Sci., 231-241, 1990.
• 4: James F. Blinn, Light reflection functions for simulation of clouds and dusty surfaces, Proceedings of the 9th annual conference on Computer graphics and interactive techniques, p.21-29, July 26-30, 1982, Boston, Massachusetts, United States
• 5: Bradford Chamberlain , Tony DeRose , Dani Lischinski , David Salesin , John Snyder, Fast rendering of complex environments using a spatial hierarchy, Proceedings of the conference on Graphics interface '96, p.132-141, May 1996, Toronto, Ontario, Canada
• 6: Robert L. Cook, Stochastic sampling and distributed ray tracing, An introduction to ray tracing, Academic Press Ltd., London, UK, 1989
• 7: 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
• 8: de Berg, M., Halperin, D., Overmars, M., Snoeyink, J., van Kreveld, M.: Efficient Ray Shooting and Hidden Surface Removal. In: Algorithmica, 12, 30-53, 1994.
• 9: Feller, W: An Introduction to Probability Theory and Its Applications. Third Edition, revised printing, Wiley & Sons, 1970.
• 10: Michael Garland , Paul Heckbert, Quadric-based polygonal surface simplification, 1999
• 11: Andrew S. Glassner, Principles of Digital Image Synthesis, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1994
• 12: Steven J. Gortler , Radek Grzeszczuk , Richard Szeliski , Michael F. Cohen, The lumigraph, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.43-54, August 1996 [doi>10.1145/237170.237200]
• 13: 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]
• 14: Grossman, J. P., Dally, W.: Point Sample Rendering. In Rendering Techniques'98, 181-192, Springer, 1998.
• 15: Marc Levoy , Pat Hanrahan, Light field rendering, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.31-42, August 1996 [doi>10.1145/237170.237199]
• 16: Levoy, M., Whitted, T.: The Use of Points as a Display Primitive. Technical report, University of Norh Carolina at Chapel Hill, 1985.
• 17: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 18: Hanspeter Pfister , Matthias Zwicker , Jeroen van Baar , Markus Gross, Surfels: surface elements as rendering primitives, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.335-342, July 2000 [doi>10.1145/344779.344936]
• 19: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical recipes in C (2nd ed.): the art of scientific computing, Cambridge University Press, New York, NY, 1992
• 20: Puppo, E., Scopigno, R.: Simplification, LOD and Multiresolution Principals and Applications. In: EUROGRAPHICS 97 Tutorial Notes, 1997.
• 21: 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
• 22: Szymon Rusinkiewicz , Marc Levoy, QSplat: a multiresolution point rendering system for large meshes, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.343-352, July 2000 [doi>10.1145/344779.344940]
• 23: Schaufler, G.: Per-Object Image Warping with Layered Impostors. In: Rendering Techniques '98, 145-156, Springer, 1998.
• 24: Jonathan Shade , Steven Gortler , Li-wei He , Richard Szeliski, Layered depth images, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.231-242, July 1998 [doi>10.1145/280814.280882]
• 25: Jonathan Shade , Dani Lischinski , David H. Salesin , Tony DeRose , John Snyder, Hierarchical image caching for accelerated walkthroughs of complex environments, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.75-82, August 1996 [doi>10.1145/237170.237209]
• 26: Sudarsky, O., Gotsman, C.: Output-Sensitive Visibility Algorithms for Dynamic Scenes with Applications to Virtual Reality. In: Computer Graphics Forum (EUROGRAPHICS 96 Proceedings), 15 (3), 249-258, 1996.
• 27: 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
• 28: Wand, M., Fischer, M., Meyer auf der Heide, F.: Randomized Point Sampling for Output-Sensitive Rendering of Complex Dynamic Scenes. technical report WSI-2000-20, WSI/GRIS University of Tubingen, 2000. http://www.gris.uni-tuebingen.de/publics/paper/Wand-2000-Randomized.pdf
• 29: Josie Wernecke, The Inventor Mentor: Programming Object-Oriented 3d Graphics with Open Inventor, Release 2, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1993
• 30: Hansong Zhang , Dinesh Manocha , Tom Hudson , Kenneth E. Hoff, III, Visibility culling using hierarchical occlusion maps, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.77-88, August 1997 [doi>10.1145/258734.258781]

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques
          Subjects: Graphics data structures and data types

General Terms:
Algorithms, Design, Theory

Keywords:
Monte Carlo techniques, level of detail algorithms, rendering systems