The randomized sample tree: A data structure for interactive walkthroughs in externally stored virtual environments

Beitrag bei einer Tagung
(Konferenzbeitrag)


Details zur Publikation

Autor(en): Klein J, Krokowski J, Wand M, Fischer M, Wanka R, Meyer auf der Heide F
Herausgeber: Sun H.; Peng Q.
Jahr der Veröffentlichung: 2002
Tagungsband: Proc. ACM Symp. on Virtual Reality Software and Technology (VRST)
Seitenbereich: 137-146
Sprache: Englisch


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. 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.



FAU-Autoren / FAU-Herausgeber

Wanka, Rolf Prof. Dr.
Professur für Informatik (Effiziente Algorithmen und Kombinatorische Optimierung)


Autor(en) der externen Einrichtung(en)
Eberhard Karls Universität Tübingen
Universität Paderborn


Zitierweisen

APA:
Klein, J., Krokowski, J., Wand, M., Fischer, M., Wanka, R., & Meyer auf der Heide, F. (2002). The randomized sample tree: A data structure for interactive walkthroughs in externally stored virtual environments. In Sun H.; Peng Q. (Eds.), Proc. ACM Symp. on Virtual Reality Software and Technology (VRST) (pp. 137-146). Hong Kong, HK.

MLA:
Klein, Jan, et al. "The randomized sample tree: A data structure for interactive walkthroughs in externally stored virtual environments." Proceedings of the Proceedings of the ACM Symposium on Virtual Reality Software and Technology (VRST), Hong Kong Ed. Sun H.; Peng Q., 2002. 137-146.

BibTeX: 

Zuletzt aktualisiert 2019-20-04 um 21:50