Quaternion Mathematics

How do folks. I just dug up from the depths a couple of quaternion tutorials I wrote a long time ago for a friends website which is no longer online so figured I might as well share them here. Enjoy.

Complex Numbers and Quaternions [part 1]

Quaternions are one of those things that have made every 3D game programmer cringe until they’ve finally bitten the bullet and decided to learn what they’re all about. I’m guessing that’s why you’re reading this so without further ado lets crack on. There’s too much base knowledge required for me to cover everything comprehensively so instead I intent to guide you through the necessary line of thinking. I leave it up to you to research all the little specifics. That is until we get to the more advanced applications of quaternions anyway. So why bother with quaternions at all? Well in games they’re useful to represent 3D rotations since they give rise to smoother and more natural looking interpolations. They are also more compact than rotation matrices and avoid the problem of Gimbal Lock, a phenomenon which causes rotations to lock when rotation axes coincide. You may have already seen a quaternion defined as a hyper-complex number with 1 real part and 3 imaginary parts. If like me you spat your coffee over the monitor when you read this, don’t panic all will be explained. Hyper just means ‘above normal’ which is used in this case since a quaternion has 4 parts whereas our ‘normal’ is to think in 3 dimensions. Complex is added since a quaternion is a complex number which is going to take some more explaining. Read on Mc Duff.

A complex number is one that is made up of both real and imaginary parts. A real number is what you usually think of when doing maths, so what is an imaginary number? Consider the following expression:

sqrt( -1 ) = ?

Try typing this into your calculator. Unless you have a super swish one capable of complex maths you’ll no doubt get an error. Why is this? Well try answering the above expression in reverse, i.e. what number would you square to get -1. Not found one yet…….well that’s because there isn’t a real number that can satisfy the expression and so instead mathematicians invented the imaginary number which can. The imaginary number is represented by the letter ‘i’ and has the following special properties:

sqrt( -1 ) = i

i * i = -1

and here’s an example of it in use:

sqrt( -4 ) = 2i

2i * 2i = ( 2 * 2 ) * ( i * i ) = 4 * -1 = -4

As mentioned earlier a complex number has both real and imaginary parts, so for example a complex number might look like ( 2 + 6i ) where 2 is the real part and 6 is the imaginary part. Mathematics with complex numbers is done component wise, with the real and imaginary parts being treated as different components. Just think of ‘i’ as being an unknown as in basic algebra with the exception it becomes a known, ‘–1’, when squared. For example:

Complex number addition
( 3 + 7i ) + ( 1 – 2i ) = ( ( 3 + 1 ) + ( 7 – 2 )i ) = ( 4 + 5i )

Complex number scalar multiplication
( 3 + 7i ) * 2 = ( ( 2 * 3 ) + ( 2 * 7i ) ) = ( 6 + 14i )

Complex number multiplication
( 3 + 7i ) * ( 1 – 2i ) = ( 3 * 1 ) + ( 3 * -2i ) + ( 7i * 1 ) + ( 7i * -2i )
= 3 – 6i + 7i + ( -14*( i * i ) ) = 3 + 1i + ( -14 * -1 ) = 17 + 1i

Note that complex number multiplication is associative but not commutative. For a more detailed explanation of complex number maths I recommend a visit to http://mathworld.wolfram.com/ComplexNumber.html

Ok, if you’re feeling comfortable with imaginary numbers and complex number maths I think we’re ready to move into the world of quaternions. To re-iterate, a quaternion is a hyper complex number with 1 real part and 3 imaginary parts. It is represented mathematically as q = ( w + xi + yj + zk ) where i, j, and k are the imaginary parts and can be thought of as a set of orthogonal axes much like the world coordinate axes except in imaginary space, ie: i = (1,0,0), j = (0,1,0), k = (0,0,1). In this way the quaternion can be thought of as consisting of a real scalar w, and a vector (x, y, z) in imaginary space.

We are specifically interested in quaternions with unit length since these are related to rotations. A unit length quaternion is one where:

w*w + x*x + y*y + z*z = 1

Note that x, y, and z are real numbers and so aren’t negated when squared. Only when the imaginary parts i, j, and k are included does this happen. To make a non unit quaternion unit (normalised) we divide it by its length (same as scalar multiplying by 1 over the length) where the length is given by:

Length = sqrt( w*w + x*x + y*y + z*z )

Mathematics with quaternions is exactly the same as with complex numbers above with each i, j, and k part treated as separate components. For example:

Quaternion addition
q0 + q1 = ( w0+w1 ) + ( x0+x1 )i + ( y0+y1 )j + ( z0+z1 )k

Quaternion multiplication
q0 * q1 = ( w0*w1 – x0*x1 – y0*y1 – z0*z1 )
+ ( w0*x1 + w1*x0 + y0*z1 + zo*y1 )i
+ ( w0*y1 + w1*y0 + z0*x1 + x0*z1 )j
+ ( w0*z1 + w1*z0 + x0*y1 + y0*x1 )k

Ok that’s just about all the foundations covered, but just before signing off for today there’s one more thing I want to mention. This is the conjugate of a complex number which, as with everything else so far, also applies to quaternions since these are themselves just complex numbers. If a quaternion is defined as:

q = w + xi + yj + zk

Then the quaternion conjugate is:

q(conj) = w – xi – yj – zk

This is important to us since for unit length quaternions, like which we are dealing with, the conjugate is equivalent to the inverse of the quaternion. We’ll be using this a lot in the next instalment when I’ll be talking about the applications of quaternions such as vector rotation, spherical linear interpolation (slerping), and conversions between quaternion and matrix formats.

Don’t worry if you’ve not taken this all in at once, we’ve covered a lot of ground. Try your hand at imaginary numbers and complex number maths until you feel comfortable with it, and don’t forget to check out Math World for extra help. You may also want to try writing your own quaternion class with just the basic math functions implemented. This will put you in a good place to take maximum advantage of my next tutorial. Watch this space and many thanks for reading.

Applications of Quaternions [part 2]

Hi again. If you read my last tutorial ‘Complex Numbers and Quaternions’ you hopefully have a good understanding of what a quaternion is mathematically. However you’re probably still wondering just what one is in the real world. Well I wouldn’t try too hard to attach physical meaning to them since they are firmly fixed in the realm of abstract mathematics. Instead I’m going to step through some of the more common applications of quaternions to give you an idea of what they’re all about and their usefulness.

As I mentioned in the last article, the reason quaternions are useful for 3D games is because they relate to rotations when of unit length. For those of you that want to sound clever, the reason for this is because a normalised quaternion is always a point located on the surface of a 4D hyper sphere. This gives rise to smoother transitions between orientations because interpolating quaternions will create arcs on the hyper sphere surface where as rotation matrices cut across the inside of the sphere in straight lines.

Anyway, that’s enough of the abstract nonsense, lets get down to something we can actually use. I’ll first explain how to rotate a vector using a quaternion since this is the most simple rotation application. The vector needs to be expressed as a quaternion so that it is compatible with quaternion maths. For a vector (x, y, z) its corresponding quaternion is (0, x, y, z). In other words its exactly the same but with an extra w scalar which is set to zero. If ‘v’ is the quaternion representation of the vector we wish to rotate and q is the quaternion we are rotating it by, then:

v(after) = q * v(before) * q(conj)

Remember from my last article that complex number multiplication is associative and so the order in which the above multiplications are carried out doesn’t matter. Like with rotation matrices, quaternions can also be concatenated. For example say I want to rotate a vector by a quaternion ‘p’ and then another quaternion ‘q’. This would be the same as rotating the vector by the quaternion which is the result of p*q. There is a down side to using quaternions over matrices for basic vector rotation though. Using a matrix takes 9 multiplications and 9 additions whereas a quaternion takes 16 multiplications and 16 additions and hence is significantly slower. Because of this quaternions are rarely used for such simple tasks.

Where quaternions really shine though is when interpolating between orientations, known as spherical linear interpolation (slerp), and hence are often used at the core of 3D camera classes. For example say we have a camera that begins with an orientation represented by the quaternion q0 and we want to gradually swing the camera round until it has an orientation described by a quaternion q1. At any time in between the camera has orientation q(t) where t is the interpolation time which uniformly varies from 0 at the beginning to 1 at the end of the interpolation. Note that if you want the interpolation to last ‘x’ seconds then you must scale between ‘x’ and ‘t’ so that ‘t’ always lies in the range 0 < t < 1. During the interpolation, q(t) always represents a point on the arc between q0 and q1 on the 4D hyper sphere surface thus giving rise to a smooth camera motion. So how do we calculate q(t)? Well first we need to know the angle between the beginning and end quaternions, q0 and q1. Remembering about imaginary number maths, this can be determined using the dot product, like so:

cos(?) = q0 dot q1 = w0*w1 – x0*x1 – y0*y1 – z0*z1

Knowing ?, the orientation quaternion at any ‘t’ is then given by:

q(t) = ( sin((1 – t)*?)*q0 + sin(t*?)*q1 ) / ( sin(?) )

“That great but my graphics API doesn’t accept quaternions in its camera functions” I hear you say. Well fear not because I’m about to show you how to convert between quaternions and rotation matrices. Like everything else so far I’ll not be going into the math derivations to save space, but simply state how it’s done. To convert from a quaternion (w,x,y,z) to a 3x3 matrix ‘R’, use the following:

R00 = 1 – 2*y*y – 2*z*z
R01 = 2*x*y – 2*w*z
R02 = 2*x*z + 2*w*y

R10 = 2*x*y + 2*w*z
R11 = 1 – 2*x*x – 2*z*z
R12 = 2*y*z – 2*w*x

R20 = 2*x*z – 2*w*y
R21 = 2*y*z + 2*w*x
R22 = 1 – 2*x*x – 2*y*y

Unfortunately converting the other way around is not so simple and involves several steps. First you must calculate the trace of the matrix using:

trace = R00 + R11 + R22

If the trace is greater than zero then the quaternion, q = (w,x,y,z), can be calculated quite simply using:

s = sqrt( trace + 1 ) / 2
q.w = s
q.x = ( R12 – R21 ) / s
q.y = ( R20 – R02 ) / s
q.z = ( R01 – R10 ) / s

If not then one of the following methods must be used. Which of the following methods to use depends upon which diagonal element of the matrix is greatest.

If R00 is greatest
s = sqrt( 1 + R00 – R11 – R22 ) / 2
q.w = ( R12 – R21 ) / s
q.x = s
q.y = ( R01 + R10 ) / s
q.z = ( R02 + R20 ) / s

If R11 is greatest
s = sqrt( 1 + R11 – R00 – R22 ) / 2
q.w = ( R20 – R02 ) / s
q.x = ( R10 + R01 ) / s
q.y = s
q.z = ( R12 + R21 ) / s

If R22 is greatest
s = sqrt( 1 + R22 – R00 – R11 ) / 2
q.w = ( R01 – R10 ) / s
q.x = ( R20 + R02 ) / s
q.y = ( R21 + R12 ) / s
q.z = s

This is all well and good when you have quaternions or rotation matrices to work with already but at some point you’ll want to create a quaternion on the fly. However how do you know what the quaternion should look like to represent a certain rotation since they are mathematically abstract. It’s fairly common and intuitive to think of rotations as Euler angles, i.e. rotations around the three world axes. So finally I will describe how to create a quaternion to describe a rotation represented by Euler angles. If ‘rx’ is the rotation around the x axis, ‘ry’ around the y axis, and ‘rz’ around the z axis, then the quaternion is calculated using:

A = sin( rx / 2 )
B = sin( ry / 2 )
C = sin( rz / 2 )
D = cos( rx / 2 )
E = cos( ry / 2 )
F = cos( rz / 2 )

q.w = A*B*C + D*E*F
q.x = F*E*A – C*B*D
q.y = F*B*D + C*E*A
q.z = C*E*D – F*B*A

Ok that’s your lot. I hope this quick guide has helped to demystify your view of quaternions and I encourage you to research into this subject more in depth if this has interested you enough to implement quaternions in your own applications. If you happen to spot any errors with any of what I have covered please post in and let me know. Have fun.