The Unnecessarily Short Ways To Do a Quaternion Slerp

Give the users a choice

In or­der to pre­vent Mag­num users from such at­ro­cit­ies, I de­cided to provide sup­port for both shortest-path and non-shortest-path in­ter­pol­a­tion. I named the func­tions Math::slerp() and Math::slerp­Shortest­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 status of such sup­port in vari­ous en­gines I checked. Hav­ing sup­port for ba­sic qua­ternion lerp next to slerp is cru­cial, as it’s just a vec­tor in­ter­pol­a­tion with a renor­mal­iz­a­tion step after — a much faster op­er­a­tion suited for cases where pre­ci­sion is not as im­port­ant (such as most an­im­a­tions with dense key­frames):

1.

^ Quat4f.in­ter­pol­ate(), I was not able to find any oth­er vari­ants

2.

^ Sler­pQua­ternion­In­ter­pol­at­or.in­ter­pol­ate(), based on the javax.vecmath im­ple­ment­a­tion above. I was not able to find any oth­er vari­ants.

3.

^ Qua­ternion.Lerp(), Qua­ternion.Slerp(), both shortest-path. Non-shortest-path is re­portedly im­possible (Unity For­um, Red­dit r/Unity3D).

4.

^ FQuat::Fast­Lerp() (shortest path but doesn’t renor­mal­ize), FQuat::Slerp() and FQuat::Sler­p­Full­Path(). Non-shortest-path lerp has to be hid­den there some­where (prob­ably just a vec­tor lerp would do that, since FastLerp() also doesn’t renor­mal­ize).

5.

^ idQuat::Slerp(), I was not able to find any oth­er vari­ants

6.

^ Qua­ternion.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­il­ar, one does a shortest-path op­tim­iz­a­tion while the oth­er does not, lead­ing to con­fus­ing be­ha­vi­or

8.

^ Ei­gen::Qua­ternion::slerp(), the only im­ple­ment­a­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­Shortest­Path(), Math::slerp(), Math::slerp­Shortest­Path()

The per­form­ance as­pect

Be­sides giv­ing the users more con­trol, there is also the per­form­ance side of things. While I ori­gin­ally didn’t as­sume the ex­tra branch to have a sig­ni­fic­ant ef­fect in slerp, my think­ing was that it’ll def­in­itely add some­thing to the ba­sic lerp, since the dot product would not be needed at all oth­er­wise:

To veri­fy the above as­sump­tion, I bench­marked the Math::lerp(), Math::lerp­Shortest­Path(), Math::slerp() and Math::slerp­Shortest­Path() im­ple­ment­a­tions in latest 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.

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

Im­ple­ment­a­tion in Mag­num — let’s fix the data in­stead

In Mag­num, users now have the choice to use any in­ter­pol­a­tion vari­ant they want. Since shortest-path in­ter­pol­a­tion is used most com­monly, Math::slerp­Shortest­Path() is the de­fault in­ter­pol­at­or picked when you spe­cify An­im­a­tion::In­ter­pol­a­tion::Lin­ear for qua­ternion tracks. That’s the least sur­pris­ing be­ha­vi­or and if you don’t like the choice, simply pass some oth­er in­ter­pol­at­or func­tion dir­ectly.

But what to do with im­por­ted an­im­a­tion data? Since that’s where in­ter­pol­a­tion will get used most, it would be nice to have some op­tim­iz­a­tion op­por­tun­ity there too.

Turns out it’s easy — un­like the tri­go­no­metry as­pects of slerp, which are hard to get rid of, op­tim­iz­ing away the shortest-path flip is easy — just patch the data on im­port! (Thanks for the hint, @Squareys!) Since mosra/mag­num-plu­gins@bba82bf, the Tiny­Glt­fIm­port­er plu­gin by de­fault patches qua­ternions in lin­early in­ter­pol­ated ro­ta­tion tracks in or­der to al­ways have the shortest path from one key­frame 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­por­ted Trade::An­im­a­tionData in­stances, you can sup­ply a dif­fer­ent in­ter­pol­at­or of your choice to ro­ta­tion tracks either dir­ectly with An­im­a­tion::Track­View::at() or by adding them to the play­er us­ing An­im­a­tion::Play­er::ad­dRaw­C­all­back():

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

The glTF an­im­a­tion im­port patch­ing is con­fig­ur­able with a runtime op­tion, so if you don’t want it for some reas­on, simply 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­ably guessed from the above overly terse code snip­pets, there’s much more to say about the new An­im­a­tion lib­rary, stay tuned for the next posts. Thank you for read­ing!