M. Wand, M. Fischer, F. Meyer auf der Heide: Randomized Point Sampling for Output-Sensitive Rendering of Complex Dynamic Scenes.
Technical Report WSI-2000-20, Wilhelm Schickard Institute for Computer Science, Graphical-Interactive Systems (WSI/GRIS), University of Tübingen, 2000.

Abstract:

We present a new output-sensitive rendering algorithm, the randomized z-buffer algorithm. It renders an image of a three dimensional scene of triangular primitives by reconstruction from a random sample of surface points which are chosen with a probability proportional to the projected area of the objects. The approach is independent of mesh connectivity and topology. It leads to a rendering time that grows only logarithmically with the numbers of triangles in the scene and to linear memory consumption, thus allowing walkthroughs of scenes of extreme complexity. We consider different methods for image reconstruction which aim at correctness, rendering speed and image quality and we develop an efficient data structure for sample extraction in output-sensitive time which allows for efficient dynamic updates of the scene. Experiments confirm that scenes consisting of some hundred billion triangles can be rendered within seconds with an image quality comparable to a conventional z-buffer rendering; in special cases, realtime performance can be achieved.

Bibtex: 

@TECHREPORT{wfm-rps-00,
   AUTHOR = {Wand, Michael and Fischer, Matthias and Meyer auf der Heide, Friedhelm},
   TITLE = {Randomized Point Sampling for Output-Sensitive Rendering of Complex Dynamic Scenes},
   NUMBER = {WSI-2000-20},
   ISSN = {0946-3852},
   INSTITUTION = {Wilhelm Schickard Institute for Computer Science, Graphical-Interactive Systems (WSI/GRIS), University of T{\"u}bingen},
   MONTH = November,
   YEAR = {2000},
   KEYWORDS = {I.3.3 [Computer Graphics]: Picture / Image Generation - Display Algorithms; I.3.6 [Computer Graphics]: Methodology and Techniques - Graphics data structures and data types; G.3 [Mathematics of Computing]: Probability and Statistics - Probabilistic algorithms.} ,
   ABSTRACT = {We present a new output-sensitive rendering algorithm, the randomized z-buffer algorithm. It renders an image of a three dimensional scene of triangular primitives by reconstruction from a random sample of surface points which are chosen with a probability proportional to the projected area of the objects. The approach is independent of mesh connectivity and topology. It leads to a rendering time that grows only logarithmically with the numbers of triangles in the scene and to linear memory consumption, thus allowing walkthroughs of scenes of extreme complexity. We consider different methods for image reconstruction which aim at correctness, rendering speed and image quality and we develop an efficient data structure for sample extraction in output-sensitive time which allows for efficient dynamic updates of the scene. Experiments confirm that scenes consisting of some hundred billion triangles can be rendered within seconds with an image quality comparable to a conventional z-buffer rendering; in special cases, realtime performance can be achieved.}
}