Archived

This topic is now archived and is closed to further replies.

executor_2k2

Can someone explain linear interpolation with quaternions?

Recommended Posts

Ok, unless I''m wrong ...


Quaternion Q1(w1,x1,y1,z1); // norm(Q1) == 1
Quaternion Q2(w2,x2,y2,z2); // norm(Q2) == 1

double t;
for( t = 0; t < 1; t += 0.01 )
{
Quaternion Q(Q1.w*(1-t)+Q2.w*t,
Q1.x*(1-t)+Q2.x*t,
Q1.y*(1-t)+Q2.y*t,
Q1.z*(1-t)+Q2.z*t);
// Q = Q1*(1-t) + Q2*t;

Q.Normalize();

// do whatever with Q
}


If Q1 and Q2 were used to store the original and final orientations of an object, then Q will represent a smooth rotation from Q1 to Q2.

Share this post


Link to post
Share on other sites
There''s a problems with that code: it will not always generate the most efficient/shortest interpolation. E.g. the quaternions

{ cos( 5), sin( 5), 0, 0} &
{-cos(10), -sin(10), 0, 0}

represent rotations through 10 and 20 degrees about the x axis. But interpoating using the given code will rotate through almost 360 degrees.

The problem arises because

{-cos(10), -sin(10), 0, 0} &
{ cos(10), sin(10), 0, 0}


represent the same rotation, but when doing interpolation they are in different places in the space used for interpolation, and produce different results.

The solution it to check how far apart the quaternions are, and if necessary flip one so they are closer. E.g. add the lines.


if (Q1.w * Q2.w + Q1.x * Q2.x + Q1.y * Q2.y + Q1.z * Q2.z < 0)
{
Q2.w = -Q2.w;
Q2.x = -Q2.x;
Q2.y = -Q2.y;
Q2.z = -Q2.z;
}




before the for loop.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Fruny has it right... although as johnb points out, you want to make sure that the quaternions point into the same direction first.

I have a very detailed explanation of why linear interpolation works well for quaternions in the March 2002 issue of Game Developer magazine (should be on shelves now). If you don''t have it or can''t get it, I can send you a copy of the article, but the printed magazine is more nicely typeset and stuff. And it''s a good magazine (especially the March issue).

The basic idea is that, hey look, slerp just walks along a great circle of this hypersphere, and it''s pretty slow. Well linear interpolation walks us along a chord instead. If we then normalize, our chord gets stretched back out to the surface of the sphere; so we''re going along exactly the same path as slerp, we''re just doing it with more computational efficiency. (There is one other gotcha, which is that we''re no longer moving along that path at constant speed. For relatively small quaternion angles, this is not noticable. For big angles, you can fix it pretty cheaply).

Then, once you write a fast vector normalizer that doesn''t do a divide and square root, you can basically interpolate quaternions really, really hyper fast.

I wrote a sample app that does quaternion linear interpolation, as well as some more involved versions that correct for the time-distortion induced by linear interpolation, but are still faster than slerp. You can download this from the gdmag web site: go to

http://www.gdmag.com/code.htm

and get mar02.zip.

-Jonathan.

Share this post


Link to post
Share on other sites
He uses a linear approximation for 1/sqrt(x). It''s good if x is around 1. Check his sources... :

inline float isqrt_approx_in_neighborhood(float s) {
const float NEIGHBORHOOD = 0.959066;
const float SCALE = 1.000311;
const float ADDITIVE_CONSTANT = SCALE / sqrt(NEIGHBORHOOD);
const float FACTOR = SCALE * (-0.5 / (NEIGHBORHOOD * sqrt(NEIGHBORHOOD)));

return ADDITIVE_CONSTANT + (s - NEIGHBORHOOD) * FACTOR;
}

/Ksero

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Yes, there is a linear approximation to sqrt... however that one function that Ksero posted is only good for about 35 degrees of quaternion arc, and you want to be able to go all the way out to 90. So I have a wrapper function that applies that linear approximation up to 3 times, as necessary.

The key thing to realize is that because you''re cutting inside the unit sphere always, the length of your vector is going to be <= 1. And since the quaternions will be no more than 90 degrees apart, the length will be >= sqrt(.5). So in order to normalize, you only need a function that works well on lengths between sqrt(.5) and 1. This is a lot easier than trying to tackle the fast normalization problem for arbitrary length vectors.

(The magic funny numbers in the linear approximation, as well as the function that calls it, were concocted using some energy minimization stuff I wrote).

-Jonathan.

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
Yes, there is a linear approximation to sqrt... however that one function that Ksero posted is only good for about 35 degrees of quaternion arc, and you want to be able to go all the way out to 90. So I have a wrapper function that applies that linear approximation up to 3 times, as necessary.


That''s what I get for not checking it out properly ... Sorry

/Ksero

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Heh well... it''s not actually improper to only use the normalizer once. It depends on what your app is like. You want to pick the fastest thing for what you need.

Like if you''re doing this skeletal animation system, and you''ve got animation data for all these joint orientations at 30Hz, and you just want to interpolate between them so that the animation is smooth if your game''s frame rate is like 200fps... well... because the quaternions are already sampled at 30Hz, they''re going to be really close together, so you can use the cheapest approximation and things will work fine.

But if you need to accurately track more extreme changes, you want to be more careful about the interpolation. I wanted to mention that so people didn''t get the wrong idea that the technique doesn''t work for big quaternion differences.

Anyway, the source code compares 4 different techniques and compares the resulting error: slerp, lerp (without normalization), fast-normalized lerp, and fast-normalized lerp with counter-warping. Which one of these you''d use depends on what you really need. But even the most heavyweight one (fast-normalized lerp with counter-warping) is still a huge amount faster than slerp.

-Jonathan.

Share this post


Link to post
Share on other sites