Inverse Kinematics (two joints) for foot placement

Author: by Simon Yeung

[In this reprinted #altdevblogaday in-depth piece, game programmer Simon Yeung presents "an analytical two joints Inverse Kinematics solution in 3D case for foot placement" on terrain.] Games sometimes need to solve Inverse Kinematics (IK) for a more realistic look, like foot placement on terrain. There are different methods to solve IK problems -- some are numerical methods which can be used for general cases, and analytical solutions exist only for simple cases like the case for two joints. I implemented the analytical method to handle the foot placement in my engine: For a simple case such as two 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, and length of the 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 the IK results look good. 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 solutions 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 it equals 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 presents an analytical two 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] http://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. [This piece was reprinted from #AltDevBlogADay, a shared blog initiative started by @mike_acton devoted to giving game developers of all disciplines a place to motivate each other to write regularly about their personal game development passions.]