ALCOMFT-TR-02-64

Jan Klein, Jens Krokowski, Matthias Fischer, Rolf Wanka and Friedhelm Meyer auf der Heide
The Randomized Sample Tree: A Data Structure for Externally Stored 3D-Scenes
Paderborn. Work package 5. May 2002.

Abstract: We present a new algorithm for rendering highly complex 3D scenes of arbitrary topology. The specific feature of our method is that it makes possible an interactive navigation of scenes consisting of more than 16 GB of polygon data (95 million polygons) that cannot be stored in the main memory, but only on a local or remote hard disk.

For the computation of an approximate image of the scene, a sampling technique is used. In the preprocessing, a so called sample tree is built whose nodes contain randomly selected polygons from the scene. This tree uses only space linear in the number of polygons. In order to produce an image of the scene, the tree is traversed and polygons stored in the visited nodes are rendered. During the interactive walkthrough, parts of the sample tree are loaded from local or remote hard disk.

We implemented our algorithm in a prototypical walkthrough system. The quality of our images is comparable to images computed by the conventional z-buffer algorithm regardless of the scene topology.

Postscript file: ALCOMFT-TR-02-64.ps.gz (1863 kb).