“Fast contact force computation for nonpenetrating rigid bodies” by Baraff

A new algorithm for computing contact forces between solid objects with friction is presented. The algorithm allows a mix of contact points with static and dynamic friction. In contrast to previous approaches, the problem of computing contact forces is not transformed into an optimization problem. Because of this, the need for sophisticated optimization software packages is eliminated. For both systems with and without friction, the algorithm has proven to be considerably faster, simple, and more reliable than previous approaches to the problem. In particular, implementation of the algorithm by nonspecialists in numerical programming is quite feasible.

1. D. Baraff. Analytical methods for dynamic simulation of non-penetrating rigid bodies. In Computer Graphics (Proc. SIGGRAPH), volume 23, pages 223-232. ACM, July 1989.
2. D. Baraff. Curved surfaces and coherence for non-penetrating rigid body simulation. In Computer Graphics (Proc. SIG-GRAPH), volume 24, pages 19-28. ACM, August 1990.
3. D. Baraff. Issues in computing contact forces for non-penetrating rigid bodies. Algorithmica, 10:292-352, 1993.
4. R.W. Cottle and G.B. Dantzig. Complementary pivot theory of mathematical programming. Linear Algebra and its Appli-cations, 1:103-125, 1968.
5. R.W. Cottle, J.S. Pang, and R.E. Stone. The Linear Comple-mentarity Problem. Academic-Press, Inc., 1992.
6. P. Gill, S. Hammarling, W. Murray, M. Saunders, and M. Wright. User’s guide for LSSOL: A Fortran package for constrained linear least-squares and convex quadratic pro-gramming. Technical Report Sol 86-1, Systems Optimiza-tion Laboratory, Department of Operations Research, Stanford University, 1986.
7. P. Gill, W. Murray, M. Saunders, and M. Wright. User’s guide for QPSOL: A Fortran package for quadratic programming. Technical Report Sol 84-6, Systems Optimization Labora-tory, Department of Operations Research, Stanford University, 1984.
8. P. Gill, W. Murray, M. Saunders, and M. Wright. User’s guide for NPSOL: A Fortran package for nonlinear programming. Technical Report Sol 86-2, Systems Optimization Labora-tory, Department of Operations Research, Stanford University, 1986.
9. P.E. Gill, W. Murray, M.A. Saunders, and H.W. Wright. Main-taining LU factors of a general sparse matrix. Linear Algebra and its Applications, 88/89:239-270, 1987.
10. P. L~ otstedt. Numerical simulation of time-dependent contact friction problems in rigid body mechanics. SIAM Journal of Scientific Statistical Computing, 5(2):370-393, 1984.
11. R.E. Marsten. The design of the XMP linear program-ming library. ACM Transactions on Mathematical Software, 7(4):481-497, 1981.
12. B. Murtagh and M. Saunders. MINOS 5.1 User’s guide. Technical Report Sol 83-20R, Systems Optimization Labora-tory, Department of Operations Research, Stanford University, 1987.
13. M. Saunders. Personal communication. September 1993.