
CMURITR9544
Robotics Institute
School of Computer Science, Carnegie Mellon University
CMURITR9544
LinearTime Dynamics using Lagrange Multipliers
David Baraff
January 1996
CMURITR9544.ps.Z
Keywords:
Current lineartime simulation methods for articulated figures are
based exclusively on reducedcoordinate formulations. This paper
describes a general, noniterative lineartime 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 loopfree 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 reducedcoordinate approaches, nonholonomic
(e.g. velocitydependent) constraints are allowed. An additional set
of k onedimensional constraints which induce loops and/or handle
inequalities can be accommodated with cost O(kn). This makes it
practical to simulate complicated, closedloop articulated figures
with jointlimits and contact at interactive rates. A complete
description of a sample implementation is provided in pseudocode.
pages
