Tour generation for exploration of 3D virtual environments

ABSTRACT

Navigation in complex and large-scale 3D virtual environments has been shown to be a difficult task, imposing a high cognitive load on the user. In this paper, we present a comprehensive method for assisting users in exploring and understanding such 3D worlds. The method consists of two distinct phases: an off-line computation step deriving a grand tour using the world geometry and any semantic target information as input, and an on-line interactive navigation step providing guided exploration and improved spatial perception for the user. The former phase is based on a voxelized version of the geometrical dataset that is used to compute a connectivity graph for use in a TSP-like formulation of the problem. The latter phase takes the output tour from the off-line step as input for guiding 3D navigation through the environment.

References

1. Akenine-Möller, T. 2001. Fast 3D triangle-box overlap testing. Journal of Graphics Tools 6, 1, 29--33.
2. Andújar, C., Vázquez, P.-P., and Fairén, M. 2004. Wayfinder: guided tours through complex walkthrough models. In Proceedings of EUROGRAPHICS, 499--508.
3. Beckhaus, S., Ritter, F., and Strothotte, T. 2001. Guided exploration with dynamic potential fields: the CubicalPath system. Computer Graphics Forum 20, 4, 201--210.
4. Bowman, D. A., Koller, D., and Hodges, L. F. 1997. Travel in immersive virtual environments: An evaluation of viewpoint motion control techniques. Proceedings of the IEEE Conference on Virtual Reality, 45--52.
5. Chase, W. G. 1986. Handbook of Perception and Human Performance, Vol II: Cognitive Processes and Performance. John Wiley and Sons, ch. Visual Information Processing.
6. Chittaro, L., and Burigat, S. 2004. 3D location-pointing as a navigation aid in virtual environments. In Proceedings of the ACM Conference on Advanced Visual Interfaces, 267--274.
7. Chittaro, L., Ranon, R., and Ieronutti, L. 2003. Guiding visitors of Web3D worlds through automatically generated tours. In Proceedings of the ACM Conference on 3D Web Tech, 27--38.
8. Cormen, T. H., Leiserson, C. E., and Rivest, R. L. 1990. Introduction to Algorithms. MIT Press, Cambridge, MA.
9. Darken, R. P., and Peterson, B. 2001. Spatial orientation, wayfinding, and representation. In Handbook of Virtual Environment Technology, Lawrence Erlbaum Associates, K. M. Stanney, Ed.
10. Darken, R. P., and Sibert, J. L. 1996. Wayfinding strategies and behaviors in large virtual worlds. In Proceedings of the ACM CHI'96 Conference on Human Factors in Computing Systems, 142--149.
11. Galyean, T. A. 1995. Guided navigation of virtual environments. In Proceedings of the ACM Symposium on Interactive 3D Graphics, 103--104.
12. Hanson, A. J., and Wernert, E. A. 1997. Constrained 3D navigation with 2D controllers. In Proceedings of the IEEE Conference on Visualization, 176--182.
13. Hong, L., Muraki, S., Kaufman, A., Bartz, D., and He, T. 1997. Virtual voyage: interactive navigation in the human colon. In Computer Graphics (SIGGRAPH '97 Proceedings), vol. 31, 27--34.
14. Igarashi, T., Kadobayashi, R., Mase, K., and Tanaka, H. 1998. Path drawing for 3D walkthrough. In Proceedings of the ACM Symposium on User Interface Software and Technology, 173--174.
15. Kaufman, A., and Shimony, E. 1986. 3D scan-conversion algorithms for voxel-based graphics. In Proceedings of the ACM Workshop on Interactive 3D Graphics, 45--75.
16. Liu, Y. K., Zalik, B., and Yang, H. 2004. An integer one-pass algorithm for voxel traversal. Computer Graphics Forum 23, 2, 167--172.
17. Ruddle, R. A. 2005. The effect of trails on first-time and subsequent navigation in a virtual environment. In Proceedings of the IEEE Conference on Virtual Reality, 115--122.
18. Tolman, E. C. 1948. Cognitive maps in rats and men. The Psychological Review 55, 4 (July), 189--208.
19. Vinson, N. G. 1999. Design guidelines for landmarks to support navigation in virtual environments. In Proceedings of the ACM CHI'99 Conference on Human Factors in Computing Systems, 278--285.
20. Wernert, E. A., and Hanson, A. J. 1999. A framework for assisted exploration with collaboration. In Proceedings of the IEEE Conference on Visualization, 241--248.
21. Witmer, B. G., and Singer, M. J. 1998. Measuring presence in virtual environments: A presence questionnaire. Presence 7, 3 (June), 225--240.

Index Terms

• Computing methodologies

  • Computer graphics

• Human-centered computing

  • Human computer interaction (HCI)