Inverse Kinematics

David Grimes
William Pentney
Winter 2001

The Inverse Kinematic Problem

    One primary issue in computer animation is the desire for a suitable method of making computer-generated objects move in a realistic fashion. One primary method of doing so, called forward kinematics, involves setting the position and orientation of an object by manipulating the object's position at each turn. This method is relatively easy to implement, but is far more difficult to use, as the amount of detail involved in moving the figure can be quite significant. Another approach, inverse kinematics, takes the opposite approach: by specifying a goal position for a particular point on the object, the computer is left to move the object to the position in an appropriate manner.

    A typical inverse kinematic system manipulates objects through altering various parameters that define the object's position, called degrees of freedom. Typically, degrees of freedom, or DOFs, specify a movement of the object, or a portion of the object, through either Cartesian space (a translation) or polar space (a rotation). Our project, for instance, manipulates a human figure which has been specified by a series of nodes or "bones", connected by joints which may rotate along a given number of axes. The figure is defined internally as a tree of nodes. Each node has a set of transformations, and each generally has at least one DOF that modifies the transformation. A node's position is calculated by applying the DOF transformations from the earlier ancestor (the root node), then the second earliest ancestor, and so on, walking down the tree to the node in question.

The Method

    An object's position is given by a position vector q, containing the values of all DOFS. The vector containing the positions of each node x is given by the equation

x = f(q),

    where f(q) applies the series of transformations described above. Constraints are placed on the position of the figure through the placement of handles on the body; this is done in our program using the left mouse button. Once a handle is placed, it places a constraint on the body; the program attempts at all times to minimize the distance between a handle and the point on the body it corresponds to. Given a handle vector h and a desired position d, the constraint is defined by the equation

h - d = 0.

     The handle may be moved through clicking and dragging; this causes the program to move the figure so as to satisfy these constraints as best as possible, while maintaining smooth movement by manipulating the components of q incrementally. This is done using a gradient descent search. Thus the constraints are not truly hard constraints, but more like goal functions. This is analogous to putting springs between the current and desired positions (or rotations). The position vector is recalculated using the equation q = q + dq, where

dq = e * g

    with an appropriately small constant e and g defined by

 g =2( dc1/dq * c1  + dc2/dq * c2 + ... + dcn/dq * cn ),





    where  each ci represents a constraint. (The set of derivatives of the constraints with respect to q represents a Jacobian matrix.) This is called an energy minimization approach; the basic approach is described in [1].

Issues

By far the most difficult part of the project was the computation of the Jacobian matrix. Although an element by element computation of each of the derivatives in the matrix is very straightforward, it is very inefficient. Thus we spend a long time designing a recursive algorithm that only computes the derivative for a particular DOF once, and keeps a chain of transformations as it traverses the skeleton tree. The computation for gradient descent step takes very little time and allows for greater accuracy without giving up interactivity.

Another difficult issue is that often times the system is under-specified, that is there are many ways the DOFs can be changed to meet the constraints. This results in greater instability, and awkward behavior. We considered "intelligent" manners of constraining the movement of the body so as to fulfill the constraints more reasonably. For instance, we added the ability to restrict movement of DOFs relative to a certain constraint by introducing artificial independence based on the distance in the tree. The user can select either a hard cut-off value, or to simply weight the more distant DOFs less. A somewhat "hackier" addition allows the user to completely lock DOFs associated with a particular node. These techniques permit one to stipulate that a limb may move but the torso should always stand still.

    One issue in coding the inverse kinematic solver was the determination of an appropriate test for termination of the gradient descent search. Currently, the movement terminates when the slope of the curve drawn by plotting the past 15 calculations of dq falls below a given small constant. At this point, the search is considered to have very nearly found a minimum (or at least a local minimum). 
 
 
 

References

[1] C. Welman. Inverse kinematics and geometric constraints for articulated figure manipulation. M.S. thesis, Simon Fraser University, 1993.
 
 
 

Downloading

(Requires libc.so.6, libX11.so.6, MesaGL) Linux executable (ikgui)