Jump to content
  • Advertisement
  • 09/11/00 03:34 PM

    Do We Really Need Quaternions?

    Math and Physics

    Myopic Rhino
    Editor's Note
    This has been, without question, the most controversial article we've ever posted, as evidenced by this thread, 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.



    [size="5"]Part I: Equivalence

    Recently some of my Fastgraph 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 ij=k, ji=-k and i[sup]2[/sup] = -1, 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 Gamasutra web site. This one is nicely derived at http://http.cs.berkeley.edu/~laura/cs184/quat/quaternion.html.

    image002.gif

    where

    image004.gif

    and (x,y,z) is a unit vector on the axis of rotation and 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).

    image008.gif

    where

    image010.gif

    and (x,y,z) is a unit vector on the axis of rotation and 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:

    image013.gif

    and from the definition of quaternions:

    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.

    image017.gif

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

    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:

    image021.gif

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

    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"]Part II: Deriving the Rotation Matrix Around an Arbitrary Axis in R[sup]3[/sup]

    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 http://mathworld.wol...ionFormula.html.

    image025.gif


    image027.gif
    image029.gif
    image031.gif
    image033.gif
    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 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 Out 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, Mathematical Properties of the 3D Rotation Matrix, to be delivered at XGDC, October 1, 2000, for further explanation and proofs.


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

    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 (Animating Rotation with Quaternion Curves, 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"]What is a vector interpolation?

    Suppose you have two vectors, P[sub]1[/sub] and P[sub]2[/sub], and a rotation angle between them, 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].

    image040.gif
    P = f(t'), image042.gif


    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 image006.gif, or any part of angle 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.

    image046.gif
    image048.gif


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

    image051.gif


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


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

    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"]Frequently Asked Questions and Frequently Stated Comments regarding Diana's quaternion article.

    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.

    1. Quaternions are necessary because without them your program will suffer from gimbal lock.

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

    2. Quaternions use less data than vector rotations.

    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.

    3. Quaternion operations are faster because they can be done using fewer operations.

    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.

    4. Quaternion operations don't require trig, vector operations do.

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

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

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

    6. You can't interpolate a rotation using a vector representation.

    A. Yes you can.

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

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

    8. Contact that Shoemake guy, that Eberly guy, that _______ guy. He will straighten you out.

    A. No thank you.

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

    A. I think they will all survive.

    Copyright (C) 2000 Ted Gruber Software, Inc. All rights reserved.



      Report Article


    User Feedback


    I would love to use axis-angle, because it's so straightforward, but the only solid issue I can see that puts quaternions out ahead of all other options is rotation concatenation.

     

    If you have an object, with its orientation in axis-angle form, it's not very easy to apply rotation to its existing orientation. I've been working on this problem for a few days, in the hopes of coming up with something as efficient as quaternions insofar as compactness and efficiency of concatenation, and the best way to use axis-angle is by converting to quaternions to perform concatenation, which then requires converting back to axis angle. To my mind, this would just be a lot better to just get rid of the intermediate part and just make it the representation used.

     

    No matter what I use, at the end of the day I still have to submit orientations to the GPU in the form of matrices, but anything I can do to speed up physics calculation is a win. Axis-angle, in this instance, is not the best.

    Share this comment


    Link to comment
    Share on other sites

    I would love to use axis-angle, because it's so straightforward, but the only solid issue I can see that puts quaternions out ahead of all other options is rotation concatenation.

    There is, in fact, a way to concatenate axis-angle rotations. A quick Google search led me to this thread: http://www.gamedev.net/topic/542932-how-to-sum-rotations-vector--angle-/

     

    tl;dr Basically, to concatenate two axis-angle pairs, you convert them to matrices, multiply them together, then convert the result back to an axis-angle representation.

    Share this comment


    Link to comment
    Share on other sites

    Here is something I will say negative about Quaternions and positive about Euler angles, which is shocking I suppose to hear from any programmer. What I'll say is, neither are perfect, but combined can work fairly well. It's culture shock I suppose from every developer who obviously knows that gimbal lock is a problem. However, how does actual gimbal lock happen? (I have to say "actual gimbal lock" because I've read articles that simply say that reaching a singularity at 90 and 270 degrees, which can be easily worked around, causes a "gimbal lock". Actually, that causes a crash if your compiler caused an exception it didn't gracefully handle, thankfully C# and .NET just return a NaN.) I define actual gimbal lock as the loss of a degree of freedom caused by the rotational dependency with not applying all rotations for each axis at once, which the Quaternions do. Let's get into the actual problems with Quaternions though.

    Firstly, consider the method of approach to get Quaternions, you take the cosine and sine of each angle divided by 2. If your original angles are clamped between 0-360, you're already losing some information. That's why every Quaternion to Euler formula that I see has a problem in getting the actual original Pitch angle, calculating by Arcsine, including the ones on Wikipedia and Euclideanspace. I actually spend a few days testing and figuring out things about Quaternions in depth, and found a better, but not perfect, process by which to get the original Pitch back, which I'll explain momentarily.

    Here's what I found. ORDER matters at every stage in the Quaternion process. In Unity for example, if you're going to recreate Unity Quaternions from scratch for mathematical testing, you'll find very quickly that when you try to pull back an Euler you'll get the wrong angle unless you specify YXZ in the creation of the Quaternion by "sandwich products" (that is... q * V_in * q^-1), and then create the rotational matrix in ZXY order.

    Once you've done all that, you get not one but two potential orientations for your original Euler angle, which mathematically works, but is annoying if you've ever seen an engine like Unity bring back a weird angle with the X flipped around 90 and 270 degrees while the Y and Z get flipped by 180 on the second angle retrieved from this Quaternion to Euler conversion, and you want your actual original angle back. If you don't do it right, you'll get some weird flips on some rotations from what it should be if you convert back to Euler and then apply it somewhere. I tested with all 36 permutations, and found that only the way I specified works with Unity, that alone tells me that Quaternions are not some magical unicorn of mathematics. It also tells me why Euclideanspace mentioned differences in NASA standards and how they had to do some flipping of signs and what not to get rotations to work.

    In other words, Quaternions aren't exactly one size fits all like the internet claims, you'll have to test and see for any engine you work with what order the Quaternions were actually applied in because it pertains to the accurate way to retrieve said angle, but then, when you do, because you don't have real accuracy in getting the pitch angle back because it's obtained by Arcsine, you'll have to basically make a decision between two angles that are equivalent, which is fine from a mathematical perspective, but not so great from a data perspective.

    So, how did I sort of fix it? Well, by creating a second Quaternion in the conversion process that has only the pitch obtained from the Arcsine and the other angles zeroes out, testing both rotation angles to see which one has a roll/yaw closer to 0 than the other, which will be either -180 or 180 on both angles. It works unless your roll and yaw are both close to 180, then it flips.

    So what I'm saying with all of that, is that it's not the best in the world for human readability simply based on the problems of Quaternion to Euler conversion.

    Imagine for whatever reason hypothetically that you're on a spacecraft marooned in space, there are no planets around, but there is a Black Hole. Let's say that you decide to go into said Black Hole since it seems like there's no other option. As you enter the Black Hole, your instrumentation uses Quaternions and it's getting you the angles back in Euler so that you can read them, but the angles keep on flipping because you're spinning around in a Black Hole, but maybe somehow not dead yet, and for whatever reason not nauseous, so even though you're ok, your instruments are going haywire because they keep flipping which Euler angle to pick, spinning out of control and you have no sense of actual direction. While a ludicrous hypothetical example, I'm simply conveying the fact that it's not the end-all be-all of rotational systems, despite whether it's computationally fast, or stores less information, etc.

    Also, just a pet peeve of mine on the internet. It's not the Euler "angles" that are the problem, since they can be easily converted to Quaternions. it's the actual rotational math created by conventional formulas to rotate said Euler angles that suffer Gimbal lock. Angles are just numbers, whether you specified 360 degrees for a rotation on an axis or 2*Pi, or even just 1 as a rotation. Quaternions on the other hand, just another representation, except that said representation basically gives you back the sine of the pitch and two other angles, leaving you with some lost data when trying to read it in a more human readable way.

    When you dig down into the actual math and you understand that math is math, and not something transcendental or magical, you understand that Quaternions have their own set of problems, hence nobody I know seems to really understand them fully, and I've read tons of articles, actually tested the math, and made it my pursuit to explore virtually every aspect of Quaternions. At the end of the day, my take away was a desire to create a rotational system that applies all of the rotations for each axes at once to get around the Gimbal lock problem, with all the original Sine and Cosine information, not sines and cosines divided by 2 initially. By the way, axis-angle methods from what I understand have the same issue as Quaternions. I feel that a better solution exists somewhere, that's my take away of digging into the guts of Quaternions and Euler angles. In the meantime, I decided to build my own rotational system in Unity3D for some mathematical testing that essentially uses both Eulers and Quaternions so that a human readable angle is tracked. However, once you start multiplying Quaternions by themselves, good luck getting the original pitch angle back, essentially. I think of it as a lossy format the same way I think of jpeg. It's great that it exists, but I would like to have a png kind of end-all be-all solution for rotations that gives you all the connecting components from human readable angles down to the actual rotations applied and doesn't suffer gimbal lock. I imagine such a system potentially being more computationally expensive, but more robust as well. Maybe not something you would put in a game, but on an actual spacecraft. Understanding said math though, opens up lots of opportunities for understanding the full spectrum of rotations.

    I don't have a mathematics degree as you have by the way, mine was in programming, at best I worked for the banks and I was on a team that won an AT&T Hackathon contest (which I detest because I would rather them call it a computer programming contest) back in 2015, looking back I should have gone for that math degree, but I would have most likely been buried in a realm of subjective proofs like I was in Discrete Math, only to write a subjective thesis to be subjectively graded for what should be an objective degree. I've been exploring this rotation problem and the spectral leakage problem in DSP (also related to cosines and sines) as of late. I simply thought that I would weigh in and give a quick... "Hey, I've been there, I know what you mean, I'm sending my sympathetic and even empathetic condolences, even though others in the game community may scoff at this post, claim inaccuracies by quibbling over semantics, and so on. Ask me if I care what they say personally, I'm interested in mathematical innovation, as are you quintessentially. You've got a whole generation of programmers out there that try to beat you into acceptance of imperfect standards at every turn on StackExchange and other sites just because they're afraid of getting in with a little mental elbow grease,  sure it causes brain pain, but I think this is one wheel that needs to be reinvented."

    P.S. My last girlfriend, whose father worked for Mission Control at NASA before he unfortunately passed away, actually laughed when I mentioned both Unity and Quaternions. I don't know if she's ever had any exposure to rotational systems, or understands the math, she worked as an administrative staff in some capacity there at NASA years ago. She was right to laugh though, amazingly, even if it was just at the silly hyped up name. I'm in some ways laughing now about Quaternions and in some ways not now that I've explored them at a deeper level, a better solution must exist somewhere, so I'm playing around with the numbers of Sines and Cosines and seeing if some of the techniques applied to Quaternions can be applied to some system that is more inclusive in terms of information. In some ways, I'm also laughing about Unity3D, and not in a good way, it's the engine I've grown dependent upon for rapid prototyping, but it has an exceeding number of limitations at every turn if you want to delve into things like, oh, say, setting a TRS matrix directly.

    Edited by John Ernest

    Share this comment


    Link to comment
    Share on other sites
    1 hour ago, John Ernest said:

    Here is something I will say negative about Quaternions and positive about Euler angles

    If your actual problem is only to get original euler angle numbers back after turning them to a representation of rotation, then this can't be an argument against quaternions or for euler angles. Orientation has little (quats) or no information (matrices) about the rotation(s) which caused it, so what you want can only work within conventions and restrictions you define for yourself (e.g. limiting angles to 0-360, euler rotation order, assuming zero as initial state as you do). This puts your whole post into personal experience with some assumptions and impressions, which is not helpful for anyone (mostly beginners) to choose the right tool for the current job.

    Matrices, quaternions, axis and angle, rotation vector, euler angles - all of them are useful for 3D rotations, and nobody should shy away from any of them. Even if some are harder to understand than others, they are all useful and necessary at some point. Full understanding is optional anyways, otherwise quats would not be so popular ;)

     

    Share this comment


    Link to comment
    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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!