[Math] Super confused by SQUAD algorithm for quaternion interpolation

quaternionsrotations

I have been trying to wrap my mind around the SQUAD algorithm (sometimes called "Spherical Cubic Interpolation", sometimes called "Spherical Quadratic Interpolation").

You can find implementations and algorithms here, here and here.

If I understand it correctly it's supposed to smooth out rotations using 4 quaternions that are in sequential order in an animation with rotation keyframes.

Now I do get SLERP and I claim to have a fairly good visualization of the hypersphere and how quaternions describe it's "surface" (does the term "surspace" exist?)

However I was confused as to why the SQUAD algorithm should work. To understand it better I simply took some paper and drew the algorithm in 0.2 steps using 2d points and LERP, pretending the paper is the surface (surspace?) of the unit hypersphere. The curves I am getting look like they are exact mirror images of what I think I actually want to have.

Maybe I am still lacking some fundamental knowledge of quaternions. I have attached a scan of my drawings:

So, my concrete questions:

Am I doing something wrong?
Am I misunderstanding what SQUAD does or
what it is for?
Am I fundamentally misunderstanding quaternions and
the curves I get are actually super fine?

Best Answer

Okay, so SQUAD does exactly what I did on paper. But it's also not broken.

My mistake was: SQUAD doesn't expect 4 consecutive quaternions q0, q1, q2 and q3. SQUAD expects q1 and q2, together with 2 helper quaternions a and b that have to be calculated beforehand.

The helper quaternions a and b will form a quadrangle with q1 and q2 that will result in curves resembling the mirrored curves in my drawing. Therefore using SQUAD on q1, q2, a and b will result in smooth interpolations over a list of rotation keyframes.

I haven't found any detailed documentation or explanation on this unfortunately, but the DirectX SDK from Microsoft has a SquadSetup method that helped me figure this out. The open source library Cesium JS also has an implementation Quaternion.computeInnerQuadrangle for finding the helper quaternions a and b to be used with SQUAD.

I haven't really understood why the helper quaternions are calculated in the way they are, but when I implement it, the result doesn't look wrong. Considering my original question is answered, this specific issue can be adressed in a separate question.

To help me get a better understanding for what's going on, I made a simple WebGL demo comparing different interpolation methods, including SQUAD the correct way and as I previously wrongly used/understood it. The demo generates 10 random unit quaternions and then interpolates between them indefinitely. It shows 12 WebGL canvas instances, 2 per algorithm. The top canvas displays the quaternions in 4d space and the current interpolated quaternion, the bottom canvas displays a cube that is being rotated by the current quaternion.

Related Solutions

Quaternions – Exponential Map, Rotations, and Interpolation

The Lie algebra to the Lie group of unit quaternions is the tangent space at $1$, i.e., the set of purely imaginary quaternions. The exponential map can then be written as $$ \exp(d)=\cos(\|d\|)+\frac{d}{\|d\|}\sin(\|d\|) $$ The corresponding parametrization at any other unit quaternion $q$ is then $$ q\cdot \exp(d)=q⋅\cos(\|d\|)+\frac{q⋅d}{\|d\|}\sin(\|d\|) $$ Note that $q⋅d$ is an element of the tangent plane at $q$ to the unit sphere, and $\|q⋅d\|=\|d\|$, so that the formula might be rewritten in terms of elements of the tangent plane.

One interpretation of the procedure in the question (exchanging ln and exp as suggested in the comments) is that a quaternion is first cast into the tangent plane of $1$ by decomposing $$ \mathfrak{q}_{prev}=\cos\alpha+\sin\alpha\,\vec n $$ using $c=Re(\mathfrak{q}_{prev})$, $\vec n'=Im(\mathfrak{q}_{prev})$, $\alpha=atan2(\|\vec n'\|,c)$, $\vec n=\vec n'/\|\vec n'\|$ and finally using $$\mathfrak{q}_{prevlog}=\alpha\vec n.$$

Then add the update vector and transform back using the exponential. One might keep the primary variables in the tangent plane if no modification happens in the exponential form, so that the logarithm transform is not necessary in every update step.

[Math] How to understand and create quaternions

In 3D space, initial coordinates are decided by the given Left-hand and Right-hand coordinates, sometimes called x-up, y-up, z-up conventions which can also be found (for example) in Wiki's EulerAngles item.

Initial Quaternions are defined corresponding to the intial x-y-z

For example, x-y-z-right hand coordinates, then 0,0,0,1 would be the initial quaternion.

Of course, the order also depends on the setting of program.

For example maybe DirectX and openGL are in different orders of the initial quaternion of the same coordinates.

And also your self programs could in one arbitrary initial order.

However, when one initial order was defined(corresponding to x-y-z), then the other 23 orders could also be well defined.

4!

(*
    24
*)

24 is the number of kinds of orders. When I decide which order was used in one 3D game engine which I cannot know the order by specification, I do experiments.

Maybe you could find a Matrix to Quaternion program, and then do rotations in Matrix, then convert the combined final matrix to Quaternions will lead you a good comprehension.

Best Answer

Related Solutions

Quaternions – Exponential Map, Rotations, and Interpolation

[Math] How to understand and create quaternions

Related Question