Cyclic Coordinate Descent (CCD)

As I mentioned on previous post. This post will describe more about CCD in relation to Inverse Kinematics and Human Body Animation.

The basic idea of Cyclic Coordinate Descent (CCD) Method is performing iterative heuristic search for each joint angle, so at the end, the end-effector could reach a desired location in space. By doing iterative heuristic search, we try to find the best location of an articulated structure given its joint angles. This would result in the best (closest) distance of the end-effectors and the desired end points. The calculation is done one joint at a time, and in backward fashion, until we reached the parent joint. For calculating the joint angle, we also give certain limitation for the angle, just like the angle of a human. We implement this, so the animation wouldn’t do any strange movement. The first thing to do in CCD method is to determine the desired location of the end-effector (X). After that, we try to minimize the distance (ΔX) between end-effector position (X^) and the desired destination (X) as low as possible. We do this by increasing/decreasing the current joint angle of the end-effector. When the distance of the end-effector is as low as possible, it means that the current joint angle (Θ) has reached its maximum point, given the current position. Then we move backwards to the upper joint, where we then try again to minimize the distance between end-effector and destination point, but this time only altering the current upper joint. We do this until we reached the parent joint. An example can be seen in the following figure.

Cyclic Coordinate Descent Method for: a) Rotational Joint and b) Prismatic Joint

For example, we can imagine when we try to move the whole hand. The first thing that we do is to calculate the minimum distance that could be reached by our hand only using the wrist joint. After that, we then move backwards and try manipulate the elbow joint and again calculate the minimum distance that could be reached by our hand. We do this until the last joint is manipulated, for instance, the shoulder joint, or even our backbone joint. Each human body joint are capable to rotate in one to three different axis (3-Dimension). This ability to rotate is called Degree of Freedom of a joint. So each joint could have 1 to 3 Degree of Freedom (DOF). Using CCD method, we try to find the best joint angle for x-axis, y-axis and z-axis for a joint given the coordinate of the destination point (i.e. the best joint angle of each axis that could make the end-effector closer to the destination point). Suppose a joint cannot move in an axis, the best joint angle for that axis is zero. After calculating both three joint angles for each axis, we then calculate the rotation matrix for each axis, using the following rotation matrix:

Where RotX is the rotation matrix for x-axis, RotY is for y-axis and RotZ is for z-axis. We then combine these rotation matrixes into a single rotation matrix:

R = RotZ*RotY*RotX

Where R matrix is the rotation matrix of a joint. Applying rotation matrix of Joint(i) towards the end-effector will cause all the part from Joint(i) up to the end-effector to rotate. After that, the calculation will move backwards to Joint(i-1) and again we calculate the joint angle for Joint(i-1) and calculate the rotation matrix. In order to move end-effector given the rotation of Joint(i-1), besides rotation matrix of the current joint, we also need rotation matrix of the previous joint and the translation matrix of the previous link. The following is the translation matrix:

Where dX, dY, dZ is the length of the link (i.e. the distance between two joints). For transforming the end-effector given the rotation of Joint(i-1), we need the matrix of R(i-1)*T(i)*R(i), where T(i) is the translation matrix from the current joint to the previous joint (i.e. length of the link) and R(i) is the rotation matrix from the previous joint. Keep in mind that the calculation is done backwards starting from the end-effector towards the parent joint.This calculation will continue until we reached the parent joint where there will be no more joints that could rotate after this joint. After reaching the parent joint, the calculated distance between current end-effector location and the desired location should be as minimum as possible.

Related post

• Human Motion Animation with Inverse Kinematics
  

Read More

Human Motion Animation with Inverse Kinematics

Human body consists of at least a hundred joint that are connected in some way. When we try to move our hand, there are at least three joint that moves (i.e. shoulder, elbow and wrist joint). Some of human body joints are also capable in moving in 3 dimensions (e.g. shoulder, hip and neck joint). Off course, as a human, we do our movement intuitively, without trying to calculate how can we reach a position (e.g. walking, reaching, looking around, etc). But, in order to animate a human movement using a computer, we have to specify the angle of rotation for each joint in order to perform a movement. The basic procedure to animate a human body movement is to use kinematics. Kinematics is one of the fields of mechanics that evaluates the position changes of an object in a period of time without considering masses or forces of the object itself. The easiest way to apply kinematics in human animation is by using a so-called forward kinematics. Forward kinematics is a low level technique for animating an articulated structure. Using this method, the animator has a great degree of freedom to control the animation, because animator has to define the angle for each body joint. However, it might take a lot of effort to define all the components of the animation for only a single movement.

On the other hand, there is inverse kinematics which could be classified as a high level approach of animating an articulated structure. Instead of defining every transformation of joints, the animator can just define the destination point of end part of the articulated structure (i.e. hand or feet), and use that position to calculate the transformation for each joint, in backward fashion (i.e. calculate the wrist joint transformation first then elbow joint and shoulder joint as the last one).

Using inverse kinematics, it is possible to get several solutions or nothing at all. The drawback of this method is that the complexity of a structure might be very high that would lead to a condition where the calculation becomes too expensive or even impossible. The inverse kinematic could pose a non-linear problem where given a certain position x, there could be multiple solution in order to reach that position.

Inverse Kinematics

By knowing the starting and the ending position of the end-effectors (i.e. hand or feet), we then try to calculate the movement of the whole articulated structure (e.g. hand movement or walking movement). The basic idea of inverse kinematic is to find the appropriate angle of every joint in the articulated structure, given a desired position. Mathematically, inverse kinematics could be expressed as:

Θ = f-1 (x) (1)

Where Θ is the joint angle and x is the end-effector position. Since articulated structures consist of several joints, the equation above would result in a non-linear equation. So for a given end-effector location x, there might be more than one solution for Θ. For solving inverse kinematics, there are three main methods that could be used, which are:

a) Analytical method The most common way to do analytical method is by creating a closed-form equation that is obtained by trigonometric approach. The problem we faced with this method is the difficulty to obtain the trigonometric equation for every joint that are available.

b) Numerical Method We can solve non-linear equation (1) by transforming it into linear equation (linearization). After linearization, the connection between end-effector and joint angles is expressed with the following equation:

dX/dt = J(Θ) . dΘ/dt (2)

where dX/dt is the end-effector velocity, dΘ/dt is the joint velocity, and J relates the changes in the joint variables with the changes in the position of the end-effector in an M x N manner, where M is the joint variables count and N is the dimensions of the end-effector vector.

J = dF(Θ)/dΘ (3)

Where F is total function matrix for the movement of every joint angle.

Inverting equation (2) will result in:

d Θ /dt = J-1(Θ) . dx/dt (4)

And to solve it is by using iterative algorithm. When dealing with this method, we were faced with a very difficult equation in the Jacobian matrix that is hard to solve even using iterative algorithm because of the complexity of the equation.

c) Optimization Method For this method, what we do is try to solve each joint angle by trying to optimize the value of it. One of the examples of Optimization Method is the Cyclic Coordinate Descent Method (CCD) where we try to improve the angle of each joint, step by step, until the articulated structure could reach the desired end location for end-effector.

The next post will cover more about Cyclic Coordinate Descent Method.

Related post

• Cyclic Coordinate Descent
  

Read More

Modeling a Tree using L-System

An L-system or Lindenmayer system is a parallel rewriting system, namely a variant of a formal grammar (a set of rules and symbols), most famously used to model the growth processes of plant development, but also able to model the morphology of a variety of organisms. [wikipedia]

When using this model, we have to define a set of grammar rules that will be used to describe the growth of the branches of a tree. The rules that we define will later be implemented as the growth of the tree in an iterative fashion. In this system, we define these following alphabets that will be used in the production rules:

f : create branch
l : create leaf
[ and ] : define a set of local area/branch. The definitions of the area are put inside the [ and ]
+ and - : rotate the branch right/left in x-axis
^ and v : rotate the branch up/down in y-axis
<> : twist the branch left/right in z-axis

By using the symbols above, we can begin to create a tree with our system. But before that, we also have to define several properties that are also important in generating the tree, which are:

• The number of production rules iterations, for determining the level of the branches,
• The angle, for determining branch curves, and
• The radius of the branches and the decreasing value of it, in an iterative way The length of the branches

The following are several examples of the production rules that are used using the system:

Tree A

Angle : 25
# Iterations: 6
Branch radius: 0.02
Branch radius reduction: 0.0015
Branch length (height): 0.15
Initial value : fffffA
Production rules : A = f[++Al][--Al]>>>A



Tree B

Angle : 30
# Iterations: 10
Branch radius: 0.01
Branch radius reduction: 0.001
Branch length (height): 0.16
Initial value : fA
Production rules : A = f[^Bl]>>[^Bl]>>A, B = f[-Bl]B


Tree C

Angle : 15
# Iterations: 13
Branch radius: 0.02
Branch radius reduction: 0.0015
Branch length (height): 0.15
Initial value : fA
Production rules : A = ^fB>>>B>>>>>B, B = [^^f>>>>>>A]

Read More