Inverse Kinematics (2 joints) for foot placement

Introduction
Game sometimes need to solve Inverse Kinematics (IK) for more realistic look like foot placement on a terrain. There are different methods to solve an IK problems, some are numerical methods which can be used for general cases, and analytical solution exists only for simple cases like the case for 2 joints. I implemented the analytical method to handle the foot placement in my engine.

2D case
For simple case such as 2 joints in 2D case. In the following figure, suppose we want to rotate the blue leg to the position of the red leg so that the leg is aligned to the ground:

Since we know the pelvis joint position, target position, length of upper leg and lower leg, we can solve the angle α using law of cosines. Then, we can calculate the vector PK' by rotating the vector PT with angle α. Hence angle δ can be calculated with the dot product between the vector PK and vector PK'. The angle at knee joint can be solved either by law of cosines or dot product.

3D case
For the 3D case, it is similar to the 2D case except the rotation may not be on the same plane in order to make to IK results look good.

As there are infinitely many solutions to make the leg reach the target position (because the leg can rotate around the axis a highlighted in red), so we can first calculate one of the solution using law of cosines just like the 2D case (i.e. find the angle α in 2D case), hence we can calculate the upper leg vector v. As this is an arbitrary solution, the result may sometimes look funny:

So, the next step is to find a solution which is close to the pose made by the artist, in other words, we want to minimize the angle δ in the above figure, which is the angle between the arbitrary solution found in the above step and the thigh position posed by the artist. To minimize angle δ, we need to rotate the vector v around the axis a (the red line in the figure) with an angle θ to a new vector v'. In the below equation, v is rotated to v' using quaternion:

As minimizing δ is equivalent to maximizing cosδ (i.e. v'.k), we need to calculate the first derivative of cosδ  and the maximum/minimum value is achieved when equals to zero (all the vectors are normalized):

Then we can get two values of θ within a range of 2π, which correspond to maximizing and minimizing the cosδ. To distinguish whether which solution is maximizing cosδ, we need to substitute θ into the second derivative of cosδ to test whether it is greater than 0, if so, then that θ will minimize cosδ, otherwise, it will maximize cosδ.

Then we can rotate the arbitrary IK solution v with angle θ to v' to give a much better look:

Conclusion
This blog post present an analytical 2 joints IK solution in 3D case for foot placement. We first compute an arbitrary solution for the pelvis joint using law of cosines, then rotate that joint to minimize the angle between the joint after the IK solution and the posed joint before IK to give a much better look.

Reference
[1] http://www.3dkingdoms.com/ik.htm
[2] www.essentialmath.com/InverseKinematics.pps
[3]: The brick texture is obtained from Crytek's Sponza Model: http://crytek.com/cryengine/cryengine3/downloads
[4] The knight model is extracted from the game Infinity Blade using umodel.