Quaternion question

I’m not very familiar with quat theory, and perhaps I missed something in the Matrix & Quaternion FAQ. I’m using Maya’s libraries to make sure the underlying code is correct.

I’m trying to produce a matrix that rotates my objects (which face up the z-axis in object space) onto a direction vector.

  
glTranslatef( actor->x, actor->y, actor->z );
MVector defHeading( 0, 0, 1 );
MVector noY( actor->dir.x, 0, actor->dir.z );
noY.normalize();
MQuaternion q = defHeading.rotateTo( noY );
glRotatef( q.asMatrix() );

This works fine, except when the direction I’m trying to rotate onto is (0,0,-1), anti-parallel to the vector I’m rotating from. In this case, the resulting up vector from the rotation matrix is (0,-1,0) instead of (0,1,0). I currently check for this special case, and create a correctly oriented quat:

q.setAxisAngle( MVector( 0,1,0 ), 180.0 );

What causes this up-vector flip, and am I handling it well, or will this approach continue to generate special cases?

I know that I can use other means to generate the rotation matrix, with an up/right vector system. I’m more curious as to how to do this with quaternions, the right way.

Thanks.

May be you’d like to check out gimbal lock, an effect that can be seen when using euler angles and equivalent quaternions implementations. See this

http://www.gamedev.net/reference/articles/article1095.asp

or google for ‘gimbal lock quaternions’.

However, I’m not entirely certain this is your problem.

madmortigan

Yeah, that’s a sticky situation for sure. The problem is that quaternions have no notion of what “up” is, so you have to supply this information explicitly somehow. That is why it is generally better to use Euler angles or Frenet frames to represent orientations, then use quaternions to interpolate between them.

I’m not quite sure what your ‘rotateTo’ function does, but here’s a function that calculates a quat given “from” and “to” vectors. It automatically handles the opposing vectors case. I tested it for the case you mentioned, and it maintained a matrix “up” vector of (0,1,0).

#define	EPSILON  (1e-10)

// NB: The normalize calls maybe omitted if 
// it is known that that input vectors will
// always be normalized. Also, you may prefer
// float to double precision calculations.
 
Quat fromTo( Vector3 from, Vector3 to )
{
    Quat result;
  
    Vector3 u1   = normalize(from);
    Vector3 u2   = normalize(to);
    Vector3 axis = cross(u1,u2);
 
    double magnitude = sqrt( dot(axis,axis) );
    if( magnitude > 1.0 )
        magnitude = 1.0;
 
    double theta      = asin( magnitude );
    double complement = PI - theta;
 
    if( dot(u1,u2) < 0.0 ) 
    {
        theta      = complement;
        complement = PI - theta; 
    }
 
    if( theta < EPSILON ) 
    {
        result.x = 0.0;
        result.y = 0.0;
        result.z = 0.0;
        result.w = 1.0;
    }
    else 
    {
        if( complement < EPSILON )
        {
            if((u1.y * u1.y + u1.z * u1.z) >= EPSILON )
            {
                axis.x = 0.0;
                axis.y = u1.z;
                axis.z = -u1.y;
            }
            else
            {
                axis.x = axis.y = 0.0;
                axis.z = 1.0;
            }
        }
  
        // Construct result from axis and angle.
        result = Quat( normalize(axis), theta );
        result = normalize(result);
    }
 
    return result;
}

edit:

added a word or two.
reformatted.

Hi,

As you’ve noticed, you need to special case the situation when vFrom == -vTo. This happens because there is no clear axis to rotate around - any axis that lies on the plane that is perpendicular to vFrom will suffice. You might also need to check for vectors that are nearly anti-parallel as well (i.e. within an epsilon) to make it 100% robust.
That said, it’s the only special case I think you’ll need. This webiste: http://number-none.com/product/ has some excellent quat articles that help to give a pretty intuitive understanding of how quats work.

stoo

Hey, I noticed this thread because of stoo’s link to my web page.

I would recommend not to follow Q’s advice too closely. There is definitely no reason to store Euler angles as your default rotation representation. Frenet frames are a better idea but they are bulkier. Quaternions are probably your best bet.

For a given rotation, the quaternion, Euler angle, and Frenet frame store exactly the same thing. There’s no difference between how much information is present in each of these. e.g. it’s totally untrue that a quaternion has no notion of where “up” is and Euler angles somehow do.

The problem CatAtWork’s having is entirely in rotateTo. The point of this function is to find the smallest rotation between two headings. (There are always an infinite number of rotations that map one vector onto another one; you want the shortest one, usually). Well, when you take the case of a vector mapping to another vector that points in the opposite direction, suddenly every direction you rotate is equally as good – you can rotate around any axis, the answer is always that a 180 degree rotation will give you the other vector.

So the problem isn’t in the quaternion (or any kind of rotation representation). The problem is in the problem statement itself – trying to come up with the shortest-path rotation when there isn’t specifically such a thing.

The code that Q pasted in handles this case by tweaking around with the coordinates to just pull an axis out of thin air. This is usually how the problem gets solved (though if you look around you can find examples with code that is made to run really fast. My articles that stoo pointed to have one or two examples of that, but there are plenty of others).

The up-vector flip that CatAtWork sees is because rotateTo is handling this problem by pulling an axis out of thin air. This axis is discontinuous with what came before, so the resulting frame is oriented around the wrong way. There’s no way for rotateTo to do a better job of this for you, unless you had a version where you provide it more information (like some way to choose a preferred frame).

Given that, the solution you have (to fix the up-vector after the fact) is not too bad. You could also just write your own version of rotateTo that takes augmented information.

Also, just to make clear, the problem has absolutely nothing to do with gimbal lock (as madmortigan suggests). Gimbal lock does not happen when you use quaternions; that’s part of the point.

-Jonathan.

Hmmm, interesting. Just to clarify a few points…

There is definitely no reason to store Euler angles as your default rotation representation. Frenet frames are a better idea but they are bulkier. Quaternions are probably your best bet.
How would you propose to create the quaternions in the first place?. Quaternions are almost invariably created from Euler angles or Frenet frames (a matrix) to begin with. Working with a quaternion directly would be unwieldy in an editor, for example. The general idea is to model the orientation in the traditional way, then convert it to a quaternion, presumably for the purpose of interpolation, followed by the conversion back to a matrix for rendering. All this could be obviated if deemed unecessary. It depends entirely on the context.

e.g. it’s totally untrue that a quaternion has no notion of where “up” is and Euler angles somehow do.
What I meant was it would be impossible to construct a quaternion with an “up” axis without explicitly defining it somehow. Whereas with Euler angles, this is implicit; it’s explicit with a Frenet frame.

The problem is in the problem statement itself --trying to come up with the shortest-path rotation when there isn’t specifically such a thing.
This is not the problem as I understand it. The problem is finding a quaternion that rotates the vector “from” to the vector “to” while maintaining the desired orientation (“up” vector). A shortest path always exists.

The code that Q pasted in handles this case by tweaking around with the coordinates to just pull an axis out of thin air.
It’s not pulled out of thin air. A careful attemp is made to find a vector orthogonal to both the input vectors. This is the very crux of the proceedure. It does this by assuming that both “from” and “to” span the plane that has “up” as its normal. If this fails, then a cannonical axis is chosen instead.

And the code is intentionally simple. CatAtWork admitted a weakness in this area, so I though it would be more informative this way. Getting rid of the normalize calls would be a good start if you know your input vectors will always be unitized. And you could favor floats over doubles if you precision requirements allow it. Here’s the best optimization of all: don’t use a funtion like this in the first place; use a simple rotation instead (if possible).

There’s no way for rotateTo to do a better job of this for you, unless you had a version where you provide it more information (like some way to choose a preferred frame).

This is precisely why I suggested using Euler angles or Frenet frames in the first place. There will always be the chance for this ambiguity. With Euler angles, for example, it’s easy, just rotate by 180 around your “up” axis, whatever it may be. Or, with Frenet frames, simply construct the basis you want directly (my personal fave).

It should be pointed out that the choice will depend on the application. Quaternions certainly excell at certain things. Once you have sufficient experience with each one, the choice will be easy for you.

How would you propose to create the quaternions in the first place?. Quaternions are almost invariably created from Euler angles or Frenet frames (a matrix) to begin with.
In my world that’s not how things go at all. Euler angles don’t exist in my code. I use matrices lots, but going from quat->matrix and almost never the other way around. (There’s a sort of data flow where representations flow downhill, and a matrix tends to be the final end-form of stuff).

Nearly all of my rotations are created directly as quaternions…

Working with a quaternion directly would be unwieldy in an editor, for example.
Yeah, totally. At the same time though, I don’t think Euler angles are much good either. In an editor you want to get away from those rotation representations and have a viewable/tweakable system that is focused on what the user is trying to do

This is not the problem as I understand it. The problem is finding a quaternion that rotates the vector “from” to the vector “to” while maintaining the desired orientation (“up” vector).
This is a bit confusing and I guess it’s hard to understand the exact situation without seeing what rotateTo does and what it’s inputs are. It seemed to me that the up-vector being what it was was just a side-effect of what he was doing, that it wasn’t enforced. Perhaps the original poster can clarify here.

A shortest path always exists.
Well, if you have a frozen up-vector (consider a 2D rotation) there still isn’t a unique shortest path – you end up with two, one clockwise around the up-vector, one counter-clockwise. The difference though is, it becomes easier to pick on e of them arbitrarily since you just know what the axis of rotation is.

It’s not pulled out of thin air. A careful attempt is made…
The “out of thin air” wasn’t a dis on your code; I was just trying to explain the nature of what MUST be done. Yes, yo ucan try carefully to find a vector orthogonal to both inputs, but if they are colinear such a vector simply does not exist. And so you must pick it out of thin air. That’s the nature of the math. Trying hard to find that orthogonal vector can help a little bit as numerical accuracy starts to degrade, but it becomes ineffective as soon as you actually hit that singularity. Which of course you know (“a canonical axis is chosen instead”).

Also I realize you wrote it to be easy to read, not fast. I wasn’t trying to say your code sucks or anything. I am a big fan of writing slow code that is easier to understand. I just wanted to put it out there that the operation can be done a lot more quickly if speed is required (otherwise someone might just look at all those normalizes and rule it out).

Nearly all of my rotations are created directly as quaternions…
Clearly you must have some well defined quats. I guess my point is that if they are not so well defined, or lack the required info, it’s going to be awkward using them, as it would appear is the case here. It’s just such a nasty “gotcha” that I simply recommend skirting around it where posssible.

I use quats exclusively for animation. But this works well because the quats are created from very well defined frames. In CatAtWork’s case, the frames are not well defined at all (just a measly vector pointing in some direction).

I just wanted to put it out there that the operation can be done a lot more quickly if speed is required (otherwise someone might just look at all those normalizes and rule it out).
Good point.

Thanks for the very constructive discussion.

Here’s my original thought process:

The from and to vectors form a plane with the y axis as its normal. (Except in the anti-parallel case)

The quaternion produced by the rotateTo function should be the shortest arc between the two, so it should lie in the y-up plane.

My slightly improved understanding is that the anti-parallel case results in an infinite number of shortest arcs between the two vectors.

After reading the Inner Product columns, I suppose I have many fundamental flaws in my general approach to all of this, but I’m not quite ready to absorb geometric algebra.

I thought this would be a good approach, since I have a fixed timestep backend, and merely interpolate between the backend states.

The fairly simple case I was using earlier clamped the vectors into the X-Z plane, but this isn’t going to last forever. I suppose I’ll have to store a quat/position or matrix instead of a just a direction vector and a position. Something inside me dislikes the idea of the alternative up/right vector approach, but maybe I’m just being silly.

I suppose I’ll have to store a quat/position or matrix instead of a just a direction vector and a position.
If all you need is a single orientation, then it’s going to hard to beat a simple matrix form. On the other hand, if you require a complex animation/rotation path, then the quats will be invaluable; but you will still need to define the basic orientations somehow. This will likely require more than a single vector, but it depends on your particulars.

Something inside me dislikes the idea of the alternative up/right vector approach, but maybe I’m just being silly.
You’re just being silly.
:stuck_out_tongue:

Seriously, maybe it would help to have a better idea of exactly what it is you’re trying to do. Is this an animated model with mutliple bones? Or is it a static model that you just want to rotate?

On the animation front, I know of model formats that store bone orientations as Frenet frames. But it’s trivial to convert these frames into quats on load, if you need to. And you can keep them as quats for the life of the model, without problems. If the modeler stores the orientations as quats, that’s okay too, since the quats already define the orientation completely. The problem occurs when trying to define an orientation “on the fly” with insufficient information, as you’ve already surmised.

On the static model front, I use Euler angles in my editor to manipulate polyhedrons, and they’re more than adequate. I also have a scripted interface for the entities in my worlds, so Euler angles make for a clean and simple interface with which an entity can orient itself dynamically. This is just to point the importance of the application question. Euler angles are by no means obsolete in all contexts; I would never suggest that they be used for animation frames, though.

This test case was for skinned meshes. I wrote an exporter for Maya that uses something similar to the md5 format, but the test case was only for orienting the models according to their ‘heading.’

Right now I’m skinning on the CPU, but using OpenGL to move the model to world space. I’m considering actually applying the translation and rotation of the model to the root bone of the skeleton, which could be a little simpler for collision.

I wrote an exporter for Maya that uses something similar to the md5 format, but the test case was only for orienting the models according to their ‘heading.’
The exporter sounds interesting. I’m not familiar with the md5 format, but I am familiar with md3, and that stores bone orientations as frames.

I’m considering actually applying the translation and rotation of the model to the root bone of the skeleton, which could be a little simpler for collision.
That sounds like a good plan. On the collision point, are you planning on interactions between the model and a virtual world? If so, then the physics/collision engine itself may drive the bone orientations to some extent (ragdoll effects, etc.). Not to go to far afield, but it certainly raises some interesting questions.