Adaptive Bounding Volume Hierarchies for Efficient Collision Queries
2009 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]
The need for efficient interference detection frequently arises in computer graphics, robotics, virtual prototyping, surgery simulation, computer games, and visualization. To prevent bodies passing directly through each other, the simulation system must be able to track touching or intersecting geometric primitives. In interactive simulations, in which millions of geometric primitives may be involved, highly efficient collision detection algorithms are necessary. For these reasons, new adaptive collision detection algorithms for rigid and different types of deformable polygon meshes are proposed in this thesis. The solutions are based on adaptive bounding volume hierarchies.
For deformable body simulation, different refit and reconstruction schemes to efficiently update the hierarchies as the models deform are presented. These methods permit the models to change their entire shape at every time step of the simulation. The types of deformable models considered are (i) polygon meshes that are deformed by arbitrary vertex repositioning, but with the mesh topology preserved, (ii) models deformed by linear morphing of a fixed number of reference meshes, and (iii) models undergoing completely unstructured relative motion among the geometric primitives. For rigid body simulation, a novel type of bounding volume, the slab cut ball, is introduced, which improves the culling efficiency of the data structure significantly at a low storage cost. Furthermore, a solution for even tighter fitting heterogeneous hierarchies is outlined, including novel intersection tests between spheres and boxes as well as ellipsoids and boxes. The results from the practical experiments indicate that significant speedups can be achieved by using these new methods for collision queries as well as for ray shooting in complex deforming scenes.
Place, publisher, year, edition, pages
Västerås: Mälardalen University , 2009. , p. 250
Series
Mälardalen University Press Dissertations, ISSN 1651-4238 ; 71
Keywords [en]
Bounding volume hierarchies, Collision detection, Rigid bodies, Deformable models, Data structures, Simulation, Animation, Three-dimensional graphics and realism
National Category
Computer Sciences
Research subject
Datavetenskap
Identifiers
URN: urn:nbn:se:mdh:diva-4665ISBN: 978-91-86135-18-8 (print)OAI: oai:DiVA.org:mdh-4665DiVA, id: diva2:133780
Public defence
2009-03-05, Alfa, Hus U, Mälardalens högskola, Högskoleplan 1, Västerås, 14:00 (English)
Opponent
Supervisors
2009-03-102009-01-142018-01-13Bibliographically approved