Abstract

Inverse kinematics is the process of determining the parameters of a jointed flexible object in order to achieve a desired pose. For example, with a 3D model of a human body, what are the required wrist and elbow angles to move the hand from a resting position to a waving position? This question is highly valid for computer animation and 3D modeling. Although, large databases of motion capture have lessened the need for IK, but research is picking up pace in the direction where we can combine IK with motion capture to get more control over the simulations and animations.

 

What is Inverse Kinematics?

There a lot many ways to approach this problem and literature is full of different techniques specialized for different types of problems. The approach we use to solve this IK problem is by using optimazation techniques.
In an IK problem, we have to come up with the joint angles for a particular position. The equation can be written as:

where you have to take the inverse of the function to come up with a set of angles. Now the analytical methods which directly use the inverse can only handle a few joints (max two). As the number of joints increases, the problem gets complex and complex and the analytical methods dont work at all. So there are a number of numerical technqiues which are used to solve IK problems. IK problems can have solutions ranging from no solution to mutiple solutions like in the figure given below:

As the figure shows that there could be multiple ways of positioning the endeffector at the goal position. Then, there comes the question of the optimal solution.

Goal of the Project

The goal of the project is to make an animated character and apply IK on it. The systems should be an interrative one where we can choose a handle and darg it to specify the desired position. The figure below illustrates the idea:

IK approach

There are a lot of techniques that solve this inverse kinematics problem:

• Analytical Methods: These methods are restricted to one or two joints as it is very difficult to come up with the inverse of non-linear functions.

• Jacobian-based Methods: There are varieties of mothods which use the Jacobian, its inverse, pseudo-inverse or transpose to come up with solutions of the IK problem. They iterate and try to make the end-effector come closer to the goal. But in order to impose constraintsm, a lot of effort is required. Moreover, if the number of joints increases they dont seem to perform well.

• Optimization-based Methods: These methods treat the IK problem as the optimaztion problem. The basic idea is to have an objective function which needs to be minimized and the constraints which have to be fulfilled.

Implementation Details

We have used Optimization techniques to solve the IK problem. It works for a character with n degrees of freedom. Different joints can have multiple degrees of freedom and they have inter-dependencies between them too. We change the whole problem into an optimazation problem and use SNOPT solver to find the solution. The solution is then applied to the animated character. The software provides an interative way of slelecting hamdles and specifying the end goals and the solver is then called which comes up the desired angles and then forwars kinematics is applied to reach that end-goal.

The SNOPT solver is given the objective function, its gradient, constraints alongwith the Jacobian w.r.t each degree of freedom, an update function which updates gradients for the constraints.Each joint has a marker which can be moved to indicate the desired position. SNOPT solver uses non-linear programming to calculate the joint angles. The SNOPT has a bulky interface and it took us some tome to figure out, how does the whole thing work! The number of inputs for the SNOPT system and the different ways, it can be used really provides a lot of flexiblity. It even can calculate the Jacobians using finite element methods, but that makes the whole process slower, so we provided our own Jacobian functions for the objective function and the constraints.

The coding was done in C++ using Micrsoft Visual Studio 2005. We used some external libraries for 3D character animaiton and matrix operations. FLTK for openGL and VL for matrix operations. VL provides a lot of matrix functions which were really useful in tarnsformation calculations.

 

Algorithm( Optimization-based Methods)

Optimization-based methods use a fundamentally differentr approach to slove the IK problem. This approach avoids the inversion step altogether. The idea is to cast the basic problem of equation as a minimization problem, then apply the standard iterative, non-linear optimization techniques to obtain a sloution. As an example, consider the problem of positiioning the end-effector at a goal position p. The distance from the current position to the goal position acts as the error measurement.

In our case the objective function is to minimize the joint angles of each joint. This assumes that the character used the minimum amount of enerrgy this way! Its a crude idea which can be modified like being the muscle force being exterted or the style which is close to human style of motion etc.

Computing the Jacobian matrix

Jacobian is the most important here for effeicient calculation of the joint angles. It can be calculated using the SNOPT as mentioned earlier but that would make the solver slower, so it was always kept in mind to construct the jacobian w.r.t objective function and the constraints.

The objective Jacobian is 1xn matrix  where n is the no. of degrees of freedom in the whole animated character. This hels the SNOPT solver find the sreach direction for the global minimum. Currenlty this is being done using SNOPT which claculates the Jacobian using finite differences.

The constraint Jacobian is 3c x n matrix where c is the no. of constraints in the system and n is the number of degrees of freedom in the whole charater. This Jacobian guides the search in the direction for the SNOPT solver. It ensures that the search goes in a direction which meets all the constraints. If you want to see the code, its right here.

 

 Results

 The software was able to run in real time. One could choose the joints it wanted to move, drag the mouse for the desired position and then let it go and then the character would try to reach that point if possible. There could be multiple solutions too. We trust the SNOPT to find a feasible one for us.

 Some screen shots of the system are shown below:

T-pose

 

Another pose

Yet another pose!

 

 References

[1]. Chris Welman, September, 1993, "Inverse KInematics and Geometric Constraints for Articulated Figure manipulation".

[2]. Sezgin Abali, September 2001, "Animation of Human Motion with Inverse Kinematics using Non-linear programming.

[3]. Philip E. Gill, October 1997, "User guide for SNOPT 5.3", University of California, San Diego.