The Randomized Sample Tree: A Data Structure for Externally Stored Virtual Environments

Meyer auf der Heide F, Fischer M, Krokowski J, Klein J, Wanka R, Wand M (2004)

Publication Language: English

Publication Type: Journal article, Original article

Publication year: 2004

Journal

Presence-Teleoperators and Virtual Environments Massachusetts Institute of Technology Press (MIT Press): STM Titles

Publisher: Massachusetts Institute of Technology Press (MIT Press): STM Titles

Book Volume: Vol. 13, No. 6, The MIT Press

Pages Range: 617-637

Journal Issue: 6

URI: http://www.upb.de/cs/ag-madh/WWW/wanka/pubs/abstracts/VRST02ABS.html

DOI: 10.1162/1054746043280619

Abstract

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 in very large scenes (30 GB/400 million polygons in our benchmark scenes) 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. The sampling process is done in the preprocessing. There, the polygons are randomly distributed in our hierarchical data structure, the randomized sample tree. This tree uses only space that is linear in the number of polygons. In order to produce an approximate image of the scene, the tree is traversed and polygons stored in the visited nodes are rendered. During the interactive walk-through, parts of the sample tree are loaded from a local or remote hard disk. We implement our algorithm in a prototypical walk-through 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. © 2005 by the Massachusetts Institute of Technology.

Authors with CRIS profile

Rolf Wanka Professur für Informatik (Effiziente Algorithmen und Kombinatorische Optimierung)

Involved external institutions

Universität Paderborn DE Germany (DE) Eberhard Karls Universität Tübingen DE Germany (DE)

How to cite

APA:

Meyer auf der Heide, F., Fischer, M., Krokowski, J., Klein, J., Wanka, R., & Wand, M. (2004). The Randomized Sample Tree: A Data Structure for Externally Stored Virtual Environments. Presence-Teleoperators and Virtual Environments, Vol. 13, No. 6, The MIT Press(6), 617-637. https://dx.doi.org/10.1162/1054746043280619

MLA:

Meyer auf der Heide, Friedhelm, et al. "The Randomized Sample Tree: A Data Structure for Externally Stored Virtual Environments." Presence-Teleoperators and Virtual Environments Vol. 13, No. 6, The MIT Press.6 (2004): 617-637.

BibTeX: Download