João Comba's Research Page

Kinetic Vertical Decomposition Trees

Thesis text (in .pdf format)


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.