Quaternions part 3

posted by harrison on September 5, 2012

If you’re looking for the start of the series, go here.

In this post, i’ll be going over the slerp function, which interpolates between two quaternions. There’s a wrong way to do it, a vector way to do it, and a quaternion way to do it.

A warning

For every rotation, there are two quaternions that represent it. Namely, q and -q. The reason is that if you flip the axis of rotation, and rotate by a negative angle, it’s the same as rotating by a positive angle around the original axis. This can give you trouble when interpolating quaternions, because slerp(q, \bar{q}, t) will not be the same rotation as slerp(q, -\bar{q}, t) except at t=0 and t=1. For correct results, you want the two quaternions to be the ‘closer’ representation. The easiest way to get good results is to find the cosine of the angle between the quaternions (by treating them as 4d vectors): cos(\omega) = q \cdot \bar{q}. if the result is negative, then negate one of the quaternions. This will make the angle traversed by the slerp function be the smaller of the two possibilities.

Also, if you want to rotate through an angle of more than \pi, you can’t do it easily with a single slerp, since slerp follows the shortest path. To get around this, you can use an intermediate rotation, and slerp from the start to the intermediate, then from the intermediate to the end. You can also keep slerping past 1: slerping to 1 will traverse angle \omega = acos(q \cdot \bar{q}), so if you wanted to do an extra full rotation, you could keep going until you got to \omega + \pi, so you could slerp until 1 + \frac{\pi}{\omega}, but many libraries will clamp at 1.

The wrong way

    \[slerp(q,\bar{q},t) = normalize((1-t)q + t\bar{q})\]

This will follow the correct path, but it will do so at an inconsistent speed. the interpolation will be faster when t is close to 0 or 1 than when it is close to \frac{1}{2}.

The vector way

The basic idea of this method is to consider the quaternions as unit 4d vectors. Given two different unit quaternions, the shortest path between them is going to lie in the plane formed by the two quaternions and the origin. In other words, the path that the slerp takes is made of linear combinations of the input quaternions. If the two quaternions were orthogonal (q \cdot \bar{q} = 0), it would be easy. You could just treat the two quaternions as basis vectors of a 2d space, and use ordinary 2d rotation:

    \[slerp(q, \bar{q}, t) = cos(t\frac{\pi}{2})q + sin(t\frac{\pi}{2})\bar{q}\]

But since the quaternions are not always orthogonal, we have to make an orthogonal quaternion, and then instead of rotating by t\frac{\pi}{2}, we have to rotate by t\theta where \theta is the angle between the quaternions, which is acos(q \cdot \bar{q}). We can get an orthogonal quaternion by subtracting the projection of \bar{q} onto q from \bar{q}:

    \[ q_\perp = normalize(\bar{q} - (q \cdot \bar{q})q) = \frac{\bar{q} - (q \cdot \bar{q})q}{sin(\theta)} \]

    \[ slerp(q, \bar{q}, t) = cos(t\theta)q + sin(t\theta)\frac{\bar{q} - (q \cdot \bar{q})q}{sin(\theta)} \]

The quaternion way

The vector way works just as well, but is a little awkward  if you’re trying to take derivatives, and it doesn’t generalize to higher order interpolation (quadratic, cubic, etc.). The basic idea for quaternion slerp is to find the quaternion q_\Delta that you need to multiply q by to get \bar{q}, and use powers of q_\Delta:

    \[q_\Delta = q^{-1}\bar{q}\]

    \[slerp(q, \bar{q}, t) = qq_\Delta^t  = q(q^{-1} \bar{q})^t \]

But in order to do this, we need to figure out  what q^t is. We can do that by going back to axis-angle representation, but because of history, we’ll call the convert-to-quaternion function e^{\frac{\theta}{2} \hat{v}} or exp(\frac{ \theta}{2} \hat{v}), and our convert-to-axis-angle function log(q). I’ll go into that naming later. Also, notice that instead of having a separate axis and angle, we use a unit axis vector, and multiply it by half the angle. The basic idea of the q^t function is to convert to axis-angle, multiply the angle by t, then convert back.

    \[q^t = e^{t log(q)} \]

exponentiation:

    \[e^{\frac{\theta}{2} \hat{v}} = cos(\frac{\theta}{2}) + \hat{v}sin(\frac{\theta}{2}) \]

or

    \[e^v = cos(||v||) + \hat{v}sin(||v||) \]

log:

    \[log(a + u) = acos(a) \hat{u} \]

It’s also worth mentioning that you can linearly interpolate rotations in log-space, and then convert the result back. This will give you a constant-speed rotation, and you can handle rotations larger than \pi if you store them as axis-angle, but it will not always follow the shortest path. If the axes are the same direction (or opposite direction), it will work well, but

Why exp/log?

So, to those familiar with complex numbers, exponentiation and logarithms shouldn’t look too surprising. To the rest of you, i’ll try to make some sense of it. It’s based on the Taylor series, which is f(x) = \sum_{n=0}^{\infty}\frac{f^{(n)}(0)}{n!}x^n, where f^{(n)} is the n’th derivative of f. One special function is e^x, which is its own derivative, so:

    \[e^x = \sum_{n=0}^{\infty}\frac{x^n}{n!} \]

also, sin and cos have interesting derivatives. for sin, every even derivative is 0 at 0, and the odd ones alternate between 1 and -1. cos is similar:

    \[sin(x) = \sum_{n=0}^{\infty}\frac{(-1)^{n}}{(2n+1)!}x^{2n+1} \]

    \[cos(x) = \sum_{n=0}^{\infty}\frac{(-1)^{n}}{(2n)!}x^{2n} \]

Also, given a unit vector \hat{v}, \hat{v} \hat{v} = - \hat{v} \cdot \hat{v} + \hat{v} \times \hat{v} = -1. So, \hat{v}^0 = 1, \hat{v}^1 = \hat{v}, \hat{v}^2 = -1, \hat{v}^3 = -\hat{v}, and higher powers just loop through those 4 values. So, let’s see what happens when we try plugging a vector into e^x:

    \[e^{\theta \hat{v}} = \sum_{n=0}^{\infty}\frac{(\theta \hat{v})^n}{n!} \]

    \[e^{\theta \hat{v}} = \sum_{n=0}^{\infty}\frac{\theta^n \hat{v}^n}{n!} \]

    \[e^{\theta \hat{v}} =\sum_{n=0}^{\infty}\frac{\theta^{2n} \hat{v}^{2n}}{(2n)!} + \sum_{n=0}^{\infty}\frac{\theta^{2n+1} \hat{v}^{2n+1}}{(2n+1)!} \]

    \[e^{\theta \hat{v}} =\sum_{n=0}^{\infty}\frac{\theta^{2n} (-1)^n}{(2n)!} + \sum_{n=0}^{\infty}\frac{\theta^{2n+1} \hat{v}(-1)^n}{(2n+1)!} \]

    \[e^{\theta \hat{v}} =\sum_{n=0}^{\infty}\frac{\theta^{2n} (-1)^n}{(2n)!} + \hat{v}\sum_{n=0}^{\infty}\frac{\theta^{2n+1}(-1)^n}{(2n+1)!} \]

and that looks a lot like our sin and cos taylor series:

    \[e^{\theta \hat{v}} =cos(\theta) + \hat{v}sin(\theta)\]

and log is supposed to be the inverse of e^x, so:

    \[log(cos(\theta) + \hat{v}sin(\theta)) = \theta \hat{v} \]

and we already know that our quaternions are in that form, so

    \[log(a+v) = acos(a) \hat{v} \]

And if you use \frac{\theta}{2} instead of \theta, you get exactly the axis-angle formula from part 1.

And that’s pretty much all the math you need to use quaternions. In future posts, i’ll talk about higher degree interpolation, and provide some sample code in some language (probably c# or c++).

 


Twisted Oak Studios offers consulting and development on high-tech interactive projects. Check out our portfolio, or Give us a shout if you have anything you think some really rad engineers should help you with.

Archive

More interesting posts (25 of 33 articles)

Or check out our Portfolio.