---
_id: '16399'
abstract:
- lang: eng
  text: "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.\r\n\r\nThe sampling process is done
    in the preprocessing. There, the polygons are randomly distributed in our hierarchical
    data structure, the randomized sample tree. This tree only uses 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 walkthrough, parts of the sample tree are loaded
    from local or remote hard disk.\r\n\r\nWe 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."
author:
- first_name: Jan
  full_name: Klein, Jan
  last_name: Klein
- first_name: Jens
  full_name: Krokowski, Jens
  last_name: Krokowski
- first_name: Matthias
  full_name: Fischer, Matthias
  id: '146'
  last_name: Fischer
- first_name: Michael
  full_name: Wand, Michael
  last_name: Wand
- first_name: Rolf
  full_name: Wanka, Rolf
  last_name: Wanka
- first_name: Friedhelm
  full_name: Meyer auf der Heide, Friedhelm
  id: '15523'
  last_name: Meyer auf der Heide
citation:
  ama: 'Klein J, Krokowski J, Fischer M, Wand M, Wanka R, Meyer auf der Heide F. The
    Randomized Sample Tree: A Data Structure for Interactive Walk-Throughs in Externally
    Stored Virtual Environments. <i>Presence: Teleoperators and Virtual Environments</i>.
    2004:617-637. doi:<a href="https://doi.org/10.1162/1054746043280619">10.1162/1054746043280619</a>'
  apa: 'Klein, J., Krokowski, J., Fischer, M., Wand, M., Wanka, R., &#38; Meyer auf
    der Heide, F. (2004). The Randomized Sample Tree: A Data Structure for Interactive
    Walk-Throughs in Externally Stored Virtual Environments. <i>Presence: Teleoperators
    and Virtual Environments</i>, 617–637. <a href="https://doi.org/10.1162/1054746043280619">https://doi.org/10.1162/1054746043280619</a>'
  bibtex: '@article{Klein_Krokowski_Fischer_Wand_Wanka_Meyer auf der Heide_2004, title={The
    Randomized Sample Tree: A Data Structure for Interactive Walk-Throughs in Externally
    Stored Virtual Environments}, DOI={<a href="https://doi.org/10.1162/1054746043280619">10.1162/1054746043280619</a>},
    journal={Presence: Teleoperators and Virtual Environments}, author={Klein, Jan
    and Krokowski, Jens and Fischer, Matthias and Wand, Michael and Wanka, Rolf and
    Meyer auf der Heide, Friedhelm}, year={2004}, pages={617–637} }'
  chicago: 'Klein, Jan, Jens Krokowski, Matthias Fischer, Michael Wand, Rolf Wanka,
    and Friedhelm Meyer auf der Heide. “The Randomized Sample Tree: A Data Structure
    for Interactive Walk-Throughs in Externally Stored Virtual Environments.” <i>Presence:
    Teleoperators and Virtual Environments</i>, 2004, 617–37. <a href="https://doi.org/10.1162/1054746043280619">https://doi.org/10.1162/1054746043280619</a>.'
  ieee: 'J. Klein, J. Krokowski, M. Fischer, M. Wand, R. Wanka, and F. Meyer auf der
    Heide, “The Randomized Sample Tree: A Data Structure for Interactive Walk-Throughs
    in Externally Stored Virtual Environments,” <i>Presence: Teleoperators and Virtual
    Environments</i>, pp. 617–637, 2004.'
  mla: 'Klein, Jan, et al. “The Randomized Sample Tree: A Data Structure for Interactive
    Walk-Throughs in Externally Stored Virtual Environments.” <i>Presence: Teleoperators
    and Virtual Environments</i>, 2004, pp. 617–37, doi:<a href="https://doi.org/10.1162/1054746043280619">10.1162/1054746043280619</a>.'
  short: 'J. Klein, J. Krokowski, M. Fischer, M. Wand, R. Wanka, F. Meyer auf der
    Heide, Presence: Teleoperators and Virtual Environments (2004) 617–637.'
date_created: 2020-04-03T11:42:11Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
doi: 10.1162/1054746043280619
language:
- iso: eng
page: 617-637
publication: 'Presence: Teleoperators and Virtual Environments'
publication_identifier:
  issn:
  - 1054-7460
  - 1531-3263
publication_status: published
status: public
title: 'The Randomized Sample Tree: A Data Structure for Interactive Walk-Throughs
  in Externally Stored Virtual Environments'
type: journal_article
user_id: '15415'
year: '2004'
...