For some reason, I've been thinking about quaternion interpolation and the different types: slerp, nlerp, exp-map, modified nlerp.
I know Casey used to be an expert at this (probably still is) and says to just use nlerp (normalized linear interpolation) for quaternions rather than the "proper" slerp (spherical linear interpolation) if that much accuracy is not needed.
I was wondering if anyone uses a modified nlerp instead to be a middle ground between nlerp and slerp? And by that, I mean change the parameter of t depending on the input.
The problem with nlerp and quaternions is that quaternions actually lie on the surface on the 4d 3-sphere with a radius of the magnitude of the quaternion. This means that the "true" path is along a geodesic on the surface of the 3-sphere meaning that its path is actually longer than tunnelling to the next point. Thus, as the interpolation parameter, t, varies, the velocity of the transform is not constant. To lessen this, you can change how t varies with respect to the two input quaternions.
By expanding the equations for geometric interpolation, the modified version of t is shown to be:
t' ≈ t + θ^2 / 6 (-2t^3 + 3t^2 - t) + O(θ^4)
This a very good approximation to what is actually needed however, it does require knowing the angle between the two quaternions, θ, beforehand. One of the advantages of not using slerp is to avoid/minimize using any operations other than basic floating point ops (e.g. not using sqrt, cos, arccos, sin, etc.).
Luckily, cosθ is very easy to calculate as it the inner/dot product of the two quaternions cosθ = dot(q_0, q_1). Using this, and the approximation of cosθ ≈ 1 - 0.5θ^2, the new modified parameter is as follows:
t' ≈ t + (1 - cosθ) / 3 (-2t^3 + 3t^2 - t) = t + (1 - q_0.q_1) / 3 (-2t^3 + 3t^2 - t).
This approximate is not as good as the previous approximation but it now removes the need for any trigonometric functions (and is still pretty close)!
The higher order terms of the Taylor series cannot be used, O(θ^4), as they _require_ the use of either sqrt or trigonometric functions and defeating the point of this approximation. And the θ^4 term is extremely small too (1/360).
This approximation does have the advantage that at t={0, 0.5, 1}, the values are identical to that of slerp and nlerp.
I was wondering if anyone uses something like this or if it is even used at all or even needed?
Regards,
Bill
I know Casey used to be an expert at this (probably still is) and says to just use nlerp (normalized linear interpolation) for quaternions rather than the "proper" slerp (spherical linear interpolation) if that much accuracy is not needed.
I was wondering if anyone uses a modified nlerp instead to be a middle ground between nlerp and slerp? And by that, I mean change the parameter of t depending on the input.
1 2 3 4 5 6 7 8 9 10 11 | Quat nlerp(Quat a, Quat b, float t)
{
Quat r = a*t + b*(1.0f - t); // (or a + (b-a)*t)
return r;
}
Quat mod_nlerp(Quat a, Quat b, float t)
{
float new_t = some_func(a, b, t);
return nlerp(a, b, new_t);
}
|
The problem with nlerp and quaternions is that quaternions actually lie on the surface on the 4d 3-sphere with a radius of the magnitude of the quaternion. This means that the "true" path is along a geodesic on the surface of the 3-sphere meaning that its path is actually longer than tunnelling to the next point. Thus, as the interpolation parameter, t, varies, the velocity of the transform is not constant. To lessen this, you can change how t varies with respect to the two input quaternions.
By expanding the equations for geometric interpolation, the modified version of t is shown to be:
t' ≈ t + θ^2 / 6 (-2t^3 + 3t^2 - t) + O(θ^4)
This a very good approximation to what is actually needed however, it does require knowing the angle between the two quaternions, θ, beforehand. One of the advantages of not using slerp is to avoid/minimize using any operations other than basic floating point ops (e.g. not using sqrt, cos, arccos, sin, etc.).
Luckily, cosθ is very easy to calculate as it the inner/dot product of the two quaternions cosθ = dot(q_0, q_1). Using this, and the approximation of cosθ ≈ 1 - 0.5θ^2, the new modified parameter is as follows:
t' ≈ t + (1 - cosθ) / 3 (-2t^3 + 3t^2 - t) = t + (1 - q_0.q_1) / 3 (-2t^3 + 3t^2 - t).
This approximate is not as good as the previous approximation but it now removes the need for any trigonometric functions (and is still pretty close)!
The higher order terms of the Taylor series cannot be used, O(θ^4), as they _require_ the use of either sqrt or trigonometric functions and defeating the point of this approximation. And the θ^4 term is extremely small too (1/360).
This approximation does have the advantage that at t={0, 0.5, 1}, the values are identical to that of slerp and nlerp.
I was wondering if anyone uses something like this or if it is even used at all or even needed?
Regards,
Bill
I'm not sure this is all that useful?
The reason nlerp is Good Enough is that the error decreases the closer together the two rotations are. So you can usually make it more accurate by just increasing the number of keyframes in your animation (or whatever series of rotations you're computing).
Throwing a slightly-more-accurate approximation at that is not really worth the extra computation, I don't think. So long as your keyframes are close together, you're not actually winning much. If you care about the accuracy enough to spend more work on it, adjust your data or go all the way and use slerp. Trig isn't *that* expensive any more.
The reason nlerp is Good Enough is that the error decreases the closer together the two rotations are. So you can usually make it more accurate by just increasing the number of keyframes in your animation (or whatever series of rotations you're computing).
Throwing a slightly-more-accurate approximation at that is not really worth the extra computation, I don't think. So long as your keyframes are close together, you're not actually winning much. If you care about the accuracy enough to spend more work on it, adjust your data or go all the way and use slerp. Trig isn't *that* expensive any more.
inverse square root is cheap enough to use IMO for something like this. The "fast" variant uses 3 fmul, a fsub (or maybe twice that if you use the second iteration of newton's method) and some integer math.
Using that you can simply do a binary search.
I picked 5 as the iteration count because that gets any angle between quaternions down until the cos of the resulting angle is within 98% of 1
Using that you can simply do a binary search.
1 2 3 4 5 6 7 8 9 10 11 | for(int i = 0; i<5;i++){
Quat r = nlerp(a, b, 0.5); //normalizes using a inv sqrt
if(t> 0.5){
a = r;
t = t*2 - 1;
} else {
b = r;
t = t*2;
}
}
Quat r = nlerp(a, b, 0.5);
|
I picked 5 as the iteration count because that gets any angle between quaternions down until the cos of the resulting angle is within 98% of 1
Edited by ratchetfreak
on
Again, computers are that fast nowadays that trig functions are probably not even a problem any more so use slerp for everything!
This is was just something I was thinking of on the drive home and wasn't really caring if it was _really_ useful. Using closer keyframes would allow for reduce the need for this and nlerp can be used but, this method would even reduce the need for a true slerp as this is _always_ at least 2 times more accurate than nlerp for large angles (from testing mathematically and with a program).
@ratchetfreak This method slightly overestimates the true value while mine underestimates. Also this requires the use of a loop and an if as its a Newton-Raphson method. Again it's just different and I will probably have to measure the difference accurately.
This is was just something I was thinking of on the drive home and wasn't really caring if it was _really_ useful. Using closer keyframes would allow for reduce the need for this and nlerp can be used but, this method would even reduce the need for a true slerp as this is _always_ at least 2 times more accurate than nlerp for large angles (from testing mathematically and with a program).
@ratchetfreak This method slightly overestimates the true value while mine underestimates. Also this requires the use of a loop and an if as its a Newton-Raphson method. Again it's just different and I will probably have to measure the difference accurately.
You can unroll that loop and use masks for the if test.
I gather that but I what I was trying to imply is that it requires more operations.
Depending on how close the angle is on the initial quats in the keyframes and how much of an error you are willing to allow you can reduce the number of iterations.
Usually the reason that you don't use slerp isn't because it's slow, but because it can't handle more than two quaternions. In the old days, the slowness of slerp was _also_ a concern, but obviously that wouldn't be true today I shouldn't think.
Given how fast computers have gotten compared to when I was working with quaternions (15+ years ago!), I would also say that some of the more expensive n-way blends that we didn't use at the time due to performance concerns would also be feasible today if for some reason you had a case where the linear bias was problematic.
- Casey
Given how fast computers have gotten compared to when I was working with quaternions (15+ years ago!), I would also say that some of the more expensive n-way blends that we didn't use at the time due to performance concerns would also be feasible today if for some reason you had a case where the linear bias was problematic.
- Casey
Thank you everyone for your replies.
This was just a thought experiment on the drive home. I did notice that every series term was just another hermite interpolation polynomial but that's not surprising as the quaternions are related to SU(2) and SO(3) group which are useful for spherical harmonics (they can be derived from quaternions) and thus you get hermite polynomials from them.
This was just a thought experiment on the drive home. I did notice that every series term was just another hermite interpolation polynomial but that's not surprising as the quaternions are related to SU(2) and SO(3) group which are useful for spherical harmonics (they can be derived from quaternions) and thus you get hermite polynomials from them.