
M. Wand, M. Fischer, F. Meyer auf der Heide: Randomized Point Sampling for OutputSensitive Rendering of Complex Dynamic Scenes. Technical Report WSI200020, Wilhelm Schickard Institute for Computer Science, GraphicalInteractive Systems (WSI/GRIS), University of Tübingen, 2000.
Abstract:
We present a new outputsensitive rendering algorithm, the randomized zbuffer 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 outputsensitive 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 zbuffer rendering; in special cases, realtime performance can be achieved.
Bibtex:
@TECHREPORT{wfmrps00,
AUTHOR = {Wand, Michael and Fischer, Matthias and Meyer auf der Heide, Friedhelm},
TITLE = {Randomized Point Sampling for OutputSensitive Rendering of Complex Dynamic Scenes},
NUMBER = {WSI200020},
ISSN = {09463852},
INSTITUTION = {Wilhelm Schickard Institute for Computer Science, GraphicalInteractive 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 outputsensitive rendering algorithm, the randomized zbuffer 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 outputsensitive 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 zbuffer rendering; in special cases, realtime performance can be achieved.}
}

