Accelerated Proximity Queries for Collision Detection and Brittle Fracture

Abstract

Interactive applications that aim for user immersion, such as computer games and training programs, require a high degree of realism of the virtual world. This goal is usually achieved by modeling the objects of the scene in great detail and generating physically realistic animations. However, the combination of both aspects makes it hard to maintain interactive rates. Previous work tackled these problems by either performing costly computations to obtain physically correct solutions, or by sacrificing accuracy to perform faster animations. In this dissertation we present techniques that use accelerated proximity queries to generate fractures, detect collisions between fragments, and detect self-collisions, in a physically plausible way, while achieving fast simulations, even when dealing with complex models. Detecting collisions and generating fracture surfaces are both geometric problems that deal with surface meshes. To generate a fracture, we calculate the crack surfaces by creating a Centroidal Voronoi Diagram of the body solving proximity queries between interior points of the object. Also, a novel algorithm to update collision detection structures after fracture is presented. These structures are used to efficiently compute contacts between newly created crack surfaces. We also introduce a Self-Collision Test Tree which precomputes the tests needed to perform a self-collision query on a bounding volume hierarchy. To test for self-collision of a node, we follow shape regularity methods which test for orientation and self-intersection of the projected contour of a patch. We present a novel algorithm to update normal cones with sublinear cost for the orientation test, and a novel method to test for self-intersection of the projected contour called the star-contour test, which is independent of the resolution of the mesh.