Document Server@UHasselt >
School for Information Technology >
Master theses >
Please use this identifier to cite or link to this item:
|Title: ||Selection Based navigation in virtual environments|
|Authors: ||VAN WEZEL, Robertus|
|Issue Date: ||2005|
|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 . Another variation that uses Voronoi diagrams to generate nodes
seems to be a better fit for our goal . 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  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  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  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 .
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 . 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
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
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.|
|Type: ||Theses and Dissertations|
|Appears in Collections: ||Master theses|
Files in This Item:
|N/A||1.92 MB||Adobe PDF|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.