“Curved surfaces and coherence for non-penetrating rigid body simulation” by Baraff

  • ©David Baraff




    Curved surfaces and coherence for non-penetrating rigid body simulation

Session/Category Title: Dynamics




    A formulation for the contact forces between curved surfaces in resting (non-colliding) contact is presented. In contrast to previous formulations, constraints on the allowable tangential movement between contacting surfaces are not required. Surfaces are restricted to be twice-differentiable surfaces without boundary. Only finitely many contact points between surfaces are allowed; however, the surfaces need not be convex. The formulation yields the contact forces between curved surfaces and polyhedra as well. Algorithms for performing collision detection during simulation on bodies composed of both polyhedra and strictly convex curved surfaces are also presented. The collision detection algorithms exploit the geometric coherence between successive time steps of the simulation to achieve efficient running times.


    1. Baraff, D., “Analytical methods for dynamic simulation of non-penetrating rigid bodies,” Computer Graphics (Proc. SIGGRAPH), vol. 23, pp. 223-232, 1989.
    2. Baraff, D., “Determining frictional inconsistency for rigid bodies is NP-complete,” Technical Report TR 90-1112, Department of Computer Science, Comell University, 1990.
    3. Barzel, R. and Barr, A.H., “A modeling system based on dynamic constraints,” Computer Graphics (Proc. SIG- GRAPH), vol. 22, pp. 179-188, 1988.
    4. Canny, J., “Collision detection for moving polyhedra,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 8, no. 2, pp. 200-209, 1986.
    5. Cundall, P.A., “Formulation of a three-dimensional distinct element model — Part I. A scheme to represent contacts in a system composed of many polyhedral blocks,” international Journal of Rock Mechanics, Mineral Science and Geomechanics, vol. 25, no. 3, pp. 107-I 16, 1988.
    6. Featherstone, R., Robot Dynamics Algorithms, Kluwer, Boston, 1987.
    7. Forsythe, G.E., Malcolm, M.A., and Moler, C.B., Computer Methods for Mathematical Computations, Prentice Hall, Inc., Englewood Cliffs, 1977.
    8. Gilbert, E.G., Johnson, D.W., and Keerthi, S.S., “A fast procedure for computing the distance between complex objects in three space,” IEEE Journal of Robotics and Automation, vol. 4, pp. 193-203, 1988.
    9. Goldstein, H., Classical Mechanics, Addison-Wesley, Reading, 1983.
    10. Goyal, S., “Second order kinematic constraint between two bodies rolling, twisting and slipping against each other while maintaining point contact,” Technical Report TR 89-1043, Department of Computer Science, Cornell University, 1989.
    11. L6tstedt, P., “Mechanical systems of rigid bodies subject to unilateral constraints,” SIAM Journal of Applied Mathematics, vol. 42, no. 2, pp. 281-296, t 982.
    12. LStstedt, P., “Numerical simulation of time-dependent contact friction problems in rigid body mechanics,” SIAM Journal of Scientific Statistical Computing, vol. 5, no. 2, pp. 370-393, 1984.
    13. Moore, M. and Wilhelms, J., “Collision detection and response for computer animation,” Computer Graphics (Proc. SIGGRAPH), vot. 22, pp. 289-298, 1988.
    14. Murty, K.G., Linear Complementarity, Linear and Nonlinear Programming, Heldermann Verlag, Berlin, 1988.
    15. Nelmark, Ju.I. and Fufaev, N.A., Dynamics of Nonholonomic Systems, American Mathematical Society, 1972.
    16. Taylor, A.E. and Mann, R.M., Advanced Calculus, John Wiley & Sons, Inc., New York, 1983.
    17. Tomlin, J.A., “Robust implementation of Lemke’s method for the linear complementarity problem,” Technical Report SOL 76-24, Systems Optimization Laboratory, Department of Operations Research, Stanford University, 1976.

ACM Digital Library Publication:

Overview Page: