Sign in to follow this  
B_old

Interpolating several rotations

Recommended Posts

Hi, (not really sure if this is the right section in the forum, but I thought it might be related.) I want to interpolate between several rotations and am looking for a good way to do this. I don't remember why, but matrices seem to be an unpopular choice. I have used a slerp() function on 2 quaternions before and that works good. Can this be extended to interpolating several quaternions? What would happen if I just sum up n yaw, pitch, roll angles and divide by n?

Share this post


Link to post
Share on other sites
I had a similar problem recently.

I opted to do a weighted blend of pairs of matrices to create a final result.
to decide the weights of the intermediate matrices (A and B in my diagram below) I just use the sum of the weights of the matrices that made it. and for the blend at each step I calculate the normalised weights of the two matrices involved.

So if I have matrices M1,M2,M3 and M4, with the weights 0.1,0.2,0.3 and 0.4 respectively I do the following



RESULT TOTAL WEIGHTS NORMALISED WEIGHTS
/ \ / \ / \
M1 A 0.1 0.9 0.1 0.9
/ \ / \ / \
M2 B 0.2 0.7 0.223 0.777
/ \ / \ / \
M3 M4 0.3 0.4 0.429 0.571







hope this helps.

Share this post


Link to post
Share on other sites
Aha, I assume this would work for quaternions as well. This could indeed be helpful.
Just curios if there is another way to interpolate between n quaternions.

Share this post


Link to post
Share on other sites
Another way to interpolate between two quaternions in a sequence of quaternions is to use SQUAD.

SQUAD isn't quite as well documented as SLERP, generally speaking, but you should be able to find some info on the algorithm via Google. I don't know how helpful it'll be, but here is the first hit from Google - the SQUAD function is described about halfway down the page.

Share this post


Link to post
Share on other sites
When you say,

Quote:
What would happen if I just sum up n yaw, pitch, roll angles and divide by n?


it sounds like you are more interested in averaging than in interpolation. What are you actually trying to achieve?

Your use of the word "interpolation" also bothers me here because, inherently, interpolation is between values of the domain AND the range of some function which we assume gives rise to the sample values -- and you haven't made clear what the elements of the domain are. Let me be more specific: Interpolation works on a set of pairs, {(x1, y2), (x2, y2), ..., (xn, yn)}, where each pair (x,y) contains an element x of the domain and an element y of the range. Now, for you I understand that your "y" values are rotations, "elements of SO(3)" in fancy-speak. What what are your "x" values? These, I should add, might be vectors themselves; e.g., a grayscale image would have 2-dimensional vectors as the "x" values and real numbers for the "y" values.

I hope this doesn't come across as pointless nitpicking. It's just that, as phrased, what the problem is exactly is not clear to me.

Cheers.

Share this post


Link to post
Share on other sites
jyk: Hm, does squad also interpolate 2 quaternions? I didn't understood how that helps with several quaternions.

Emergent: You are right, the example was bad. Maybe if I multiply each yaw, pitch, roll with a weight and divide by the sum of weights? Because I certainly don't want the average.

Specifically I have a fixed number of rotations. I also have an equal number of 3d Points, that are associated with the rotations. Now I take a random point x and measure the distance to the other points. The closer x is to a certain point the more influence the associated rotation should have. The resulting rotation is what I am looking for.
It imagine it like morphing between several targets. It is easy for 2 rotations. (In fact I'm also morphing color but I was under the impression that this is as easy as I wrote above.)

Share this post


Link to post
Share on other sites
You could use SLERP, but then the result would be order dependent. I thin normalized LERP(good old linear interpolation) would work better, and as a bonus, it`s faster. Suppose you have n points affecting your rotation, then t1..tn would be your weights(ti = (1-di/d)/(n-1), I think, where di is the distance between the points, and d is the sum of these distances). Your resulting rotation would be Normalize(SUM(ti*qi)),where qi is the coresponding quaternion. Hope I got it right.
EDIT: the problem with what I wrote is that if your point is exactly over a reference point, you still get influence from other reference points(hope this makes sense). You have to find a better expression for ti.

Share this post


Link to post
Share on other sites
Quote:
Original post by B_old
Specifically I have a fixed number of rotations. I also have an equal number of 3d Points, that are associated with the rotations. Now I take a random point x and measure the distance to the other points. The closer x is to a certain point the more influence the associated rotation should have. The resulting rotation is what I am looking for.


Ah, ok; got it. Thanks for clarifying. The domain is R^3; the range is SO(3). Gotcha. Is there any structure to the (x,y,z) points in the domain? Are they arranged in a regular grid? Are they arbitrary?

Share this post


Link to post
Share on other sites
Quote:
Original post by B_old
I have used a slerp() function on 2 quaternions before and that works good. Can this be extended to interpolating several quaternions?


For 3 points, the idea would be to use barycentric coordinates to define a weighted average of those points. Unfortunately, this idea does not work for quaternions in a natural way. To visualize, imagine a spherical triangle whose vertices are the "quaternions". How do you choose a set of weights for the vertices to obtain a specified point in the spherical triangle?

To see how folks generalize the concept, do a Google search on "spherical barycentric coordinates".

Share this post


Link to post
Share on other sites
I think Einar89 was on the right path :-)

I would do in pseudo (unoptimised):


resulting_rot = 0
for (all refpoints)
{
ti = 0
nqi = 0
distance_i = refpoint_i - your_random_point
if (distance_i <= 0 (or epsilon))
{
// use this ref point's rot only
resulting_rot = refpoint_i.qi;
break;
}
ti = 1 / distance_i
nqi = normalise(ti * qi)
resulting_rot = normalise(resulting_rot + nqi)
}




As you know distance_i will always be positive so you have to decide a range or an epsilon to resolve points proximity otherwise the condition if distance_i <= 0 will not always hit. I'm sure you know it ;-)

Share this post


Link to post
Share on other sites
Quote:
Original post by Dave Eberly
For 3 points, the idea would be to use barycentric coordinates to define a weighted average of those points. Unfortunately, this idea does not work for quaternions in a natural way. To visualize, imagine a spherical triangle whose vertices are the "quaternions". How do you choose a set of weights for the vertices to obtain a specified point in the spherical triangle?

To see how folks generalize the concept, do a Google search on "spherical barycentric coordinates".


This would be very useful if we could do it for four points, since then we could interpolate inside a tetrahedron, and do simplicial interpolation using a Delaunay tetrahedralization (for scattered data) or Kuhn tetrahedralization (for data on a grid).

This is sort of a direction I wanted to go in with this, but I'm not sure how... Any thoughts?

The other direction to go in, especially if we're on a grid, would be to use n-"linear" interpolation with SLERP, as Einar89 suggested. The order-dependence bothers me though; I feel like the "right" answer should be unique.

Share this post


Link to post
Share on other sites
Thanks for all the answers!
Actually the points mark the corners of a quad on the x-z-plane, a fifth point is directly in the middle of the quad. So in that sense they could be considered as 2D. But as I want to use the distance I don't know if it matters. The rotations are 3D.

Here is a video of what I mean. (With only 3 "control-points" that lie on a line, so I actually only interpolate between the closest 2 at any given time.)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this