Jump to content

  • Log In with Google      Sign In   
  • Create Account


Why Diana Gruber's wrong about Quats


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
164 replies to this topic

#1 Shaterri   Members   -  Reputation: 122

Like
Likes
Like

Posted 12 September 2000 - 05:46 AM

Diana Gruber has written a very interesting article about Quaternions for the Gamedev site; if you haven''t read it yet, you can find it here. It''s certainly worth reading as one person''s perspective on the issue. Unfortunately, I also find it to be inaccurate (or at least misrepresentative) on several counts. Mrs. Gruber is welcome to her own opinions on whether quaternions are worthwhile for her own programming efforts, but at the same time obviously a lot of people _have_ implemented quaternion-based rotations for their graphics and physics engines, and physicists (not just mathematicians) have been actively using them since Hamilton discovered them (as the most convenient representation of the double cover of SO(3) by S^3, to put it in the most technical terms) so I think there''s at least some empirical evidence that they _do_ indeed do something ''that couldn''t be done more easily using more traditional mathematics'', to use her phrase. But she''s also wrong about some of the specifics; here''s why I think so. Firstly, Mrs. Gruber compares building a rotation from a quaternion to building a rotation from a rotation angle and an axis; I won''t reproduce the formulas but you can get them from her article. Her implication is that building from a rotation angle is easier, but let''s count. Computing the matrix from a quaternion involves 10 multiplications: squaring each of w, x, y, and z, and computing the product of each of these with the others (w*x, w*y, w*z, x*y, x*z, and y*z). And of course, w^2 + x^2 + y^2 + z^2 (the term she puts into the lower right corner) is just 1, which implies that one of the squarings can be eliminated and brings us down to 9 multiplies. The fastest way I can find to compute all the products needed to build the rotation matrix from angle/axis takes 10 multiplies: s*x, s*y, s*z, t*x, t*y, and then tx*x, tx*y, tx*z, ty*y, ty*z, and finally tz^2 can be computed as t-tx^2-ty^2 without any additional multiplications. She also fails to mention that if you use the axis-angle representation then you have to compute the cosine and sine of your angle of rotation, and those will far and away dominate the costs of multiplication. Secondly, while examining the cost of building a rotation (matrix) initially, she completely ignores the cost of composing rotations. Two quaternions can be multiplied straightforwardly with twelve multiplies and a handful of additions, and it''s possible to multiply two quaternions using just 8 multiplies (this is a classical result, but I don''t have a good reference and my own code doesn''t use it; can anyone else provide a pointer?). The standard way of multiplying two 3x3 rotation matrices takes 27 multiplies and it''s possible to show that two 3x3 matrices can''t be multiplied with fewer than 17 multiplications. If composition of rotations is a major part of your application (for, e.g., a kinematics system), then this can be a fairly substantial improvement. She talks about the benefits of quaternions (stability and unit length) being ''obviously present in the rotation matrix (since they are the same matrix).'' But a quaternion is _not_ a matrix, and it''s not an axis-and-angle pair either. All three of these are ways of representing a rotation (that is, an element of SO(3)) -- but they''re different representations. The fact that it''s possible to convert from the quaternion representation to a matrix representation does not mean that the representations are equivalent in terms of stability, any more that it means they''re equivalent in terms of mathematical costs (as we saw above). I''m not going to suggest that quaternions are more stable than a rotation matrix, but I _will_ say that they''re easier to stabilize. Consider, again, a kinematics animation system. Let''s say your object is rotating with nonconstant velocity, so that you have to multiply by an instantaneous rotation matrix every frame. Eventually floating-point roundoff will make the aggregate rotation non-orthogonal, whatever representation you use (i.e., it won''t be an exact representation of a rotation any more). This usually leads to shearing, stretching, or compression of the transformed object. In the case of a quaternion representation of rotations it''s easy to re-orthogonalize your rotation; all that''s involved is a normalization of your quaternion, just as you''d normalize a vector. But the process of ensuring that a rotation matrix is orthogonal and of re-orthogonalizing it is substantially more complex. Mrs. Gruber also goes on to dismiss the issue of Slerps, mentioning mostly the ''alternative method'', and tries to scare off the reader by talking about ''logarithms, exponents, the fourth dimension...'' -- but of course, that''s not how anyone actually _implements_ it. The primary use for the exponential interpretation of quaternion slerps is for dynamics, again; if you need to know the angular velocity along, say, a spline rotation curve then it''s possible to compute it by taking the derivative of the quaternion ''position'' formula (but I won''t go into the details of this, because it _is_ a fairly involved process and I don''t want everyone''s eyes glazing over). As far as actual implementation of slerps -- well, here''s a direct paste of the source code from my quaternion engine:
    
// Slerp interpolates between two unit quaternions, maintaining ''uniticity''.
Quaternion Slerp(Quaternion Q0, Quaternion Q1, float T) {
  float CosTheta = Q0.DotProd(Q1);
  float Theta = acosf(CosTheta);
  float SinTheta = sqrtf(1.0f-CosTheta*CosTheta);
  
  float Sin_T_Theta = sinf(T*Theta)/SinTheta;
  float Sin_OneMinusT_Theta = sinf((1.0f-T)*Theta)/SinTheta;

  Quaternion Result = Q0*Sin_OneMinusT_Theta;
  Result += (Q1*Sin_T_Theta);

  return Result;
}
    
Now, certainly cosines (and inverse cosines) and square roots are a little bit scary, but they''re hardly _that_ frightening. I don''t think you''re likely to find many graphics programmers who can''t make sense of the code above. She asks ''Can''t we find a simpler way to interpolate between vectors in R3?'' and goes on to demonstrate an easy answer to her question. The problem is, interpolating between two vectors with a rotation is _NOT_ the same as interpolating between two rotations! For instance, if a camera is rotating it has not only a lookat vector but also an up vector (in effect, a twist angle) and Mrs. Gruber''s method of rotating between two vectors doesn''t deal with this issue at all. One might think that if you had two rotations in axis-angle form -- (v1, theta1) and (v2, theta2) -- then the two could be interpolated by using her formulas to interpolate v1 and v2 and then simply taking theta as (1-t)*theta1+t*theta2. The problem with this formula is that it''s not mathematically accurate (the rotation is at inconstant speed and isn''t geodesic), which makes the motion of tumbling objects look wrong in an animation. The only accurate way of interpolating between two rotations is with a slerp, and the easiest way of representing a slerp is between two quaternions. I''m sorry that Mrs. Gruber doesn''t seem understand the various benefits that using quaternions really _can_ offer and sorry that she''s so active in crusading against them; while they''re certainly not necessary for every project I hope this post makes it a little more clear why one would want to use them and why (to answer the title of her article) ''Yes, some of us really do need quaternions''.

Sponsor:

#2 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

Likes

Posted 12 September 2000 - 06:53 AM

The contents and proofs in Mrs Grubers Article are valid, but she forgets one thing - ''Gimbal Lock''. This alone is something well worth using Quaternions to get around.

I really don''t see the point in writing an article so large when I can tell her in one paragraph why a Quaternion should be used, and I haven''t even bothered to outline the many other benefits (there are tons of stuff posted on this topic).

If people have been asking for Quarternions support in her fastgraph library then maybe there is good reason for it. is anyone actually using fastgraph for a full commercial game project though? To define commercial, I don''t want follow ups telling me someone is selling a poker game. What about some serious games?


#3 Shaterri   Members   -  Reputation: 122

Like
Likes
Like

Posted 12 September 2000 - 07:49 AM

Actually, the issue of Gimbal lock is only relevant to the question of ''quaternions vs. Euler angles'', and in Mrs. Gruber''s defense she never once mentions Euler angles in her article. Euler angles are yet another representation of the rotation group (one I forgot to mention), and they _do_ suffer from the problem of Gimbal lock just as the anonymous poster said, but neither the axis-angle and rotation matrix representations that she offers nor quaternions suffer from it. They''re an excellent reason to use quaternions over Euler angles but they don''t actually address the issue in Mrs. Gruber''s article (or my reply) of quaternions vs. rotation matrices.


#4 baskuenen   Members   -  Reputation: 122

Like
Likes
Like

Posted 12 September 2000 - 08:40 AM

Another thread here on gamedev: Quaternions - Why use them?



#5 dgruber   Members   -  Reputation: 133

Like
Likes
Like

Posted 12 September 2000 - 11:43 AM

Shaterri,

Identify yourself further, please.

Your message is long, and I don''t want to address all your points at once. So don''t think I am ignoring details. I''ll get to them, eventually.

Let''s start with paragraph 2. The terms w,x,y,z. What are those exactly? Unless I am mistaken, they are shorthand symbols that represent quaternion elements. The usual representation for a rotation quaternion is q=cos(a)+u*sin(a) where a is the rotation angle divided by 2, and u(x'',y'',z'') is the unit vector representing the axis of rotation.

So your elements actually look something like this:

w = cos(theta/2)
x = x'' sin(theta/2)
y = y'' sin(theta/2)
z = z'' sin(theta/2)

It seems to me you have left a few sines, cosines, divides and multiplies out of your operation count.

More later...

Diana


#6 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

Likes

Posted 12 September 2000 - 12:33 PM

Check out Real Time Rendering (ISBN 1-56881-101-2) page 47, where you will find a formula for conversion from a unit quaternion to an orthogonal matrix involving no trigonometric functions.




#7 CodeDemon   Members   -  Reputation: 363

Like
Likes
Like

Posted 12 September 2000 - 12:47 PM

I don''t mean to intrude or anything, but I guess what would decide the final straw in terms of what is most efficient, would be to profile both well written quaternion and well written matrix code, for equivalant operations, and compare the results.

One thing quaternions might be better choice for is sending arbitrary orientations (and not just around a single axis), over a network. Their smaller size could make a difference when a signifcant number of objects need to be kept track of, especially when squeezing stuff through a 56K modem. To go off on a slight tangent, you could lose some precision, and convert the floating point values of the quaternion to a signed 16-bit 0:15 fixed point representation (they''re normalized values, same as an 3x3 axial frame without scaling information). I digress... anyway, this would be more ideal than sending a 3x3 axial frame (the upper 3x3 sub-matrix).

One thing a matrix suffers from that a quaternion does not, is that over time, if you concatenate various orientations together into one matrix, is that the values degrade due to loss in floating point precision. This is known as de-orthonormalization. In otherwords, the axes aren''t quite perpindicular to each other. You can perform an orthonormalization operation on the matrix to line-up the axes again, but it''s an operation that can be advoided. When an axial frame is generated from a quaternion, the axes are orthonormal. Of course, this problem is rarely encountered because most programmers generally regenerate the rotation matrix each frame, and there''s no noticable entropy.

Diana, you''ve got some good points though. Most programmers treat quaternion math as a black box, hell, I do. Vector and affine space transformations are a ton more intuitive to understand, and easily implemented. Adding quaternions to your code base means another data construct, and more coding... and a less stream-lined pipeline. Maybe in the end, it''ll just boil down to preference, who knows.

Just some thoughts to add to the discussion. Cheers!

- Jesse Towner

#8 Shaterri   Members   -  Reputation: 122

Like
Likes
Like

Posted 12 September 2000 - 12:48 PM

Sorry for not identifying myself previously. My name''s Steven Stadnicki (scruff@halcyon.com) and I should note that I''m not currently in the game development industry, although I have been in the past; currently I''m working at a media processor company doing graphics driver and windowing system API work. I have about 10 years of professional 3d graphics and games programming experience under my belt, though, and another 4-5 years of hobbyist study of the subject before that, so I''m not exactly a babe in the woods either.

I''m going to focus on the meat of the reply here:

quote:

The terms w,x,y,z. What are those exactly? Unless I am mistaken, they are shorthand symbols that represent quaternion elements. The usual representation for a rotation quaternion is q=cos(a)+u*sin(a) where a is the rotation angle divided by 2, and u(x'',y'',z'') is the unit vector representing the axis of rotation.



Actually, you''re mistaken. Mathematically speaking, a quaternion is simply a pair of four numbers [w, x, y, z] that represent a point in R^4, along with a special element [1, 0, 0, 0] that acts as the identity quaternion, certain set of rules that tell you how you multiply two of these things to get another one, and another set of rules telling how you can find the inverse element for any given element (which is to say, they form a group). Computer graphics (and by and large, physics) is interested in the subgroup of unit quaternions, that is, the ones for which w^2+x^2+y^2+z^2 = 1; that''s because this subgroup (you can convince yourself that multiplying two unit quaternions leads to another unit quaternion if you try hard enough, so it _is_ a subgroup) corresponds to the set of all possible rotations in three-space (aside from the minor detail that q and -q represent the same rotation).

The ''representation'' you defined is actually a mapping; it''s how you get from one representation of this rotation group (by axis and angle) to another (by quaternions). Certainly if your initial data consists of an axis and a rotation angle then you have to do a little bit of trigonometry to convert it to quaternion representation. But if your data isn''t in that form then it''s quite possible to use quaternions without ever having to keep any data in axis-angle formula. I''ve got an application that does exactly this; it simulates a randomly tumbling object by slerping between randomly generated rotations. Note that this involves more than just spinning the object around one axis, then spinning it around another one, then... etc etc; the object legitimately tumbles, twisting around several axes at the same time as it interpolates orientations. This is an effect that''s difficult to get (accurately) with axis/angle representation, nearly impossible to get with rotation matrices as the ''base'' representation, and easy to get with quaternions.


#9 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

Likes

Posted 12 September 2000 - 01:02 PM

This is the anonymous poster who initially refered to ''gimbal lock''.

Whoever shot me down is quite right about the gimbal lock with reference to Euler angles, and in fact I should have pointed out that I was talking about the programming of character animation and implicitly refering to the various methods involved.

Yes, while Mrs Grubers article does not mention Euler angles, the title of her article does question the use of quarternions and that is what I meant to answer.

So...use them for character animation and save yourself a lot of time, after all why would you use anything else? Have you ever tried fitting 1000s of frames of rotational animation into a PS?




#10 CodeDemon   Members   -  Reputation: 363

Like
Likes
Like

Posted 12 September 2000 - 01:11 PM

Anonymous:

Yeah, it would appear their smaller size has many advantages, from optimizing how much data is sent over a network, to conserving memory (especially on systems where this is a commodity) and diskspace.

- Jesse Towner

#11 voodoo   Members   -  Reputation: 122

Like
Likes
Like

Posted 12 September 2000 - 04:39 PM

BAH! You guys just love to throw around all these fancy terms!



#12 GKW   Members   -  Reputation: 200

Like
Likes
Like

Posted 12 September 2000 - 05:00 PM

I have had two years of college calculus and quats still seem beyond me. The author never mentions gimble lock but every article out there say use quats to avoid gimble lock, not use quats because they are better than eulers. I think this is the flawed point of the article. Both have there uses, get over it.

I wanrned you! Didn't I warn you?! That colored chalk was forged by Lucifer himself!

#13 Michael Tanczos   Senior Staff   -  Reputation: 5183

Like
Likes
Like

Posted 12 September 2000 - 05:24 PM

Perhaps you should have considered how one would feel if confronted with the blanket statement that they were outright wrong. If I were Diana I would be on the defensive now, perhaps it would have been better to show some additional considerations as to the benefits of quaternions. This is counterproductive to the learning experience IMO.

If I could be so bold, I would say that us programmers are driven a lot by ego, so when we see something technical we don''t agree with our natural instinct is to crush it into the ground. "Oh man, what the hell was he thinking when he wrote this? He should have done this!" (Don''t deny it, we''ve all done it)

Yup, we''re a simple folk, driven by ego.. so be kind. Umm, remember the golden rule? If you wrote an article that had a flaw, would you prefer a personal email from someone explaining the problems with it or an embarrassing statement posted on several USENET newsgroups that you''d have to defend to safe face? =)

You always have the opportunity to write an article entitled, "Why Quaternions are Good."

Play nice!

Take care.

---
Michael Tanczos


#14 Shaterri   Members   -  Reputation: 122

Like
Likes
Like

Posted 12 September 2000 - 06:11 PM

(Reply, this time around, actually E-mailed to Michael. :-)

#15 Shaterri   Members   -  Reputation: 122

Like
Likes
Like

Posted 12 September 2000 - 06:32 PM

While I''m at it, I''d also like to take the opportunity to apologize to Mrs. Gruber for the tone of my article and the more personal attacks against her. As I said, I really have no objections to her personal decision not to use quaternions and should have restricted my reply to her article strictly to technical issues (where I still, obviously, feel that the article was in error and where I feel quaternions have many benefits). My apologies for anything that''s gone outside the bounds of technical matters, however.


#16 mossmoss   Members   -  Reputation: 326

Like
Likes
Like

Posted 13 September 2000 - 01:54 AM

I have to agree with Shaterri. I am currently a professional game developer revising our quaternion/vector-based character animation system.

I never deal with sine or cosine. Operations on quaternions are fairly simple and relatively efficient. (I may not have the most efficient implementation, but it's decent enough.)

There's the issue of gimbal lock, although since the artists I work with usually stay away from Euler controllers, it's not usually a problem.

However, another important issue is the interpolation. It's much easier to interpolate between two quaternions rather than between two matrices -- a lot less work. And if you're interpolating between Eulers, it's much less painful. There are exactly two slerps between any two quats (ie, the short and long routes around a hypersphere); there are many paths between two Eulers.

Storage is a final issue... If you've got a lot of animation data, quaternions are compact storage for an orientation, especially with quantization (we did well on one project putting a single quat into a 32-bit word). Only Euler angle is smaller, but they have many more problems. And not everyone works on Windoze desktops with tons of memory....


---- --- -- -
Blue programmer needs food badly. Blue programmer is about to die!

Edited by - mossmoss on September 13, 2000 8:55:17 AM

#17 dgruber   Members   -  Reputation: 133

Like
Likes
Like

Posted 13 September 2000 - 03:23 AM

Stephen,

Apology accepted and thank you for not calling me Mrs. Gruber any more.

Your code snippet is interesting, but it is taken out of context. It doesn''t say much about what comes before and after. For example, building a transform and applying it to 10,000 vertices is a different issue than building a 10,000 transforms. Also, if you have to convert your quaternion to a matrix anyway (to be compatible with DirectX or OpenGL, for example, or to incorporate translation information), does the work of the conversion offset the savings in the interpolation?

(Side note: I''m sure we could get Kevin Hawkins to sponser some kind of contest here on gamedev.net, but let''s wait a bit before we launch into that. To properly design a benchmark, we need to better define what conditions apply to the rotation).

> For instance, if a camera is rotating it has not only a
> lookat vector but also an up vector (in effect, a twist
> angle) and Mrs. Gruber''s method of rotating between two
> vectors doesn''t deal with this issue at all.

It was not presented as a final solution, just as an illustration of an interpolation. Interesting how you mention camera rotation here, (as in, inadequate for) and then jump to tumbling objects. Most games have only one camera position per frame, but may have multiple rotating objects. You don''t use the same rotation strategy for each. Random with respect to tumbling objects is more acceptable than random with respect to the camera, for example, and the camera transform changes only once per frame, but you may have many tumbling objects. (Although you probably don''t.) So while you need an Up vector for the camera position, you probably don''t need it for tumbling rocks.

> The only accurate way of interpolating between two rotations
> is with a slerp, and the easiest way of representing a
> slerp is between two quaternions.

Are you saying there is no accurate way to represent a slerp with vectors? I don''t think that''s what you''re saying. I think you are saying there probably is an accurate way to do it with vectors, but it is more work than the quaternion method. But how do we know that is true? Quaternions have so dominated the research, has anyone even bothered to try to come up with a vector solution, and then optimize it?

Seeing the one-to-one correspondence between the matrices composed of quaternions and vectors, it seems to me there must be a correspondence between other operations too. After all, vectors evolved from quaternions, and became popular because they were shown to greatly reduce the work done by quaternions.

There is a need for much more research in this area. I don''t pretend to have done all the work that needs to be done. In fact, I did relatively little. The intention of my article was to stimulate others to look into it further. Somebody should get out the works of Gibbs, et al, and study the old arguments. It would make a nice graduate research project.

Another thought on tumbling rocks, could there be an even easier way that doesn''t involve quaternions or vectors? A look-up table, perhaps? Not adequate for a camera orientation of course, but if you are writing asteroids, for example, with many tumbling rocks, you could eliminate rotation calculations altogether and just move on some random path through a series of preset rotations. In which case both vectors and quaternions would be overkill.

Diana


#18 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

Likes

Posted 13 September 2000 - 04:09 AM

Michael Tanczos:

I think there are two reasons why the initial reactions to this article were so strong.
First, the tone in the article wasn''t very nice. Diana implies that ''Academic types'' use quaternions just because they''re conceptually harder to understand and because you can use a lot of fancy words while writing about them. It''s pretty naive to think that the only reason why people use quaternions is that they''re dificult to understand. People studying mathmatics or computer science, usually have some sort of common sense and wouldn''t just choose one approach over another because it sounds cleverer....
The second reason is a lot simpler, she obviously doesn''t have clue about what quaternions are good for . . . the part concerning slerp is totally off, as pointed out by other posts.

What i wanted to say was, i don''t think Shaterri should apologize for his post, that article was a punch in the face to a lot of us.... when you''ve spend time studying quaternions (and finally understod them), it doesn''t feel nice being written off as an idiot ...

Just for the record my name is John, I study computer science and mathmatics at the university of Copenhagen.

#19 dgruber   Members   -  Reputation: 133

Like
Likes
Like

Posted 13 September 2000 - 04:41 AM

This is to MossMoss who has never used sine or cosine in his quaternion operations. In fact, most rotation matrices are built without using trig functions either. An example is here: http://msdn.microsoft.com/library/psdk/directx/imover_884k.htm
although I don''t really like the way Microsoft does it because I think taking the sqrt is unecessary for comparisons, and you can save time by using a fixed World Up vector. The World Up vector is merely a frame of reference, coplaner with two of the rotated axes. It hardly ever needs to be changed, so why pass an Up vector every single time the function is called? Things like that make vector operations look inefficient, but in reality it is Microsoft that is being inefficient.

To all the people who have emailed me saying that quaternions save time because you can pass less data across the network... what makes you think vectors require more data than quaternions? Describing a rotation requires a fixed, minimal amount of information, no matter how you represent it. Vectors don''t require more information than quaternions. The difference is in the operations, not in the data.

The problem of re-orthogonalizing matrices has been exaggerated. Run tests. I did. The set of special orthogonal matrices is a closed set. The floating point precision on a pentium is very high, round-off errors are trivial and tend to balance out. Take 10,000 random orthogonal matrices, multiply them together, and the result will be an orthogonal matrix. Try it.

Diana


#20 firahs   GDNet+   -  Reputation: 288

Like
Likes
Like

Posted 13 September 2000 - 06:52 AM

Well, i read the article. And here is probably the best way i can summerize my impression of it.

Lets call Matricies a car, and Quaternions a bicycle.

Lets say we have to travel this arbitrary path, we don't know the properties of the path.

Diana's article is basically saying, "ooh take the car, its better" And some people are saying "No, take the bike, its better"

But what we all have to realize, is that the path can either be wide enough to accomodate a car, or too narrow, making the bicycle a better means of transportation.

So, in conclusion: Each method has its own pro's and con's. Just dismissing one without looking at what the path will accomodate.

Im not going to call anything that diana had in her article _wrong_ per se. But she is guilty of misrepresenting a few things.






Edited by - firahs on September 13, 2000 2:05:20 PM




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS