Cubic interpolation of rotations in 3d transform animation track is unpredictable.

[mohrcore]

Godot version:
v.3.2.2.stable.official, v.3.2.3.beta.custom_build.bdd1e7486 (bdd1e74)

OS/device including version:
Gentoo/Linux x86_64

Issue description:
Cubic interpolation of 3d rotations seems to produce unpredictable splines.

I tried to create a 3D animation using 3D transform track in AnimationPlayer node. I made 3 keyframes in total.
In the first two keyframes, the rotation of the node is unchanged, in the third, the object is rotated. Interpolating the animation with nearest and linear options seems to work fine. However if I switch the track interpolation to cubic, the node rotates towards the angle specified in the third keyframe and the back to the original angle within the period between first two keyframes. Then, after the second keyframe it bounces off and rotates again towards the angle specified in the third keyframe as it should.

Expected result: the node's rotation should stay unchanged during the period between first two keyframes (wrapping is set to clamp), then after the second frame it should smoothly rotate towards the angle specified by the third keyframe.

Steps to reproduce:

The simplest scenario has been already described above, however other animations of rotation of 3d transform also result unexpected interpolations. Some of these interpolations seem to be not even continuous (eg.: the rotation "bouncing" off the angle defined by keyframe instead of going through it smoothly).

The simplest steps for reproduction would be:

1. Create a 3D scene.
2. Place a node (MeshInstance for example)
3. Place AnimationPlayer as it's child
4. Create a simple animation in AnimationPlayer with 3D transform track for it's parent.
5. Place some keyframes, some of which should change node's rotation, others should keep the rotation from their forerunners.

Minimal reproduction project:
godot_animation_bug.zip

[fire]

I've been using https://github.com/KhronosGroup/glTF-Sample-Models/tree/5bbe0b378d703a506ce8ae12c7dc829e42546d3b/2.0/InterpolationTest to test too, but it's also different.

[mohrcore]

Ok, I checked the source code and the code for cubic slerps for quats looks really sketchy to me:

Quat Quat::cubic_slerp(const Quat &q, const Quat &prep, const Quat &postq, const real_t &t) const {
#ifdef MATH_CHECKS
	ERR_FAIL_COND_V_MSG(!is_normalized(), Quat(), "The start quaternion must be normalized.");
	ERR_FAIL_COND_V_MSG(!q.is_normalized(), Quat(), "The end quaternion must be normalized.");
#endif
	//the only way to do slerp :|
	real_t t2 = (1.0 - t) * t * 2;
	Quat sp = this->slerp(q, t);
	Quat sq = prep.slerpni(postq, t);
	return sp.slerpni(sq, t2);
}

If I get it right (prep is a quat before *this and postq is a quat after q), there's no way it would work in the scenario I've described. The third keyframe would have the postq quat, so when interpolating between *this and q which are the same, the result would gravitate towards postq just to go back to the same quat and the worst part is that the derivative would end up having a wrong sign. Maybe there's something I've overlooked in the implementation, but for now the presented interpolation method seems to me, to be fundamentally wrong.

[mohrcore]

@fire I'm not familiar with the whole glTF stuff, but it seems weird to me that with cubic interpolation the cube on gif stops overy 90 degrees.

[GNSS-Stylist]

This may be related to the wobbly/"wrong way around" interpolation of Quat when using cubic_slerp I stumbled upon as seen in this video:
https://youtu.be/6T5wmcpTBtk
The "triangle" and the camera as childs of the same spatial-node are using slerp. The car, using the same source values, is first using cubic_slerp and later slerp_ni (which also seems to sometimes interpolate "wrong way around", although this might be a feature(?)).

Code for this test can be found from:
https://github.com/GNSS-Stylist/LOSolverDemo_Godot/tree/godot_quat_interpolation_issue
Interpolation is implemented in file LOScriptReplayer.gd. When using cubic_slerp, this is used:
quat = quat_a.cubic_slerp(quat_b, quat_pre_a, quat_post_b, fraction)
where quat_b, quat_pre_a, quat_post_b, fraction are the ones seen as text on the video and the result (quat) is labeled "interp" there.

What I expected was cubic_slerp to smoothen out those slight discontinuities in direction seen in slowed-down camera movement when piecewise (slerp) linear interpolation switches between "pieces", something like the SQUAD here:
https://www.gamasutra.com/blogs/VegardMyklebust/20150911/253461/Spherical_Spline_Quaternions_For_Dummies.php

"Disclaimer": I'm not very familiar with quaternions (just used them first time here, because I needed some kind of interpolation of orientations), so there might be false assumptions etc. in the text above.

(Edit: Apparently github was smart/intrusive enough to already dig the reference from my recent commit...)

Godot version: 3.2.2.stable
OS: Windows 10

[fire]

I implemented https://math.stackexchange.com/questions/2650188/super-confused-by-squad-algorithm-for-quaternion-interpolation 's SQUAD but still testing cubic interpolation algorithm, had some bugs. Will report back with a branch and maybe a pr.

[fire]

Is this the proper solution for the opening reproduction project?

[mohrcore]

I've seen that math exchange post as I was searching for quat interpolation algorithms and I thought that the issue described there looked suspiciously similar to what I've been experiencing with Godot. I'm still confused by the whole concept of helper quaternions and unsure where they exactly fit into the whole thing as well how they are actually calculated.

The behaviour on the gif looks like what I would expect SQUAD to behave like.

Also, as a side note I find it weird and misguiding to call SQUAD cubic_slerp. cubic_slerp is an oxymoron itself, but it being actually a quadratic interpolation makes it kinda hilarious.

[fire]

I submitted a pull request. #41626

Edited:

If I remove the initial wobbly, the math breaks the interpolation demos from GLTF2.

[GNSS-Stylist]

Tried the fix with my "flying car demo": https://youtu.be/ZhJpJgQBAsU
"Wrong way around"-turns seem to be less frequent/severe in this (than in https://youtu.be/6T5wmcpTBtk ), but they still happen now and then. Wobbliness is gone, but this seems to follow slerp (see "diff (selected-slerp)") when not "glitching", instead of SQUAD/cubic-slerp(?).

[fire]

Can you make a flying demo for me to test with? Not sure if it's open source.

[GNSS-Stylist]

It can be found here: https://github.com/GNSS-Stylist/LOSolverDemo_Godot/tree/godot_quat_interpolation_issue
License for the code is MIT, 3D-models are CC-BY (not mine, I just used them).

[fire]

I don't see a test case that uses cubic_slerp?

[GNSS-Stylist]

You can change interpolation method of the car by changing "LOSolver_TimeShift"'s "Quat Interpolation Method". Quats used in the interpolation are printed in lower left corner. See my post above for some more info.

[fire]

Added a clamp function, and testing the change on cubic_slerp.

Edited: Interested in http://www.cemyuksel.com/research/interpolating_splines/ but one step after the other. Get this quat patch complete first.

[GNSS-Stylist]

There seem to be discontinuities when using the latest commit ( 5c6e45e ) in some cases, see https://youtu.be/61QawNpJeOA
Made some modifications to my demo (see previous messages) to better see these issues.

Some instructions can be found from readme.md, few most relevant in this context /changed (changed also some namings (hopefully better) and other stuff from the previous version):

• You can change interpolation method using "LOSolver_Interpolated->Quat interpolation method" and replay speed with "Main->Replay speed" (as shown in Godot's editor).
• F3-key changes camera to one looking at the X-axis basis vector, F4 to one more zoomed-in.
• Using "camera rig camera" (=F2) doesn't make sense here, since origins for both the object and camera are the same.
• Committed version skips 3/4 of the lines (="keyframes") of the source files to make interpolation issues more visible. You can change this using "readLineSkip" in LOScriptReplayer.gd.
• Press R to get rid of the traces (and restart).
• Location/orientation scripts (*.LOScript-files) consist of "keyframes" with a steady 125 ms interval, but since in the committed version 3/4 of these are skipped, they are effectively 0.5 s apart.
• Do not change "timeshift" nor activate "Visibility script". These don't make sense with this.

Sorry for this late reply, I didn't have time/energy to build anything usable before.

[fire]

If you're interested there's a survey of orientation interpolation methods at http://www.adrian-haarbach.de/interpolation-methods. The most interesting are listed below:

RQBez: The curve looks very similar to SQUAD, but is actually a uniform cu-bic Bezier curve of the quaternion coeffi-cients ∈ R4 with subsequent renormaliza-tion. The segments are joined withC2con-tinuity requirements, thus we have global control.

CuBsp: ThisC2curve is the uniform cumulative cubic B-spline onSU(2), in-troduced by [21] and used in [22, 27]. The angular velocity graph shows that this curve minimizes angular accelerations. Ithas local control, but the inner keyframes are only approximated.

They also have an executable demo with runtime costs.

[fire]

godot_animation_bug.zip

Update bug project for latest master.

[GNSS-Stylist]

Investigated this further (in godot 4) as I'm planning to use this for camera track with sparsely placed keys. Have to admit that I'm still "super confused" (as someone else in the stackexchange-link above)... But after days of mostly trials and errors managed to get somewhat smooth-looking movements out.
Video taken from the godot editor:

2022-01-24.22-02-23.mp4

Red cube and axes show slerped rotations for comparison, blue cube shows the next key, green cube cubic_slerped rotations.

There are 4 identical keys between 20...26 s. Cubic_slerped object actually first rotates a bit over the "rest-position" there before settling and takes identical "step back" before going on. Not sure if this is how squad should work(?) However calculation of those helper quaternions uses quaternion log-function that has a division with the length of the vector part of the quaternion (that becomes zero when some of the subsequent source quaternions are identical) so I wrote some code to handle these cases. Anyone know how helper "tangent" quaternions are supposed to be calculated when some rotations are identical?

Here's another video from a running project:

2022-01-24.18-05-02.mp4

Bottom part has the same objects as the previous video, on top there's objects following the same rotations as my previous videos/godot projects (red = slerped, green = cubic_slerped, yellow lines connecting the points used for interpolation).

Godot project (Godot 4):
Quat_cubic_slerp_issue_single.zip
You can fly around by first pressing CTRL and WASD-QE-keys/mouse wheel. Switch to 6DOF-mode (roll = R/F-keys) with TAB. "Playback speed" can be changed using number keys (7 = normal speed, 6 = half, 5 = quarter, 8 = double etc), for rewind keep SHIFT-pressed. Backspace resets playback.

Quaternion.c&h (Godot 4) sources:
quaternion_modified_src.zip
I also tried code from the mentioned PR #53692, but there was some problem with it (which, still being super confused I don't remember any more). Wrote some functions as statics to keep my confusion at more tolerable level (it was easier to clone/compare some calculations from the source documents when using static functions).

Not sure if this is the way this is supposed to work. There are also some limits and such in the source files that are just thrown there and "seemed to work" so this is definitely not "release ready" code. But feel free to utilize these if you find them helpful.

Edit:
Forgot to mention that I also removed some is_normalized()-checks from quaternion.cpp because they were triggered now and then most probably due to rounding errors accumulating. Returned quaternion is now normalized as a last step. Source (document) used for some operations: https://users.aalto.fi/~ssarkka/pub/quat.pdf

[fire]

I'll investigate your notes over this week and the next.

[fire]

Discussed with @TokageItLab .

We discussed modified akima may be able to solve this. Tokage posted some plots of modified akima. The main part is the graphs and not the text.

When I last talked to @reduz about this issue, he mentioned it was ok to replace the current cubic with makima or at least trial a proposal/pr for it.

[TokageItLab]

Above images are quoted from:

(c) sikino(2020)

• https://slpr.sakura.ne.jp/qp/akima-interpolation/
  • https://slpr.sakura.ne.jp/qp/wp-content/uploads/2020/11/Akima_eye_c-1038x519.jpg

(c) 1994-2022 The MathWorks

• https://jp.mathworks.com/help/matlab/ref/makima.html
  • https://jp.mathworks.com/help/matlab/ref/datainterpolationcomparisonexample_01_ja_JP.png
  • https://jp.mathworks.com/help/matlab/ref/datainterpolationcomparisonexample_02_ja_JP.png

[GNSS-Stylist]

You mean using (modified) akima directly for quaternion's component (i, j, k, w-values) and normalize afterwards?

Have to admit that I had doubts if this kind of interpolation would work nicely (still being confused). To see the differences I made a modification to the code that returns component-wise interpolated (lerp) and normalized quaternion from cubic_slerp-function. This is how it looks like with almost the same data as before (there are some keys added to the end of the animation, though):

2022-01-26.12-08-46.mp4

As the differences are so small I moved the slerped and (now)lerped version on top of each other and re-colored the traces of lerp to yellow. AnimationPlayer-version on the left.

Difference doesn't actually look too bad. Lerp moves faster at the start and end of the interpolated range (as expected), but at least with these rotations the effect isn't so big. However it can be seen on the colored cubes quite easily. On the more densely keyed version on the right it's actually hard to even distinguish them.

Would be nice if users could choose between interpolation modes. I have no idea how/if this could be done, though.

Stumbled upon quite thorough discussion about very similar issues on blender forum:
https://devtalk.blender.org/t/quaternion-interpolation/15883/9

Modified Godot-project:
Quat_cubic_slerp_issue_single_Ver2.zip

Modified quaternion-sources (cubic_slerp = lerp):
quaternion_modified_Ver2.zip

[TokageItLab]

The implementation that directly interpolate each element and does the normalization is probably wrong. I guess we need to adopt the difference and norm of the two quaternions into the modified akima formula.

[GNSS-Stylist]

While twiddling with this I decided to test also component-wise interpolation with standard cubic-interpolation. Here's the result:

2022-01-28.22-07-26.mp4

To the eye looks to be quite close to squad.

Code (not pretty, just a quick hack to test this):

static real_t cubic_interpolate_real(const real_t p_pre_a, const real_t p_a, const real_t p_b, const real_t p_post_b, real_t p_c) {
	// This is cloned straight from animation.cpp

	real_t p0 = p_pre_a;
	real_t p1 = p_a;
	real_t p2 = p_b;
	real_t p3 = p_post_b;

	real_t t = p_c;
	real_t t2 = t * t;
	real_t t3 = t2 * t;

	return 0.5f *
		((p1 * 2.0f) +
			(-p0 + p2) * t +
			(2.0f * p0 - 5.0f * p1 + 4 * p2 - p3) * t2 +
			(-p0 + 3.0f * p1 - 3.0f * p2 + p3) * t3);
}

static Quaternion flip_to_shortest(const Quaternion& compared, const Quaternion& flip) {
	if (compared.dot(flip) < 0.0) {
		// Return flipped
		return Quaternion(-flip.x, -flip.y, -flip.z, -flip.w);
	}
	else {
		// No flipping necessary
		return flip;
	}
}

Quaternion Quaternion::static_cubic_slerp(const Quaternion& p_q0, const Quaternion& p_q1, const Quaternion& p_q2, const Quaternion& p_q3, const real_t& p_t) {
	if (true) {
		// Flip quaternions to shortest path if necessary (p_q1 used as a reference)
		Quaternion q0 = flip_to_shortest(p_q1, p_q0);
		Quaternion q1 = p_q1;
		Quaternion q2 = flip_to_shortest(p_q1, p_q2);
		Quaternion q3 = flip_to_shortest(q2, p_q3);	// Need to compare with possibly already flipped q2

		return Quaternion(
			cubic_interpolate_real(q0.x, q1.x, q2.x, q3.x, p_t),
			cubic_interpolate_real(q0.y, q1.y, q2.y, q3.y, p_t),
			cubic_interpolate_real(q0.z, q1.z, q2.z, q3.z, p_t),
			cubic_interpolate_real(q0.w,_q1.w, q2.w, q3.w, p_t)
		);
	}

	if (false) {
		// Test code to compare slerp and lerp
		// (just return lerp)
		// (This was active in the previous example)
		return static_lerp(p_q1, p_q2, p_t);
	}

Personally I will probably stick to this for now (as it is good enough for my use case) but will still keep my eyes open for other methods. Modified akima looks quite nice indeed.

Edit: Added flipping of quaternions when needed (previous version interpolated long way around now and then).

[fire]

Headsup, I moved your project into a github git repo, I want to try the modified akima interpolation.

I added labels.

Reference

https://github.com/fire/godot-40592

[fire]

@GNSS-Stylist I wish to use this an a benchmark for Godot Engine for 1) testing slerping vs cubic slerping 2) cubic slerping 1000 transforms for networking replication.

What are your thoughts? To do that a license compatible or exactly the same as the Godot Engine MIT license is required.

[TokageItLab]

In my opinion, this issue seems to be confusing two issues.

1. cubic_slerp() may take a rotation path that is not the shortest
2. cubic_slerp() and cubic_interportion() cause overshoot

I'm not sure about issue 1, as I haven't tested it properly, but if it's true about issue 1, I think we should close this issue and repost the these issues since these problems have different fundamental causes.

[GNSS-Stylist]

Made a pull request with added LICENSE-file (MIT) for @fire 's repo: fire-archive/godot-40592#1. Added Jon Ring (@jonri) and Roujel Williams (@SIsilicon) to the "copyright-list" also, since the first person controller was created and modified by them. Personally I don't really care much about the copyright here, but can't decide on behalf of others.

Have to agree with @TokageItLab that this issue got somewhat bloated over time.

[SIsilicon]

Why am I here?

[GNSS-Stylist]

@SIsilicon The first person controller used in the repo above was originally written by you ( https://github.com/SIsilicon/Godot-Ocean-Demo ) so the "copyright-list" entry also made it way here.

[SIsilicon]

The first person controller isn't mine actually. If you look in the credits section of my project you'll see I got it from a tutorial by Jeremy Bullock, almost line for line. So if anything, you should credit him.

[TokageItLab]

Superseded by #57951 and #57952.

[fire]

Reopened because we posted a new attempt at fixing this.

#63380