or: How I Learned To Stop Worrying And Embrace The Math

My artsy illustration degree was about as useful as a chocolate teapot in setting me up for my job as technical director.  When I read white papers, I feel dyslectic when looking at the wall of math and the academic wording. Now after some years of experience, I want to share some core code bits and understandings of the stuff that makes it possible to make pretty pictures, animations and games on the computer in a wording that I hope will be a bit more understandable than many of those white papers. First up: Spherical Spline Quaternion Interpolation or SQUAD for short.

What is it?
It's a formula that makes it possible to smoothly go between a set of rotations.

Where would I use it?
If you were making some animation code where you wanted some 3d object to go through a set of keyframes of different rotations for example, 'tweening' smoothly.

What do I need to understand to use it?
A basic understanding of Quaternions helps, but mainly you need to know that:
- Quaternions are rotations
- They are different to Euler angles, but they don't suffer from gimbal lock.
- They're not as straightforward to understand as Euler angles and have different problems to Euler angles.
- If you try to visualize them, your head explodes.

How does it work?
Do you know splines / curves from animation programs or vector drawing programs? It's a lot like that but in crazy quaternion space. The trick is that you need to compute something sensible as the tangents so that you can go smoothly through a bunch of keyframes.

What problem does it solve?
Normally, you might reasonably interpolate between Quaternions using SLerp (Spherical Linear Interpolation) or Lerp (Linear Interpolation) but if you're going to go between more than two key rotations, these functions are visually to the surface of a sphere what a straight line is to a sheet of paper.

Let's take a look at it visually. Here is a vector being rotated by SLerp through several rotations:

Although it's smoothly interpolating in time, it's not really affected by what the next quaternion after the current two is, so it just moves in a straight line from one quaternion to the next. If you have lots of keyframes this could still appear smooth, but with just a few spaced out ones, it doesn't look smooth. Now let's look at what this looks like with SQUAD interpolation:

Much better!  The rotations appear to be anticipating where it's going to go next, and we get a smooth curve occuring on the surface of the sphere. These rotations are much more visually pleasing and we need a lot fewer keyframes to achieve a smooth looking motion.

Because it's properly interpolating over all the different axis we can now get some interesting tangents by rotating the quaternions about the twist axis:

Unity Implementation
The unity project with source code and an example of use file can be downloaded here

Unity's Quaternion class isn't quite enough for to implement SQUAD, so we need to expand on that a bit first. The first script in the package below (QuaternionExtensions.boo) helps us extend the Quaternion class with functions that we need to complete the SQUAD calculations. Among other things we need a version of SLerp that's a bit different to the SLerp method in Unity in that it doesn't flip, as well as some basic things like scaling or adding to the Quaternion directly.

The second script (SQUAD.boo) contains the implementation of SQUAD itself. Looking at the code top down, our entry point might be something like the method Spline() with a number of quaternions that make up the spline, and a value t along that curve.

SplineSegment() returns the interpolated value between the 4 quaternions it's operating on (the part it's working on is the "line segment" between q1 and q2, the first and final quaternion are the previous and next quaternion after this line segment).

Intermediate() is the function that produces the nice and smooth tangent values between the rotations. There's some magic stuff going on in there and I'll let you play with the -0.25 value yourself. I'll cover briefly what is happening but I don't have a very deep understanding of why this works myself.
First it transforms the first and last quaternions by the inverse of the middle quaternion putting them in world space.
It then performs the quaternion Log function on them that we added in QuaternionExtensions.boo, adds them together, scales them by a magic number and performs quaternion Exp before transforming them back into the space of the middle quaternion and normalizing the Quaternion.

SQUAD() is then called on q1 and q2 with the two tangent values we got from Intermediate().  This is where we need to use the SlerpNoInvert() method we added to the Quaternion class. If we just use the Slerp() function from Unity there will come a point where unity clamps the domain of the Quaternion which basically looks like our poor vector travels through interdimensional space and ends up in some completely different place in our puny 3 dimensional world.

Special thanks to Pekka Kytölä for helping me learn this.

As always you can continue following Ludus development on gladiator.training