top | item 22200260

Let's remove quaternions from every 3D engine (2018)

627 points| lelf | 6 years ago |marctenbosch.com

326 comments

order
[+] dahart|6 years ago|reply
> As a side note, Geometric Algebra contains more than just Rotors, and is a very useful tool to have in one's toolbox.

I worked in a game engine where a pair of mathy programmers fell in love with Geometric Algebra, and use this same argument that quarternions ought to be replaced to overhaul all of the math code in the engine using Geometric Algebra. The character rigging system removed matrices and used GA instead.

This caused several large problems in the code base:

For one, it slowed the code down a little because the GPU interface is all matrices, so there were conversions to matrices all over the place, rigging in particular.

And only two guys in the studio knew Geometric Algebra, and they didn’t invest time in teaching it or helping people understand it, they just hoisted it on everyone. All the rest of the programmers knew matrix math but not Geometric Algebra, so they would end up avoiding touching any of the GA code, i.e., any code that dealt in transformations. The two guys ended up with a lot of support of their own creation, but they were short with their answers, in part because they got so many questions, so the problem never went away.

The third problem is this whole rewrite was unnecessary. Fixing gimbal lock with quaternions is a tiny corner of the game engine, whereas using GA throughout is a massive rewrite. Matrices work really well for 98% of the code, and it’s not really a huge problem to have one or two routines that convert to quaternions and back while they do a rotation. It is a problem when any transform at all involves bivectors and rotors and you have no idea what the hell those are nor do you have time in your schedule to take a math class at work.

Personally, I’m intrigued by GA and have wanted to learn it for a while, but having used it in production, I’m mildly against replacing quaternions with GA, and very wildly against replacing matrices with GA.

[+] oppositelock|6 years ago|reply
I'm a former game engine lead from many years ago, from around the time that quaternions were becoming popular, since we never used them before the early 2000's, really, as 3D was young and rotation matrices sufficed.

Quaternions came into favor to solve the problem of gimbal lock in composed Euler rotation matrices. This happens when you create a rotation which rotates one axis into another, and end up with a matrix that loses one axis (it loses an eigenvector), and you become "trapped" in the new rotated frame and can't ever rotate out of it. Quaternions don't suffer from this problem, but they're also tricky to work with and reason about, and their rotations can become funny when composed - instead of rotating from orientation A to B, they'll go through a C in a very different place. You need to create heuristics to keep rotations looking sane with quaternions. In the games that I've worked on, we took other precautions to avoid gimbal lock in rotations and stuck to Euler matrices. For example, in a flight simulator, you always computed the final rotation matrix for the plane location directly from its heading, pitch and roll, and so, you'd never suffer gimbal lock.

Why stick to Euler matrices and not some better Geometric Algebra or Quaternions? Because it's really easy to interpolate, and think about plain old rotations about a vector, and you can teach anyone to avoid gimbal lock. It's easier to avoid that problem than to train a bunch of junior engineers on higher level math.

[+] madrox|6 years ago|reply
As an engineering manager who's had to push adoption of new technologies, I feel this argument in my bones.

That said, taking your argument to the extreme, we all probably should've stuck with PHP, since everyone understood it and, well, was it really worth the switching cost? Naturally that's dumb, so there's a certain amount of "how do we get there?" with any new technology that's probably a good idea.

That's probably not going to get answered by the principal engineer who says This Tech Is The Future. It's going to get answered by people like you who think about switching costs and the impact new tech has on people.

[+] jessermeyer|6 years ago|reply
These problems are not inherent of GA, but of (flawed) implementation details and deeper social problems. GA code boils down to essentially the same computations as 'raw' Linear Algebra, and should be implemented as such. Your math centered programmers fell in love with the idea without ever figuring out how to really use it.
[+] SkyBelow|6 years ago|reply
I feel like this requires the same concern when replacing any system. Even if the new tool is better in theory, does it have enough people using it/experts working on it that it is better in practice and does the costs of replacing it justify the improvement.

Just look at something like a 50 year old IBM mainframe vs. the newest Sql Server with .Net Core running on the server of your choice. Is the latter the better choice for a new application? Yes. Yet many very successful businesses don't replace their mainframes because the benefits do not justify the costs.

[+] ur-whale|6 years ago|reply
The wikipedia page for GA, and in particular the introduction, is an absolutely perfect example of the horrible quality of math pages on wikipedia.
[+] moralestapia|6 years ago|reply
This is more or less the thing with "Category Theory".

Very fancy and neatly structured code but in the end you accomplish pretty much the same; and now nobody on the team understands a bit about what you're doing.

[+] earenndil|6 years ago|reply
GPUs don't have dedicated matrix hardware anymore, making it questionable whether you really need to convert your GA structures to matrices first. [1] finds that quaternions are faster than matrices on modern hardware; I find that questionable, but it at least shows that they are comparable.

1: https://tech.metail.com/performance-quaternions-gpu/

[+] notduncansmith|6 years ago|reply
Thank you for the anecdote! Sorry to leave such a small comment but I believe you meant “foisted it on everyone”, not “hoisted”.
[+] agumonkey|6 years ago|reply
Although the fact that GPUs are not ready for GA .. forcing a model that cannot fit onto hardware is quite a massive naive mistake.
[+] BlueTemplar|6 years ago|reply
The main issue here is that they tried to port what sounds like a mature code base. Imagine changing programming languages! They should have restarted from scratch, and with a team fluent in Geometric Algebra...
[+] BlueTemplar|6 years ago|reply
IIRC matrices are still required in Geometric Algebra ? Maybe by "matrix math" you mean "Vector Algebra? "
[+] nautilus12|6 years ago|reply
Isn't the data structure that supports quaternions just one dimension up from matrices? Why not continue using matrices and retain that last dimension seperately somehow? Then it doesn't require having to retool the GPU/matrix side of it. IE you will have multiple matrices where you would have had one otherwise.
[+] smcameron|6 years ago|reply
> Fixing gimbal lock with quaternions

Huh? I thought quaternions don't have any problem with gimbal lock. That's a problem with Euler angles and matrices.

Edit: I think you meant using quaternions to fix gimbal lock problems with matrices, which makes sense.

[+] pflats|6 years ago|reply
I'm a pure math dude at heart, even if I don't get to do it much any more.

Two years ago, my wife asked me, "If you had to get a math equation tattooed on your body, what would it be?" I answered, "i^2 = j^2 = k^2 = ijk = -1".

I felt a brief flush of anger when I saw this headline.

This is an extraordinarily good article that should be read by pretty much anyone doing graphics programming.

[+] xg15|6 years ago|reply
> I answered, "i^2 = j^2 = k^2 = ijk = -1".

Could you explain why? For someone without a math background, it seems indeed like a pretty arbitrary thing to define.

(I can understand the idea behind complex numbers and how the multiplication rules followed from the desire to define the square root of a negative number - however, so far, I don't get the motivation of introducing even more "special" elements)

[+] tzs|6 years ago|reply
It's nice to see something other than e^(ᴨi)=-1.

If I had to get a math tattoo, I think I'd go for lim n→∞ Q_n^(1/n) = e^(ᴨ^2/(12 log 2)).

That comes from a theorem proved by Khinchin and Lévy. Khinchin proved that for almost all real numbers if you take the sequence of convergents of their continued fraction expansion, {P_1/Q_1, P_2/Q_2, ...}, then the sequence {Q_1, Q_2^(1/2), Q_3^(1/3), ...} approaches a limit, which is the same limit for almost all real numbers. Then Lévy determined the value of that limit, which is now called either Lévy's constant or the Khinchin–Lévy constant.

If not that, then this (in standard math notation rather than the verbose notation I'm using here):

Line 1: Let H_n = sum i=1 to n 1/n

Line 2: Hypothesis: sum d|n d < H_n + e^H_n log(H_n) for all n > 1

That's neat because that hypothesis is true if and only if the Riemann hypothesis [1] is true [2].

The Riemann hypothesis is a conjecture about complex numbers, and is widely considered to be the most important unsolved problem in pure mathematics. That it turns out to be equivalent to a such a simple conjecture involving just integers and a couple real functions from pre-calculus is a surprise.

[1] https://en.wikipedia.org/wiki/Riemann_hypothesis

[2] https://arxiv.org/abs/math/0008177

[+] logfromblammo|6 years ago|reply
Mine would be the Fano plane mnemonic for octonion multiplication, using two curves of constant width instead of the triangle and the circle. That's got the quaternions covered with the inside curve.

It can go next to the skeletal formula for benzaldehyde on my imaginary nerd canvas.

[+] DonHopkins|6 years ago|reply
Then you could dress up for Halloween as Broome Bridge!
[+] pastrami_panda|6 years ago|reply
I love quaternions, but I have to ask: you'd rather have that formula than Euler's identity tattooed?
[+] jayshua|6 years ago|reply
I’d probably go with “e^pi*i = -1”. Kinda cliched, but I really love that equation.
[+] jtolmar|6 years ago|reply
I'd probably pick the normal-normal conjugate prior, in precision form.
[+] Koshkin|6 years ago|reply
She probably hoped for a different answer.
[+] ColinWright|6 years ago|reply
I've only skimmed the article, but it seems to be saying this:

> Instead of using this thing you don't understand and investing the time to understand it, why don't you use this other thing you don't understand, and invest the time to learn that instead.

Indeed, later in the article the author says:

> We can notice that 3D Rotors look a lot like Quaternions ... In fact the code/math is basically the same! The main difference is that i, j, and k get replaced by y∧z, x∧z and x∧y, but they work mostly the same way.

Have I got that right?

[+] xg15|6 years ago|reply
Your opinionated summary implies that both concepts are equally hard to understand, but the whole point of the author is that rotors are potentially a lot easier to understand and reason about than quaternions.

He also gives a concrete reason: For 3D objects, rotors operate fully in 3D, whereas quaternions are in 4D. This means you can visualize rotors and imagine "how they work" whereas with quaternions, you have to more or less blindly trust the formulas.

[+] onedognight|6 years ago|reply
Yes, you have that right. The underlying operations are the same. What you are missing is that the ideas from geometric algebra work in any dimension! Quaternions are a “trick” that only works in 3D.

You can write down Maxwell’s equations using the geometric algebra easily, and it will make them better! They will be obviously coordinate independent.

Pretty much anything with a cross product will be better written using geometric algebra.

[+] Certhas|6 years ago|reply
That's not correct. Mathematically as they describe the same thing they have to be translatable into each other. But one is a natural mathematical definition, the other exploits a completely unintuitive incidental mathematical isomorphism.

If you would read a few sentences on from where you quote, this becomes evident.

    ij = k
is arbitrary, needs to be memorized and just happens to do what you want for reasons that require a lot of working out.

    (xy)(yz)=x(yy)z=xz
On the other hand requires zero memorization.
[+] mcnamaratw|6 years ago|reply
Sure, people who are happy customers of quaternions and don't feel driven to understand what's under the hood, why change?

The pitch in the OP is (I think) intended for people who feel pressure to understand why it works. Geometric algebra can be built up yourself by picturing actual rotations, one dimension at a time. It's physical from the start. Quaternions are a finished math system that you have to reverse-engineer to understand. Some people like one approach or the other better.

Some geometric algebra people are kind of true believers. That's probably not helping the notation get traction.

[+] zupatol|6 years ago|reply
I haven't read that particular article, but from other sources I've read quaternions appear to be mysterious/magical even to people who know them, while the rotors have a very concrete geometrical interpretation in geometric algebra.

Geometric algebra also addresses much more than just rotating stuff, it's just that when you want to do rotations it leads naturally to something very similar to quaternions.

[+] LanceH|6 years ago|reply
The best 3d location/vector method I've used allowed rotations using normal x,y,z coordinates, but you could do rotate an object in the xyz of the engine itself, the object, or the object that object was currently attached to. This made things like shooting a lob from a forward facing gun easy, since you could raise the shot from the gun rather than the world and no quaternions were involved. I don't know if quaternions were used underneath.
[+] ianai|6 years ago|reply
That’s a notational change that incurs unneeded, increased cognitive load. That’s admittedly a mile high view.
[+] spacedome|6 years ago|reply
Amusingly the discovery of Quaternions by Hamilton was also followed by arguments within the mathematical community as to whether mathematics should be rewritten in the language of quaternions, as Hamilton proposed to do and subsequently spent the rest of his life pursuing. Initially many mathematicians found them confusing, Hamilton's book is unusually difficult to read and there were no others. The work of Grassmann was somewhat neglected at the time, and eventually the Gibbs/Heaviside notion of vectors (essentially what we use today) emerged as a competitor to the quaternions. It seems it was a particularly bitter mathematical divide, up there with Newton vs Leibniz. Here is a quote by Tait, one of the "quaternionists":

"Even Prof. Willard Gibbs must be ranked as one of the retarders of quaternion progress, in virtue of his pamphlet on Vector Analysis, a sort of hermaphrodite monster, compounded of the notations of Hamilton and of Grassman"

See "History of Vector Analysis" by Crowe or "Hamilton, Rodrigues, and the Quaternion Scandal" by Altmann. Nice to see the author cites these!

The Geometric Algebra comes from Clifford Algebras, which where an attempt to combine Hamilton's Quaternions and Grassmann's forms, and in fact contains both as sub-algebras. In the case of 3D rotations calling them Rotors or Quaternions seems mostly like a different way of thinking about the same thing.

I think this would be more kindly put as "reimagining" quaternions and not "removing" them. The additional geometric intuition from GA does seem useful, and even as someone who has used quaternions extensively (though in a very different context), I would also choose to work with Geometric Algebra as a framework for geometry over Quaternions.

The visualizations are quite good here, it is a good way to understand bi-vectors, you can wiggle them about a bit in 3D instead of just staring at parallelograms on a page. The only criticism I have is that they say quaternions and the cross product come "out of nowhere", but then the way they present the geometric product is equally "out of nowhere".

[+] VikingCoder|6 years ago|reply
While we're at it, can we please move the homogeneous coordinate to be the first value in memory? That way, a vector or a point, if they're represented sparsely in the data structure, just work.

[1], a point at the origin, is the same as [1 0] - a point at the origin in 1 dimension, or as [1 0 0], a point at the origin in 2 dimensions, or [1 0 0 0], a point at the origin in 3 dimensions.

Similarly, [0] is a zero vector. [0 0 0 0] is a zero vector in 3 dimensions.

Having to know [0 0 1] is a point at the origin in 2 dimensions (with a homogeneous coordinate), while [0 0 1] is a z vector in 3 dimensions (without the homogeneous coordinate), is just silly.

Why did we do this to ourselves?

[+] ArtWomb|6 years ago|reply
When I was learning graphics, the reasoning around quaternions was to avoid "gimbal lock". It was just taken as orthodoxy without question.

I think going forward next gen 3D engines will have to account for the improvements in GPU hardware realized by advances in machine learning. Mixed precision matrix multiply at massively parallel scale. As well as the demands of next-gen games. Things like real time ray tracing of deformable meshes ;)

[+] stared|6 years ago|reply
Quaternions are 3D rotations (plus, possibly, rescaling). The author notes that they have the same API (I like this term used in mathematical context).

So, the actual point is that the word quaternions (and "these strange i, j, k") is confusing. Rightfully (at least for anyone without a background in maths or physics).

"Let's remove Quaternions from every 3D Engine" -> "Let's remove the word 'quaternion' from every 3D Engine"

(Nice explanations and visualization, anyway!)

[+] iorrus|6 years ago|reply
The reason many people have trouble understanding quaternions is that they reason about them incorrectly.

Quaternions are actually a separate 'thing' when compared to vectors (which is why their multiplication seems off and the square is a negative number).

Quaternions should be considered a versor (a rotation around great circles), that is a change in direction which is different from a vector.

See this work: https://archive.org/details/cu31924001506769/

[+] crubier|6 years ago|reply
I am impressed at the number of people reacting with « Euler angles are fine » or « quaternions are fine, we always did this way ». Having worked extensively with them it is obvious that Euler angles are broken beyound repair (singularities, 12 competing variations...) and quaternion are too (they only work in 3D). This article is extremely interesting and absolutely true. If geometric algebra had been discovered earlier we would never have needed a lot of these unnatural constructs.
[+] pauljurczak|6 years ago|reply
In order to make geometric algebra really nice, you have to go 5D, see versor.mat.ucsb.edu. This imposes a significant computational overhead. Nice things are expensive.
[+] moron4hire|6 years ago|reply
You don't need to understand the root construction of Quaternions to use them in game code anymore than you need to understand the root construction of the Reals to be able to do arithmetic in game code. Just treat them as opaque values that have certain operations you can perform to get certain results and be done with it.
[+] DonHopkins|6 years ago|reply
From the title, I was expecting to read an article by a crazy old retro mathematician shaking his fist and yelling at clouds that we should all go back to using Euler angles. But this was a much better article than the title suggested!
[+] graphpapa|6 years ago|reply
This seems to be an excellent introduction to geometric algebra, a topic I have had difficulty picking up so far.
[+] epicgiga|6 years ago|reply
Let's remove them from one 3d engine first, and see how it goes.
[+] diegoperini|6 years ago|reply
Putting content aside (it's great actually), I love the format used for the article. Each header is also a link to a time point in the accompanying video. There are interactive canvases that are also used in the video. The only missing part is a teacher AI which I can ask questions to (just kidding).
[+] Koshkin|6 years ago|reply
They say Geometric Algebra is "the new language of physics" and whatever else; my problem with this is that, unlike, say the calculus of differential forms (or tensors), it does not make sense in more general manifolds which are at the heart of the modern theoretical physics. Geometric Algebra, therefore, is more like something that, sure, could be taught in high school in an attempt, for example, to streamline elementary vector algebra and thus eliminate some nasty questions (should they arise); yet, there is some mental load to it that may make it not worth the effort...
[+] scythe|6 years ago|reply
His criticism of the cross product seems more poignant than his criticism of quaternions in computer programming. One might ask -- why not teach bivectors in introductory math instead of cross products?

Historically it seems like 3D geometry and particularly cross products in the context of electromagnetism fomented the primary demand in mathematics education for students to be taught vectors. Unfortunately the mathematics curriculum (in Western countries) has not really been updated in decades to better prepare students for the jobs of today; we still enroll all students in a sequence that culminates in differential equations and particularly in second-order linear differential equations, which just so happen to be crucial to control problems in electrical and mechanical engineering. While many people's jobs involve some kind of mathematics somehow, only a few jobs involve the mathematics of electrical engineering, and I suspect that is part of the reason why so many students are bored in math class.

[+] GlenTheMachine|6 years ago|reply
A point that I don't think has been mentioned here: quaternions as a representation of attitude are really just a funky parameterization of an Euler axis/angle representation. Quaternions happen to be parameterized in a way that lets you avoid the evaluation of trigonometric functions when expressing their dynamics. This used to be important, e.g. in aircraft control systems, because computing power was extremely limited and you didn't want to have to evaluate sines and cosines in real time.

The biggest disadvantage of using quaternions over Euler axis/angle representations is that quaternions are basically impossible for humans to visualize, whereas Euler axis/angle representations are easier than transformation matrices, Euler angles, or any other representation.

So why not just use Euler axis/angle representations instead? Nobody cares any more about evaluating cosines at 1 kilohertz, and there would be none of this complicated geometric algebra stuff that nobody understands.