# Interpolating several rotations

## Recommended Posts

B_old    689
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 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 on other sites
B_old    689
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 on other sites
jyk    2094
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 on other sites
Emergent    982
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 on other sites
B_old    689
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 on other sites
Einar89    144
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, its 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 on other sites
Emergent    982
Quote:
 Original post by B_oldSpecifically 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 on other sites
Dave Eberly    1173
Quote:
 Original post by B_oldI 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 on other sites
ddlox    168
I think Einar89 was on the right path :-)

I would do in pseudo (unoptimised):

resulting_rot = 0for (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 on other sites
Emergent    982
Quote:
 Original post by Dave EberlyFor 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 on other sites
B_old    689
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.)