# Physics - Open Forum Discussion - Inverse Kinematics question

By: nobody ( Nobody/Anonymous )
Inverse Kinematics question
2003-04-25 17:37
I have been building a skeltal animator and am adding inverse kinematics( The cyclical kind described on your web page ). In 2 dimensions I can get the bones to act correctly but the minute I start moving bones outside of the plane there are cases where things do not converge. I was wondering if you had encountered a similiar problem. The root bone behaves as it should but descendant bones start wobbling all over the place.
Also here is some code for a lookat function
it is just generic code and needs optimization but it seems to work. It yields a quaternion so all you do is multiply the current rot matrix by the lookat quat: (lookat_quat * currot_quat) to get a new rotation that looks at the object.
//**** UTILITY ****//
Quaternion LookAt( vec3 target_pt, vec3 end_pt, vec3 pivot_pt ){
float angle;
Quaternion q;

vec3 cur_axis = end_pt - pivot_pt;
vec3 tar_axis = target_pt - pivot_pt;
vec3 norm;

// turn vectors into unit vectors
cur_axis = Normalize( cur_axis );
tar_axis = Normalize( tar_axis );
angle = acos( Dot( tar_axis, cur_axis ) );
// if no noticable rotation is available return identity quaternion
// this way we avoid Cross product artifacts
if( fabs(angle) < 0.0001 ){
q = q.Quat_From_AxisAngle_Rad( 0, 0, 1, 0 );
return q;
}

// in this case there are 2 lines on the same axis
if( fabs(fabs(angle)-180) < 0.001){
cur_axis = cur_axis.Rot_x( 0.5f );
// there are an infinite number of normals
// in this case. Anyone of these normals will be
// a valid rotation (180 degrees). so I rotate the curr axis by 0.5 radians this way we get one of these normals
}

norm = Cross( tar_axis, cur_axis );
norm = Normalize( norm );

q = q.Quat_From_AxisAngle( -angle, norm[0], norm[1], norm[2] );

return q;
}

By: nobody ( Nobody/Anonymous )
RE: Inverse Kinematics question
2003-04-25 17:47
To elaborate on my IK question. The first bone bent: the bone at the end of the tree, appears to get bent correctly. Then a root bone is bent using the same process but it is bend in a way which undos any child bone approximation. It throws the child bone orientation off so much that the child bone does not ever converge torwards a point. I have tested this by stopping the IK chain from traveling farther down to root bones. I was wondering if there is a set of known cases where this can be a problem or if this is something buggy in my code.

By: nobody ( Nobody/Anonymous )
RE: Inverse Kinematics question
2003-04-26 05:14
I found a reference to my problem at http://www.cs.wisc.edu/graphics/Courses/cs-838-2000/Students/zhong/p3/doc/proj3.html. It is a twisting problem and I am working on a fix.
There is an error in the previous lookat 180 should be PI since I am using radians instead of degrees.

By: martinbaker ( Martin Baker )
RE: Inverse Kinematics question
2003-04-26 11:10
Thanks for this, before you sent the third e-mail I did some thinking about convergence of this method and I added some thoughts on the subject to the end of this page:

I don’t know if this is valid, I’d be interested to hear what anyone thinks.

Thanks also for the lookAt function, I am planning to add this to the appropriate page. (Some lookAt methods that I have seen also have an input to specify the up direction so that the view can be rotated to give a particular up direction) Any idea how to do this?

Martin

By: nobody ( Nobody/Anonymous )
RE: Inverse Kinematics question
2003-04-26 22:14
There is some vector et = from the eye to the target. The up vector is passed in. First normalize the et and up vectors. et is the z axis of your rotation matrix. Crossing et and up vectors you get the x axis of the rotation matrix, since the cross gives you the normal to et and up. Special case occurs when et and up lie on the same axis in this case you have to treat these seperately. Once you have the x axis and z axis of the rotation matrix just cross these 2 to get the y axis normal. Now you have the complete rotation matrix.
It helps to visualize the orthonormalized( rotation matrix ) as three unit vectors which lie along the axis. To see this is true just draw these from a matrix. For a 3x3 matrix with 9 floats choose:
x= [0], [1], [2]; y= [3], [2], [4]; z= [5], [6], [7];
or
x= [0], [3], [5]; y= [1], [2], [6]; z= [2], [4], [7];
One of these will be the axis for the rotation matrix pre rotation the other will be the axis post rotation. I didn't realize this for a while but once I did it really simplified many operations such as billboarding for particle engines.
As a side note, when animating objects and changing rotations in discrete timsteps, there are many cases where orthonormalizing a rotation is helpful. There are some methods of directly orthonormalizing a matrix such as Gramm-Schmidt, but I suspected that this didn't scale the matrix back symettrically( I was suspicious that it might twist the matrix. causing and object to roll in a less than straight line ) I did not test this however. What I did was to convert the matrix to a quaternion and normalise the quaternion then convert it back to a matrix. Time consuming but it worked. Drawing my objects was always the bottleneck not the computation of object positions. I was able to take hundreds of small timesteps between drawing frames with no noticable slowdown with 20 + pool balls. If you are animating a rotating object and you notice that it is skewing it is good to orthonormalize the matrix.
You can take advantage of the ability to skew a matrix to produce an artificial bounce deformation to an object. Just used the collision normal to deform the ball/object the same way you would use the angular velocity vector to temporarily deform the balls rotation matrix and you will have a squashed ball.

By: martinbaker ( Martin Baker )
RE: Inverse Kinematics question
2003-04-29 18:06
I have tried to implement the lookup function here:

I tried to use quaternions instead of matrix, and I don’t think it is quite right, can anyone help?

Thanks,

Martin

By: nobody ( Nobody/Anonymous )
RE: Inverse Kinematics question
2003-05-01 22:19
This is in response to my first inverse kinematics question. I fixed my skeletal animation system so that bone dragging happens the way you expect it to. This was more work than was necessary and I suspect that adding features and building a more complex system will give me more problems because I have not designed the bone and joint data structures correctly.
I am sure that if I had taken more time to see how you had implemented these I could have learned how do build better bones.
When applying the recursive Inverse Kinematics method described on one of these pages there is a difference between applying it in 2 and 3 dimensions. This happened for me because I was using angle axis representation for all of my calculated vectors. In 2 dimensions the axis will always be perpendicular to the plane that you are working on. If you work through some sample recursive problems on paper you will see that in 2D these axis will not impart any twist on a bone. If you work through some examples in 3D there are cases (especially where bones are bend at big angles) where the rotation axis imparts a twist on the current bone. The result of this is that the child bones may be rotated away from the target point. In many cases they will never converge since the twist places them farther from the target than when they started. I can send you a diagram of this if you would like.
The way I finally got dragging to work was to manipulate the bone points according to the algorithm and then after dragging was complete I went back and recalculated all of the bones rotation matrices.
I do not think this is a complete solution. In my method of recalculating bone rotation I lose information about previous twist of bones. Maybe I just need better data structures. Maybe stored bone twist seperate from orientation.
I also apologize for any headache my lookat function has caused. I will try to help work out the bugs. I will give you a version that just builds the rotation matrix also. I am sure there are many ways this can be improved.

By: martinbaker ( Martin Baker )
RE: Inverse Kinematics question
2003-05-02 09:51
> This is in response to my first inverse kinematics question. I
> fixed my skeletal animation system so that bone dragging
> happens the way you expect it to.

I would welcome any more code you have, which could be made available on the website.

> This happened for me because I was using angle axis
> representation for all of my calculated vectors.

In some ways it is easier to go straight to quaternions because the acos used to calculate the angle between the vectors cancels out the cos used to convert to quaternion. As discussed here:
https://www.euclideanspace.com/maths/algebra/vectors/angleBetween/index.htm

> In many cases they will never converge since the twist places them farther
> from the target than when they started. I can send you a diagram of this
> if you would like.

Yes please, is it similar to the effect discussed under convergence here?
https://www.euclideanspace.com/physics/kinematics/joints/ik/index.htm

> The way I finally got dragging to work was to manipulate
> the bone points according to the algorithm and then after
> dragging was complete I went back and recalculated all
> of the bones rotation matrices.
> I do not think this is a complete solution. In my method
> of recalculating bone rotation I lose information about
> previous twist of bones. Maybe I just need better data
> structures. Maybe stored bone twist seperate from orientation.

Since this is based in practical experience I am sure there are good reasons for doing this, but it does appear a bit inefficient. I like the idea of holding this information as quaternions for the rotation and 3d vectors for the offsets. This also seems a good way to specify constraints, for instance do you prevent bones from rotating in a way that is not anatomically possible?

> I also apologize for any headache my lookat function has caused.

Not at all, it was very useful.

> I will try to help work out the bugs. I will give you a version
> that just builds the rotation matrix also. I am sure there are
> many ways this can be improved.

Martin

By: nobody ( Nobody/Anonymous )
RE: Inverse Kinematics question
2003-05-02 23:18
Here is my best understanding of the problem. Where you describe the recursive method of IK on you page https://www.euclideanspace.com/physics/kinematics/joints/ik/index.htm

When building this algorithm for a 3D environment it does not behave as would be expected. Starting at some bone the goal is to point the bone tip torwards the goal point and if that doesn't touch the goal point descend down the skeleton until either the goal has been reached or there are no more child bones. This can be done by extracting the angle and axis from the two vectors:

v1 = first_bone_tip - cur_bone_base
v2 = goal - cur_bone_base

The angle is extracted using the Dot product and the axis is extracted using the Cross product.
Now you have a rotation that will move v1 onto v2 in angle axis form you can turn this into a quaternion or other form. This much works in 3d also.

Where I was having problems (In the 3d version )was that I was applying this rotation to the current bone I was on while moving torwards the root bone. It seems like this should work and it does some of the time.
What I think was happening but I may be wrong. First you think of a vector( v1 ) and an angle axis form of rotation ( ang, v2 ). Now think of what happens when you rotate v1 by the angle axis.
If v2 lies in the plane perpendicular to v1 then you are not twisting the vector v1 at all you are just turning it in the direction you want. When all bones lie on the 2d plane this will always be the case. There are only two vector the up and down which will always be perpendicular to the bone. If v2 was not perpendicular to v1 than in addition to turning v1 you would also be twisting it. Something weird to think about is that there may be several rotations with different amounts of twist that will result in v1 pointing the same direction.

Now go back to the 3d bone case picture a bunch of bones connected at angles that go in all 3 dimensions. Now draw the vector from the third_bone_base to the first_bone_tip and from the third_bone_base to the goal point. These two vectors lie in a plane. The vector is derived from them using the Cross product will be perpendicular to that plane. This is also the vector you use in the angle axis.
Now picture this normal from this triangle I have described and I think you will be able to find many cases in 3 dimensions where this is not perpendicular to the bone axis (When the skeleton get especially bendy in all directions). Now when you apply this rotation to the current bone in addition to rotating the bone it would put a twist on the bone. Once the twist is there it will effect the child bone tree rotating it clockwise or counter clockwise throwing everything off. This was not taken into account in the 2d version of the algorithm because it can't happen in the 2D version.

I tried many things to fix this and had many headaches. What I did was to use the original algorithm but did not apply rotation to bones as I moved them. Instead I just stored there end points and lengths and manipulated those. This works good for me. The problem is when dragging is completed I then have to recalculate all of the rotations for the bones from the bones positions. I thought I had done this correctly but after more testing it still needs some work. I am starting to think I need a clearer perspective on what aspects of rotation I should be storing in my bones.

Hopefully this has been more illuminating. I think what I have said is true but I am also going to say don't rely on this 100%. Maybe I have some other bug in my code somewhere. I am still trying to figure a better bone representation and what kind of problems could arise from the one I currently have.

By: nobody ( Nobody/Anonymous )
RE: Inverse Kinematics question
2003-05-04 21:34
I found a bug in my program which may be related to problems I was having earlier. If you have a chain of n Quaternion rotations which effect each other.
q(n) * ... * q4 * q3 * q2 * q1 = Q
q(n-1) * ... * q4 * q3 * q2 * q1 = Q2
Like you might have for a series of bones. I knew Q and q1, q2 ... q(n-1) and was trying to extract q(n).
First I tried:
q(n) = conjugate(Q2) * Q
This gave me good results until I had more than 2 bones then it went bad.
Then I tried:
q(n) = conjugate(q(n-1)) * ... * conjugate(q4) * conjugate(q3) * conjugate(q2) * conjugate(q1) * Q;
And this worked. This may be obvious to people people who have worked with rotations for a while but it fooled me for a while.