Contact trees: adaptive contact sampling for robust dynamics

Algorithms for rigid body dynamics with contact are well known, but challenging to implement due to the interplay between large time steps, general purpose collision detection packages and pragmatic approximations of the underlying inequality constrained contact problems. While research on rigid body simulation has focused heavily both on contact resolution and collision detection, contact generation has essentially been ignored. Most contact resolution algorithms presume that an ideal set of contacts, fully characterizing system constraints, are available, while collision detection methods generally presume that their task is finished once a set of intersecting primitives has been identified. Bridging the gap between these domains, by generating representative contact samples, contact point locations and their associated normals, is crucial for the accuracy, robustness and speed of simulation. This is highlighted by two observations:

• A contact resolution method, no matter how robust and accurate, is restricted by the quality of constraints it has been provided with.

• Narrow phase collision detection algorithms, although in some senses highly optimized, often perform too much and the wrong kind of work because they do not consider the form of input desired by the physical solver.