Thesis text (in .pdf format)
Abstract
This thesis presents a new structure called the Kinetic Vertical
Decomposition Tree (KVD-tree), used for the dynamic maintenance
of visibility information for a set of moving objects in space.
Visibility information is important in many applications, including
graphical rendering, animation, motion planning, etc. Yet visibility
is expensive to compute and difficult to update as the objects in
the environment move and occlude each other and the observer(s).
The KVD-tree is a single structure that not only (1) allows dynamic
maintenance of visibility, but also (2) represents a vertical
decomposition of the space, (3) allows collision detection
among moving objects, and (4) it is kinetically maintained based on
the kinetic data structures framework.
In terms of structure, the KVD-tree is a special type of Binary
Space Partition tree (BSP-tree), a hierarchical data structure
commonly used in solid modeling and computer graphics for feature
classification and visibility determination. For a scene composed
of polygonal objects, the BSP-tree corresponds to a hierarchy of
binary partitions of space using the hyperplanes that support the faces of
the polygons as partitioners. In the KVD-tree, additional cuts are
introduced from edges and vertices, so that a vertical decomposition
induced by the polygonal model is formed. The bounded complexity
of the cells in this decomposition allows the creation of certificates
that indicate times when the movement of objects causes a change
in the decomposition. These certificates are used within
the framework of kinetic data structures to identify when the
structure of the KVD-tree changes. The update of the KVD-tree involves
a series of local changes in the tree, accomplished by special
update algorithms. The certificates can be used to detect collisions
of objects in the scene, which can then be avoided by providing appropriate
actions to the update algorithms.
|
