Skeleton transforms

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 R^j_i is the rotation (or orientation) of joint i with respect to joint j, and T^j_i is the translation of joint i with respect to joint j. Letting p⁰_n (joint n with respect to the world) be the point you're interested in, the formula becomes:

p⁰_n = R⁰₁T⁰₁R¹₂T¹₂R²₃T²₃...R^n-1_nT^n-1_n[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 pⁿ_n+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:

p⁰_n = (R⁰₁T⁰₁R¹₂T¹₂R²₃T²₃...R^n-1_nT^n-1_n)[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:

p⁰_n = (R⁰₁(T⁰₁(R¹₂(T¹₂(R²₃(T²₃...(R^n-1_n(T^n-1_n[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:

pⁿ_n+1 = Tⁿ_n-1Rⁿ_n-1...T³₂R³₂T²₁R²₁T¹₀R¹₀[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]

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 R^n-1_nT^n-1_n), 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]

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]

This doesn't add anything to the convo,

They have an MD5 format?!?! here I am using md2 like a sucker!

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.