Calculating a quaternion so a bone points in a specified direction

Question

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.

Answer 1

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, P^w_bone 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 R^l_bone 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

R^w_child = R^w_parent * R^l_child

and

P^w_child = P^w_parent + R^w_child * P^l_child

(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, R^l and P^l - 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

R^l_child = R^w_parent^-1 * R^w_child

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) :

P^l_child = R^w_child^-1 * (P^w_child - P^w_parent)

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!

Answer 2

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.