Monday, December 15, 2014

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.

No comments:

Post a Comment