G-Engine #9: Quaternions

Way back in G-Engine #4, we rendered a triangle, and there was much rejoicing. Since then, the posts in this series have primarily focused on implementing mathematical constructs in code. This point is the final math pre-requisite before we can move on to more interesting things.

Think of a game engine as its own little universe: at first, there is nothing - the void. Concepts such as time, position, and orientation don’t exist yet. Suddenly, the game loop and delta time introduces the concept of time. With vectors, we can convey positions, directions, and distances. Slowly, our universe takes shape and we can convey important concepts in code.

But what about rotations? Vectors can store position, direction, and scale data, but they are not effective structures for 3D rotations. We need some other option to convey rotations in code.

One structure that is very effective for 3D rotations is the Quaternion. Much-maligned for their apparant complexity, Quaternions allow us to efficiently store and use 3D rotation data. In this post, we’ll explore why we use quaternions, what they are, how to perform common operations with them, and finally I’ll provide some tips for writing your own Quaternion class.

Rotation Basics

A 3D rotation can be defined in terms of two pieces of information: the axis of rotation and the angle of rotation.

For example, if you stand up and turn your head to the left or right, the axis of rotation points straight up in the air and the angle of rotation will be either a positive or negative number depending on which direction and how far you turned your head.

Rotations are commonly described like so: “a rotation of A units about the X axis.” In that description, the axis of rotation is the X axis, and the angle of rotation is A.

Usually, a rotation angle’s units will be either degrees or radians. A full rotation is 360 degrees or 2π radians. A half rotation is 180 degrees or π radians. The unit circle can be helpful to visualize the full range of angles.

The coordinate axes X, Y, and Z are commonly used as axes of rotation. However, any unit-length vector can be used as an axis of rotation. For example, (0.707, 0.707, 0) is an axis halfway between the X and Y axes.

What Does a Rotation Do?

Conceptually, a rotation changes an object’s orientation. If you are facing north, and you “rotate 90 degrees about the up axis”, you’ll be facing west (assuming that positive angles are counter-clockwise). A rotation is applied to an object to change its orientation.

In a virtual world, changing an object’s orientation means changing its facing direction or its position. When the object is a 3D model, this means that each of the model’s vertices are rotated. Generally, we can say that rotations in a 3D world primarily function by modifying a vector in some way (since we usually respresent positions and directions using vectors).

When a rotation is applied to a vector, the portion of the vector that is parallel to the axis of rotation does not change, but the portion that is perpendicular to the axis does change. Though we describe rotations as being “about” an axis, the rotation actually affects everything on the 2D plane perpendicular to the axis.

Handedness

In the earlier example about facing north and rotating 90 degrees, it was unclear whether you’d end up facing east or west after rotation unless you specify whether positive angles are clockwise or counter-clockwise.

This decision speaks to the handedness of the rotation. It is so-called because you can choose either a “left-handed” system or a “right-handed” system. In a left-handed system, positive angles are clockwise. In a right-handed system, positive angles are counter-clockwise.

The concept of handedness comes from a handy (hah) method of remembering what convention is being used: point your thumb in the direction of the axis of rotation; your fingers curl in the direction of a positive rotation. If you point your thumb/axis towards your face, your fingers curl clockwise on your left hand and counter-clockwise on your right hand.

Handedness is a topic we briefly touched on when discussing the cross product, and we will discuss it again in more detail when we dig into transforms and coordinate systems in a future post.

Rotation Representations

In 2D, a rotation can be represented by a single float value (the angle of rotation). A 2D game only has one 2D plane to rotation, so there’s only one possible axis of rotation!

In 3D, a rotation can occur about any of the three coordinate axes or an arbitrary axis. The possible rotations are more vast than in 2D, so the method for representing them also becomes more complex.

There are a few different methods we could use to represent 3D rotations. But what makes a good representation? The primary criteria are:

  • Doesn’t take up too much memory.
  • Concatenating multiple rotations into a single rotation should be efficient.
  • Rotating a vector should be efficient.
  • Converting to and from matrix form should be efficient.

Some secondary criteria worth considering:

  • When animating objects, rotations need to be interpolated. So, interpolating ought to be correct and efficient.
  • A physics simulation can affect an object’s rotation. So, a representation that can be easily used in numeric integration would be nice.

Based on these criteria, let’s briefly discuss a few possible representation options: Euler angles, axis/angles, matrices, and finally quaternions.

Euler Angle Representation

Perhaps the most intuitive way to represent a 3D rotation is with three float values, each representing an angle of rotation about the x, y, and z coordinate axes. This seems like a natural extension of a 2D rotation.

This representation has two benefits: it takes up little memory, and it is fairly intuitive. But otherwise, this representation has some downsides.

Concatenating rotations and rotating vectors are not straightforward or efficient operations. Interpolating between rotations also doesn’t work correctly. Converting to and from matrix representation is not efficient and has some limitations. This representation also suffers from a phenomonon called gimbal lock.

Because Euler angles are so intuitive and easy to visualize, they are often used in 3D modeling package and commercial game engine interfaces to specify rotations. However, they are usually converted to/from another internal format to avoid the problems outlined above.

Axis/Angle Representation

Another way to represent a 3D rotation is by specifying an axis of rotation and a rotation about that axis. Using this method, it is possible to represent any 3D rotation using just four float values (three for the axis vector, one for the angle).

This representation doesn’t suffer from gimbal lock and it only uses four float values. However, it still has a lot of the problems of Euler angles: concatenating rotations and rotating vectors are both inefficient. Converting to matrix form is doable, but converting back has some limitations.

The idea of axis/angle is powerful, easy to understand, and easy to visualize. If only we could use the axis/angle concept with a more efficient structure… (mysterious music and foreshadowing)

Matrix Representation

3D graphics APIs require that scale, rotation, and translation data be provided in a matrix structure, so it seems reasonable to just store rotations in a matrix directly and be done with it.

Actually, this is not a bad idea! A matrix allows us to concatenate rotations and rotate vectors efficiently using matrix multiplication. Matrices also interpolate pretty well, and they can be used in physics simulations. And obviously, there’s no need to convert to/from matrix form in this case!

Matrices do take up more space than other options. A 3D rotation requires a 3x3 matrix, or nine float values.

Matrices tick a lot of our boxes, but quaternions usually edge them out by being somewhat more performance and memory efficient. Position and scale are represented as vectors before being converting to matrix form for the rendering system - rotations can also benefit from an intermediate representation.

Quaternion Representation

Quaternions are fairly complex mathematical objects, but when used to represent rotations, you can think of them as axis/angle rotations. Quaternions allow us to use the idea of axis/angle representation, but take advantage of a more efficient structure.

The benefits of quaternions include:

  • Memory efficient, at only four float values.
  • Concatenating rotations is efficient.
  • Rotating a vector is (fairly) efficient.
  • Converting to and from matrix form is efficient.
  • Interpolation works well and is more efficient than matrix interpolation.
  • They work well in physics simulations.

There are two downsides to quaternions. First, the math is somewhat obtuse and difficult to understand. Second, vector rotation is slightly less efficient than in matrix form - if you need to rotate a lot of vectors, consider converting to matrix form first.

Because of the benefits quaternions provide and the minimal downsides, they are commonly used in game engines, and they’re what I’ll spend the rest of this post discussing.

What is a Quaternion?

Quaternions were originally divised as a way to work with complex numbers. If, like me, you are rusty with complex numbers, that’s OK! Quaternions used as rotations do not require a deep knowledge of complex numbers.

A quaternion consists of four values: x, y, z, w. The (x, y, z) portion is called the vector part and w is called the scalar part.

The vector part roughly correlates to an axis of rotation, while the scalar part roughly correlates to an angle of rotation. The axis and angle data are encoded in these values, but some math is required to extract them.

A quaternion may seem similar to a 4D vector - both consist of four float values called x, y, z, w. Though not interchangeable, it’s true that some quaternion operations behave just like vector operations, and they even share some of the same terminology.

Quaternion Operations

Fortunately, there are only a few quaternion operations that we need to define to use them for 3D rotations.

Addition and Subtraction

Let’s start with something simple: to add and subtract quaternions, simply add or subtract corresponding components.

(4, 3, 2, 1) + (-3, 5, 2, 6) = (1, 8, 4, 7)

You might expect that adding two rotation quaternions together would concatenate the two rotations, but that isn’t the case.

Multiplication

Multiplying two rotation quaternions has the effect of concatenating the rotations. So, it’s a pretty important operation!

Quaternions have unique multiplication rules that also act as their defining characteristic. This wikipedia section explains the multiplication rules in a pretty digestible way (keeping in mind the imaginary number equality i 2 = -1).

Given two quaternions q1 and q2, consider the vector parts and scalar parts separately. Say q1.v refers to the vector part and q1.s refers to the scalar part.

Multiplication can then be performed like so:

result.v = (q1.v ⨯ q2.v) + (q1.s * q2.v) + (q2.s * q1.v);
result.s = (q1.s * q2.s) - (q1.v • q2.v);

In other words, the result’s vector part is calculated by summing three things:

  • Cross product of the two vector parts.
  • q1’s scalar part multiplied by q2’s vector part
  • q2’s scalar part multiplied by q1’s vector part

And the result’s scalar part is the product of the two scalar parts minus the dot product of the two vector parts.

The order of multiplication affects the result. q1 * q2 has the effect of rotating by q2 and then by q1; q2 * q1 has the effect of rotation by q1 and then q2. In other words, concatenated rotations occur in right-to-left order.

Length and Normalization

In this regard, vectors and quaternions share behavior and terminology. You can calculate the length of a quaternion using the Pythagorean theorem:

length = sqrt(x * x + y * y + z * z + w * w);

A unit quaternion has a length of 1. To normalize, divide each component of the quaternion by the quaternion’s length.

Quaternions used for 3D rotations should always be unit length. This usually makes the math simpler and more efficient. But it also means that accidentally using a non-unit quaternion will give incorrect results.

Multiplying two unit-length quaternions always results in another unit-length quaternion. But be careful of other operations that might de-normalize the quaternion (many floating-point operations or interpolation). If a quaternion has recently been subjected to a lot of operations, it may be a good idea to normalize it before using it to rotate something.

Scalar Multiplication

As with vectors, you can multiply a quaternion by a scalar value, which multiplies each component by the scalar value and affects the length of the quaternion.

5 * (3, 2, 8, 0.5) = (5 * 3, 5 * 2, 5 * 8, 5 * 0.5) = (15, 10, 40, 2.5)

You might expect that negating a quaternion (multiplying by -1) would negate the rotation it represents. But actually, a negated quaternion represents the exact same rotation as the original quaternion!

Negation will negate both the axis of rotation and the angle of rotation. Imagine a counter-clockwise rotation about an axis. Negating the axis causes the angle of rotation to flip to clockwise. But negating the angle causes the angle to flip again back to counter-clockwise!

If we want to actually negate a rotation, we have to negate the axis or the angle, but not both. To do this, we can use quaternion inversion.

Inversion

As with matrices, multiplying a quaternion by its inverse gives us the Identity quaternion, which has a vector part of (0, 0, 0) and a scalar part of 1.

If a quaternion represents a rotation about an axis, the inverse represents the opposite rotation about that axis. The inverse undoes the rotation performed by the original quaternion.

Fortunately, the inverse is simple to calculate for quaternions.

Quaternions have a concept borrowed from complex numbers called the conjugate. A quaternion’s conjugate has the same scalar part, but the vector part is negated.

conjugate.v = -q.v;
conjugate.s = q.s;

A quaternion’s inverse can then be calculated as conjugate / lengthSquared. Since the quaternions we use for rotations are unit length, this equation simplifies: a unit-length quaternion’s inverse is equal to its conjugate!

Negating only the axis via inversion causes the angle to negate, which is exactly what we want in order to calculate an opposite rotation.

Vector Rotation

Applying a quaternion to a vector causes the vector to rotate about the axis. As described previously, the portion of the vector that is perpendicular to the axis of rotation is modified, while the parallel part does not change.

To rotate a 3D vector using a quaternion, we first treat the vector as though it was a quaternion with a w value of zero. We can then use quaternion multiplication to rotate the vector using this equation:

rotatedVector = quat * vector * quatInverse;

In other words:

  1. Multiply the vector by the quaternion.
  2. Multiply the result by the quaternion’s inverse.

This somewhat unusual structure is called a sandwich product because the vector is “sandwiched” between the quaternion and the quaternion’s inverse.

The reason this causes the vector to be rotated correctly involves some fairly complex mathematical manipulation - I recommend one of the resources mentioned at the end of this post if you’re interested in learning more.

Conversions

Quaternions are efficient, but the problem remains that other representations like Euler angles and axis/angle format are easier to manipulate and debug. We must also be able to convert to matrix form to send rotation data to the rendering system.

So, let’s discuss how we can convert between quaternions and other representations.

Axis/Angle Conversion

If the vector rotation equation is expanded and some substitutions are performed, you end up with this equality:

quaternion = sin(angle/2) * axis + cos(angle/2)

This tells us a few interesting things:

  • The scalar part w of a quaternion is equal to cos(angle/2).
  • The vector part (x, y, z) of a quaternion is equal to axis * sin(angle/2).
  • The length of the vector part is sin(angle/2).

Using this, we have a fairly simple way to create a quaternion from an axis and an angle:

// Assuming the axis is normalized...
q.s = cos(angle * 0.5f);
q.v = sin(angle * 0.5f) * axis;

To do the opposite (quaternion to axis/angle), we just need to reverse this math:

angle = acos(q.s) * 2.0f;
axis = q.v / sin(angle * 0.5f);

Euler Angles Conversion

Each Euler angle is a rotation about the X/Y/Z coordinate axes - represent each one as an axis/angle. From there, generate one quaternion per axis. Finally, concatenate the three quaternions to get the final quaternion.

Converting from a quaternion to Euler angles is not inefficient, but it is complex. I’m not sure I could fully explain these equations if I tried! See this wikipedia page for full details, and of course the G-Engine source code for source code.

Matrix Conversion

Converting a matrix to a quaternion exploits some fortunate observations about the matrix format:

  1. The trace of a rotation matrix (the sum of diagonal elements) equals 2 * cos(θ) + 1. We’ll use this as the scalar part of the quaternion.
  2. Subtracting certain symmetric elements of a rotation matrix for each component of a vector gives us 2 * sin(θ) * axis. We’ll use this as the vector part of the quaternion.

These two pieces of data are very close, but not quite, the data required to calculate a quaternion from an axis/angle. To get it in the right form, it’s actually possible to simply:

  1. Add 1 to the scalar part (resulting in 2 * cos(θ) + 2).
  2. Normalize the quaternion.

And that’s it! Surprisingly, these operations cause the quaternion to fit the equation mentioned in the axis/angle section above, and we’re good to go.

Converting a quaternion to a matrix simply requires populating each entry in the matrix using specific values from the quaternion. The values required for each entry are outlined here.

Writing a Quaternion Class

Unlike vectors and matrices, we only need one quaternion class. The class should support at least the following operations:

  • Construction, Copy Construction, and Assignment
  • Equality checks
  • Addition and subtraction
  • Quaternion multiplication
  • Scalar multiplication
  • Length calculation and normalization
  • Inverse calculation
  • Vector rotation
  • Extraction of axis/angle and euler angles

You can view the G-Engine quaternion class header and source.

Next, I’ll highlight some considerations when writing a quaternion class.

Naming

I decided to name my class Quaternion (shocking, I know). If you don’t like typing, I’ve also seen Quat used. As always, we want the name to be clear!

Data Layout

Like a 4D vector, the x/y/z/w elements should all be float values, and they should be laid out sequentially in memory. There should be no other data members in the class.

Constructors & Accessors

You want this class to hide the internal complexity of quaternion math and expose an easy to use public interface. This allows developers to use quaternions to perform rotations without having to understand everything happening under the hood.

One way you can do this is by providing a set of constructors that allow you to generate quaternions from various friendlier representations. In addition to the default constructor and a constructor that lets you set the x/y/z/w component directly, I’d recommend having constructors that take in axis/angle, matrix, and euler angle representations.

Likewise, you will want accessors that allow users to convert a quaternion back to axis/angle or Euler angle representations. You could also have a function to convert to a matrix, but this logic commonly exists inside separate functions related to transformation matrices (something I’ll cover in a future post).

Data Access

As with vectors, I think it’s OK to leave the data members public on a quaternion. The structure of the internal data is well-defined and unlikely to ever change.

There are times when it may be valuable to directly manipulate or access the internal values. For example, direct access results in more readable code when writing out equations involving quaternions.

String Output

It can be helpful to output a quaternion to the log for debugging or data recording. You can overload operator<< as a convenient way to do this.

When debugging rotation issues, the x/y/z/w values of the quaternion are not very helpful - it’s hard to tell whether the values are correct or not. For this reason, I usually output the quaternion in axis/angle format. This makes it more obvious when there’s a bug in rotation code (maybe the axis is pointing the wrong way or the angle is obviously wrong).

For similar reasons, I usually output angles in degrees instead of radians. I think most people find degrees a little more intuitive than radians, but it’s a matter of personal preference.

Pre-Defined Quaternions

Defining some static quaternions for Identity and Zero are useful. The Identity quaternion has a vector part of (0, 0, 0) and a scalar part of 1. The Zero quaternion has all zeros.

Conclusion

The vector, matrix, and quaternion classes form a core set of math classes from which we can start to build a 3D transform system and rendering pipeline. The next post in this series will finally start to dive into this more exciting material!

If you plan to write your own game engine, creating these low-level mathematical constructs can be a huge hurdle. Some aspects are difficult to understand, it’s easy to make mistakes, and it must be done before you can see 3D objects moving around a 3D world. Hopefully, these last few posts act as a helpful guide!

As with previous math topics, I’ve tried to provide enough info to enable effective use of quaternions in a game engine. If you want more in-depth explanations for some of the math and derivations that I glossed over, check out these resources:

comments powered by Disqus