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 10E14 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.

Download:

	Paper: The Randomized z-Buffer Algorithm:  Interactive Rendering of Highly Complex Scenes Michael Wand, Matthias Fischer, Ingmar Peter, Friedhelm Meyer auf der Heide, Wolfgang Straßer To appear in SIGGRAPH 2001 Conference Procedings	PDF: preprint.pdf (1.153 KB) Compressed Postscript: preprint.ps.zip (2.752 KB) ACM Copyright Notice
	Video: The Randomized z-Buffer Algorithm:  Interactive Rendering of Highly Complex Scenes Michael Wand, Matthias Fischer, Ingmar Peter, Friedhelm Meyer auf der Heide, Wolfgang Straßer To appear in SIGGRAPH 2001 Video Procedings	MPEG-1 (352 x 288 - 43.3 MB): video.mpg AVI (MPEG-4 V2, 352 x 288 - 20 MB): video.avi ACM Copyright Notice
	Technical Report: Randomized Point Sampling for Output-Sensitive Rendering of Complex Dynamic Scenes Michael Wand, Matthias Fischer, Friedhelm Meyer auf der Heide Technical Report, WSI/GRIS, University of Tübingen, WSI-2000-20, ISSN 0946-3852, November 2000	PDF: technicalReport.pdf (903 KB) Compressed Postscript: technicalReport.ps.zip (2,637 KB)
	Diploma Thesis (in German): Approximative Darstellung dreidimensionaler Szenen mit randomisiertem z-Buffer Michael Wand Diplomarbeit, University of Paderborn, March 2000	Compressed Postscript: diplomarbeit.ps.zip (19,2 MB, in German) PDF: diplomarbeit.pdf (14,2 MB, in German)