Linear-Time Dynamics using Lagrange Multipliers
David Baraff
Proceedings of the Annual Conference on Computer Graphics
and Interactive Techniques (SIGGRAPH)
Volume 30, Pages 137-146, 1996
Many simulation methods in computer graphics use reduced coordinates (also
known as generalized coordinates) to describe a system's degrees of freedom.
However, finding the reduced coordinates for a particular system can be
arbitrarily hard.
The goal is to significantly speed up the computation of a physics-based
system's dynamics when the number of constraints is proportional to the number
of bodies in the system.
This paper describes a method for computing the dynamics (Lagrange multipliers
that describe what constraint forces to apply)
of a system of n
bodies with O(n)
constraints and no closed loops. These constraints, each
of which is between exactly two bodies, are
called the primary constraints. A method is then described for
incorporating k
one-dimensional
auxiliary constraints, which include constraints
between a body and itself, constraints between more than two bodies, and
constraints which cause closed loops. The additional constraints add a cost
of O(kn)
, when k
is much smaller than n
.
Multiplier
methods have a ``drift" problem for which constraint stabilization techniques
have been proposed [4] [3].
Differential-algebraic equation (DAE) techniques are a more complex but more
powerful approach to solve this problem [5]. Reduced
coordinates completely eliminate the drift problem.
However, arguments in favor of multiplier methods have been given
[17] [3] [1]
[8]. Multiplier methods do not require
parameterization, have strong modularity, and allow the use of nonholonomic
constraints (such as relations between two objects' velocities) which
reduced coordinates do not allow.
However,
the dynamics for loop-free articulated rigid body systems can be computed in
O(n)
time [7] using reduced coordinates. However, if
reduced coordinates are not desired, this paper's algorithm is of practical
value even for articulated rigid body simulations.
Lagrange multiplier methods involve solving a matrix equation. Structures
with limited branching allow us to exploit bandedness of the matrices
[15] [12].
Different types of constraints are explored in [10].
Ways of expressing constraints as conditions on the accelerations of bodies in
a system have been explored [3] [1]
[8] [13]. See
[14] for a basic introduction to reduced coordinates and
multiplier approaches.
This paper uses block matrices [9] to formulate the problem.
The sparsity of block matrices are exploited following [6].
Auxiliary constraints are incorporated following [2].
The algorithm was tested on 2D and 3D rigid body systems, with a factor of
forty speedup over an earlier O(n3)
algorithm [2]. The
algorithm required no numerical adjustments, unlike an
earlier algorithm [13] that used a linear-time
reduced-coordinate method from [11].
This paper shows that the dynamics of a loop-free system of n
bodies can be
computed in O(n)
time using maximal coordinates and Lagrange multipliers
(as opposed to reduced coordinates). Closed loops and contact are later
incorporated into the computation.
The algorithm in this paper does not have linear complexity with respect to
the number of loop closures and contact points in the system being simulated.
- 1
-
D. Baraff.
Issues in computing contact forces for non-penetrating rigid bodies.
Algorithmica, 10:292-352, 1993.
- 2
-
D. Baraff.
Fast contact force computation for nonpenetrating rigid bodies.
Computer Graphics (SIGGRAPH), 28:23-34, 1994.
- 3
-
R. Barzel and A. H. Barr.
A modeling system based on dynamic constraints.
Computer Graphics (SIGGRAPH), 22:179-188, 1988.
- 4
-
J. Baumgarte.
Stabilization of constraints and integrals of motion in dynamical
systems.
Computer Methods in Applied Mechanics and Engineering, 1:1-16,
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 Academic Publishers, 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.
International Conference on Robotics and Automation, pages
689-694, 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,
1995.
- 13
-
P. Schröder and D. Zeltzer.
The virtual erector set: Dynamic simulation with linear recursive
constraint propagation.
In Proceedings of the 1990 Symposium on Interactive 3D
Graphics, volume 24, pages 23-31, 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 (SIGGRAPH), 26:221-230, 1992.
- 16
-
A. F. Vereshchagin.
Computer simulation of the dynamics of complicated mechanisms of
robot manipulators.
Engineering Cybernetics, 6:65-70, 1974.
- 17
-
A. Witkin, M. Gleicher, and W. Welch.
Interactive dynamics.
In Proceedings of the 1990 Symposium on Interactive 3D
Graphics, volume 24, pages 11-21, 1990.
ctj