Inverse Kinematic

Summary

Introduction

In this article I will explain how I implemented inverse kinematic for one of my college assignment. Inverse kinematics (IK) is an animation method that’s more straightforward than forward kinematic. A goal position of the action is defined by positioning the effector of a chain and the algorithm calculates how to position the rest of the chain to reach that goal. For example, to bend a leg, you drag the leg’s end effector and the rest of the chain follows.

leg effector

I used as reference for two models, one is Bob the dwarf, taken from this tutorial and the other is Peter from the GV2 lab in Trinity College.

 

 

Bob and Max say hi :-)

Bob and Max say hi 🙂

To test the Inverse Kinematic algorithm and for debugging purpose I initially created and skinned a 3D model consisting of a joined mesh of three cones, see figure below:

Cones

Cones modeled in Blender

Each cone has a bone, and the last bone you see in the picture above is the end-effector.

Implementation

I implemented the Cyclic Coordinate Descent (CCD) based on 1998 Jeff Lander’s tutorial.  This technique was first outlined by Li-Chun Tommy Wang and Chih Cheng Chen in a paper in the IEEE Transactions on Robotics and Automation. CCD involves minimizing the system error by adjusting each joint angle one at a time. Jeff’s implementation was only 2D, to “transform” it to work with 3D models was not as straightforward. As seen in the figure below, there’s an end-effector E, current bone R, and target D. The goal is to rotate the vector RE onto the vector RD.

Cyclic Coordinate Descent

Cyclic Coordinate Descent

For this algorithm I chose to work in world space. First to do is to calculate the end-effector position E and the current bone R in world space and the euclidean distance ED. The distance is compared at every iteration with a constant minimum distance. This is done in order to check if the end-effector is close enough to determine the end of the algorithm.
Once E and R are in world space I calculate the dot-product between the normalized vectors RE and RD. This determines how much the vector RE should rotate to be aligned with RD.
The dot-product though doesn’t say the direction of the rotation thus the cross product between RE and RD is to be calculated.

Here is my C++ implementation on GitHub.

Video