Quaternions

Quaternions are an interesting bit of mathematics.  You can read the Wikipedia article if you really want to understand what they're all about (or, attempt to understand, depending how mathematically inclined you are), but I jut want to talk a bit about using them in games.

Note:  this is only dealing with unit quaternions (i.e. length of 1).  In a more generalized case, they can be of any length, but for purposes of expressing rotations in games, they should only be unit length. 

Transformations

When dealing with geometry transformations, we generally need to worry about three things:

• Translation (change in position)
• Rotation (change in orientation)
• Scale (change in size)

In games, we often use a 4x4 affine transformation matrix, as this is very efficient for most hardware to work with.  You can combine translation, rotation and scale into a single matrix.  You can also store this as a 4x3 matrix, as the last row is always (0, 0, 0, 1).

Even better, if you have multiple transformations you want to apply, you just multiply all of the matrices together and get a single matrix that does all of them at once.  This happens a lot in character animation, where the finger is positioned relative to the hand, the hand is relative to the wrist, the wrist is relative to the elbow, the elbow is relative to the shoulder, and so on.

Quaternions are another way of specifying the rotation.  Note that it is only rotation, so if you want to store scale and translation, you need to store those separately.  This is still very space-efficient.  Even using four-component vectors for each, it's still the same size as a 4x3 matrix.  If you don't need scale, it's 4x2.

Notation

There is a lot written about quaternions, but I find a lot of the articles to be pretty confusing.  When talking about programming, a quaternion and vector are essentially identical from a data storage point of view.

I put a quaternion into an (x, y, z, w) vector like this:

x = axis.x * sin(angle/2)
y = axis.y * sin(angle/2)
z = axis.z * sin(angle/2)
w = cos(angle/2)

where 'axis' is the (unit) vector you want to rotate around, and 'angle' is the angle to rotate.

What I find most confusing is people putting the 'cos(angle/2)' component in the first component of the quaternion/vector.  Mathematically there's nothing wrong with this, as long as you're consistent.

In Real Life, this causes a lot of confusion when you want to multiply a vector that has been stored as (x, y, z, w) with a quaternion that has been stored (w, x, y, z), so don't store it that way.  It's worse when articles have labeled the components (q0, q1, q2, q3) and it's not at all obvious what has been stored where.

Inspection

The way quaternions store data, it's possible to get some intuitive understanding of the rotation it represents by inspecting the values.

From the axis/angle assignment above, if angle=0, you get:
(sin(0), sin(0), sin(0), cos(0)) =
(0, 0, 0, 1)

Which is the identity quaternion rotation - if you see (0, 0, 0, 1), there is no rotation. 

For any other rotation, the (x, y, z) components will be some non-zero scale of the rotation axis, so inspecting the (x, y, z) components will give you some idea what axis it's rotating around.

If you remember your trigonometry, the amount of rotation should be obvious too:

• w = 1 = cos(0/2) means angle=0
• w = 0.7071 = 1/sqrt(2) = cos((pi/2)/2) means angle=pi/2, or a quarter turn
• w = 0 = cos(pi/2) means angle=pi, or a half turn

Operations

Quaternion multiplication is completely unintuitive, :
q0 * q1 =
( q0.w*q1.x + q0.x*q1.w + q0.y*q1.z - q0.z*q1.y,
  q0.w*q1.y - q0.x*q1.z + q0.y*q1.w + q0.z*q1.x,
  q0.w*q1.z + q0.x*q1.y - q0.y*q1.x + q0.z*q1.w,
  q0.w*q1.w - q0.x*q1.x - q0.y*q1.y - q0.z*q1.z )

Rotating a vector (v = (x, y, z, 0)) by a quaternion (q) is fairly straightforward:


v' = inverse(q) * v * q

The inverse of the quaternion (x, y, z, w) is (-x, -y, -z, w).


Even if you are storing scale and translation, this is fairly easy:

• scale = (sx, sy, sz) 
• rotation = (qx, qy, qz, qw)
• translation = (tx, ty, tz)
• scale_inverse = (1/sx, 1/sy, 1/sz)
• rotation_inverse = (-qx, -qy, -qz, qw)
• translation_inverse = rotate(rotation_inverse, scale_inverse * (-tx, -ty, -tz))

Compare with the inverse of an arbitrary 4x4 matrix and you'll understand how much more straightforward this is.

Final thoughts

There are a lot of situations where using quaternions can be very helpful - particularly if you need to take the inverse of a transform very frequently.  Having your transforms broken out into separate scale / rotation / translation components can also be very beneficial, depending on how you're animating these values.

This doesn't mean quaternion rotations should be used everywhere - matrix transformations are certainly sufficient.  You will almost certainly need a matrix for rendering, and converting back and forth between quaternions and matrices is not trivial.

Random Blog Day

On my mind recently:

I watched @Jonathan_Blow live-coding on twitch.tv - he has been working on his own language, and it's nice to watch someone else have mind-bending code generation problems for a change.  :)

I have a lot of interest in game development languages, though I have primarily focused on scripting, as opposed to an entire game development language.  It's probably a little vague as to which category some things should drop into. 

Conceptually, I like to think of scripting as writing custom code for individual game objects.  This doesn't make it strictly game-specific, but it probably tends to be.  Ultimately, it lets you glue all of the bits of the game engine together into something new.  Also, having some syntactic control can let you specify certain this more easily.  For instance, I have special notation to convert musical beat/measure values into actual time values, and ways to specify timing, sequencing and interpolation.  It could be done in C, but the point is to make it easier to read and write than make it possible.

Engine coding is a fairly different beast.  First, you probably have to talk to third party libraries, even if that's just DirectX, OpenGL, basic operating system, etc.  So, you're probably stuck at some point with whatever language those are written in.  For simpler games you can get away with a higher level language, but for maximum performance and compatability, you're still looking at C/C++.

One interesting idea is to have a sort of pre-compiler that spits out C/C++ code.  I've seen similar things done before, to varying degrees of success.  This is pretty much guaranteed to degrade the already dubious quality of debuggers and debugging, but it's a way to add language features that are otherwise hard to get.  For instance, pre-hashed strings.

-----


In other news, the new World of Warcraft expansion Warlords of Draenor is out.  It is good. :)  They have done a lot of work scripting out quests, and there are a lot of places with a huge number of NPCs wandering around, which helps to bring the world to life a lot more than I remember seeing before.  Some of the battles are truly epic.

You have your own garrison now, which is a pretty cool idea, although we'll have to see how some of the features play out.  Since everyone is doing stuff in their own garrison, you don't see other people as much.  As a hardcore solo player, it doesn't affect me much, just feels a bit weird for an MMO. 

You can also build buildings to give you access to the various professions, including ones you haven't taken on yourself.  On one hand, this seems like a good idea, as it gives you access to some of the crafting you otherwise wouldn't have.  On the other, you can't have all of the buildings at once, and you probably want the ones you do have the professions for, so your choices are kind of limited.


-----

That's all for now - sorry I haven't been posting recently.  Too much going on, not enough stuff that makes good blog posts.  :)