The Unnecessarily Short Ways To Do a Quaternion Slerp

Com­ing to an es­tab­lished work­flow for the first time is al­ways an in­ter­est­ing ex­pe­ri­ence be­cause I don’t have any “it’s been like this since for­ev­er” in­sights form­ing my opin­ion yet. This time it’s about quater­nion in­ter­po­la­tion and a sud­den op­ti­miza­tion op­por­tu­ni­ty.

Tra­di­tion­al­ly, quater­nion slerp() in Mag­num was done like this:

\begin{array}{rcl} \theta & = & \arccos \left( \frac{q_A \cdot q_B}{|q_A| |q_B|} \right) = \arccos(q_A \cdot q_B) \\[5pt] q_{SLERP} & = & \cfrac{\sin((1 - t) \theta) q_A + \sin(t \theta) q_B}{\sin(\theta)} \end{array}

Noth­ing ob­vi­ous­ly wrong there, right? Or at least I thought so. While im­ple­ment­ing all sorts of in­ter­po­la­tion meth­ods for the new An­i­ma­tion frame­work that’s part of the up­com­ing Mag­num re­lease, I dis­cov­ered that the An­i­mat­ed Tri­an­gle glTF sam­ple is ro­tat­ing in a fun­ny way: first it goes three quar­ters of the way and then in­stead of fin­ish­ing the cir­cle it goes back­wards. Ap­par­ent­ly I was not the on­ly one with this prob­lem.

Hav­ing a flash­back to four years ago when I was im­ple­ment­ing a sim­ple an­i­ma­tion sys­tem for 2D touch­screen UIs, the first thing that came to my mind is that the an­i­ma­tion da­ta is wrong — in­stead of go­ing from 270° to 360°, the an­i­ma­tion re­quests to go from 270° to 0° and some­how the glTF play­ers and im­porters in­ter­pret that as go­ing for­ward in­stead of back­ward and no­body ques­tioned the be­hav­ior un­til now.

See­ing the com­ment about which view­er was used for ver­i­fi­ca­tion of the sam­ple, I first thought these im­ple­men­ta­tions were a bit “spe­cial” and it’s not usu­al to do it like this. Turns out I was wrong (of course) — the Short­est Path quater­nion slerp is the com­mon way:

\begin{array}{rcl} d & = & q_A \cdot q_B \\ {\color{m-info} q'_A} & {\color{m-info} =} & {\color{m-info} \begin{cases} {\color{m-default} \phantom{-}q_A}, & d \ge 0 \\ -q_A, & d < 0 \end{cases} }\\[15pt] \theta & = & \arccos({\color{m-info}|}d{\color{m-info}|}) \\ q_{SLERP} & = & \cfrac{\sin((1 - t) \theta) {\color{m-info} q'_A} + \sin(t \theta) q_B}{\sin(\theta)} \end{array}

But the seed of doubt had al­ready been plant­ed and so I was still un­sure if this is the right way to do it — the short­est-path choice ba­si­cal­ly takes one de­gree of free­dom away from the us­er. Googling around, I found var­i­ous peo­ple ask­ing how to by­pass the short­est path as­pect (Uni­ty Fo­rum, Red­dit r/Uni­ty3D) and get­ting ex­treme­ly dense replies along the lines of “you are ask­ing for the im­pos­si­ble”, “there are in­fi­nite ways to do that” or “go through Eu­ler an­gles in­stead”.

Give the users a choice

In or­der to pre­vent Mag­num users from such atroc­i­ties, I de­cid­ed to pro­vide sup­port for both short­est-path and non-short­est-path in­ter­po­la­tion. I named the func­tions Math::slerp() and Math::slerp­Short­est­Path() (and not slerp() and slerpNotShortestPath()) to sug­gest the one with the longer name is do­ing some­thing ex­tra and might not be al­ways the best choice.

Here’s the sta­tus of such sup­port in var­i­ous en­gines I checked. Hav­ing sup­port for ba­sic quater­nion lerp next to slerp is cru­cial, as it’s just a vec­tor in­ter­po­la­tion with a renor­mal­iza­tion step af­ter — a much faster op­er­a­tion suit­ed for cas­es where pre­ci­sion is not as im­por­tant (such as most an­i­ma­tions with dense keyframes):

lerp lerp
SP
slerp slerp
SP
javax.vecmath [1]
javagl [2]
Unity 3D [3]
Unreal Engine [4] ?
id Tech 4 (Doom 3) [5]
three.js [6]
GLM [7]
Eigen [8]
Magnum::Math [9]
1
Quat4f.in­ter­po­late(), I was not able to find any oth­er vari­ants
2
Sler­pQuater­nion­In­ter­po­la­tor.in­ter­po­late(), based on the javax.vecmath im­ple­men­ta­tion above. I was not able to find any oth­er vari­ants.
3
Quater­nion.Lerp(), Quater­nion.Slerp(), both short­est-path. Non-short­est-path is re­port­ed­ly im­pos­si­ble (Uni­ty Fo­rum, Red­dit r/Uni­ty3D).
4
FQuat::FastLerp() (short­est path but doesn’t renor­mal­ize), FQuat::Slerp() and FQuat::Slerp­Full­Path(). Non-short­est-path lerp has to be hid­den there some­where (prob­a­bly just a vec­tor lerp would do that, since FastLerp() al­so doesn’t renor­mal­ize).
5
idQuat::Slerp(), I was not able to find any oth­er vari­ants
6
Quater­nion.slerp(), I was not able to find any oth­er vari­ants
7
glm::lerp() and glm::slerp(), note that even though the name is sim­i­lar, one does a short­est-path op­ti­miza­tion while the oth­er does not, lead­ing to con­fus­ing be­hav­ior
8
Eigen::Quater­nion::slerp(), the on­ly im­ple­men­ta­tion where you have to do a weird a.slerp(b, t) in­stead of slerp(a, b, t). I was not able to find any oth­er vari­ants, even this one was hard to find.
9
Math::lerp(), Math::lerp­Short­est­Path(), Math::slerp(), Math::slerp­Short­est­Path()

The per­for­mance as­pect

Be­sides giv­ing the users more con­trol, there is al­so the per­for­mance side of things. While I orig­i­nal­ly didn’t as­sume the ex­tra branch to have a sig­nif­i­cant ef­fect in slerp, my think­ing was that it’ll def­i­nite­ly add some­thing to the ba­sic lerp, since the dot prod­uct would not be need­ed at all oth­er­wise:

\begin{array}{rcl} {\color{m-success} d} & {\color{m-success} =} & {\color{m-success} q_A \cdot q_B }\\[5pt] {\color{m-success} q'_A} & {\color{m-success} =} & {\color{m-success} \begin{cases} {\color{m-default} \phantom{-}q_A}, & d \ge 0 \\ -q_A, & d < 0 \end{cases} }\\[15pt] q_{LERP} & = & \cfrac{(1 - t) {\color{m-success} q'_A} + t q_B}{|(1 - t) {\color{m-success} q'_A} + t q_B|} \end{array}

To ver­i­fy the above as­sump­tion, I bench­marked the Math::lerp(), Math::lerp­Short­est­Path(), Math::slerp() and Math::slerp­Short­est­Path() im­ple­men­ta­tions in lat­est Mag­num mas­ter (mosra/mag­num@4b7d­ab1). Hov­er over the bars be­low to see pre­cise num­bers; bench­mark code for ref­er­ence is here.

2.43 ± 0.13 ns 7.27 ± 0.25 ns 6.53 ± 0.19 ns 48.91 ± 1.91 ns 37.81 ± 1.8 ns 0 10 20 30 40 50 ns baseline lerpShortestPath() lerp() slerpShortestPath() slerp() benchmark overhead ~15% faster ~24% faster CPU time, Linux x64, GCC 8.1 -O3, Core i7 8th gen

The big dif­fer­ence with slerp sur­prised me — I as­sumed the time spent by the \arccos() cal­cu­la­tion would hide most of the branch­ing over­head — this big dif­fer­ence prob­a­bly points out to spec­u­la­tive ex­e­cu­tion done by the CPU, where many things get cal­cu­lat­ed twice and in the end on­ly half of them is used.

Im­ple­men­ta­tion in Mag­num — let’s fix the da­ta in­stead

In Mag­num, users now have the choice to use any in­ter­po­la­tion vari­ant they want. Since short­est-path in­ter­po­la­tion is used most com­mon­ly, Math::slerp­Short­est­Path() is the de­fault in­ter­po­la­tor picked when you spec­i­fy An­i­ma­tion::In­ter­po­la­tion::Lin­ear for quater­nion tracks. That’s the least sur­pris­ing be­hav­ior and if you don’t like the choice, sim­ply pass some oth­er in­ter­po­la­tor func­tion di­rect­ly.

But what to do with im­port­ed an­i­ma­tion da­ta? Since that’s where in­ter­po­la­tion will get used most, it would be nice to have some op­ti­miza­tion op­por­tu­ni­ty there too.

Turns out it’s easy — un­like the trigonom­e­try as­pects of slerp, which are hard to get rid of, op­ti­miz­ing away the short­est-path flip is easy — just patch the da­ta on im­port! (Thanks for the hint, @Squareys!) Since mosra/mag­num-plug­ins@bba82bf, the TinyGlt­fIm­porter plug­in by de­fault patch­es quater­nions in lin­ear­ly in­ter­po­lat­ed ro­ta­tion tracks in or­der to al­ways have the short­est path from one keyframe to the oth­er. The code that does that is just this:

Containers::ArrayView<Quaternion> values;
Float flip = 1.0f;
for(std::size_t i = 0; i < values.size() - 1; ++i) {
    if(Math::dot(values[i], values[i + 1]*flip) < 0) flip = -flip;
    values[i + 1] *= flip;
}

Then, once you have the im­port­ed Trade::An­i­ma­tion­Da­ta in­stances, you can sup­ply a dif­fer­ent in­ter­po­la­tor of your choice to ro­ta­tion tracks ei­ther di­rect­ly with An­i­ma­tion::Track­View::at() or by adding them to the play­er us­ing An­i­ma­tion::Play­er::ad­dRaw­Call­back():

Animation::TrackView<Float, Quaternion> track;
Quaternion rotation = track.at(time, Math::slerp);

The glTF an­i­ma­tion im­port patch­ing is con­fig­urable with a run­time op­tion, so if you don’t want it for some rea­son, sim­ply flip the switch back to false:

std::unique_ptr<Trade::AbstractImporter> importer =
    manager.loadAndInstantiate("TinyGltfImporter");
importer->configuration().setValue("optimizeQuaternionShortestPath", false);

And that’s it! As you have prob­a­bly guessed from the above over­ly terse code snip­pets, there’s much more to say about the new An­i­ma­tion li­brary, stay tuned for the next posts. Thank you for read­ing!

Magnum 2018.02 released

The new Mag­num mile­stone brings We­bGL 2.0 and We­bAssem­bly, VR sup­port, lots of niceties for Win­dows users, iOS port, new ex­per­i­men­tal UI li­brary, im­proved test­ing ca­pa­bil­i­ties, sup­port for over 80 new as­set for­mats, new ex­am­ples and much more.

Introducing Guest Posts

One of the goals while build­ing the new Mag­num web­site was to low­er the bar­ri­er for con­tribut­ing con­tent. With Git and GitHub it’s al­ready very easy to con­trib­ute code to the project it­self, so why not ex­tend that to the web­site as well?

page 1 | older articles »