Fast Application of Inverse-Dynamic Forces to Articulated Bodies
This section describes Master's Thesis work by Preston Pfarner and explanatory background.
Forward-dynamic forces are dependent on positions and velocities, but not on other forces. Inverse-dynamic forces also have a dependence on other forces in the system. Finding consistent inverse-dynamic forces generally requires the solution of an inverse problem because of their mutual dependencies.
By using inverse-dynamic forces, constraints on bodies can be effected. One body can be constrained to remain attached to another, but still be free to rotate, for example. Work on this topic has been done by Barzel, Woodbury, and others.
Complex bodies can be constructed from simpler ones with constraints. An articulated figure can be constructed from simple rigid bodies by implementing their joints with constraints. While this method works and is conceptually simple, it leads to sizable efficiency costs. The system of equations in the inverse problem scales with the number of unconstrained degrees of freedom in the joints. Solving these equations typically takes about O(N2.3) time, where N is the total number of unconstrained degrees of freedom.
Articulated bodies can also be implemented by representing the space of relative motion between sub-bodies. Then all states in this space represent valid configurations of the articulated body. For any articulated body whose connectivity has a tree topology, further improvements can be made. This field has been explored by Featherstone and Lathrop.
Contributions from forward-dynamic forces that are applied to a child body can be propagated to parent bodies all the way back to the root body. There the acceleration in response to this force can be computed, and accelerations for child bodies are calculated back to the leaves. I will refer to this process as the articulated-body system. This method takes O(N) time. However, it is more limited than the dynamic constraint method as it cannot deal directly with cycles or with inverse-dynamic forces.
I have been working on a method that allows use of dynamic constraints in an articulated-body system. This allows use of the articulated-body method when its restrictions permit, and the less efficient dynamic constraint method for any remaining joints. By implementing this in a structured modeling system, the choice of algorithm can be hidden from the user, and can change dynamically throughout the course of the simulation.
By allowing the use of the more efficient method whenever possible, the algorithm will scale as O(N + Nc + c2.3), where N is the number of unconstrained degrees of freedom, c is the number of cycles in the articulated body. c cannot be greater than N, and is typically much smaller. This can result in a large speedup over the pure dynamic constraint method, while still preserving its generality.