“Linear-time dynamics using Lagrange multipliers” by Baraff

Current linear-time simulation methods for articulated figures are based exclusively on reduced-coordinate formulations. This paper describes a general, non-iterative linear-time simulation method based instead on Lagrange multipliers. Lagrange multiplier methods are important for computer graphics applications because they bypass the difficult (and often intractable) problem of parameterizing a system’s degrees of freedom. Given a loop-free set of n equality constraints acting between pairs of bodies, the method takes O(n) time to compute the system’s dynamics. The method does not rely on matrix bandwidth, so no assumptions about the constraints’ topology are needed. Bodies need not be rigid, constraints can be of various dimensions, and unlike reduced-coordinate approaches, nonholonomic (e.g. velocity-dependent) constraints are allowed. An additional set of k one-dimensional constraints which induce loops and/or handle inequalities can be accommodated with cost O(kn). This makes it practical to simulate complicated, closed-loop articulated figures with joint-limits and contact at interactive rates. A complete description of a sample implementation is provided in pseudocode.

1. D. Baraff. Issues in computing contact forces for nonpenetrating rigid bodies. Algorithmica, 10:292-352, 1993.
2. D. Baraff. Fast contact force computation for nonpenetrating rigid bodies. Computer Graphics (Proc. SIGGRAPH), 28:23- 34, 1994.
3. R. Barzel and A.H. Barr. A modeling system based on dynamic constraints. In Computer Graphics (Proc. SIGGRAPH), volume 22, pages 179-188. ACM, July 1988.
4. J. Baumgarte. Stabilization of constraints and integrals of motion in dynamical systems. Computer Methods in Applied Mechanics, pages 1-36, 1972.
5. K.E. Brenan, S.L. Campbell, and L.R. Petzold. Numerical Solution of Initial-value Problems in Differential-algebraic Equations. North-Holland, 1989.
6. I.S. Duff, A.M. Erisman, and J.K. Reid. Direct Methods for Sparse Matrices. Clarendon Press, 1986.
7. R. Featherstone. Robot Dynamics Algorithms. Kluwer, 1987.
8. M. Gleicher. A Differential Approach to Graphical Manipulation. PhD thesis, Carnegie Mellon University, 1994.
9. G. Golub and C. Van Loan. Matrix Computations. John Hopkins University Press, 1983.
10. C. Lanczos. The Variational Principles of Mechanics. Dover Publications, Inc., 1970.
11. R.H. Lathrop. Constrained (closed-loop) robot simulation by local constraint propagation. In International Conference on Robotics and Automation, pages 689-694. IEEE, 1986.
12. D. Negrut, R. Serban, and F.A. Potra. A topology based approach for exploiting the sparsity of multibody dynamics. Technical Report 84, Department of Mathematics, University of Iowa, December 1995.
13. E Schr6der and D. Zeltzer. The virtual erector set: Dynamic simulation with linear recursive constraint propagation. In Proceedings 1990 Symposium on Interactive 3d Graphics, volume 24, pages 23-31, March 1990.
14. A. Shabana. Dynamics of Multibody Systems. Wiley, 1989.
15. M.C. Surles. An algorithm with linear complexity for interactive, physically-based modeling of large proteins. Computer Graphics (Proc. SIGGRAPH), 26:221-230, 1992.
16. A.F. Vereshchagin. Computer simulation of the dynamics of complicated mechansisms of robot manipulators. Engineering Cybernetics, 6:65-70, 1974.
17. A. Witkin, M. Gleicher, and W. Welch. Interactive dynamics. In Proceedings 1990 Symposium on Interactive 3d Graphics, volume 24, pages 11-21, March 1990.