Using Quaternions?

Interpolation is used as an animation technique, where particular transformations are defined at sample times, and the actually used transformations at frame times inbetween are computed from the temporarily surrounding samples.

Rotations can be interpolated if given in matrix form, however, it has some drawbacks: It suffers from gimbal lock, numerical stability, is mathematically expensive (in comparison to other representations) and it may look unnatural.

Quaternions (to be precise: _unit quaternions_) are another representation for rotations. They allow a mathematically less complex interpolation, provide less numerical problems, and yield in smoother and hence more natural looking in-betweens. Key words a slerp ("spherical linear interpolation") between 2 surrounding samples, and squad ("spherical cubic interpolation") between 4 surrounding samples (similar to cubic splines).

However, since (unit) quaternions are good for rotations only, the entire transformation has to be divided up in their respective parts (translation, rotation, and, if used, others). But that has to be done for interpolation anyway. To compose (and last to apply it to points and vectors) the resulting transformation one than has to convert the quaternion to an equivalent rotation matrix. But the computational overhead is neglectible. (If you want to see comparisons and computational efforts, look at e.g. Eberly's www.geometrictools.com/Documentation/RotationIssues.pdf).

he's right. but more generally, an interpolation is a way to get from one thing to another, or to blend between two things. for example, linear interpolation between two points is the line connecting the points. cubic interpolation between two points is a curve of degree 3. interpolation from the color black to the color white goes smoothly from black to grey to white. since a quaternion represents an orientation(rotation), interpolation between two quaternions goes from one to the other smoothly. it takes the shortest path in "orientation space"(just made that word up) that is to say, it travels the through the shortest number of orientations from one rotation to another, further it does it in a smooth fassion.

Tim

Yes, timw said it: interpolation for itself is more generally useable as for transformations alone.

The stuff itself is something interesting, and describing it in all its aspects is more complex. E.g. a linear interpolation represented by a polynomial of degree 1 considers 2 sample points, a quadratic interpolation 3 samples, a cubic interpolation 4, and so on. However, the line, quadratic, cubic, or what ever need not be defined in the domain one expects, namely onto a plane in 3D (since we are looking at 3D gfx here).

The slerp/squad operations are done on a surface of a sphere (that is why they are named "spherical ..."). This is necessary since for a smooth rotation interpolation one does not want to interpolate _positions_ but _angles_. This is one cause why slerp interpolation looks more smooth than its real linear counterpart (the "lerp" interpolation).

Unfortunately, since slerp operates on a sphere, and quaternions need 4 co-ordinates to work, the aforementioned sphere is actually a hyper-sphere. Hence there are two unit quaternions possible for the same orientation in 3D: q and -q. So there are 2 possible arcs from which one has to be selected; since although irrelevant for an orientation, the two possibilities are not the same for interpolation. One can choose the shorter or the longer arc. Normally the shorter arc is preferred.

Quote:

Original post by haegarr Rotations can be interpolated if given in matrix form, however, it has some drawbacks: It suffers from gimbal lock, numerical stability, is mathematically expensive (in comparison to other representations) and it may look unnatural.

This is not generally true. It is perfectly possible to formulate slerp in matrix form that when applied as a transformation is exactly the same as the quaternion formation, and can be implemented much cheaper than conversion to quaternion, slerping, and conversion back (assuming your native representation is matrix, not quaternion).

Having said that, if one is just looking for code/algorithm to slerp, you're much more likely to find it implemented in terms of quaternions than matrices (because (a) they're trendy and (b) they're more useful in heirachical systems where you spend more time applying transformations to transformations than to vectors....)

@MrRowl: Yes, it is possible to do slerp in matrix representation, and I said it already in my original posting.

However, the matrix representation of rotation uses 9 scalars in a 3x3 orthogonal matrix form, while the quaternion uses 4 scalars. The computational effort at least comes into play if after some calculation steps the rotation numbers becomes to come incorrect due to numerical issues. As the internet mentions this happens earlier to matrices than to quaternions. Moreover, to normalize the matrix one has to do things like Gram-Schmitt orthogonalization, and that are definitely costs higher than those of normalizing quaternions.

And sure, I assumed that the samples are already given in quaternion, saving the costs for matrix->quat conversion. It is also true that applying a quaternion to a vector is more costly than applying a matrix. That is why I've said that conversion costs quat->matrix are to be considered. However, if the count of vectors is high enough the conversion costs are neglectible.

In fact, what representation to use is a decision each programmer has to made itself. But I would not say I use it because "they are trendy". _IMO_, in an overall view (e.g. memory footprint especially for particles, FK due to scene graph, IK, physics, interpolation) the quaternions are superior, although they inject some kind of inhomogenity (w.r.t other affine transformations, which are all expressed by matrices directly).

For a small simple app it doesn't play such a role. However, LeChuckIsBack wanted to know about quaternion and interpolation. I mean we've given him something to think about ;-)

[Edited by - haegarr on October 21, 2005 5:06:04 AM]

Useful paper here

It's actually quite practical :) Also, it talks about incremental interpolation (i.e. your 10 steps), which will probably have a different optimal solution than just a single one-off interpolation.

When interpolating a transformation containing translation and rotation just separate out the two parts and interpolate them separately.

For interpolating rotation: Have you yet decided whether to use matrices or quaternions? The load of theory was though of giving you a decision help ;-)

For interploating translation: Also here you first have to decide "how smooth" your interpolation should look like. The fastest, simplest, and unpleasing way is straight linear interpolation (it is unpleasing since it will show sudden movement changes at the sample points). So normally one uses a degree 3 polynonial to compute the blending factors for 4 samples. However, even than you have to decide the method how to compute them: By Bezier-Spline, NURBS, ...

Of course, I can write down general formulas here. It _is_ inherently complex if I explain this stuff for general cases, so I think if you don't want to read all this theoretical stuff you have to decide first what you want.

[EDIT: Ah, MrRowl has found a suitable paper. I think that is the best way ...]