Quaternions: A User's Guide

Introduction

If you're having problems with rotating objects using pitch, yaw and roll (i.e. Euler angles), the following article might help. In Blitz 3d, the parameters of the RotateEntity and TurnEntity commands are Euler angles. There are problems with Euler angles, and I'll tell you a way round them using quaternions. I'll explain a little more about what quaternions are and what they do, but I won't be going into the maths behind them. For one thing, it's unnecessary if all you need to do is use them (rather than understand them). And for another, I've only the vaguest idea about the maths myself, and there are many people more qualified than I to tell you about them. Look at the references at the end for some excellent background reading.

If you want to download all the source mentioned in this article, here it is.

The problem with Euler angles

What's wrong with using pitch, yaw and roll? On the surface, nothing. Any rotation you care to think of can be expressed exactly with these three numbers, and a convention for the order they are applied. (In Blitz, this is the order yaw then pitch then roll: this is important, because different orders give different rotations.) However, they can be difficult to manipulate.

Interpolation

It is very difficult indeed to interpolate between two rotations using Euler angles alone. If you don't believe me, try it... Here's an exercise you can do to prove it to yourself. Copy and paste the following code into Blitz (or download it here), and run it:

; Quickly set up a scene
Graphics3D 800,600
SetBuffer BackBuffer()
WireFrame True
Global cube = CreateCube()
Global cam = CreateCamera()
TranslateEntity cam, -5, -2, -5
PointEntity cam, cube
CameraViewport cam, 0, 0, GraphicsWidth (), GraphicsHeight ()

; We're going to rotate a cube between these two angles: (sp = start pitch, er = end roll, etc)
Global sp# = 90, sy# =  0, sr# =  0 ; The start rotation
Global ep# =  0, ey# =-90, er# = 90 ; The end rotation

; Start off by rotating the cube to it's initial rotation
RotateEntity cube, sp, sy, sr, 1
CaptureWorld : RenderWorld

Text 10, 10, "Press escape for ideal rotation" : Flip 1 : Repeat : Until KeyHit(1)

; Show the rotation we want to achieve, by using Blitz's tweening
RotateEntity cube, ep, ey, er, 1
For t = 0 To 200
	RenderWorld Float(t)/200
	Flip 1
Next
Text 10, 10, "Press escape for our own rotation" : Flip 1 : Repeat : Until KeyHit(1)

; Try to emulate the rotation
For t = 0 To 200
	RotateCube(Float(t)/200)
	CaptureWorld : RenderWorld
	Flip 1
Next

Text 10, 10, "Press escape to end" : Flip 1 : Repeat : Until KeyHit(1)
End

Function RotateCube(tween#)
	; Delete this code, replace it with something that works!
	RotateEntity cube, (ep - sp)/tween, (ey - sy)/tween, (er - sr)/tween, 1
End Function

The object of the exercise is to create a correct implementation of RotateCube. To test if it's correct, compare the rotation it gives to the one given by Blitz's own internal tweening system: if they're the same, you've got it. Now try it again with different start and end angles...

Why would you want to do something Blitz's tweening already does? Well, Blitz can only tween whole scenes: with this you can tween individual objects' rotations yourself, at different rates etc.

It's a difficult problem. Not impossible, though: I'm going to show you a correct implementation of RotateCube later on.

Gimbal lock

This is also a problem with Euler angles: at certain rotations you lose a degree of freedom. What this means is, say an object has been rotated so its pitch is 90 degrees. Now, changing the object's yaw and roll have the same effect. It's hard to imagine without seeing it.

If you want to see this effect in action, download and run GimbalLock.bb. Press [up] until the pitch = 90 degrees. Now, experiment with pressing [left] and [right], and [a] and [z]: they both rotate the cube around the same axis. There are ways round it, and the way I'll show you involves quaternions.

Quaternions

A quaternion is a set of four numbers that can be used to represent a rotation. That's it, really. The maths behind them use imaginary numbers, spheres in 4 dimensions, etc, but don't worry about that for now. I still don't really get the maths - look at some of the links in the Credits section for background info.

How do you use them? Start by downloading the source file Quat.bb, and use the functions in there. As supplied, you also have to use the Quat and Rotation types defined at the top of the file, but you can always change it if you're not happy.

To get you started, there are functions to convert from Rotations to Quats, and vice versa. Which is nice, but what can you do with them?

Slerp!

Here's how you smoothly interpolate between two rotations. There's a method called Slerp that will do this for you (Spherical Linear intERPolation, I think). It's easy to use: you provide two quaternions to interpolate between, a value in the range zero to one, indicating how far along the interpolation you want to go, and pass in another quaternion to store the result. You can then convert this result to a Blitz-style Euler Rotation, and use the RotateEntity command as usual.

As an example, here's an implementation of RotateCube, from the program above...

Function RotateCube(tween#)
	Local startQuat.Quat = New Quat
	Local midQuat.Quat = New Quat
	Local endQuat.Quat = New Quat
	Local startRot.Rotation = New Rotation
	Local midRot.Rotation = New Rotation
	Local endRot.Rotation = New Rotation

	; initialise the rotations
	FillRotation(startRot, sp, sy, sr)
	FillRotation(endRot,   ep, ey, er)

	; convert rotations to quats
	EulerToQuat startQuat, startRot
	EulerToQuat endQuat, endRot

	; do the interpolation
	QuatSlerp midQuat, startQuat, endQuat, tween

	; convert back to blitz-style eulers
	QuatToEuler midRot, midQuat

	RotateEntity cube, midRot\Pitch, midRot\Yaw, midRot\Roll, 1

	Delete startQuat
	Delete midQuat
	Delete endQuat
	Delete startRot
	Delete midRot
	Delete endRot
End Function

(Full source: Tweening2.bb) I've left it unoptimized to hopefully make it clear what's going on. I'll be giving some tips on optimization later on.

No gimbal lock

The other mathsy function in Quat.bb is MultiplyQuat. It multiplies two quaternions together: Qr = Q1 x Q2. The good thing about this is that rotating an object by the result (Qr) is exactly the same as applying rotation Q1 to the object, and then applying Q2. The order here is important, as Q1 x Q2 is not the same as Q2 x Q1.

So you can easily concatenate rotations. How does this help avoid gimbal lock? Download GimbalLock2.bb, have a look at how it differs from the original gimbal lock example, and play around with it.

Usage notes

If you look at the source of the functions in Quat.bb, you'll notice some heavy trigonometry usage. They are not "cheap" functions to call (in terms of time) and you should try to call them only when absolutely necessary. For example, in RotateCube() above, you only really need to work out the start and end Quats once, as these do not change from call to call.

You can bypass some unnecessary calculations by splitting the slerp function into two: one that sets up the values that remain the same for the whole rotation, and stores them globally somehow, the other does the bare minimum of calculations for each tween value. Be careful that you either have only one slerp going on at a time, or figure out a way round it... Also, precalculate as many Quats as possible before using them in-game (the extent to which you can do this will depend on your game, of course).

There are also some accuracy constants you can fiddle with if you know what you're doing: they basically refer to the tolerance of when a floating point number is compared to an extreme value (usually zero).

Credits

As I've mentioned a few times, I don't fully understand quaternions myself. So how did I write Quat.bb? Well, there's hardly anything in there that I actually came up with myself, and it is heavily based on sourcecode available elsewhere on the net. It's safe to say I'd never have worked out answers to my problems without the following sources:

An excellent introduction to quaternions, and the basis of the EulerToQuat, QuatSlerp and MultiplyQuat functions, written by Nick Bobic [link]

The basis of the QuatToEuler function, by Jeff Lander [link] [homepage]

More background articles at GameDev.net [link]

The best way I've seen of describing gimbal lock, by Gernot Hoffmann [link: pdf]

More advanced slerping, by Gernot Hoffman [link: pdf]

And many thanks to all the generous people on comp.graphics.algorithms, who helped me understand and fix the bugs I found whilst putting Quat.bb together.

Contact me

Any comments on this article? Found a bug? Email me at web@dscho.co.uk. All source code provided may be used in your own projects, feel free to modify, redistribute, whatever. I think as the routines in Quat.bb have been made so public, you should be able to use it freely: if in doubt, contact the original authors. I'd be interested to hear from anyone who does use it, but, you know, no biggie. Apologies for the state of the examples, they could do with cleaning up a bit. This article is also available in the BlitzCoder "Articles/Tutorials" section.

Page created: 15/11/02. Updated 13/12/02 [Expanded usage notes, corrected link for gamedev.net, added BlitzCoder link].