Inverse Kinematics

What is inverse kinematics? As it relates to computer graphics, forward kinematics involves a transformation from joint angles to 3D positions. Given some articulated figure, we can describe the figure by relating each joint angle to the limb it is attached to. Given the angles in question, we can straightforwardly calculate the end points of the limbs using coordinate transforms. Inverse kinematics asks, given a desired end point or position for an articulated figure, can we calculate the angles?

Forward kinematics is simple, because a set of joint angles specifies exactly one position. Inverse kinematics, however, is difficult: most real systems are underconstrained, so for a given goal position, there could be infinite solutions (i.e. many different joint configurations could lead to the same endpoint). The field of robotics has developed many inverse kinematics systems which, due to their constraints, have closed-form solutions. The inverse kinematics problem for computer animation is much harder because it must work for arbitrary figures, like human arms or legs.

The Math

Several techniques for solving inverse kinematics problems exist. An iterative approach utilizing the Jacobian matrix was chosen for this project. For sufficiently small changes, the change in angle and change in position are linearly related by the Jacobian matrix:

dX= J(Theta)dTheta (1)

where the Jacobian matrix J is the defined as follows:

J= [dX/dTheta1 dX/dTheta2 ... dX/dThetaN] (2)

The column vectors dX/dthetai are the partial derivatives of the end point with respect to the ith joint angle Thetai.

Thus, we can rewrite (1) as

dTheta= J-1dX (3)

This is only valid when J is nonsingular. With articulated figures, however, J is quite often irregularly shaped, and has no inverse. A Moore-Penrose pseudoinverse is a good approximation, and will work for matrices of any shape. The pseudoinverse of a matrix M is the unique matrix denoted M+ that has the following properties [1,2]:

  1. MM+M=M
  2. M+MM+=M+
  3. (M+M)T=M+M
  4. (MM+)T=MM+
Boullion and Odell [1] present an iterative method for calculating the pseudoinverse of arbitrary matrices. Thus, the heart of the inverse kinematics iterative solution is the equation

dTheta= J+dX (4)

Choose dX to be a small vector in the direction from the end point to the goal, calculate the pseudoinverse of the Jacobian, and then calculate the change in Theta. Increase Theta by dTheta and repeat the process. This technique will eventually converge on the goal point.

The Jacobian method, with the nice property of convergance, is not necessarily optimal. Other methods exist which minimize energy spent (mainly used in robotics), as well as methods which minimize the length of the path travelled. For purposes of this project, the Jacobian works nicely because of the interactive nature. The user drags the mouse in the direction of the desired path, and the Jacobian method will follow it.

Korein and Badler [3] present an optimized approach to inverse kinematics. The technique is hierarchical. Instead of calculating the change in all the angles at once, the base segment is moved so that the goal point is in the "reach space" of the rest of the segments. Then, the base segment is fixed, and the next segment is moved so that the goal point is in the reach space of the rest of the segments. The process is repeated until the final segment moves to the goal point. Korein and Badler also present a technique for turning and under-constrained system into a system of N equations in N unknowns by introducing new constraints using a Lagrangian operator.

References

1
Boullion, T. and Odell, P. Generalized Inverse Matrices. New York. : Wiley-Interscience, 1971.

2
Cline, R. Elements of the Theory of Generalized Inverses for Matrices. Newton, Mass. : EDC/UMAP, 1979.

3
Korein, J. and Badler, N. "Techniques for generating the goal directed motion of articulated structures." IEEE Computer Graphics and Applications, 2(9), 71-81.

4
Watt, A. and Watt M. Advanced Animation and Rendering Techniques: Theory and Practice. New York: ACM Press, 1992.

5
Zhao, J. and Badler, N. "Inverse kinematics positioning using nonlinear programming for highly articulated figures." ACM Transactions on Graphics, 13(4), 313-336.