# Inverse Kinematics for Game Programming

Note: This is an article for the Carnegie Mellon course Technical Animation (15–464). Also, I cannot guarantee that there is no bad language in the following article… I get a bit mad at Google and Unity in this…

One of the major programming fields with programming motion is Inverse Kinematics (IK), specifically with segmented arms. Said problem is commonly seen within animation, for the simulation of jointed arms in characters or in other motion of long chains. More specifically, IK allows a user to simulate the motion of a chain (of bones) without having to manually control each of them, for example allowing an animator to control the motion of a leg by just moving the foot.

This problem is also encountered in games, with similar inspirations for their use. There are a couple of notable examples, for instance Shadow of the Colossus, which has every limb of the main character simulated with IK, in order to allow for players to climb a colossus with more free control.

However, in order for IK to be used in games, it must be cost effective time-wise. Thus, in order to explore that pseudo-empirically, I implemented three common IK techniques in Unity with a custom bone prefab. Namely, the techniques considered were Cyclic Coordinate Descent (CCD), Jacobian Transpose, and Forward and Backward Reaching Inverse Kinematics (FABRIK).

First, before we go into the three implementations, I first want to go into a bit into the process of creating the bones for my simulation, to both work as an introduction to the terminology used in IK, and as a hope that maybe there will be feedback on better ways on implementing it, because MAN, there were some interesting hiccups.

The prefab (Bone) is simple: Sphere + smaller sphere + cylinder. The regular sphere operates as the Joint, the smaller sphere operates as the End, and the cylinder operates as a scale-able Shaft. A Chain is formed when a series of Bones are connected, End to Joint, into a sequence, with the final end of the sequence called the End Effector. Shown below is one example screenshot taken of a Bone Chain (giggles):

Each bone in the chain should be rotated at the joint… Oh yeah, and if you haven’t noticed, the scaling and movement are all done in script. Here is the prefab:

Now, the chain needs to a goal, because goals are fun:

And with a bit more C# funtimes, we get a scale-able bone chain with a movable target!

So now that we have a scale-able and properly orientable bone chain and moving target, we can start the process of making the bone chain invade the personal space of our target!

Our (not sure why I’m including you on my journey, but hey, the more the merrier) first process is Cyclic Coordinate Descent (CCD).

CCD is a serial algorithm for IK. Basically, it iterates through the bone chain, starting from the end bone, and operates on each to move the chain of bones. It does this by lining up the vector between the end effector and the current joint (v_eej) with the vector between the joint and the target position (v_tj). To do this in Unity, we first get the two vectors by your favorite method (lol, I just subtracted one point from the other…), get the axis of rotation via a Vector3 cross product, get the signed angle between both vectors relative to said axis, and then apply the rotation of the bone along the rotation axis in World space.

While this works for the first bone, there is a slight problem with later ones. Unfortunately, due to the Unity transforms issue, I cannot take advantage of parenting one joint to the next to rotate all of a portion of a chain at a time. Thus, the rotations of one joint must propagate down the chain to the end effector. Admittedly, if one was to implement this with a custom game engine, one must also propagate the rotations in a similar way, so having such a limitation is pretty reasonable. It does mean that later joints need to propagate more, throwing CCD into the handwavily ~O(n²) complexity class… ouch. But oh my god, I have inverted kine!

It seems all fine and good so far… but let me just move the target around close to the source and…

Ouch… So the problem with CCD is that there is overcorrection. If we do an extreme case and present its progression stepwise, it becomes clearer.

CCD in extreme cases overcorrects in order to reach the target, which only gets compounded because later bones in CCD do not care about what is between them and the end effector, rather it only cares about the vector between itself and the end effector. As a result, when you start updating CCD at sequentially different target locations, the bone chain gets all tangled.

There are ways around this, though. The article which I so expertly namedropped has a followup explicitly on CCD, Making Kine More Flexible. For example, it is possible to restrict the angle that each bone can move (as well as restrict axes), causing more realistic motion. Plus, for less bones, CCD does a pretty good job.

Still, there are other alternatives to CCD that can be used in games. And with that excellent segue…

Jacobian methods are actually a pretty common method used in cinematic animation, so by that logic, it’s perfectly fine to do them in Unity, right?

In a nutshell, Jacobian methods for IK incrementally solve for the end effector approach problem in a process called Gradient Descent. In a very watered down sense, Gradient Descent places your target at a position of low “energy”, and you solve for a way to get your effector point to the point of lowest energy in this energy space you created (if it isn’t clear by now that my home major is Physics, now you know).

For the sake of this assignment, I will not be recounting Jacobian Transpose (and other Jacobian methods) outside of that previous paragraph, but if you are interested… TERM DUMP! [Jacobian Pseudoinverse, Damped Pseudoinverse].

I started with calculating the Jacobian, which I did with an analytic method provided to me through course material (cross products ftw!). I then saved those as a List of Vector3’s for convenience. The axes of rotation I used were similar to CCD, namely the optimal axis for rotation for the vectors v_eej and v_tj for each bone in the chain.

Admittedly, without doing some very interesting things with libraries in C#/C++ and DLLs because Unity decided to only have preset matrix dimensions with respective libraries, and because I don’t trust myself enough to implement an optimal matrix library in C# yet, I did Jacobian transpose, since it ends up being very convenient. You see, in the previous paragraph, I got the Jacobian as a neat List of Vector3's, and coincidentally, the angle perturbations I need are basically dot products between each column of the Jacobian (row actually, because transpose) and the end effector perturbation vector (vector between the end effector and target, v_eet, multiplied by a weight). So like that, I have my angle perturbations (with their respective axes)!

Unfortunately, I do get a similar problem as with CCD, in which I need to propagate my rotations. But no matter, by Odin’s beard, I have once again Inverted Kine!

This time, if I do similar motions as I had done with CCD, the chain does not get tangled up!

Also, I have to say it, the arc it takes is pretty aesthetically pleasing…

Unfortunately, there are a few problems to Jacobian Transpose in context to games. Most noticeably is that the method seems pretty slow to reach the target. This is because unlike CCD (and FABRIK later on), it is a gradient based technique that gets us incrementally close to the target. But the solution seems simple… I just increase the factor that I use with v_eet, right?

Ow… So besides the probably obvious overshooting issue that happens when you do GD with big steps, there is another problem, namely that the transpose is only just a decent approximation to the inverse of the Jacobian. As a result, in certain cases, the method can overcorrect.

There actually is a decent way to calculate the scaling factor based on the Jacobian and v_eej, but A) it requires more calculations, and B) it requires mxn matrix multiplication noooooooo.

Besides, Jacobian Transpose is not fully free of the biggest problem, namely the cost. Again, ignoring getting the Jacobian and multiplying it out (it should handwavily be O(n)), the angles need to be propagated to the end effector bone, resulting in the return of the dreaded O(n²) term.

There is one slight advantage to Jacobian Transpose, though. The Jacobian calculation is pretty simple and easily parallelizable, so if I had better programming skills, I could probably take advantage of that. Unfortunately, that is not the case, and it still doesn’t fully deal with the O(n²) term, so we must look elsewhere for our aesthetic IK.

The final IK method I used was Forward and Backward Reaching Inverse Kinematics, or FABRIK. In very quick terms, it aligns bones to either the target or the end of the next joint, moves it to the next joint or target, realizes that at the very end the last bone is not in the original position, and reverses the process with the original location as the target. Short, simple, and sweet. Or in a more aesthetically pleasing mode:

Oh yeah, spoilers for FABRIK, but it ended up being the most pleasing with a lot of bones.

Anyways, pretending we didn’t just see that video, I have, by the power of the Jade Emporer, Inverted Kine!

Isn’t that so pleasing? The main aesthetic benefit of FABRIK is that it feels like if the bone chain was exactly that, a bone chain.

It doesn’t have the problems of CCD with clumping, and it seems a lot faster that Jacobian Transpose! And it almost seems to take the best of both worlds! It really just makes you wonder, just what is it that makes FABRIK so fast?

Well, since FABRIK propagates motion by rotating and shifting bones, it really only passes over the chain 2n times… or to put it in another way…

WE GOT OUT OF THE O(n²) HOLE!

No, seriously, FABRIK is fast. Let me compare by adding a ridiculous amount of bones to our simulation…

With CCD, there is slight lag.

With Jacobian Transpose… OH GOD WHY…

But with FABRIK, the simulation runs pretty smoothly…

Actually… why not take it to 1000…

FABRIK only has a bit of lag in the simulation. But what about CCD?

Pretty significant in lag. Although I will admit there is also a bit of aesthetic to the shape of the chain… Now, I cringe to even imagine it… but what about Jacobian Transpose…

Such ungodly things were never meant to exist in this mortal realm…

(In retrospect, I probably should have done this running it in Unity with the profiler open to have more empirical data to use for the comparisons… or have it be in the UI… Oh well, I swear, the pattern in lag is consistent)

Besides the decrease in the upper bound of computation, there are other interesting effects that come from FABRIK. First off, FABRIK seems to simulate the motion of a chain really well. I assume this is because unlike the previous methods, FABRIK almost simulates the motion of bones as if they were physical links in said chain. The second thing to note is that movement of the target does not affect the movement of bones closer to the anchor of the chain. It appears that the extreme curvature seen in CCD is distributed over the bones closer to the effector in FABRIK. Finally, although it wasn’t implemented in this assignment, it is possible to program methods of constraint to FABRIK joints, allowing for more realistic motion than the bone snakes I’ve been playing around with.

To be honest, this assignment has me hard pressed to find reasons to praise CCD, and it certainly has me second guessing a lot of the decisions I had made with the resulting simulation. And it really shows why Jacobian methods are likely not that useful in a game context, as frame computation time, even with parallel programming, is very valuable in high end game development. But I just don’t feel comfortable announcing FABRIK as any kind of winner…

Ah, who am I kidding. FABRIK is fast, smooth, and from a quick look looks constrainable without too much added complexity to the computation. If I were to have to design a rig system for a game, I would definitely lean on FABRIK as the skeleton to that system…

Oh wait… skeletons aren’t just long chains, and although I can think of constraint methods pretty simply, branching skeletons aren’t really coming that quickly to mind with FABRIK. But hey, it’s always something new to explore.

Overall, I really had a lot of fun with this assignment, so much that it became harder and harder to submit it, as I just kept on thinking of and adding new components and features (note the lines of text in the UI for different variables). If I had more time (as in if I didn’t submit this late with grace days), I would have totally explored adding angle based constraints to CCD and FABRIK, maybe have dabbled with constructing complicated skeletons with the tools I have, and hey, maybe I would have implemented n by m matrices to get Jacobian Pseudoinverse and Damped Pseudoinverse working. Plus, this assignment gave me an opportunity to explore Unity 3D (I’ve only been making 2D student games, so this was a fun breath of fresh air).

I definitely want to revisit this project sometime in the future, maybe to make some kind of fun wibbly physics puzzler with chains, maybe to explore doing these same things outside the Unity engine. But this has definitely been a fun learning experience.

Anyways, if you are not my instructor and would like additional resources on IK, I’d recommend checking out the articles “Oh My God, I Inverted Kine” and “Making Kine More Flexible” for examples of CCD and game focused IK, the paper “ Introduction to Inverse Kinematics with Jacobian Transpose, Pseudoinverse and Damped Least Squares methods” for a big list of Jacobian methods and the mathematics behind it, and the paper “ FABRIK: A fast, iterative solver for the Inverse Kinematics problem” for a better description of the FABRIK algorithm.

Bye guys!

- Ray