Sign in to follow this  
The Steve

How do quaternions work?

Recommended Posts

Sneftel    1788
Idiots can learn how to use quaternions, but will not be capable of learning how they work. People who aren't idiots, but simply aren't yet well-informed about quaternions, will get a lot from this paper.

Share this post


Link to post
Share on other sites
The Steve    143
Thanks, Guys - Both of those links help. However, I am still a little bit lost. To be clear, I'm not really an idiot, but I have had a very difficult time visualizing quaternions. I'm trying to read that 2nd paper, but it's quite complex and requires a lot of math. I guess it must just be a very complex subject, but is there an example of anyone that shows the absolute basics of how quaternions can be used to make a rotation?

Share this post


Link to post
Share on other sites
jyk    2094
Quote:
Original post by The Steve
Thanks, Guys - Both of those links help. However, I am still a little bit lost. To be clear, I'm not really an idiot, but I have had a very difficult time visualizing quaternions. I'm trying to read that 2nd paper, but it's quite complex and requires a lot of math. I guess it must just be a very complex subject, but is there an example of anyone that shows the absolute basics of how quaternions can be used to make a rotation?
The usage of quaternions with respect to rotations is pretty well-documented.

There are a lot of articles and tutorials available online. Caveat emptor, though - a lot of these contain misleading or simply incorrect information. For that reason, I'd stick to reputable sources if possible (Eberly, Shoemake, and Jason Schenkel [sp?] come to mind - the latter contributed some good articles on the subject to GPG I or II, I believe).

You don't need to have a deep understanding of the math behind quaternions to use them effectively (although it's good to have an appreciation - or at least an awareness - of it).

As a way to represent and manipulate rotations, quaternions are fairly straightforward. As I'm sure you know, a quaternion has four elements, usually referred to as x, y, z, and w. x, y, and z taken together form the 'vector part', while w is the 'scalar part'.

We can encode an axis-angle rotation in a (unit-length) quaternion as follows:
q.v = (axis/|axis|)*sin(angle/2)
q.w = cos(angle/2)
From there, pretty much everything about how we use quaternions in the context of rotation falls out from the following equation:
v' = q*v*q-1
In this equation, q is a quaternion that encodes an axis-angle rotation (as shown above), v is a vector encoded as a quaternion (the vector is assigned to the vector part of the quaternion, with the real part - w - taking on an arbitrary value, usually zero), and v' is the vector (again, in quaternion form) after rotation.

It's also worth noting that for unit-length quaternions the inverse is equivalent to the conjugate, and that the equation as presented above assumes the 'mathematically correct' definition of quaternion multiplication (a 'reversed' form is also used sometimes, but we'll leave that aside for now).

The equation can be shown to be correct in various ways; Schenkel and Shoemake each have shown how the equation can be derived in various papers. (That said, unless you're particularly curious, you can just take it for granted that the correctness of the equation can be proved.)

From this equation, we can also show fairly easily that the product of two quaternions represents an axis-angle rotation that is equivalent to the rotations represented by the two quaternions applied in sequence. In this way, quaternions function much as rotation matrices do (that is, through them, rotations can be combined through concatenation).

Although you can rotate vectors 'manually' via the above equation, in practice it's seldom done this way (for a variety of reasons). Instead, the quaternion is usually converted to matrix form, and the matrix is then used to apply the transformation.

The algorithm for converting a quaternion to a matrix is well-documented, and can be derived in a number of different ways if one is interested. When consulting references on the subject, just be aware that the form of the resulting matrix depends on vector notation convention (row or column).

Ultimately, quaternions are more or less functionally equivalent to 3x3 matrices in terms of their behavior with respect to rotations. The differences between quaternions and matrices in this context basically have to do with storage requirements and run-time efficiency (and, to a lesser extent, the elegance and/or stability of some of the algorithms involved).

My advice regarding quaternions is, in general, to use matrices instead unless you have a specific reason to use quaternions, and can articulate that reason clearly (even if only to yourself).

Hm, I hadn't intended to write this long of a post, but in any case, I hope the information contained therein will be helpful to you.

[Edited by - jyk on February 20, 2008 1:20:56 PM]

Share this post


Link to post
Share on other sites
The Steve    143
Wow - that was one seriously awesome explanation and was basically what I needed to hear. Thanks JYK, you're awesome.

The main reason behind my desire to understand quaternions (besides wanton self punishment) is that I've been trying to understand the Quake 3 engine from the ground up and Carmack makes use of a lot of quaternions there.

My programming desires right now are to create a simple engine that can load a 3DS model on the fly, do some simple lighting, and then later add some arbitrary bot/creature (even a sphere) to the environment that moves around in random motion and uses collision detection to determine what walls/objects it would bump into.

Unfortunately, the greatest problem I've run into with my understanding of other 3D engines is the math portion. I run into quaternions and say "what the heck?"

Share this post


Link to post
Share on other sites
Ashkan    451
These articles at GeometricTools.com written by Dave Eberly do a decent job of explaining the mathematical concepts used inside Wild Magic. I highly recommend these articles considering Dave's depth of knowledge. Search for "quaternion" on this page and you'd come up with some really good ones on the subject.

Share this post


Link to post
Share on other sites
The Steve    143
Thanks for the links guys, I'm going to check them out soon. I wanted to point out, however, that I looked up quaternions in the angular displacement section of the book "3D Math Primer for Graphics and Game Development" and it is really pretty badass. I strongly recommend it if you're finding the concept a little hard to understand.

With that said, I have a general question that I'll try to phrase as best I can:

When you say you're rotating about an "arbitrary axis," does this mean that the vector that's pointing in any given direction is rotating like a spinning top, or does it mean that it's moving the head of the vector in a rotation that extends from the base to another given point in 3D space, sort of like someone holding the navigation aids for airplane pilots and pointing from one direction to another?

Share this post


Link to post
Share on other sites
jyk    2094
Quote:
Original post by The Steve
When you say you're rotating about an "arbitrary axis," does this mean that the vector that's pointing in any given direction is rotating like a spinning top, or does it mean that it's moving the head of the vector in a rotation that extends from the base to another given point in 3D space, sort of like someone holding the navigation aids for airplane pilots and pointing from one direction to another?
Assuming your pages are the same as mine, check out page 110 of '3D Math Primer'. There's a nice diagram there showing a vector (lebeled v) rotating about an axis (labeled n).

Looking at the diagram, you can imagine the head of v rotating in a circle about n. This demonstrates pretty clearly what we mean by 'rotation about an arbitrary axis'.

Share this post


Link to post
Share on other sites
The Steve    143
Quote:
Original post by jyk
Quote:
Original post by The Steve
When you say you're rotating about an "arbitrary axis," does this mean that the vector that's pointing in any given direction is rotating like a spinning top, or does it mean that it's moving the head of the vector in a rotation that extends from the base to another given point in 3D space, sort of like someone holding the navigation aids for airplane pilots and pointing from one direction to another?
Assuming your pages are the same as mine, check out page 110 of '3D Math Primer'. There's a nice diagram there showing a vector (lebeled v) rotating about an axis (labeled n).

Looking at the diagram, you can imagine the head of v rotating in a circle about n. This demonstrates pretty clearly what we mean by 'rotation about an arbitrary axis'.



Thanks again, JYK.

Good to know we have the same book! :) OK - I understand. Now, eh...lemme ask yet another dumb question - why would someone want to do that in a video game?

Steve

Share this post


Link to post
Share on other sites
jyk    2094
Quote:
Original post by The Steve
OK - I understand. Now, eh...lemme ask yet another dumb question - why would someone want to do that in a video game?
You mean rotate one vector around another?

Axis-angle rotations are (more or less) the basis of all manipulation of orientations in 2-d and 3-d simulations (in 2-d, we can think of all rotations as occurring about a single axis). A spaceship in flight, a projectile flying through the air, a barrel tumbling end over end, the orientations of the limbs in an animation keyframe - each can be thought of and represented in terms of axis-angle rotations.

Practically every time you sit down and play a game (be it an FPS, third-person arcade game, or 3-d RTS game), you see countless millions of these vector rotations take place. Most often, the context in which these rotations occur is that of geometric data (such as the vertices of a model) being transformed by dedicated hardware for the purpose of rendering. It's also sometimes necessary (or at least convenient) to perform these calculations in software for the purpose of collision detection, AI, and so on.

Perhaps what you're really asking is why would we want to manually rotate one vector about another, as described in the aforementioned pages of '3D Math Primer'. In that case, the answer is, we usually wouldn't. Typically, rotations are applied via matrix transforms (perhaps with a quaternion, axis-angle, or Euler-angle representation as an intermediate). However, ultimately, all of these operations reduce to the rotation of one vector about another, as shown in the aforementioned diagram.

I'm not sure whether I answered your question - please post back if I didn't :)

Share this post


Link to post
Share on other sites
The Steve    143
Haha, you didn't, but that was still a really interesting post! :)

Let me see if I can ask my overall question in a more broad sense and then refine it to this specific context.

My real question, I suppose, is how can an axis-angle manipulation transform a vector from one position to another? Consider, for a moment, your spaceship example.

Say I wanted a spaceship to launch from a platform and have it simulate the path that it would need to take to follow the curvature of the earth. How could I create a path for my spaceship to follow, and then reevalute the object space of my spaceship to the world space, then camera space, so that I can accurately observe that path?

From what I know of matrix math, I could theoretically do this by multiplying my object by a given matrix at certain points along that path. But, from my impression, there seems to be a way to do this more elegantly with quaternions. However, from looking at that rotation picture, I don't see how this is possible....and holy cow, as I'm writing this post, I think I just got it.

OK - is this right - say I have a given spaceship along my path. Technically, if I know the unit vector of that path at a given moment, I could then adjust that vector to whatever position I would like because I could give it an angle, theta, and then a given displacement from my point original vector?

I swear, if I can't figure this out, I'm going to bust out photoshop and start drawing pictures...then write a tutorial on quaternions for people that hate math.

Share this post


Link to post
Share on other sites
Raghar    96
Quote:
Original post by The Steve

My real question, I suppose, is how can an axis-angle manipulation transform a vector from one position to another? Consider, for a moment, your spaceship example.


You have a vector perpendicular to the rotation axis. Rotation is an operation that transforms things perpendicular to the axis, and preserves perpendicularity (and distance to the axis).

http://mathworld.wolfram.com/RotationFormula.html There is a nice drawing.

Share this post


Link to post
Share on other sites
Gage64    1235
Maybe this example will help:

Say you have a character that's looking at a certain point, and you want to make it look at another point (say, an enemy that's approaching it). To accomplish this, you need two pieces of information - an axis of rotation, and an angle of rotation (which indicates how much to rotate).

You can get that information in the following way:

Let's mark the character's position as P, the point that the character is currently looking at as V, and the point we want it to look at as D.

1) Create two vectors: One from P to V, and another from P to D. The first is simply V-P, and the second is D-P. Normalize both vectors. We'll mark these as V1 and V2, respectively.

2) Take the dot product of V1 and V2. This will give you the cosine of the angle between these vectors. Using the arccos function, you can extract the angle.

3) Take the cross product of V1 and V2. This will create a vector that's perpendicular to both V1 and V2. This, in fact, is the axis of rotation. Note that the cross product is not commutative (i.e., VxU != UxV. In fact, VxU == -UxV), so you have to watch the order.

Now that you have these two pieces of information, you can construct a matrix that performs a rotation around the axis from step 3, by the angle from step 2.

All of these steps are explained in your book (which I have too, by the way).

Share this post


Link to post
Share on other sites
The Steve    143
Quote:
Original post by Gage64
Maybe this example will help:


Hey Gage,

YES - that did help. Something step by step like that was just what I needed. I can see how you'd need to use that for a bot, monster, or something of that nature frequently - or just as a way to force an object to turn in any given direction. It feels good to say I understand that.

Now, this brings me to another question. Say I had two platforms, A and B, and A is above B. If I wanted to have a spaceship take off from platform A and land on platform B while following a very unusual 3-Dimensional path, how would I do something like that step by step?

Steve

Share this post


Link to post
Share on other sites
Gage64    1235
What do you mean by "unusual path"? I ask because you could actually achieve that without any rotation (just translate the ship up and down).

Share this post


Link to post
Share on other sites
The Steve    143
Quote:
Original post by Gage64
What do you mean by "unusual path"? I ask because you could actually achieve that without any rotation (just translate the ship up and down).


What I mean by a complex path is a very fluid path that a real ship might take if it was in an atmosphere. Taking off, pitching up, banking into a climb, leveling off, descending into an opposite bank, leveling off again, flaring, then landing.

- Is it possible I'm overthinking this? Is it just a simple series of applied matrix multiplcations and quaternions to determine the direction it needs to go and how it needs to be manipulated?

Another confusing example I could throw out would be something like a rope physics demonstration. Other than the *crazy* math behind that, how would you actually render the manipulations of the rope?

I think I'm going to get a rep on the forums for asking too many questions :).

Share this post


Link to post
Share on other sites
Gage64    1235
Quote:
Original post by The Steve
I think I'm going to get a rep on the forums for asking too many questions :).


There's no such thing as asking too many questions. [smile]

Quote:
What I mean by a complex path is a very fluid path that a real ship might take if it was in an atmosphere. Taking off, pitching up, banking into a climb, leveling off, descending into an opposite bank, leveling off again, flaring, then landing.

- Is it possible I'm overthinking this? Is it just a simple series of applied matrix multiplcations and quaternions to determine the direction it needs to go and how it needs to be manipulated?


First, I just want to say that some of what I'm about to say may not be complete or accurate. I'm not familiar with any articles/tutorials that specifically address this issue, and there might be simpler ways to achieve this, in which case I hope someone will correct me.

About the spaceship rotations, you could actually achieve those without quaternions. Of course, you could also use quaternions for that, but I don't think there's any benefit to doing that (I could be wrong; I also don't understand quaternions very well).

In general, all of these transformations (pitching, banking) can be done with matrices (just construct a matrix to rotate around the appropriate axis), but it's a little more complicated than that. The reason is that these rotations need to be performed around the spaceship's local axes. For example, to pitch the ship, you can't just rotate it around the world space X-axis. You have to rotate it around a vector that points to the side of the ship (often called the 'right' vector). The local Y and Z-axis vectors are called 'up' and 'look-at' (or sometimes 'forward') vectors, respectively. These vectors are perpendicular to each other and are of unit length.

You can imagine these 3 vectors as a coordinate system, and the object is at it's origin. Unlike the world coordinate system, however, which is fixed in one place, this coordinate system follows the object wherever it goes, translating and rotating along with it.

Initially, when the spaceship model is in object space, you know the exact orientation of the ship so you can specify these 3 vectors directly. If you then want to apply a rotation around the right vector, you must also transform the up and look-at vectors around the right vector, so that the 3 vectors stay perpendicular and point in the appropriate directions (e.g., the up vector should still point up from the ship).

Now, how do you construct a rotation matrix that will apply all of these rotations? If you're using row vectors (like Direct3D), you write the 3 vectors as the rows of a 3x3 rotation matrix (in a 4x4 matrix, just replace it's upper-left 3x3 portion with these vectors). If you're using column vectors (like OpenGL), you write then as the columns.

I think those are all the main points. If you have any specific questions, I might be able to explain further.

Actually, one more thing worth mentioning is that when you perform rotations around all 3 vectors, you might encounter something called Gimbal Lock, but I'm not really qualified to explain that so I'll leave that to someone else.

Finally, if you want the ship to follow a predetermined path (say, along a curve), you'll probably need to use quaternions and an operation called 'slerp' (spherical-linear interpolation) to interpolate orientations, but that's another topic I'm not qualified to explain. [sad]

Note that some of these concepts are covered by your book (though not necessarily in great depth).

Sorry for the long post. I hope some of it makes sense. [smile]

Share this post


Link to post
Share on other sites
The Steve    143
That makes sense, and basically sounds like what I'm asking. I guess what it comes down to for me is that I didn't realize that quaternions were just used as a replacement for Euler because of Gimbal lock and efficiency. I think, had I been able to figure out the fact that this is what I was trying to do, it would have made it a lot easier.

Let me ask a question about a quaternion itself. Is the "quaternion" both the vector and the angle rotation put in one, or is it the displacement? If I have something pointed in a certain direction (call it Vector A) and I want to make it point in another, could I simply say "I apply quarternion X to vector A?"

And does anyone have a list of example somewhere of some of the operations that quaternions can perform on vectors in general?

Share this post


Link to post
Share on other sites
The Steve    143
LOL - believe it or not, I just read that John Carmack didn't use quaternions in Quake 3, just in Quake 3 arena for something random! Boy, if that isn't an excuse to say "forget it," I don't know what is. :)

Share this post


Link to post
Share on other sites
Boder    938
Quote:
Let me ask a question about a quaternion itself. Is the "quaternion" both the vector and the angle rotation put in one, or is it the displacement? If I have something pointed in a certain direction (call it Vector A) and I want to make it point in another, could I simply say "I apply quarternion X to vector A?"


Yes, I think there would be a rotation that could point any vector in any direction.

I think quaternions can just rotate vectors, but you can use vectors to construct quaternions? not positive

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this