Selection Based navigation in virtual environments

Abstract

An important aspect of Virtual Environments is navigation. Most of the time, the user controls the camera directly, allowing full access to the environment. But in some situations, it might be more desirable to have the software automatically generate locations for the camera and the paths needed to travel between those locations. This should enable the user to concentrate on other, more important tasks. The goal of this thesis is to determine if it is possible and feasible to provide users with the option to select an object(1), and then have the camera automatically travel to a destination from which the object can be viewed in its entirety, with as little obstruction in front of the camera as possible. In order to achieve this, various methods have been researched in previous literature for the phases needed to create this mode of navigation. First, the various phases of path planning are discussed. Static and dynamic environments are discussed separately for these phases, since they require different approaches. The pre-processing phase involves creating a roadmap, which can be done either manually or automatically. Since manual roadmap generation is not an option, we focus on the methods that enable software to automatically generate good roadmaps. Most of those methods are variations of the Probabilistic Roadmap Method (PRM). One of these variations randomly generates sample points, of which some can be used as either guard nodes or connectors between guard nodes [2]. Another variation that uses Voronoi diagrams to generate nodes seems to be a better fit for our goal [3]. It also uses circle-smoothing to create a C1-continuous path, which is a requirement for natural camera navigation. It is also possible to use deterministic Halton points [18] instead of random points to obtain a natural result with uniform coverage of the environment and consistent running times. A tricky part of roadmap generation is to make sure that narrow passages have decent node coverage. This can be done by using the bridge test [17] in addition to a more uniform sampling method. The second phase is the actual path planning algorithm. A few variations on the Dijkstra and A* search [24] algorithms are discussed. A* search is a well known and easily implementable search algorithm, and we will use it for both types of environment. However, dynamic environments require an altered version of the A* search algorithm that supports collision detection. One such algorithm is the Lazy PRM method [20]. Then, there is the post-processing phase of path planning, where camera orientation and speed during the course of the path will be calculated. It is essential that the viewer gets cues about where he is going, that the path is smooth and C1 continuous, and that the speed of the camera depends on the curvature of the path, to prevent motion sickness [6]. Also, it is recommended that a speed diagram is used, which gradually accelerates and decelerates speed when needed instead of abruptly changing it. Using a speed diagram makes the path C2 continuous and thus even more smooth. Finally, literature on camera positioning is briefly discussed, but we discover that brute force algorithms are still the driving force behind most of the methods. We will have to find some optimizations for brute force camera positioning that have not been mentioned in these papers. After the extensive literature section, a few possible optimizations to speed up camera positioning are suggested. Most of these are based on bounding volumes and reducing the amount of collision detection required. The next chapter describes our implementation, both the result and the difficulties and other interesting things we encountered during development. A manual of the application is provided in an appendix. Only the path planning methods for static environments have been implemented. Finally, we reach a conclusion and decide if selection-based navigation is possible with the techniques described in this thesis. (1) However, the method for selecting the object is a choice that should be left to the application designer and it will not be discussed in this thesis.