|
CMU-RI-TR-95-44
Robotics Institute
School of Computer Science, Carnegie Mellon University
CMU-RI-TR-95-44
Linear-Time Dynamics using Lagrange Multipliers
David Baraff
January 1996
CMU-RI-TR-95-44.ps.Z
Keywords:
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.
pages
|