• Advertisement
Sign in to follow this  

Practical issues with quaternions

This topic is 3725 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm having some trouble understanding how to use quaternions in a practical way in my engine. I tried something where I stored the game state by a pitch and azimut angle, but before I managed to implement this with quaternions, I found out that many professional engines seem to use a quaternion (and a position vector) to store the STATE of each object, something that seems confusing to me. The way I understood it, a system storing the state in the form of a quaternion works like this: i. On mouse rotation: 1. get user rotation angles a_p and a_a (pitch and azimut, respectively) 1. Let q be the old quaternion representing the orientation of the object 2. Let x be the x axis in world space (i.e. 1,0,0). 3. Let x' := q * x * q.conjugate() 4. Make a quaternion out of x' and a_p, maybe normalize etc 5. Let q' := x' * q' * x'.conjugate() 6. Let y be the y axis in world space (i.e. 0,1,0). 7. Let y' := q' * y * q'.conjugate() 8. Make a quaternion out of y' and a_a, maybe normalize etc 9. Let q'' := y' * q' * y'.conjugate() 10. update object state with q set to q'' ii. When rendering this object: 1. calculate a rotation matrix R from q by using one of the quaternion-to-rotation-matrix translation recipes given in almost all quaternion tutorials on the web, and then use W = T * R as model-to-world matrix in the rendering My questions are: - Is this the correct maths/pseudo code? - Is this really that much faster than using matrices (especially if you compare quaternions to SIMD optimized matrix-vector multiplications? Or are there some optimization shortcuts that I've forgotten in the listing above? - Finally, how should I constrain the pitch angle to a certain allowed interval?

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by all_names_taken
I'm having some trouble understanding how to use quaternions in a practical way in my engine. I tried something where I stored the game state by a pitch and azimut angle, but before I managed to implement this with quaternions, I found out that many professional engines seem to use a quaternion (and a position vector) to store the STATE of each object, something that seems confusing to me.

The way I understood it, a system storing the state in the form of a quaternion works like this:

i. On mouse rotation:
1. get user rotation angles a_p and a_a (pitch and azimut, respectively)
1. Let q be the old quaternion representing the orientation of the object
2. Let x be the x axis in world space (i.e. 1,0,0).
3. Let x' := q * x * q.conjugate()
4. Make a quaternion out of x' and a_p, maybe normalize etc
5. Let q' := x' * q' * x'.conjugate()
6. Let y be the y axis in world space (i.e. 0,1,0).
7. Let y' := q' * y * q'.conjugate()
8. Make a quaternion out of y' and a_a, maybe normalize etc
9. Let q'' := y' * q' * y'.conjugate()
10. update object state with q set to q''

ii. When rendering this object:
1. calculate a rotation matrix R from q by using one of the quaternion-to-rotation-matrix translation recipes given in almost all quaternion tutorials on the web, and then use W = T * R as model-to-world matrix in the rendering

My questions are:
- Is this the correct maths/pseudo code?
- Is this really that much faster than using matrices (especially if you compare quaternions to SIMD optimized matrix-vector multiplications? Or are there some optimization shortcuts that I've forgotten in the listing above?
- Finally, how should I constrain the pitch angle to a certain allowed interval?
As far as I can determine, the use of quaternions (and of incremental rotations) as described above is more or less pointless. Also, I would think that any minor differences in speed in relation to the matrix version would be a) negligible and b) unimportant (assuming that this is only being done once per game update).

If you want FPS-style motion (which is what your post suggests), I recommend simply representing your object in terms of a position and an Euler-angle pair (azimuth-elevation, pitch-yaw, or whatever). Then, simply construct a matrix from these data when needed. (Incidentally, this makes pitch/elevation constraint trivial.)

I have some links I can post if you need more info on how to implement this.

(BTW, even when using Euler angles/spherical coordinates, you can easily construct a quaternion-vector pair if needed, say, for use with an existing scene graph system or third-party API.)

Share this post


Link to post
Share on other sites
Ok... but why are quaternions so popular and used in so many engines (for example Ogre3D), if they are so problematic? What is all the hype about?

Share this post


Link to post
Share on other sites
Some adventages over matrix

- It takes 4 floats values to store rotations.

- some people say it help to avoid the gimback lock effect in some cases.

- Quaternions are very good for doing smooth interpolation, that mean calculationg all orientation you want between a initial and final orientation; that is done using an algorith called SLERP, for example if you do NewRotation=SLERP(initial,final,k); "k" is a value between 0 and 1 so if you do a loop like 0.01 to 0.99 you will get a smooth rotation going from "initial" to "final" quaternion; that is a must when doing character animation where you need to calc frames between keyframes.

Using quaterion for camera movement is also good if you want to do some kind inertia & acceleration using the initial camera orientation and the desired final camera orientation.

Share this post


Link to post
Share on other sites
Quote:
Original post by tpascal
Some adventages over matrix
- some people say it help to avoid the gimback lock effect in some cases.
These people are ignorant and wrong.
Quote:
- Quaternions are very good for doing smooth interpolation

That's the biggie. Even linearly interpolating quaternions looks surprisingly good. Also, quaternions are more numerically stable than matrices; it takes them longer to skew significantly from SO(3), and renormalizing them in a reasonable way is much simpler.
Quote:
Using quaterion for camera movement is also good if you want to do some kind inertia & acceleration using the initial camera orientation and the desired final camera orientation.
Another good reason. Everyone talks about SLERPing, but SQUADing (spherical quadric interpolation) can produce some really great results, particularly for camera motion. Others have used NURBS curves over quaternions-as-vectors to accomplish similar effects.

Share this post


Link to post
Share on other sites
I've also heard that quaternions avoid gimbal lock and I am surprised to learn that it's not true. Does anyone know how or why that rumor started?

Share this post


Link to post
Share on other sites
Quote:
Original post by CDProp
I've also heard that quaternions avoid gimbal lock and I am surprised to learn that it's not true. Does anyone know how or why that rumor started?

As far as I can tell, it started because everybody "knows" that gimbal lock is bad, yet practically no one understands what it is. And since quaternions differ from euler angles in not exhibiting gimbal lock, people somehow associated gimbal lock with "normal" rotation, and lack of gimbal lock with "quaternion" rotation.

In reality, gimbal lock is an effect which one rarely encounters in game development; unless you are writing a flight simulator or an IK solver, you're unlikely to ever see it.

Share this post


Link to post
Share on other sites
Gimbal lock is a result of improper combinations of successive rotations: when the rotation axis of a later rotation is placed to be in parallel with the rotation axis of a previous rotation. Since Euler angles are a rotation representation that is defined to be the combination of three rotations, running into situations with gimbal lock seems to be easier, but that's due to a lack of understanding of how to properly combine rotations represented by Euler angles.

Share this post


Link to post
Share on other sites
Ok, thanks for clearing up the gimbal lock issue, now my use of matrices feels much better :)

And if I understood correctly, in practise I should mainly be using quaternions for cutscenes and the like?

About character animation, is the effect much worse with matrices? I was planning to use a matrix palette for bones animation, but does that look bad? Should I instead try to create a quaternion+position pairs palette for bone animation in my engine?

Share this post


Link to post
Share on other sites
Quote:
Original post by all_names_taken
And if I understood correctly, in practise I should mainly be using quaternions for cutscenes and the like?
Erm, no - what gave you that impression exactly? :)

Just think of it this way: you can use a quaternion anywhere you would normally use a rotation matrix (more or less), and the only differences are going to be internal (i.e. not visible) trade-offs in storage requirements, efficiency, code clarity, and so on.
Quote:
About character animation, is the effect much worse with matrices? I was planning to use a matrix palette for bones animation, but does that look bad? Should I instead try to create a quaternion+position pairs palette for bone animation in my engine?
Again, it's not about 'effect' or how something looks - the person viewing the simulation is not going to be able to determine whether matrices or quaternions were used just by looking.

IMO there's little point in choosing a rotation representation until you have a pretty good understanding of the differences between them. For this purpose I recommend this article, which provides an excellent overview of the subject.

Share this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
Gimbal lock is a result of improper combinations of successive rotations: when the rotation axis of a later rotation is placed to be in parallel with the rotation axis of a previous rotation. Since Euler angles are a rotation representation that is defined to be the combination of three rotations, running into situations with gimbal lock seems to be easier, but that's due to a lack of understanding of how to properly combine rotations represented by Euler angles.


That was nicely put. About Euler angles: There's a lot of ambiguity when talking about Euler angles, and it seems very often that whenever someone uses a triple of angles to represent an orientation some way, it's automatically called Euler Angles -representation. I see wikipedia's Euler Angles article give some kind of distinction to the different conventions, but in the latter paragraphs they seem to forget what had been written in the first paragraph.

In my mind, I distinguish two types of "Euler angles" -uses:
1) Fixed Axes rotations, or what I call the Euler angles. This is 3 rotations about fixed "world" axes, the exact order (XYZ, YZX, ...) is specified as a convention.

2) Rotating Axes representation, or what I think of as "yaw-pitch-roll" -representation. The axes about which we rotate are not fixed, but change according to the previous rotations we have already applied to the object.

Now, gimbal lock is a *LOGIC* problem and not a representation problem. (1) suffers from gimbal lock, because of the reason SiCrane mentioned, whereas (2) cannot exhibit this behavior. This is independent of whether you use matrices or quaternions to represent rotations.

The reasons where quaternions are preferable over matrices:
- Storage Space (4 vs 9), which gives us the preferred less degrees of freedom -property (only the unityness to take care about)
- You can extract the angle and axis of rotation easily, whereas with a rotation matrix it requires more computation (and approximation if the matrix gets skewed)
- Concatenating rotations is computationally less demanding and more stable.
- You can perform different kinds of interpolation.

Quote:
Original post by all_names_taken
And if I understood correctly, in practise I should mainly be using quaternions for cutscenes and the like?

About character animation, is the effect much worse with matrices? I was planning to use a matrix palette for bones animation, but does that look bad? Should I instead try to create a quaternion+position pairs palette for bone animation in my engine?


With bone animation, you have three goals: (of which some might be secondary to you)
- to be able to reproduce the bone animation as exact as it is seen in your modeling package
- to do it reasonably fast
- to consume as little storage space as possible

With bone animations you have a few choices with the storage format:
1) some kind of Euler angles -convention
2) ready-sampled matrices (fast but poor quality, interpolating is hard)
3) quaternions

The common way is to convert quaternions to matrices for the GPU, but there are a few papers that do quaternion skinning on the GPU. Which approach to take depends on what your requirements are.

For camera animations (assuming that these don't come from artist data), the only right way is to choose whichever representation is easier for your logic. Pick a cool quaternion camera if you can figure out a nice use for it. If not, implement a robust matrix camera. Camera will probably be quite near the core gameplay code, so the features vs complexity vs expressability aspects will tell you what you need.

Share this post


Link to post
Share on other sites
Quote:
Original post by clb
In my mind, I distinguish two types of "Euler angles" -uses:
1) Fixed Axes rotations, or what I call the Euler angles. This is 3 rotations about fixed "world" axes, the exact order (XYZ, YZX, ...) is specified as a convention.

2) Rotating Axes representation, or what I think of as "yaw-pitch-roll" -representation. The axes about which we rotate are not fixed, but change according to the previous rotations we have already applied to the object.
But these are the same thing. A fixed-axis XYZ-order rotation is equivalent to a ZYX-order "rotating axis" rotation. It's just the same old object-local versus world-local thing: a matter of nomenclature, not of functionality.

EDIT: er, wait. The WP article already says all that. Did I misunderstand you? Apologies if I'm angrily agreeing. [wink]
Quote:
Now, gimbal lock is a *LOGIC* problem and not a representation problem. (1) suffers from gimbal lock, because of the reason SiCrane mentioned, whereas (2) cannot exhibit this behavior.
I'd disagree with that. Gimbal lock as in "look up, then turn left and wonder why you're still looking up" is a logic problem, true, but gimbal lock as in an IK joint which has ended up with a singular Jacobian is most certainly a representation problem. And that problem can occur regardless of what order you're doing your rotations in.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
gimbal lock as in an IK joint which has ended up with a singular Jacobian is most certainly a representation problem.


I don't think that actually qualifies as a gimbal lock problem. It's a problem with the same symptoms as gimbal lock, but it's a different underlying issue, much in the same way that returning a reference to a local variable can have the same symptoms as a buffer overrun. Similar results, different causes.

Share this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
Quote:
Original post by Sneftel
gimbal lock as in an IK joint which has ended up with a singular Jacobian is most certainly a representation problem.

I don't think that actually qualifies as a gimbal lock problem. It's a problem with the same symptoms as gimbal lock, but it's a different underlying issue, much in the same way that returning a reference to a local variable can have the same symptoms as a buffer overrun. Similar results, different causes.

Sure it's a gimbal lock problem. The middle of three axial rotations has caused the first and third axial rotations to line up, reducing the rank of the matrix by 1. It's really the situation that could most exactly be called gimbal lock, given that it's the exact mathematical analogue of locked gimbals on a gyroscope.

Share this post


Link to post
Share on other sites
Then I'm failing to see why that would be representation specific problem. I thought you were talking rounding errors or something similar resulting in a degenerate matrix. But if the middle of the axial rotations cause the rotations to line up, then it would be a gimbal lock problem no matter what representation was used.

Share this post


Link to post
Share on other sites
In the case of a quaternion representation, the Jacobian of the mapping from quaternion to end effector is 3x4 instead of 3x3. In the general case, the system is underconstrained (not counting the unit-length quaternion invariant), and in the worst case it's critically constrained. In either case it's pseudoinvertible, and after a correction step the resultant quaternion is re-normalized (which will make progress in all cases except where the end effector is facing directly towards or away from the goal). You could do the same thing with a rotation matrix, I assume, using a QR decomposition (but I've never tried this).

Share this post


Link to post
Share on other sites
In molecular IK, you can use a polar decomposition as a correction step, I don't know if it applies to skeletal animation, since constraints are generally very different between the two domains. (I can't see why not, since the theory is essentially the same.) However, the cost of doing so is absurdly expensive; almost as bad as transforming the rotation matrix to a quaternion, normalizing that and converting back. It clobbers any benefits of doing the IK as a rotation matrix, so you might as well switch to a quaternion representation anyways. So I guess I agree with you in practice, but disagree in theory.

Share this post


Link to post
Share on other sites
I've always worked with 3x3 matrices and 3-vectors (I made a little wrapper Camera and Transform class over OpenGL's 4x4 matrices for this) and never encountered gimbal lock, I've even made something with planets that rotate in a solar system, with moons around them, many different rotations and translations all stacked together, and where you control a space ship in 6-DOF with newtonion physics, all with 3x3 matrices, and I've never encountered gimbal lock. What's wrong with me? :)

Share this post


Link to post
Share on other sites
Lode:
You only get gimbal lock when you do some sort of 3 axis rotation like what OP described in first post. The issue happens when two axises happen to be parallel.
Basically, Euler angles of any sort suffer from gimbal lock, whereas quaternion or matrices themselves do not (as long as you don't do something exceptionally dumb such as keeping 3 quaternions for pitch, yaw, and roll like how some poster did a while ago, expecting that disguising those angles as quaternions will somehow magically help him). In OP's first post, he is actually using pitch and azimut angles (uncomplete Euler angles)

Furthermore, gimbal lock is an issue only when you do some sort of motion that's different from just varying your angles directly. Like for example if you interpolate rotations. Or implement airplane/spaceflight simulator.

I'm using quaternions to process camera rotations in my programs, mostly because i almost always use free flight style camera. Also as was pointed out quaternions are good for interpolation.

I have a special class for rotation&translation transform, which has a quaternion and vector inside. It has multiply operator defined and is usable just like 4x4 rotation&translation matrix but without the extra overhead, and can be converted to 4x4 matrix in the end for loading into opengl etc. It also has functions for separately rotating and translating it, in local or global system. Very handy.

For interfacing with other software, though, i represent camera orientation with 2 vectors, forward and up. That's to make it easier for other people to write importers and exporters. (quaternion is not always enough to specify the camera orientation; you need to know along which axis the camera is looking in the camera's local space (commonly +z or -z but may be +y))

Share this post


Link to post
Share on other sites
Just to chime in. The different ways of representing orientation/rotations each have their own pros and cons. And at times one will be preferable for a particular operation.

------------------------------------------------------------------
Euler Angles can be very compact and an excellent way to represent orientation; however, they can cause very big problems (gimbal lock) when being used to represent rotations and interpolating between two Euler Angle representations.

Using Euler Angles for 3D animation data or especially for object rotation in a fully 3D physics engine will usually result in a very bad time.
------------------------------------------------------------------

Matrix representation suffers mainly from size, and lack of good interpolation ability especially when being used to represent a full transformation space: rotation, scale and position.

But that is also where they excel. Being able to concatenate multiple rotations, scaling and translations, and being able to easily undo it all. Also they provide the basis vectors (just that little 3x3 portion gives you orientation) for the inertial space of an object without any extra maths, unlike quaternions and euler angles.
------------------------------------------------------------------

Quaternions, unlike full Matrix Representation, only represent rotation about an axis. For interpolating between rotations in general there is no better choice.
Like Matrix represented rotations, Quaternions also can be combined through multiplication.

They can represent orientation as well but you'll have to do some math if you want the basis vectors, unlike Matrix Rotations. They also have the benefit of being more compact than a 3x3 rotation matrix, and only slightly larger than a Euler representation.
-------------------------------------------------------------------

Summary:

Euler Angles:
good for orientation, small size, bad at rotation.

Matrices:
Can present full transformation: rotation, scaling, translation
Can concatenate many rotations, translation, etc...
After all that scaling and rotating you still have a clean way to get the basis vectors.
They are Large relative to the alternatives.

Quaternions:
Excellent for rotation interpolation.
Can combine rotations easily.
Relatively small.
They can't represent a full transform like a 4x3 (or 3x4) matrix can.





Just my two cents.

[Edited by - HAM on November 8, 2007 6:09:19 AM]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement