Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

In an attempt to solve this question, I decided to figure out the absolute (world space) directions of each joint in the source pose (as normalized unit vectors), and then rotate the joints of the target to match that direction. The problem is, how do I calculate the rotation quaternion such that the bone (the vector from the joint to its child) is in the specified direction in world-space.

UPDATE: Here's my current thinking. For each bone, the transformation matrix will be:

(1) absolute transform = local rotation * relative transform to parent in bind pose * parent absolute trasform

So, say we have 3 joints: Shoulder -> Elbow -> Wrist. We already have an absolute transform for Shoulder, and are trying to calculate the rotation for Elbow such that Elbow -> Wrist will go in the same direction it is in the source animation. From (1), the absolute transformations will be:

(2) ELBOW absolute = ELBOW local * SHOULDER to ELBOW relative * SHOULDER absolute

(3) WRIST absolute = WRIST local * ELBOW to WRIST relative * ELBOW absolute

By substitution we get:

(4) WRIST absolute = WRIST local * ELBOW to WRIST relative * ELBOW local *
                     SHOULDER to ELBOW relative * SHOULDER absolute

Our constants are: ELBOW to WRIST relative, SHOULDER to ELBOW relative, and SHOULDER absolute. WRIST local will consist only of rotation, no translation/scale. The problem is to find a value for ELBOW local such that...

(5) normalize(position(ELBOW absolute) - position(WRIST absolute)) = desired direction

(6) ELBOW local consists only of rotations (no translation/scale)

Now since we know the length of the bone and the desired direction it's possible to estimate the position part of of WRIST absolute, but the rotation will be unknown (and this problem seems impossible to do recursively, AFAICT).

My initial thought was that because WRIST local is rotation-only and I will solve for it in the next iteration of the loop, I could completely ignore it in the calculation of ELBOW local. Steven Stadnicki's answer below suggested it might not be that easy, since the orientation of the bone is important for skinning. However, if I can get this working on a stick figure I can cross that bridge later.

share|improve this question
2  
Hm, so if I got this right: targetDir = normalize(childPos - selfPos) . If you have a currDir, then why not compute the quat from axis angle.. similar to how they proposed it here –  teodron Apr 24 '12 at 12:38
    
@teodron -- If only it were that easy, but there are 3 other matrices it will be multiplied by. I will update the question. –  Fraser Apr 30 '12 at 19:07
    
One question, because I have the feeling that your updated question is holding an obvious answer which you don't want: Why don't you write:M = inv(childRelative) * childAbsolute * inv(parentAbsolute) * inv(selfRelative) as you would with such matrix equations? What are the selfRelative and childRelative matrices? The usual way one does transformation chaining is: childTransform = parentToChild * parentTransform . The other matrices are not that obvious in what their purpose should be. The problem is interesting and it might be swell to crack the mystery :). –  teodron May 1 '12 at 15:34
    
@teodron - Sorry, I should have been clearer. selfRelative is the bind pose matrix of the parent to this bone (the parentToChild of which you speak). childRelative is the bind-pose matrix of the current bone to the child in question. These are from the skeleton and are fixed. As for "why not solve it like a normal matrix equation", two reasons: first, M needs to be rotation-only and I also don't have the complete childAbsolute matrix, only the position part. –  Fraser May 1 '12 at 23:51
1  
Complicated problem, seems to be heavily underdetermined, so least squares/pseudo inverse tricks could help, but it's a mess and you have to do it numerically. First of all, just your rotation matrix adds 4 unknowns and is non-linear, whereas your elbow_local introduces another 8.. that's 4 equations with 8 unknowns.. Consider using kinematic chains.. with fewer degs of freedom. Have you heard of the Denavit-Hartenberg convention? I used that with pretty decent results –  teodron May 4 '12 at 8:31
show 2 more comments

2 Answers

up vote 3 down vote accepted
+100

From your description of your problem, it sounds like the heart of the matter might be that your representation is currently missing data. A bone isn't simply the vector from one joint to the next — it's a full transformation matrix representing the orientation of the local frame, either with respect to world space or with respect to the local frame of the next bone 'up the chain'. For instance, imagine a character with a scar on their forearm; having the vector from the character's elbow to their wrist will tell you where their hand will be positioned, but it doesn't carry enough information to let you know where the scar would be — for instance, whether it's pointing up or pointing down. This orientation information should be part of your source skeleton.

Once you have things represented in terms of full local orientation frames and not simply directional vectors, the rest of the information should fall out easily; exactly as you suggested in your post, you'd use matrix inverses to 'peel off' the layers of your transformations and get at the juicy matrix M in the middle. For instance, if you have childAbs = childRel * M * selfRel * parentAbs, then multiply by childRel-1 on the left of both sides, and then parentAbs-1 * selfRel-1 on the right of both sides to get M = childRel-1 * childAbs * parentAbs-1 * selfRel-1. Note that inverting a product of matrices changes the order their inverses are multiplied in, so that order matters here — (A * B)-1 isn't (in general) equal to A-1 * B-1, but instead to B-1 * A-1.

Once you've got your matrix M, there should be plenty of information on the web on how to convert it to a quaternion; if you're looking for help with that particular step, then let me know and I can flesh this out with a couple of links, but it seems like there are several other issues you'll have to tackle right now before you even need to consider it.

EDIT: After a few days to think about it, I've written up this rough description of the process for going from worldspace to local information; hopefully this will shed a bit more light.

I'm going to work in terms of a decoupled scheme where each bone consists of a rotation matrix and a displacement; the rotation matrix is applied at the root of the bone, and the displacement is given in bone-local coordinates. This does two important things:

  1. It allows for multiple bones to be attached to the same socket, making a proper skeletal tree a bit easier- for instance, collarbones can be easily attached to a central point between the shoulderblades, or finger bones to a central point on the wrist.
  2. It means that most animation of a bone can be done by just changing the rotation associated with that bone; for instance, a bicep can be moved by changing its orientation, causing the location of the elbow to be shifted around. In fact, bones will often have a displacement of (0, 0, L), where L is the length of the bone - the far end of the bone is directly along the local-Z axis from the bone's attach point.

This isn't necessarily the approach I'd recommend for implementation, but it's the most straightforward for talking about how to do it; while the precise results won't be directly applicable to your situation, IMHO that's actually for the best: it gives you better chances of understanding how the derivation works and how to derive the precise formulas that will apply to your own version of the problem.

A few quick definitions of the quantities we're working with: A superscript of 'w' designates a worldspace value, while 'l' denotes a local value. We'll use P for position, and R for rotation; for instance, Pwbone would be the worldspace target position of a bone, (as opposed to its base position, which of course is the target position of its parent), while Rlbone would be the local orientation of the bone - that is, how it's rotated with respect to its parent's frame.

Now, given this we can derive the target position and orientation of any given joint - as some of the comments suggest, the relationship is recursive. In particular, we have

Rwchild = Rwparent * Rlchild

and

Pwchild = Pwparent + Rwchild * Plchild

(These say, respectively, 'The world orientation of the child is its local orientation composed with the world orientation of its parent' and 'The world position of the child is its parent's world position offset by its local displacement (as translated into the appropriate worldspace coordinates)'.)

Given this, we can now solve these equations to find the bone's parameters - that is, Rl and Pl - in terms of the worldspace data we're given. This also gives another reason why we need not just the position but also the worldspace orientation of all the joints; it's an essential component to the solve.

Finding the local orientation is straightforward; we can just multiply both sides of our orientation equation by the inverse of the parent's worldspace orientation, getting

Rlchild = Rwparent-1 * Rwchild

The local displacement is also relatively easy to figure, since we know the displacement in worldspace and the transformation matrix to get from local space to worldspace (which means we know the matrix to go the other way) :

Plchild = Rwchild-1 * (Pwchild - Pwparent)

Notice one thing, too: none of these equations depend on the local position or orientation of the parent bone, just the worldspace values for the parent and the child - so while they feel recursive (and the calculation to find the worldspace values for the bones needs to go from the root of the skeleton out to its leaves because of dependencies on results) they can actually be done in any order.

Hopefully this gives you a better sense for what's going on - it's easy to get bogged down in all the transformations flying around. Let me know if this helps!

share|improve this answer
    
The source skeleton consists of rotations. The direction vector thing was just an attempt for me to retarget it. I can easily get the source rotation (relative to its own frame), but I don't know how this will help me, as the source has a different bind pose. As for the second part of your post, the problem is figuring out what childAbsolute will be -- I know the position, but not its local rotation. –  Fraser May 1 '12 at 9:22
    
... (wouldn't let me edit) For the purpose of calculating the rotation of the current bone, I don't necessarily care what the local rotation of the child bone will be, only that it's in the correct position. –  Fraser May 1 '12 at 9:31
    
@Fraser I worry that we're talking past each other a bit, but I simply don't understand how you can not care what the local rotation of the child bone will be. That data is essential for any skinning application on the skeleton, shy of stick-figure animation (or 2d, but then we're talking about a different problem entirely). What are you doing with your target pose such that orientations aren't a part of it? –  Steven Stadnicki May 1 '12 at 19:27
    
@Fraser If you're saying 'I only have positions on the target pose's joints, not any orientation' and you need to determine reasonable orientations for the target pose's bones too, then that's another problem altogether (and a much, much harder one), but even there I feel like the problem would be much better solved by trying to figure out how you can get the orientation out of your target pose data, rather than by trying to craft a 'reasonable' orientation on your own. –  Steven Stadnicki May 1 '12 at 19:31
    
I re-wrote the question to make it clearer what I'm trying to accomplish. Here's a video of my progress as of 2 weeks ago: youtube.com/watch?v=H6Qq37TM4Pg ... Thanks for all your help, dude. –  Fraser May 2 '12 at 0:35
show 1 more comment

If I got this right, you are storing the whole skeleton bones vertexes into a matrix. I think your problem is more related to the way you are storing the Bones than to quaternions themselves.

I'll try to explain what I mean:

Since you basically have the result of the rotation (a rotated bone to use as a model), and you want to know the quaternion that would generate that result for other bones, why can't you store the bones as vectors, instead of generating a matrix?

You could a bone stored as a vector made of 2 points (Head,Tail). Since you are rotating it, Head will be the fulcrum and Tail will rotate around an arbitrary axis. That's a quaternion's job.

Now, since you have Bone A a 'rested' position, and you want to match Bone B direction you need to know the amount of rotation Alpha and the Axis. Right?

Getting the angle between the 2 Bone Vectors A and B you will find Alpha, and the normalized result of the cross product of AxB will get you the Axis.

The only thing that is getting this more complicated for you is that you need to extrapolate the Bone Vector from the matrix you're using beforehand so maybe you could just store the bones as vectors (pair of points) instead of creating a matrix.

Also, since you are basically rotating a bone in relation to how its parent was rotated (that's what I got from your code) then you probably could simply ignore all that.

Since you want to match another bone's position, you already know that position to be legit, so all the relative-rotation stuff shouldn't be necessary.

share|improve this answer
    
The problem with storing them as vectors is interpolation between frames or blending multiple animations. –  Fraser May 1 '12 at 1:37
    
I can't comment other users answers (yet) so...anyway, if you need more data than just 2 points, then store them in a manner that suits you. Both answers you got till now are pointed at the same problem: you're either missing data or you're using a format that causes you problem. If a bone contains rotation and translation, you could just store the respective infos without dealing with a full matrix and so avoiding the whole conversion. Using just quaternions and 2-3 points per bone, the position of the child would just be dependant on the parent's one so the system should take care of itself. –  Darkwings May 1 '12 at 18:52
    
The whole purpose of this is to be able to retarget animations from one skeleton to another so that the results can be sued like an artist-created animation, as well as be blended with procedural and artist-created animations. The data I'm storing is a rotation quaternion for each bone relative to its parent for each frame. This is already working for imported animations. I don't want to change the way I store the result animations -- this step is entirely part of the pipeline; I want the end result to work in the same way as (and inter operate with) other animations. –  Fraser May 1 '12 at 23:41
    
I saw the video. I'm still convinced that to easily store a rotation relative to a known axis (relative to the parent bone) you're still complicating your life. I understand that the reason you want a rotation-only matrix is to prevent unwanted translations, resulting in invalid parent-children position. Something that couldn't happen anyway if you were using the parent bone as the axis bound using just quaternions. Else you'd need to endlessly convert from matrix to quaternion, and then matrix again. In short, I share Steven Stadnicki's POV, when he says that it's not just a math problem. –  Darkwings May 2 '12 at 12:36
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.