“Contact trees: adaptive contact sampling for robust dynamics” by Kaufman, Sueda and Pai

  • ©Danny M. Kaufman, Shinjiro Sueda, and Dinesh K. Pai




    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.


    1. Baerentzen, J. A. 2005. Signed distance computation using the angle weighted pseudonormal. IEEE Transactions on Visualization and Computer Graphics 11, 3, 243–253.
    2. Barzel, R., Hughes, J. F., and Wood, D. N. 1996. Plausible motion simulation for computer graphics animation. In Computer Animation and Simulation 96, 183–197.
    3. Frisken, S. F., Perry, R. N., Rockwood, A. P., and Jones, T. R. 2000. Adaptively sampled distance fields: a general representation of shape for computer graphics. In Proceedings of ACM SIGGRAPH 00, 249–254.

ACM Digital Library Publication:

Overview Page: