Game Math: Interpolating Quaternions with Circular Blending

This post is part of my Game Math Series.

While processing data for skeletal animations, we are usually faced with a series of discrete samples of positions and orientations. The positional samples are typically stored as a series of 3D vectors, and the orientational samples are typically stored as a series of quaternions. The most straightforward way to interpolate between positional samples is using piece-wise lerp (linear interpolation), and the counterpart for orientational samples is using piece-wise slerp (spherical linear interpolation). For more information on slerp, please see my previous post on quaternion basics.

The samples are sometimes too far apart, and we can see the visual artifact of discontinuous change in the first-order derivative of interpolation, i.e. the interpolation is not smooth at sample points.

In this post, I will present to you a technique for interpolating orientational samples in a smooth fashion called circular blending. I leaned about this technique from the MAT 351 class at DigiPen, taught by professor Matthew Klassen.

Let’s say we are given a series of quaternions:

    \[ q_0, q_1, q_2, ..., q_n \]

Let q_i and q_{i + 1} denote the two quaternions we are trying to interpolate between, and let t denote the interpolation parameter (0 \le t \le 1). Also, let r_i(t) denote the interpolating curve between q_i and q_{i + 1}.

If we are just using the straightforward slerp approach, we get:

    \[ r_i(t) = Slerp(q_i, q_{i + 1}, t) \]

This is a C^0 curve, meaning the curve is only continuous up to the zeroth-order derivative, i.e. the curve itself. The first-order derivative is generally not continuous at sample points using this approach.

Circular blending gives us a nice C^1 curve, which means the curve is continuous up to the first-order derivative. It is difficult to visualize quaternions, so I will use a 2D analogy to explain how circular blending works and how to mathematically work it out.

Theory

In order to interpolate between two quaternions q_i and q_{i + 1} using circular blending, we also need the two neighboring samples q_{i - 1} and q_{i + 2}. Let the figure below represent the four sample points:

circular blending 0

If we just use piece-wise slerp, this is what the curve will look like:

circular blending 1

We can easily see the abrupt change of slope at sample points.

To prepare for circular blending between q_i and q_{i + 1}, we draw two circles; one passes through q_{i-1}, q_i, and q_{i + 1}; the other one passes through q_i, q_{i + 1}, and q_{i + 2}. Let us denote these two circles C^1_i and C^2_i, respectively. Also, let us denote the arcs on these circles going from q_i to q_{i + 1} as r^1_i(t) and r^2_i(t), with r^1_i(0) = r^2_i(0) = q_i and r^1_i(1) = r^2_i(1) = q_{i + 1}.

circular blending 2

The formula for circular blending between q_i and q_{i + 1} is as follows:

    \[ r_i(t) = Slerp(r^1_i(t), r^2_i(t), t) \]

It is as simple as taking the slerp between the two arcs connecting q_i and q_{i + 1}. The arc r^1_i(t) fully contributes to the slope at q_i, and the arc r^2_i(t) fully contributes to the slope at q_{i + 1}.

circular blending 3

So why does this give us a C^1 curve? Let’s add the curve between the next pair of samples, q_{i + 1} and q_{i + 2}. We need another sample q_{i + 3} in order to draw the circle C^2_{i + 1}.

circular blending 4

Notice how the arc r^1_{i + 1}(t) fully contributes to the slope of r_{i + 1} at q_{i + 1}. The arc r^1_{i + 1}(t) is part of the same circle as the arc r^2_i, so the slope is continuous at the sample point q_{i + 1}.

Now let’s look at how we can find these circles and the desired arcs.

Details & Derivation

Given three points, q_0, q_1, and q_2, we would like to find a circle that passes through these points. Let C denote the center of this circle. Also, we would like to find the parameterized arc r(t) that goes from q_1 to q_2, where r(0) = q_1 and r(1) = q_2.

circular blending 5

Let \overrightarrow{v_1} denote the vector from q_0 to q_1, and let \overrightarrow{v_2} denote the vector from q_0 to q_2. Let m_1 denote the midpoint between q_0 and q_1, and let m_2 denote the midpoint between q_0 and q_2.

circular blending 6

If we draw the bisectors of \overrightarrow{v_1} and \overrightarrow{v_2}, they should pass through the center of the circle, because a bisector of a line segment connecting two points on a circle always passes through the center of the circle. The bisectors are perpendicular to their corresponding vectors \overrightarrow{v_1} and \overrightarrow{v_2}. Let the direction vectors of the two bisectors be denoted as \overrightarrow{n_1} and \overrightarrow{n_2}.

circular blending 7

To find \overrightarrow{n_1} and \overrightarrow{n_2}, we use the formulas:

    \[ \overrightarrow{n_1} = \overrightarrow{v_2} - proj_{\overrightarrow{v_1}}(\overrightarrow{v_2}) \]

    \[ \overrightarrow{n_2} = \overrightarrow{v_1} - proj_{\overrightarrow{v_2}}(\overrightarrow{v_1}) \]

where proj_{\overrightarrow{a}}(\overrightarrow{b}) denotes the projection of the vector \overrightarrow{b} onto the vector \overrightarrow{a}.

Now we have the parameterized formula for the two bisectors, b_1(s) and b_2(t):

    \[ b_1(s) = m_1 + s \overrightarrow{n_1} \]

    \[ b_2(t) = m_2 + t \overrightarrow{n_2} \]

The center of the circle C is at the intersection of these two bisectors, so we need to find the parameter pair (s, t) that satisfies:

    \[ m_1 + s \overrightarrow{n_1} = m_2 + t \overrightarrow{n_2} \]

If we rearrange the equation, we get:

    \[ s \overrightarrow{n_1} - t \overrightarrow{n_2} = m_2 - m_1 \]

Remember that we are working with quaternions, so the vectors \overrightarrow{n_1}, \overrightarrow{n_2}, and (m_2 - m_1) are all 4D vectors. This means that we have four equations for two unknowns, which is more than enough. All we have to do is to pick two equations and use Cramer’s Rule to solve for (s, t). Beware that the two equations you choose might not have a solution, i.e. you get a zero determinant when applying Cramer’s Rule; so be sure pick two equations that do not give you a zero determinant when solving for (s, t). We can obtain C by plugging either s or t back into its corresponding bisector equation.

Now that we have the center of the circle C, the last step is to find the parameterized arc r(t) where r(0) = q_1 and r(1) = q_2. We aim to find the arc in the following form:

    \[ r(t) = C + R(cos(t\theta)\overrightarrow{u} + sin(t\theta)\overrightarrow{v}),  \]

where \theta is the angle between q_1 and q_2, so \theta = cos^{-1}(q_1 \cdot q_2); R is the radius of the circle; \overrightarrow{u} and \overrightarrow{v} form an orthonormal basis of the plane that contains the circle.

Finding \overrightarrow{u} is easy. It is the unit vector pointing from C to q_1:

    \[ \overrightarrow{u} = \frac{q_1 - C}{|q_1 - C|} \]

As for finding \overrightarrow{v}, we first find the unit vector \overrightarrow{w} pointing from C to q_2:

    \[ \overrightarrow{w} = \frac{q_2 - C}{|q_2 - C|} \]

and then we can find \overrightarrow{u} by taking out from \overrightarrow{w} its parallel component to \overrightarrow{u}:

    \[ \overrightarrow{v} = \frac{\overrightarrow{w} - proj_{\overrightarrow{u}}(\overrightarrow{w})}{|\overrightarrow{w} - proj_{\overrightarrow{u}}(\overrightarrow{w})|} \]

Visually, here’s the whole picture:

circular blending 8

We are done! We have found the circle that passes through the three points, as well as the parameterized arc r(t) on the circle that satisfies r(0) = q_1 and r(1) = q_2.

One last thing. You might wonder what we should do if the three points are collinear. There’s no way we can find a circle with finite radius that passes through three collinear points! Remember that we are working with unit quaternions here. Three different unit quaternions would never be collinear because they lie on three different spots on the 4D unit hypersphere, just as three different points on a 3D unit sphere would never be collinear. So we are good.

Demo

Finally, let’s look at a video comparing the results of piece-wise slerp and circular blending in action.

About Allen Chou

Physics / Graphics / Procedural Animation / Visuals
This entry was posted in Gamedev, Math. Bookmark the permalink.

3 Responses to Game Math: Interpolating Quaternions with Circular Blending

  1. Jura says:

    Would be really nice if you share your source code for this interpolation!

  2. Nathan Reed says:

    Interesting idea, but why not simply use Catmull-Rom splines? The math is simpler, plus game engines will likely have spline interpolation code already. One could even consider Hermite splines with user-controlled tangents, as is usually done for other animation curves, though I’m not sure how useful this would really be with quaternion.

    • Allen Chou says:

      Yes, the math for Catmull-Rom splines is indeed simpler. I hope I’m not giving the wrong impression that circular blending is superior than any other interpolation techniques; I just wanted to present one of the techniques that can be used to smoothly interpolate quaternions.

Leave a Reply