The Randomized z-Buffer Algorithm:Interactive Rendering of Highly Complex ScenesMichael Wand*Matthias Fischer†Ingmar Peter*Friedhelm Meyer auf der Heide†Wolfgang Straßer** WSI/GRIS, University of Tübingen † University of PaderbornAbstractWe present a new output-sensitive rendering algorithm, the ran-domized z-buffer algorithm. It renders an image of an arbitrarythree-dimensional scene consisting of triangular primitives byreconstruction from a dynamically chosen set of random surfacesample points. This approach is independent of mesh connectivityand topology. The resulting rendering time grows only logarith-mically with the numbers of triangles in the scene. We were ableto render walkthroughs of scenes of up to 1014triangles at interac-tive frame rates. Automatic identification of low detail scenecomponents 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 imagequality is comparable to that of common approaches like z-bufferrendering. The precomputed data structures employed by therandomized z-buffer allow for interactive dynamic updates of thescene. Their memory requirements grow only linearly with thenumber of triangles and allow for a scene graph based instantia-tion scheme to further reduce memory consumption.Categories and Subject Descriptors: I.3.3 [Computer Graphics]:Picture/Image Generation – Display Algorithms; I.3.6 [ComputerGraphics]: Methodology and Techniques – Graphics data struc-tures and data types; G.3 [Mathematics of Computing]: Probabil-ity and Statistics – Probabilistic algorithms.Keywords: Rendering Systems, Level of Detail Algorithms,Monte Carlo Techniques1 INTRODUCTIONAlthough the capabilities of computer graphics hardware havedramatically increased in the past years, the handling of scenecomplexity is still one of the most fundamental problems in com-puter graphics. Interactive display of highly complex scenes likelandscapes with extensive vegetation, large city models, or highlydetailed datasets in scientific visualization are a major challengefor rendering algorithms.To be able to render highly complex scenes at interactiveframe rates, the running time of the rendering algorithm has to beoutput-sensitive. Analogous to Sudarsky and Gotsman [26], weconsider a rendering algorithm output-sensitive if its time com-plexity depends only weakly on the complexity of the input scene.Classic algorithms, like the z-buffer algorithm, fail to meet thisrequirement because their running times grow linearly with thenumber of elementary objects in the scene [26]. Although sophis-ticated hardware implementations are available, these algorithmsare not capable of displaying highly complex scenes in real-time.In this paper, we present a new output-sensitive rendering al-gorithm, the randomized z-buffer algorithm. The main idea of thealgorithm is to generate an image of a scene by reconstructing itfrom a dynamically chosen set of random surface sample points.The sample points represent the complex scene geometry, hencenot every single triangle must be handled separately during ren-dering. In a first step, random sample points are chosen so thatthey cover the projections of objects in the image plane approxi-mately uniformly. This can be done in highly output-sensitivetime. Here, the randomized selection is the key to avoid expensivegeometric queries. In a second step, the algorithm reconstructs theocclusion between the chosen sample points and renders theresulting image using the visible points. Our approach has thefollowing main advantages:Efficiency: Therenderingtimeforasceneconsistingofntriangles covering an on-screen projected area of a pixels (includ-ing occluded triangles) is O(a·logn). The logarithmic growth ofthe rendering time in n permits rendering of highly complexscenes. An automatic fallback strategy to conventional z-bufferrendering for low detail scene components insures that the render-ing speed cannot drop below that of conventional z-buffer render-ing. A caching strategy for sample sets is used to make optimaluse of accelerated graphics hardware. Using a prototype imple-mentation, we are able to render walkthroughs of scenes consist-ingofupto1014triangles at interactive framerates. The algorithmuses O(n)storageandO(n·logn) precomputation time. In order tostore highly complex scenes in main memory, we adopted a scenegraph based hierarchical instantiation scheme [29].Generality:The algorithm takes arbitrary models consistingof triangles as input. Rendering times and results are independentof the input topology. Arbitrary local illumination models can beused to define the surface appearance.Image quality: We will give analytical and experimental evi-dence that the image quality is comparable to conventional ren-dering results for a broad range of input scenes, covering mostmodels found in practical applications.Interactive editing: The data structures used for the selectionof sample points allow for efficient dynamic updates: Insertionand removal of an object can be handled in O(t)timewheret isthe height of an octree built for the objects in the scene. This per-mits interactive update times for local modifications of the scene.The remaining part of this paper is organized as follows: Thenext section gives an overview on the randomized z-buffer algo-rithm. In Section 3, we briefly review related work. Afterwards,the two main steps of the algorithm, image reconstruction (Sec-tion 4) and sample point generation (Section 5), are discussed indetail. The image reconstruction is described first because it setsthe preliminaries for the point selection scheme. In Section 6, thetotal running time of both steps is determined. Section 7 describesthe automatic invocation of conventional z-buffer rendering,sample caching, and scene graph based scene encoding. Resultsare discussed in Section 8. The paper concludes with some ideasfor future research.* {wand, peter, strasser}@gris.uni-tuebingen.de† {mafi, fmadh}@uni-paderborn.dePermission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copiesare not made or distributed for profit or commercial advantage and thatcopies bear this notice and the full citation on the first page. To copyotherwise, to republish, to post on servers or to redistribute to lists,requires prior specific permission and/or a fee.ACM SIGGRAPH