Miguel A. Otaduy: Research

Collision Detection and Proximity Queries

Collision detection is a fundamental problem in computer animation, physically-based modeling, geometric modeling, and robotics. It is a geometric problem that deals with finding out whether and where objects intersect, or computing separation distance, penetration depth, or closest features between the objects.

One of the most complex problems associated to collision detection is the computation of the penetration depth between two intersecting objects, which can be answered either in a local [→] or in a global manner [→]. Collision detection may be answered using a variety of acceleration data structures, such as bounding volume hierarchies, spatial partitioning, or distance fields [→]. And, given a certain data structure, the collision detection problem includes both the update of the data structure and the query itself. In simulations with topological changes, such as fracture, the data structures are typically recomputed when the objects break, but an efficient restructuring algorithm can reduce the overall computational cost [→].

Haptic rendering, due to its stringent computational requirements, calls for extremely efficient collision detection. At the same time, it allows for approximate methods geared to computing perceptually accurate forces. Some of the efficient approximate collision detection methods for haptic rendering employ multiresolution approaches based on dual hierarchies [→], selection of levels of detail based on perceptual criteria [→], or representations that combine low-resolution geometry and a high-resolution roughness texture [→].

On deformable objects with sparse contact, the cost of updating the acceleration data structures is often higher than the cost of the query itself. However, if the deformation is defined as a combination of a few linear transformations, it is possible to update the data structures with a cost linear in the number of transformations, regardless the combinatorial complexity of the objects. This concept can be applied, for example, to adaptive simulations on tetrahedral meshes [→], or point-based animations [→].

Students: Jorge Gascón [→], Sara Schvartzman [→].

Collaborators: Ming Lin (UNC) [→], Denis Steinemann (VirtaMed) [→], Young Kim (EWHA) [→]. Avneesh Sud (Microsoft) [→]. Dinesh Manocha (UNC) [→], Stephane Redon (INRIA) [→], Markus Gross (ETH Zurich) [→].

Last modified June 10, 2009