Linear-time dynamics using Lagrange multipliers

Publisher Website
Google Scholar
Abstract
Current linear-time simulation methods for articulated figures are based exclusively on reduced-coordinate formulations. This pa- per describes a general, non-iterative linear-time simulation method based instead on Lagrange multipliers. Lagrange multiplier meth- ods are important for computer graphics applications because they bypass the difficult (and often intractable) problem of parameter- izing 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 con- straints' topology are needed. Bodies need not be rigid, constraints can be of various dimensions, and unlike reduced-coordinate ap- proaches, 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 pro- vided in pseudocode.

This publication has 7 references indexed in Scilit: