This has been, without question, the most controversial article we've ever posted, as evidenced by [url="http://www.gamedev.net/community/forums/topic.asp?topic_id=25314"]this thread[/url], among others. Although Mrs. Gruber is certainly entitled to her opinion about the usefulness of quaternions, and although we will continue to provide developers with an outlet to express their opinions, we've come to feel that this article contains misinformation (as many have pointed out) that could prove to be confusing and misleading to the many beginners who turn to us as a source of information. Therefore, we've decided to remove this from our article indicies. The article itself (the page you are viewing) will remain to prevent broken links, and so that people can see what the hubbub was all about. If you choose to read on, be sure to read the thread above as well.[/i]

[size="5"][b]Part I: Equivalence[/b][/size]

Recently some of my [url="http://www.fastgraph.com"]Fastgraph[/url] customers requested quaternion support for 3D rotations in Fastgraph. I researched the matter and I was surprised by what I found. There seems to be a bit of a quaternion mania going on. Quaternions are documented extensively in books, articles, and on the internet. Programmers are using them to write games. But are they really a useful tool for 3D graphics programming? It seems to me, they are not.

Quaternions are a mathematical oddity. They involve imaginary numbers and a 4th dimension. They have a unique algebra, with the multiplication operations being particularly unwieldy. Using rules such as [b]ij=k[/b], [b]ji=-k[/b] and [b]i[sup]2[/sup] = -1[/b], it is possible to build a function set that will rotate points in a 3D space. Quaternions work. They do the job they are asked to do. But are they doing anything that couldn't be done more easily using more traditional mathematics? I don't think so.

Here is a common matrix representation of quaternion rotation. A variation (with rows transposed) can be found at the [url="http://www.gamasutra.com/features/programming/19980703/quaternions_07.htm"]Gamasutra[/url] web site. This one is nicely derived at [url="http://http.cs.berkeley.edu/%7Elaura/cs184/quat/quaternion.html"]http://http.cs.berkeley.edu/~laura/cs184/quat/quaternion.html[/url].

[attachment=3177:image002.gif]

where

[attachment=3178:image004.gif]

and (x,y,z) is a unit vector on the axis of rotation and [attachment=3179:image006.gif] is the angle of rotation.

Here is a standard matrix representation of rotation around an arbitrary axis. I found this in Graphics Gems (Glassner, Academic Press, 1990).

[attachment=3180:image008.gif]

where

[attachment=3181:image010.gif]

and (x,y,z) is a unit vector on the axis of rotation and [attachment=3179:image006.gif] is the angle of rotation.

The first matrix was derived using quaternions. The second matrix was derived using standard geometry and algebra in the Euclidean 3-space, R[sup]3[/sup] (see Part II of this document for the derivation). I propose to show that these matrices are exactly the same. This can be done using proof by exhaustive enumeration.

I will use the following trigonometric identities:

[attachment=3182:image013.gif]

and from the definition of quaternions:

[attachment=3183:image015.gif]

To prove the matrices are not only equivalent but identical, I will compare one element at a time. I will start with the upper left corner.

[attachment=3184:image017.gif]

Which verifies that the first term of each matrix matches. The second term is compared in the same manner:

[attachment=3185:image019.gif]

Exhaustive enumeration requires I show the equivalence of all 16 elements. I will leave the other 14 elements as an exercise for the reader. Or you can just believe me. All 16 matrix terms can be compared and found to be exactly equivalent.

The "benefits" of using quaternions (unit length, stability, etc.) are obviously present in the rotation matrix (since they are the same matrix). The operation count is better with the rotation matrix. The quaternion operation uses this:

[attachment=3186:image021.gif]

which involves a sine, a divide and 2 multiplies. The rotation formula uses the equivalent

[attachment=3187:image023.gif]

which requires only a cosine and a subtraction.

Considering the simplicity of the matrix based on Euclidean geometry and the complexity of the matrix based on quaternion algebra, and considering that both matrices require identical inputs, and generate identical outputs, and considering the overall usefulness of the rotation matrix for such things as relative motion and rendering optimizations, I propose using Euclidean geometry exclusively in 3D graphics programming. Quaternions should be relegated to their proper place in mathematics: an interesting phenomenon, useful in an academic sense to demonstrate the properties of set theory and abstract algebra, but not a proper tool for software engineers. As my 8th grade math teacher Mr. Brown would have said, using quaternions to solve a rotation is like going around the block to get next door.

[size="5"][b]Part II: Deriving the Rotation Matrix Around an Arbitrary Axis in R[sup]3[/sup][/b][/size]

The rotation matrix R is so intrinsically useful, it is worth taking the time to look at the derivation. I will borrow the diagram from Eric Weisstein's World of Mathematics, which credits it to Goldstein, 1980. See [url="http://mathworld.wolfram.com/RotationFormula.html"]http://mathworld.wol...ionFormula.html[/url].

[center] [attachment=3188:image025.gif]

[/center]

[attachment=3189:image027.gif]

[attachment=3190:image029.gif]

[attachment=3191:image031.gif]

[attachment=3192:image033.gif]

[attachment=3193:image035.gif]

= rR

Where r is the original point in vector format, r' is the rotated vector, (x,y,z) is a unit vector on the axis of rotation, and [attachment=3194:image037.gif] is the angle of rotation.

The equation r'=rR is particularly useful in 3D graphics programming because of the information you can glean from the rotation matrix R. The last row of R is the [b]Out[/b] vector, a unit vector pointing in the direction of the view. With this information, you can construct a transform for forward motion. You can also eliminate points behind the camera. You can also do relative rotations without changing the properties of the rotation matrix, because the set of special orthogonal matrices is closed under multiplication. See my paper, [i]Mathematical Properties of the 3D Rotation Matrix[/i], to be delivered at [url="http://www.xgames3d.com/xgdcmain.htm"]XGDC[/url], October 1, 2000, for further explanation and proofs.

[size="5"][b]Part III: Spherical Linear Interpolations (SLERPS)[/b][/size]

Perhaps the best argument for the use of quaternions is the smooth interpolation between two points on a curve. A quaternion formula for slerps was given by Ken Shoemake in 1985 ([i]Animating Rotation with Quaternion Curves[/i], Computer Graphics, Vol 19 No 3, pp. 245-254). An alternate method involves taking the derivative of a quaternion (which is a logarithm), interpolating, and performing a quaternion exponential on the result.

Does that work? Yes, of course. Is it the best way to do it? You tell me. Calculus on imaginary numbers, logarithms, exponents, the fourth dimension... it hardly sounds efficient. Can't we find simpler way to interpolate between vectors in R[sup]3[/sup]?

[size="3"][b]What is a vector interpolation?[/b][/size]

Suppose you have two vectors, P[sub]1[/sub] and P[sub]2[/sub], and a rotation angle between them, [attachment=3179:image006.gif]. Your goal is to rotate from P[sub]1[/sub] to P[sub]2[/sub], but not immediately. You want to take the shortest path between the two vectors, over a period of time, or a number of steps. The path is an arc traced by the vector P. What you are looking for is a function f(t') where t' is the "time" parameter expressed as a fraction of the rotation between P[sub]1[/sub] and P[sub]2[/sub].

[center][attachment=3195:image040.gif]

P = f(t'), [attachment=3196:image042.gif][/center]

Note I am using t' as the time parameter so as not to confuse it with t in the rotation matrix R defined above.

To rotate by angle [attachment=3179:image006.gif], or any part of angle [attachment=3179:image006.gif], you need an axis to rotate around. It is easy to find. Just normalize the vectors P[sub]1[/sub] and P[sub]2[/sub] and take their cross product. The result will be a unit vector perpendicular to both.

[center] [attachment=3197:image046.gif]

[attachment=3198:image048.gif]

[/center]

You can then plug (x,y,z) and t' [attachment=3179:image006.gif] into the rotation matrix R above, and the result will be a perfect interpolation.

[center][attachment=3199:image051.gif][/center]

You can confirm P = P[sub]1[/sub] when t' = 0 and P = P[sub]2[/sub] when t' = 1.

[size="5"][b]Conclusion: Why is Anybody Using Quaternions Anyway?[/b][/size]

Believe it or not, the quaternion vs. vector debate goes back more than 100 years. Quaternions were developed by William Rowan Hamilton around 1843 and immediately took their place in mathematical history as a solution in search of a problem. In 1901, just two years before his death, a Yale professor named Josiah Willard Gibbs published a treatise on vector algebra which included a definition of the vector dot product and vector cross product. Vector algebra was put forth as a simple, robust alternative to quaternions. Egos erupted, tempers flared, and the debate raged. Gibbs' vectors were championed posthumously by his colleague, Edwin B. Wilson, along with Oliver Heaviside in England. Quaternions were defended by Peter Guthrie Tait, but it was a losing battle. Vector algebra triumphed over its non-Euclidean predecessor, and the popularity of quaternions faded.

So why has the debate been re-ignited at the beginning of the 21st century?

Software engineers, in general, are not mathematicians. They can code an algorithm, but they rely upon others for a rigorous proof of an algorithm's suitability for a task. In this case, quaternions have been shown to effectively solve problems of 3D rotation and interpolation. But why has nobody looked beyond quaternions for a simpler solution until now? Perhaps they have, and we just haven't heard from them.

Quaternions lend themselves well to graduate projects and technical theses. They are very complicated, so describing them (and defending them) can take many words and many pages of formulas. Vectors, by comparison, are straightforward to the point of being boring. There is not much new to say about vector operations in R[sup]3[/sup].

Quaternions are a popular buzzword. They sound "cool". And their intrinsic difficulty is appealing. Only the most focused, deep-thinking programmers are able to understand and use them. But that is not enough to ensure that they are the right tool for the job. Sometimes it takes an open mind to look beyond the hype and consider the mathematical alternatives. As Mr. Brown would have admonished, you are not seeing the forest for the trees.

If you are considering using quaternions in a 3D graphics programming project, take some time to compare quaternion operations to their vector counterparts. You may find, as did Gibbs, Wilson and Heaviside, that quaternions are not the panacea some would have you believe.

[size="5"][b]Frequently Asked Questions and Frequently Stated Comments regarding Diana's quaternion article.[/b][/size]

Diana is tired of responding the same questions and comments over and over and so has prepared this canned response. If your question/comment about quaternions is not answered here, then don't worry about it. It probably isn't very important anyway.

[b] 1. Quaternions are necessary because without them your program will suffer from gimbal lock.[/b]

A. Nonsense. Gimbal lock is only an issue if you use Euler angles.

[b] 2. Quaternions use less data than vector rotations.[/b]

A. In my article, I expressed rotations in an axis/angle format. Four floats. In case you missed it, I also showed how to convert between quaternion and axis/angle rotations.

[b] 3. Quaternion operations are faster because they can be done using fewer operations.[/b]

A. Disregarding my informal proof that the minimum operation count will be exactly the same, don't forget to consider the operation count in converting quaternions to a matrix format in order to make them compatible with DirectX or OpenGL, or to add translation information, for example.

[b] 4. Quaternion operations don't require trig, vector operations do.[/b]

A. Don't get too hung up on this. A dot product is a cosine whether you are talking about vectors or quaternions.

[b] 5. Quaternions do not suffer from the same kind of normalization/orthogonalization problems that matrices do.[/b]

A. I have tested this and I don't believe it is an issue. The round-off error in either case will be trivial.

[b] 6. You can't interpolate a rotation using a vector representation.[/b]

A. Yes you can.

[b] 7. Have you ever written any actual code? / Do you even know anything at all about mathematics?[/b]

A. I have been writing games professionally since 1987. I have a degree in mathematics.

[b] 8. Contact that Shoemake guy, that Eberly guy, that _______ guy. He will straighten you out.[/b]

A. No thank you.

[b] 9. You have done a grave disservice to mathematics/physics/the game development community/newbie programmers/your company/your reputation.[/b]

A. I think they will all survive.

[center]Copyright (C) 2000 Ted Gruber Software, Inc. All rights reserved. [/center]

0

Report Article

Sign in to follow this

Followers
0