Sign in to follow this  
LeChuckIsBack

Using Quaternions?

Recommended Posts

This is from DirectX Help:
Quote:
Using quaternion interpolation, an application can calculate a smooth and reasonable path from one axis and orientation to another. Therefore, interpolation between q1 and q2 provides a simple way to animate from one orientation to another. When you use composition and interpolation together, they provide you with a simple way to manipulate a geometry in a manner that appears complex. For example, imagine that you have a geometry that you want to rotate to a given orientation. You know that you want to rotate it r2 degrees around axis2, then rotate it r1 degrees around axis1, but you don't know the final quaternion. By using composition, you could combine the two rotations on the geometry to get a single quaternion that is the result. Then, you could interpolate from the original to the composed quaternion to achieve a smooth transition from one to the other.
I worked a lot with matrix compositions, but what is that interpolation stuff? (I'm no ace in math...) How exactly can I achieve that smooth transition (e.g. very useful in moving a ship). Can somebody give me an example? Please don't send me to read some math book :)

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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....)

Share this post


Link to post
Share on other sites
@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]

Share this post


Link to post
Share on other sites
Hey, thanks for the theory! - you kind of overloaded me :O

But could you please give me a practical example? Let's say I have a starting matrix A and an ending matrix B. How can I smoothly rotate from A to B in, let's say, 10 steps (for example, if I have to rotate slow and nice a turret toward its target)?

// let's suppose rotation it's done in origin:
|a b c 0| |k l m 0|
A = |d e f 0| to B = |n o p 0|
|g h i 0| |q r s 0|
|0 0 0 1| |0 0 0 1|
//
// and what if the objects need also to translate (like a
// airplane doing some acrobatic things)?
|a b c 0| |k l m 0|
A = |d e f 0| to B = |n o p 0|
|g h i 0| |q r s 0|
|x y z 1| |X Y Z 1|
// where x,y,z != X,Y,Z, ofcourse

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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 ...]

Share this post


Link to post
Share on other sites
Well, since DirectX is based on matrices, I will have to choose them... I've printed MrRowl's useful paper and I think that the matrix multiplication is the best solution:

// a few initializations at start - very unexpensive
M1 = quattomat(q1);
Ma = quattomat(q1 * cos(kt) plus qo * sin(kt));
M = inv(M1) * Ma;
Q = M1;

// and the big cycle - in fact, i will not use that Q = Q * M in a FOR sequence,
// but once per frame. So I will get:
// number_of_objects_to_animate * just_a_matrix_multiplication / frame
// which i think is almost perfect :)

for n = 2 : k plus 1
Q = Q * M;
end


Do you think I could get better then that?
(sorry about the "plus" thing, don't remeber how to display it in HTML...)

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