Original Post
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;
}
|
