“The randomized z-buffer algorithm: interactive rendering of highly complex scenes” by Wand, Peter, Meyer auf der Heide, Straßer and Müller-Fischer

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 1014 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.

1. Appel, A.: Some Techniques for Shading Mashine Renderings of Solids. In: Proceedings of the Spring Joint Computer Conference, 37-45, 1968.
2. Arvo, J., Kirk, D. A: Survey of Ray Tracing Acceleration Techniques.In: Glassner, A. (editor): An Introduction to Ray Tracing, Academic Press, 4 th printing, pp. 201-262, 1991.
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. Blinn, J. F.: Light Reflection Functions for Simulation of Clouds and Dusty Surfaces. In: Computer Graphics (SIGGRAPH 82 Proceedings), 16 (3), 21-29, 1982.
5. Chamberlain,xB., DeRose, T., Lischinski, D., Salesin, D., Snyder, J.: Fast Rendering of Complex Environments Using a Spatial Hierarchy. In: Proc. Graphics Interface ’96, 132-141, 1996.
6. Cook, R.L.: Stochastik Sampling and Distributed Ray Tracing. In: Glassner, A. (editor): An Introduction to Ray Tracing. Academic Press, 4 th printing, pp. 161-199, 1991.
7. Csuri, C., Hackathorn, R., Parent, R., Carlson, W., Howard, M.: Towards an Interactive High Visual Complexity Animation System. In: Computer Graphics (SIGGRAPH 79 Proceedings), 13 (3), 289-299, 1979.
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. Garland, M.: Quadric-Based Polygonal Surface Simplification, Ph.D. thesis, Technical Report CMU-CS-99-105, Carnegie Mellon University, 1999
11. Glassner, A. S.: Principles of Digital Image Synthesis. Morgen Kaufmann Publishers, 1995.
12. Gortler, S. J., Grzeszczuk, R., Szeliski, R., Cohen, M. F.: The Lumigraph. In: SIGGRAPH 96 Proceedings, Annual Conference Series, 43-54, 1996.
13. Green, N., Kass, M., Miller, G.: Hierarchical Z-Buffer Visibility. In: SIGGRAPH 93 Proceedings, Annual Conference Series, 231-238, 1993.
14. Grossman, J. P., Dally, W.: Point Sample Rendering. In Rendering Techniques’98, 181-192, Springer, 1998.
15. Levoy, M., Hanrahan, P.: Light Field Rendering. In: SIGGRAPH 96 Proceedings, Annual Conference Series, 31-42, 1996.
16. Levoy, M., Whitted, T.: The Use of Points as a Display Primitive. Technical report, University of Norh Carolina at Chapel Hill, 1985.
17. Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, 1995.
18. Pfister, H., Zwicker, M., van Baar, J., Gross, M.: Surfels: Surface Elements as Rendering Primitives. In: SIGGRAPH 2000 Proceedings, Annual Conference Series, 335-342, 2000.
19. Press, W.H., Teukolsky, S.A., Vetterling, W.T., Flannery, B.P.: Numerical Recipes in C, The Art of Scientific Computing, Second Edition, Cambridge University Press, 1992.
20. Puppo, E., Scopigno, R.: Simplification, LOD and Multiresolution Principals and Applications. In: EUROGRAPHICS 97 Tutorial Notes, 1997.
21. Reeves, W. T.: Particle Systems – A Technique for Modeling a Class of Fuzzy Objects. In: Computer Graphics (SIGGRAPH 83 Proceedings), 17 (3), 359-376, 1983.
22. Rusinkiewicz, S., Levoy, M.: Qsplat: A Multiresolution Point Rendering System for Large Meshes. In: SIGGRAPH 2000 Proceedings, Annual Conference Series, 343-352, 2000.
23. Schaufler, G.: Per-Object Image Warping with Layered Impostors. In: Rendering Techniques ’98, 145-156, Springer, 1998.
24. Shade, J., Gortler, S., He, L., Szeliski, R.: Layered Depth Images. In: SIGGRAPH 98 Proceedings, Annual Conference Series, 231-242, 1998.
25. Shade, J., Lischinski, D., Salesin, D. H., DeRose, T., Snyder, J.: Hierarchical Image Caching for Accelerated Walkthroughs of Complex Environments. In: SIGGRAPH 96 Proceedings, Annual Conference Series, 75-82, 1996.
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. Teller, S.J., Sequin, C.H.: Visibility Preprocessing For Interactive Walkthroughs. In: Computer Graphics (SIGGRAPH 91 Proceedings), 25 (4), 61-69, 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. Wernecke, J.: The Inventor Mentor: Programming Object-Oriented 3d Graphics With Open Inventor, Release 2. Addison Wesley, 1994.
30. Zhang, H., Manocha, D., Hudson, T., Hoff, K.: Visibility Culling using Hierarchical Occlusion Maps. In: SIGGRAPH 97 Proceedings, Annual Conference Series, 77-88, 1997.