Implicit bounding volumes and bounding volume hierarchies
Leonidas Guibas, An Nguyen · 2006
Computing and maintaining proximity information between objects are crucial tasks in modeling and simulating the world around us as in robotic motion planning, physics based simulation, molecular dynamics, etc. The information is important as objects in real life do not normally penetrate and most of the interactions between objects happen when they are near each other. Popular methods for answering proximity and collision queries use bounding volume hierarchies (BVHs). In these methods a bounding volume hierarchy is constructed for each object so that the object is captured in more and more details as one goes down the hierarchy. Bounding volume hierarchies allow one to determine quickly if two objects are not in close proximity. The further apart the objects are, the less traversal the methods have to do and thus the less work in determining the proximity between the objects. This dissertation presents results that show the power of implicit bounding volumes and implicit bounding volume hierarchies for proximity query and collision detection. The first part of the dissertation, we propose to use of zonotopes (Minkoswki sums of line segments) as bounding volumes. By defining the bounding volumes implicitly through generating segments, complicated shapes can be captured tightly with a small number of segments. Efficient algorithms for computing exact and approximate optimal bounding volumes, as well as algorithms to detect interference between zonotopes are provided. In the second part of this dissertation, we study ways to represent bounding volume hierarchies implicitly as combinatorial objects, making them stable when objects undergo large deformation. We rigourously analyze the performance of our data structures and algorithms, and obtain the first data structure for bounding volume hierarchies that is maintainable under motion and deformation. We also show that proximity structures such as (1 + e) well separated pair decompositions, (I + e)-spanners, approximate Voronoi diagrams, and approximate k-centers can be obtained from our bounding volume hierarchies, and these structures are also maintainable under motion and deformation.