Inverse Kinematics

Inverse Kinematics

This article has been superseded by a New Inverse Kinemaics Article

Kinematics is the process of calculating the position in space of the end of a linked structure, given the angles of all the joints. It is easy, and there is only one solution. Inverse Kinematics does the reverse. Given the end point of the structure, what angles do the joints need to be in the achieve that end point. It can be difficult, and there are usually many or infinitely many solutions.
This process can be extremely useful in robotics. You may have a robotic arm which needs to grab an object. If the software knows where the object is in relation to the shoulder, it simply needs the calculate the angles of the joints to reach it.
This would also be a great thing to have in 3D games. Say you had, for example a dragon with a really long neck, you could get the dragon to reach down and eat the player, bending it's neck in a realistic way. A player might want to pick up an object or press a button. The user would see the character on screen reach out and touch it, instead of just waving it's arm somewhere near like Alone In The Dark.

I have written a DOS demo to illustrate this. The screen shows a tail which trys to touch a target represented by the small spinning cube. You can move the target around in space with the keyboard. The tail has a small amount of springyness and gravity added, so you will probably find that the tail keeps moving even when it has found the target, trying to get into a more comfortable position.
The shape of the tail is stored in a file called tail.cfg. You can try fiddling around with it to make different objects.

No Solutions

In many cases, it will be impossible for the linked structure to touch the target. For example, you cannot touch your elbow with your hand and you cannot reach the top of a tall tree from the ground. In some cases, the system I am about to describe may become unstable, especially if the target moves far out of range of the structure.

One Solution

Two Solutions

If there are two solutions, this technique will find which ever is closest to the current state of the structure.

Many Solutions

When there are more than two joints, there will frequently be infinitely many solutions to the problem. However, some solutions will be better than others. If your structure represents an arm for example, some solutions will look more comfortable and others very strained. There is often an optimal solution.

More About The Algorithm

I came up with this method for inverse kinematics with a little thought and trial and error. No doubt there are many ways around this problem, but this is the only one I know. It is quite simple, and I am about to explain it.
This algorithm won't immediately find the solution. It is not a simple function where you give it the target and it replies with the angles. It is an iterative procedure. This makes it much more realistic for use in software, especially games where you want objects to move smoothly.
The solution is found by virtualy applying a force to the end of the linked structure and pulling it into position. The effect of the force is applied to each of the joints to bring the structure a little closer to it's target. So, even if there is no solution, a close one is often found. Because the joints are handled seperately, you can give them various properties, like stiffness, springyness etc. They can also each have an optimal position which the algorithm will try to keep as close to as possible.

Inverse Kinematics in 2D

Let's start with a single joint. It can rotate around one axis (anti-clockwise is positive) in this case. The vector R is at right angles to the bone. A force vector F is constructed from the end point to the target. The angle between R and F is a.
Now here's the really easy bit. The speed at which you should rotate the joint is proportional to the dot product of R and F. As it stands, the dot product of the two vectors is positive, and indeed the joint should rotate in the positive direction to move closer to the target. If F is at right angles to R, then the joint is as close to the target as it will ever be, and it should not rotate further. At this point the dot product of the two vectors is zero.

torque = (R.F) * k

That's it. That was the hardest bit. From now on, everything is simply a variation on that theme. When you have more than one joint, you just repeat the above algorithm for each joint in turn.

Starting from the joint nearest the end point:
1. Calculate a force vector from the end of the bone to the target.
2. Calculate the dot product of the force vector and the Right angle vector.
3. Multiply it by a small value, like 0.01.
4. Add it to the angle of the joint.

Do this for all the joints, continuously.

Inverse Kinematics in 3D

In 3D things get very slightly more complicated. There are three possible axis about which a joint can rotate. I have tried applying the above method to a 3D structure, but the results were not so good. I'm not really sure why. Anyway this maths works, just. It's something that needs lots of fiddling with to get the settings just right.

Enough, onwards.

Joint axis perpendicular bone

Firstly, lets take the above example again, but this time in 3D. It is a 2 jointed system, and we'll take joint number 1 first. There are several vectors here, namely;
a Vector along the axis of the joint.
b Vector along the bone.
r Vector at Right angles to a and b.
f Force vector, from End Point to Target.
If the force vector is parallel to a then the joint won't rotate. If it is parallel to b then you're just pulling along the bone, and the joint won't rotate. Armed with this reasoning, I decided that the torque on the joint was proportional to the sine of the angle between a and f and the sine of the angle between b and f.

If the End Point is on the target, then you don't want the structure to move any more, but if the End Point is very far from the target, then you want the structure to move there quickly. Again, I decided that the torque should also be proportional to the magnitude of the force vector.

One thing the previous two paragraphs do not tell you is which direction the joint needs to move. So the joint should move in a positive direction of the force points along r, and in a negative direction of the force points in the opposite direction to r.

So, put these three things together, and you get:

torque = Mag(f) * SinVect(a, f) * SinVect(b, f) * sign(CosVect(r, f)) * Sensitivity

Where SinVect and CosVect return the sin and cos of the angle between two vectors respectively, Mag returns the length of a vector, and sign returns the sign of a number. Sensitivity is some small scaler constant.

So then you move onto the next joint up the structure. Re-calculate the vectors a,b and f, and calculate the torque for joint 2. Calculate the torque for all the joints in the whole structure, then add the torque to each joint to it's angle. The End Point of the structure should now be closer to the target. Repeat the process continuously, and it should do it's best to keep touching the target.

Joint axis through bone

Right, this may look a little complicated, but there is nothing new here. This is a linked structure consisting of four joints. Joint number two, however, rotates about the axis of it's bone. Same thing as twisting your wrist. It is this joint that is important. As before, vector a is along the axis of rotation, but this time it is also along the bone. The vector b now goes from the begining of the joint to the End Point. The vector r is as usual perpendicular to both.

To reach the target, joint 2 needs to rotate 90 degrees (see right diagram).

And to conclude, vector b is different for joints whose axis of rotation is parallel to the bone.

Fiddling Around

Now that you can do basic Inverse Kinematics, there's loads of adjustments you can make to the system to make it behave in different ways. As I said before, some solutions are better than others, either because they look better, or involve less movement, or are more comfortable.

Smooth curves

Real tails on real animals rarely have kinks in them. They tend to bend in a fairly smooth curve. The tail in the demo is made from pairs of joints at right angles to eachother. The origional tail I wrote tended to kink and bend in unrealistic ways. So I added some springyness to the joints. This makes the joints reluctant to bend, and the more you bend them, the more the fight back. This has the effect of spreading the bend evenly over the tail.
Take a look at a dinosaur's tail. It is very thick at the body, becoming thin, and more flexable towards the end. This property can be simulated in the linked structure by making the links less and less springy towards the end.

Comfortable Positions

Limbs prefer to be in comfortable positions. This can again be accomplished be adding some spring to the joints. However, in this case it might be best to have a range of movement for each joint, over which there is no springyness. This range is considered to be comfortable. As the joint moves out of the comfortable range, it fights back more and more until it reaches it's limit, where it refuses to rotate furthur.
It may also be desirable to keep the limb as low as possible. People rarely keep their arms up in the air for long periods of time unless strictly necessary. So positions should be chosen where the the least energy is required to hold it there.