We present a new data structure for rendering highly complex
virtual environments of arbitrary topology. The special feature of
our approach is that it allows an interactive navigation of scenes
consisting of more than 30 GB of polygon data (400 million
polygons) that cannot be stored in main memory, but only on a
local or remote hard disk. Furthermore, it allows interactive
rendering of substantially more complex scenes by instantiating
objects.
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 only uses space that is 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.
Analysis and experiments show that the quality of our images is
comparable to images computed by the conventional z-buffer
algorithm regardless of the scene topology.
In: Proceedings of the
ACM Symp. on Virtual Reality Software and Technology (VRST); 2002, pp. 157-146.