Sign in to follow this  
dcosborn

Skeleton transforms

Recommended Posts

I've been working for a couple of weeks at getting skinned animation in my game. Its working except for one fundamental detail: the bones are getting screwed up during coordinate system conversions. I'm using the md5mesh format, which stores bones in object space. I'm taking these bones and transforming them into parent space, performing the necessary animations (none at the moment), and converting them back to object space for rendering. Everything works if I just leave them in object space, but then I wouldn't be able to animate them. I realize this might be a bit confusing (its certainly confusing me) so I don't expect anyone to solve the problem for me; just help me figure out what I might have done wrong. I suspect the math logic must be wrong somehow. The general format of my math functions is fn(output, operand1, operand2, ...). Everything is shortened (ie: quat refers to quaternion, conj refers to conjugate). Here's my method for getting the bones from object space into parent space:
// bone->origin is a 3 component origin vector
// bone->orient is the bone's orientation as a quaternion

// 1. subtract the parent's origin from the bone's origin
util_math_vec3_sub(&bone->origin, &bone->origin, &bone->parent->origin);
// 2. find the inverse of the parent's orientation
struct util_math_quat parent_orient_inv;
util_math_quat_conj(&parent_orient_inv, &bone->parent->orient);
// 3. multiply the inverse with the bone's orientation
util_math_quat_cat(&bone->orient, &bone->orient, &parent_orient_inv);

// now bone->origin and bone->orient should be relative to the parent
Now, using the results of the previous method, we try to get the bones back into object space:
// bone->space is the final object space matrix for vertex skinning

// 1. generate the bone's matrix using its orientation
util_math_mat4_quat(&bone->space, &util_math_mat4_id, &bone->orient);
// 2. translate the bone's matrix using its origin
util_math_mat4_tlat(&bone->space, &bone->space, &bone->origin);
// 3. concatenate the bone's matrix onto the parent's matrix
if (bone->parent) util_math_mat4_cat(&bone->space, &bone->space, &bone->parent->space);

// the resulting matrices are used to transform the mesh's weighed vertices
My bones are stored in an array, sorted with root bones coming first and terminal bones coming last. This is so I can iterate forwards to cumulate the effects of my transformations through the heirarchy, or backwards to avoid cumulation. The first method iterates backwards so that each bone's parent remains in object space until all of its children have been transformed. The second method iterates forwards so that the transformations can be accumulated down the heirarchy. [Edited by - dcosborn on October 23, 2005 4:54:28 PM]

Share this post


Link to post
Share on other sites
This is the basic method I learned when doing skeletal animation. Let's say you want to find the world-space coordinate of joint n, and that the joint hieracrhcy is numbered 1,2,3,...,n (i.e. 2 is a child of 1, 3 is a child of 2, etc.) and that joint 1 is a child of the world-space, denoted 0. Let's say that Rji is the rotation (or orientation) of joint i with respect to joint j, and Tji is the translation of joint i with respect to joint j. Letting p0n (joint n with respect to the world) be the point you're interested in, the formula becomes:

p0n = R01T01R12T12R23T23...Rn-1nTn-1n[0 0 0 1]T

That's just a concatenation of standard local-to-world transformations designed to support a hierarchial joint structure. If you were trying to find the position of some vertex attached to joint n, then instead of [0 0 0 1]T you'd use the position of that vertex with respect to joint n (if that point is labeled n+1, then pnn+1).

I think a source of a lot of confusion is the actual implementation of the trasnformation chain. The primary reason being, even though matrix multiplication is technically associative, different ways of implementing the chain of transformations lead rise to new concepts such as accumulated and non-accumulated transformations. For example, if you implement the above like this:

p0n = (R01T01R12T12R23T23...Rn-1nTn-1n)[0 0 0 1]T

Where you multiply all the transformations together and then apply them to the point, then they accumulate from left to right. However, if it's implemented like this:

p0n = (R01(T01(R12(T12(R23(T23...(Rn-1n(Tn-1n[0 0 0 1]T))))))))

where each transformation is individually applied to the point from right to left, giving rise to a bunch of intermediate partially transformed points, now the transformations are non-accumulated in the order you apply them, and all rotations/translations remain relative to the original frame. While in the end it doesn't matter which way you do it, each implementation has its own conceptualization of how the transformations affect the point and in what order. In the first case, you need to start from the root and go down to the child in order to accumulate the transformations, while in the secoond case you start from the child and apply each transformation to the point until you get to the root. But in both cases, you don't need to worry about the inverse transformations which is something I see in your code, since you have all local-to-world transforms and no world-to-local. The inverse case isn't exciting for just the joints because the location of joint n relative to it's own coordinate frame is [0 0 0 1]T (since the location of a joint defines the origin of its local frame), however if you have some arbitrary point labeled n+1 you want to find in the joint n frame, then the world-to-local transform would look like this:

pnn+1 = Tnn-1Rnn-1...T32R32T21R21T10R10[X Y Z 1]T

Where [X Y Z 1]T is the location of point n+1 in world-space. Notice how I switched the superscripts and subscripts - this is just a convenient way of saying the inverse matrix. Combined with the reverse application of the transformations, you get the full inverse transformation.

I hope that helped and didn't add any more to your confusion! [smile]

EDIT: Just wanted to clarify something. The notation [X Y Z W]T means I'm using column-vectors. If I were using row-vectors, everything would be reversed.

[Edited by - Zipster on October 23, 2005 8:13:18 PM]

Share this post


Link to post
Share on other sites
Thanks for laying everything out so clearly. I think part of my confusion may be from the fact that my joint orientations (rotations) are in joint-local space while my joint origins (translations) are in parent space. I didn't really think about that before but I think it may affect how I should order my transformations and I should have mentioned it. If I rotate a joint before translating it (as in Rn-1nTn-1n), the resulting origin, which should be based on the parent, will have been rotated by the local orientation... right?

[Edited by - dcosborn on October 23, 2005 9:17:27 PM]

Share this post


Link to post
Share on other sites
You know more about the MD5 format than I do, so how you actually go about transforming your points back and forth depends on what information you have. From my understanding, the mesh joint data is in absolute coordinates. However they give you both a translation and a rotation. Right now when you render the joint hierarchy, do you apply the rotation first or the translation first? Likewise, when you're calculating the 3D vertex data from the weights, do you apply any transformations to the weights first or are they already in world-coordinates, and do you just add them to the joints?

It's also possible to convert the animation-data into object space, which would save you a transformation stage. Because right now it seems like you'd convert object-space to world-space to perform animation, back to object-space for the renderer, which at some point must convert back to world-space for the underlying API. So you can either convert the animation data to object-space and use your existing rendering technique, or convert your mesh data into world-space and rewrite your render code to work with data that's already in world-space. Just some suggestions [smile]

Share this post


Link to post
Share on other sites
Zipster, thanks for all your help. I actually have it ALMOST working. There's a couple quaternions that seem to be reversing. But otherwise, its looks like its finally acting as it should. FYI, you were right about the transformation order.

illadel4life, MD5 supports weighed skeletal animation rather than keyframes. You should really give it a try. Its all in text format too, so its fairly easy to parse with some *scanf() calls.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
some infos about the md5 files can be found here:

http://www.doom3world.org/phpbb2/viewtopic.php?t=2884




"There's a couple quaternions that seem to be reversing."

maybe this helps:

http://www.doom3world.org/phpbb2/viewtopic.php?t=2884#30185

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this