Closed for Non-Iterative Inverse Kinematics

Last year I submitted an article to the Game Programming Gems people on IK.

The article titled 'Non-Iterative, Closed Form, Inverse Kinematic Solver' ( a mouthful I apologize ), was published in Game Programming Gems 8 that was released in March. I just received my copy, and it is very satisfying to see the article in print in a well respected hard cover volume, and that the article is highlighted in the preface is especially gratifying. Getting the article written up and polished was not an insignificant amount of work.

http://www.amazon.com/Game-Programming-Gems-Adam-Lake/dp/1584507020

The algorithm presented in the article has been through many stages of evolution starting out as a much simpler, limited solution in CAT1. It was developed considerably for CAT2 , and for the article it was overhauled once again to improve the behavior.

My personal perspective is that this algorithm renders solvers such as CCD redundant especially in the field of game development, and I build a case for this in introduction section of the article. However, I hope that this will spur people on to refine and develop the solver further based on particular requirements in their project.

I was rebuilding the solver recently (after the article submitted for publishing), and I think I may have found a way to develop the idea even further, simplifying even more the basic concept, and providing greater level of control.

The idea in the solver is that for every bone in a chain hierarchy, you can identify 2 important values that can be used to drive the solution.

The algorithm assumes a hierarchical solve, calculated either from the base of the chain to the tip, or vice versa. As each bone in the chain is solved, the resulting solution will have an effect on the children bones as they will need to solve according to the results of their parents. Basically, for the overall solution to be valid, each bone must be solved such that they allow the remaining bones in the chain to be solved.

This introduces the first condition, that each bone must be solved such that the distance from the tip of the bone to the goal allows the rest of the chain to reach the goal if possible.

The resulting pose of the bone must allow the children to reach the goal if possible. This gives us a maximum allowable angle for the bone relative to the vector between the bone and the goal.

The other key concept of the solver is the the FK pose of the chain prior to solving gives us what we might consider a 'model' answer. The concept being that IK applies a minimal change in pose to the chain thereby preserving the pose of the character, and also allowing FK animation to drive the shape of the chain over time.

We de-construct the model pose to a 'desired angle' for each bone at a given distance from the goal.

In the article, I go into detail including diagrams, and example code on how to derive a solution for a chain in a single pass of the hierarchy by comparing the 2 angles, and using them to infer a new angle for the exact context the chain is actually being solved in. This is achieved by linearly interpolating the 2 values according to a parameter extracted from the context of the solve. The actual distance to the IK goal.

The algorithm works very well, and I think that they accompanying code should demonstrate this. However, there is one weakness to the solver that bugs me.

For long chains, where the length of the chain is far greater than the distance to the goal, the solution, while technically correct, may produce results that are undesirable. Bones in the chains may bend too far or too little for the character they are solving for. Now, I am really splitting hairs, and I would actually like to see a character who which I predict the problems might occur.

This motivated me to think a bit more about the problem, and I decided that what would be prefect would be some very specific way of describing the angles of the bones for the range of possible contexts. This description would need to satisfy at least the first condition mentioned above, but I think both would be important. I think that a parametric function curve could be defined that would give artists very explicit control over the solving, while always producing a valid result that respected the FK pose of the chain prior to solving. I have started prototyping this new curve based method, and although my initial results are really a step down from the solver presented in the book, I do have confidence that there is a new, simpler, clearer version of the solver on the horizon.

=Data Size=

With the ability to specify a curve which defines the angles for the bones for a range of contexts, this would also give the engineers the option of eliminating all the FK animation data on limb bones where IK would be solved. Effectively, instead of specifying a pose for the limb at every frame of every animation, you provide a set of curves, which describes the ideal pose of the limb under all possible conditions. These curves could be extracted from reference animation for example, giving the artists the ability to say, 'this is how this leg should always be solved'.

The position of the tip of the chain would need to be extracted prior to this step and stored because no doubt you will need this data later, but many engines, including the Unreal Engine already do this. The other channel that you would need to keep somehow would be possibly the root bone orientation. This is because it will contain some twist information that cannot be derived at runtime. I believe this twist information could be reduced to a single float channel.

For complex creatures with many chains with many bones each, this would remove a big chunk of your data without affecting the quality of the animation at all. This is just an idea.

If you are interested in the problem of IK, or looking for a solution, then I would recommend that you check out the book.

I find the domain of IK interesting, and I plan to keep working on variations of this solution until every possible avenue has been explored. If anyone has any questions/comments, please send them my way.