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.

Dual Quaternion

Introduction
Continue to the last post which introduce Dual Number, it can be extended to Dual Quaternion. Dual Quaternion is similar to Quaternion with all the real numbers replaced by dual numbers:

Dual quaternion can also be regrouped into the following form by:

which is in terms of 2 quaternions (real part and dual part).

Arithmetic operations
Dual quaternion can perform arithmetic operations as below:

Addition:

Multiplication:

Conjugate:

Norm:

note that the norm of a dual quaternion is a dual number.

Dual Quaternion as Rigid Transform
Unit Dual Quaternion can represent a rigid transformation (i.e. rotation & translation) like matrix. Like ordinary quaternion, dual quaternion can represent a rotation using ordinary quaternion with the dual part equals to zero:

To representation a translation (tx, ty, tz), the following dual quaternion can be used:

Then, we can combine the above 2 transform into 1 dual quaternion (which is also unit dual quaternion) to represent a rotation followed by a translation

With the above arithmetic operations, we can transform a point p(px, py, pz), using unit dual quaternion like ordinary unit quaternion:

Dual Quaternion - Matrix Conversion
Sometimes it is convenient to have methods to convert between Unit Dual Quaternion and Matrix. Assume we have ordinary quaternion - matrix conversion functions.

Converting Dual Quaternion to Matrix:
Given any unit dual quaternion which is composed of a rotation followed by a translation, we have:

Therefore, we can find the rotation matrix by considering the real part of the dual quaternion while the translation (i.e. tx, ty, tz) can be solved by using system of linear equations by equating coefficients.

Converting Matrix to Dual Quaternion:
Given a rigid transform matrix, we can decompose the rotation matrix into real quaternion as usual and the translation dual quaternion can also be obtained by:

then multiply the translation dual quaternion with rotation dual quaternion will give the answer.

Blending Rigid Transform using Dual Quaternion
Using dual quaternion to represent transform is better when blending multiple transformations, which can be applied to skinning a mesh. From that paper, it suggests using an fast approximation for blending called Dual quaternion Linear Blending (DLB):

note that the norm in the denominator is a dual number, which can be treated as 1 divided by the norm and gives another dual number (using dual number division) so that it can be multiply by a dual quaternion.

Conclusion
Dual quaternion is an alternative way to represent a rigid transform other than matrix. And it may gives a faster accumulation of transformation if joint inferences per vertex is large enough according to "Spherical Skinning with Dual-Quaternions and QTangents".



Reference:
[1] Dual Quaternion for Rigid Transformation Blending: http://www.jarmilakavanova.cz/ladislav/papers/sdq-i3d07/sdq-i3d07.pdf
[2] Spherical Skinning with Dual-Quaternions and QTangents: http://www.crytek.com/sites/default/files/izfrey_siggraph2011.pdf
[3] Estimating 3-D location parameters using dual number quaternions: https://pwww2.cse.tamu.edu/volzfest/proceedings/paper-dedications/Shao_Lejun.pdf
[4] Dual quaternion as a tool for rigid body motion: http://www.ingegneriameccanica.org/papers/pennestrivalentini_paper.pdf

Dual Number

Introduction
Recently, I read the "Spherical Skinning with Dual-Quaternions and QTangents" from Crytek. It raised my interest on the topic of "Dual Number" (which is related to Dual Quaternion). Dual number, just like imaginary number, has the form of:

where the real number a is called real part and the real number b is called dual part.


Arithmetic operations
Dual number can perform the arithmetic operations as below:

Addition:

Multiplication:

Division:

Finding derivative using Dual Number
The interesting part of dual number is when it is applied to Taylor Series. When substituting a dual number into a differentiable function using the Taylor Series:

This gives a very nice property that we can find the first derivative, f'(a), by consider the dual part of f(a+bε), which can be evaluated using dual number arithmetic.
For example, given a function

we want to find the first derivative of f(x) at x = 2, i.e. f'(2). We can find it by using dual number arithmetic where f'(2) will equals to the dual part of  f(2+ε) according to Taylor Series.

Therefore, f'(2)= 8/9, you can verify this by finding f'(x) and substitute 2 into it, which will give the same answer.

Conclusion
By using dual number, we can find the derivative of a function using dual arithmetic. Hence, we can also find the tangent to an arbitrary point, p, on a given parametric curve which is equals to the normalized dual part of the point p. For those who are interested in finding out more about dual number, I recommend to read the presentation "Dual Numbers: Simple Math, Easy C++ Coding, and Lots of Tricks" by Gino van den Bergen in GDC Europe 2009.

Reference:
[1] http://en.wikipedia.org/wiki/Dual_number
[2] http://www.gdcvault.com/play/10103/Dual-Numbers-Simple-Math-Easy

Using PID Controller

Introduction
Several weeks ago, I need to implement a game screen for user to choose a level. At that time, I read some post and article about using PID controller for controlling the behavior of a system, so I decided to try it on the UI. PID controller is a control loop feedback mechanism which generate an output to a system based on the difference between a measured value and a desired value:

where f(t) is the output apply back to the system, e(t) is the difference between a measured value and a desired value and P, I, D are tuning variable for controlling the behavior. More information can be found on this post.

Using PID Controller
In the UI, the user can drag on the view to choose the level, when the user swipe on the icons, they will scroll according to velocity and acceleration. The output of PID Controller is used to control the acceleration so that there will always be an icon staying in the middle of the screen when the system becomes stable. The code is ported to WebGL as below(need a WebGL enabled browser to view):

Your browser does not support the canvas tag/WebGL. This is a static example of what would be seen.

P: I: D:

Tuning the PID variables
The behavior of the scrolling can be controlled by tuning the constants: P, I, D. The effects of changing the 3 constants can be summarized as below:

Summary of the effects of PID constant from Wikipedia

You can play around with the 3 Constants with the input text field above if you have a WebGL enabled browser.

Conclusion
Using PID Controller to manage the system is convenient but it is a bit tricky to tune the PID constants. It is easier to tune the constant one by one and referring to the above table. The source code of my implementation can be downloaded here.

Reference:
[1]: http://en.wikipedia.org/wiki/PID_controller
[2]: http://altdevblogaday.com/2011/08/07/animation-using-closed-loop-control/
[3]: http://altdevblogaday.com/2011/02/27/webgl-part-2-in-the-beginning-there-was/
[4]: http://www.learnopengles.com/how-to-embed-webgl-into-a-wordpress-post/