## Contact Handling

Contact is a phenomenon that introduces discontinuities in the motion of objects. In comparison to contact-free motion, the computation of dynamic motion under contact is far more complicated, due to such discontinuities. Deformable objects present many degrees of freedom, making the problem high-dimensional. Furthermore, deformable objects suffer from large contact areas and complex frictional effects. Among the various problems in the simulation of contact and deformations, our research has addressed three major topics: simulation of dynamic deformations, collision detection, and collision response. Our techniques are not restricted to one application target, and can be applied on different areas depending on their accuracy and performance. Some examples include offline computer animation, video games, medical simulation, or haptic rendering.

### Collision response

Robust approaches to contact dynamics formulate contact handling as a constrained optimization problem. For deformable objects with many degrees of freedom and many contacts, such approaches have been traditionally considered as impractical. Instead, we have designed nested iterative solvers for both the deformations and the contact forces that lead to robust yet efficient contact handling of deformable objects (Otaduy et al. 2009). We are using such efficient solutions for constraint-based contact handling on a diverse range of applications, including haptic rendering and surgical simulation.

We have designed other extensions to constraint-based collision response methods too. One remarkable example is modeling adhesion or sticking forces in a constraint-based framework, which allows a seamless inclusion of such forces in standard constraint-based solvers (Gascón et al. 2010). We have also addressed the computational cost incurred by scenarios that combine rigid and deformable models, which produce a large number of inertially coupled contacts (Miguel and Otaduy 2011).

Despite the success of constraint-based collision response, many engineering applications still rely on penalty-based collision response methods, due to their higher efficiency. Penalty-based methods, however, are regarded as less robust and prone to discontinuities and instabilities. We have designed a novel penalty method that models continuous forces and involves only small changes in practice (Tang et al. 2012).

### Collision detection

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 (Kim et al. 2002, Kim et al. 2002b), or closest features between the objects. Collision detection may be answered using a variety of acceleration data structures, such as bounding volume hierarchies, spatial partitioning, or distance fields (Sud et al. 2004). And, given a certain data structure, the collision detection problem includes both the update of the data structure and the query itself.

One of the most complicated problems in collision detection is to efficiently detect collisions of an object against itself, a problem known as self-collision detection. The complexity of this problem is due to the difficulty to discern features that are actually colliding from others that are simply topologically nearby. Hierarchical algorithms for self-collision detection have been known for almost twenty years, but the existing algorithms had to trade efficiency for robustness. We have designed a novel hierarchical algorithm, based on star-shaped polygons and a self-collision test tree that solves self-collision detection queries efficiently (Schvartzman et al. 2010).

Simulations of rigid or deformable bodies often rely on precomputed data structures for collision detection. However, in simulations with topological changes, such as fracture, the data structures are typically recomputed when the objects break. We have designed novel collision detection data structures that can be efficiently updated under brittel fracture events (Glondu et al. 2012), algorithms for local restructuring of data structures under progressive fracture (Steinemann et al. 2009), and also algorithms that balance restructuring and rebuilding under general fracture simulations (Otaduy et al. 2007).

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. We have applied this concept to accelerate collision detection on adaptive simulations based on tetrahedral meshes (Otaduy et al. 2007), on point-based animations (Steinemann et al. 2008), or even for self-collision detection based on normal bounds (Schvartzman el al. 2009).

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. We have designed efficient approximate collision detection methods for haptic rendering, employing multiresolution approaches based on dual hierarchies (Otaduy and Lin 2003), selection of levels of detail based on perceptual criteria Otaduy and Lin 2003b, or representations that combine low-resolution geometry and a high-resolution roughness texture (Otaduy et al. 2004).