I'm the author of Klein and was surprised to see a sudden burst of traffic so I checked the usual suspects and ended up here :)
My goals for authoring Klein was to provide a library for performing all manner of geometric operations using the language of Geometric Algebra. The benefits are that the formulism is exception-free (meaning, for example, parallel planes have a well-defined line of intersection, that projections to higher/lower grade entities make sense, etc), and works equally well on points, lines, and planes. Practitioners coming from robotics/animation will also find the entirety of the Lie algebra/group inside GA as well for smooth interpolation, etc.
As a graphics engineer, I found most libraries out there unsuitable because of performance reasons. We're used to having nicely packed SIMD optimized quaternions for example. Klein fills this gap and (hopefully) in a manner where you can use it even if you don't understand the Geometric Algebra (yet!). Over time, I'd like to round out the documentation to explain the underlying theory, which I find unreasonably elegant and has shifted my thinking in the last few years.
Let me know if you have any questions about Klein or geometric algebra!
I saw a post in the last month or so on the front page of HN that linked a video lecture and a paper/presentation on GA, it’s still sitting in my watch/read folder unfortunately. So, since you volunteered for questions, I’ll ask a few:
- is there a generally accepted, or just personally approved, set of introductory materials on GA, to get one up to speed? I have a decent mathematics background, but I have been focusing on other areas recently so I am a bit rusty.
- I think your goals for Klein look interesting, and since you are a graphics engineer, I assume you are aware of the prior art (your comment indicates this is correct), so, is the main draw of using GA as an implementation theory the elegance of the underlying math alone, or does the math create a new space for potential optimization in the graphics space (I am assuming that your mention of performance penalty in existing implementations is due to a lack of focus on performance not unsuitability of GA to a performance domain).
The 3 links I compiled here (https://www.jeremyong.com/klein/references/) I consider an absolute must for starting to consume GA. The book (ref #3) has one chapter undergoing revision regarding the usefulness of the degenerate metric for modeling projective geometry. My understanding is the chapter will be released for free once finished. From this alone, I was able to piece together enough to write one working implementation of GA that I was able to use to verify the computations and my understanding. Klein is my third GA library which I wrote once I was pretty sure I was comfortable with the formalism. Another great set of resources is anything posted on bivector.net.
> re: question 2
The elegance of the math does help me identify better optimizations in a number of cases, but in other cases, it makes a whole series of operations well-defined (for which there was no good analog before). I posted some examples in another comment, but essentially, quats and dual-quats generally only work on points, and in a somewhat awkward manner. I can't easily compose 2 rotations, a translation, a dual quat, and a quat, and then expect it to work on a line for example. In GA, this is ... completely trivial. And because it all fits nicely in the framework, all the above benefits from the same SIMD optimizations.
I believe the reason GA was not considered well-suited for production/perf reasons is twofold. First, prior art focused on GA with arbitrary dimensionality/metric (results in either increased compilation time, or reduced performance). Second, there wasn't much overlap between practicitioners of GA, and graphics/animation engineers on the other side. I view Klein as "low-hanging fruit" in that sense, and consider myself fortunate to have come across the theory in the manner I did. I had written it off as just "an easier to understand Quaternion," but once I realized how much I (and perhaps some of my colleagues) were missing, I opted to actually try and productionize GA to "fill the gap" so to speak.
(FYI tried to send this over an hour ago but HN keeps rate limiting me :( )
As a quick note: I think your last comment up thread answered my second question reasonably well, it posted while I was writing my comment. But any additional details you want to share will be welcome.
Working on them! That said though, the audience of this article was originally meant to be animation engineers that have already "earned some stripes" and wanted to see the GA formulation.
I'm in the intended audience group then, as a game developer who works on animation regularly but only has a passing familiarity with geometric algebra. You could say I am "GA curious". But I'm afraid I didn't get much out of that article. I had hoped I would get more information about the benefits of using GA over standard matrix and quaternion methods. Instead, at the first mention of something GA related (which was motors) it was glossed over, as a hand wavy "don't worry about this". Later, pages of difficult math (which I skimmed over trying to find the punch line) were devoted to, if I understood, trying to do the equivalent of slerp that everyone is familiar with and is easy with quaternions (though perhaps just as complicated to derive). What I would have liked to have seen is an article that starts off with some motivation about what benefit one gets from looking at skeletal animation through this lense, for example, are there problems that vex people using standard methods which just don't occur when using GA?
The math is definitely more easy to grok if you've seen/used Lie Algebra/Group formalisms before so that's another shortcoming, but the main thing GA gives us here is a "dual-quaternion slerp" which I literally could not find an implementation of anywhere! The formula for a quaternion slerp is actually not too hard to derive, but a dual-quaternion slerp is far more difficult. Part of the point of the post was that this was somewhat surprising to me (both that GA makes it approachable, and that dual-quaternion slerp implementations didn't exist in the wild).
Thanks! I'm curious what motivated you to want to use a dual quaternion or why you want a slerp algorithm for that. I have yet to run across a use for a dual quaternion. Wikipedia says that they are used in mechanics to represent rigid transformations. That sounds useful for animation but most animation or computer graphics people would represent a rigid transformations with a quaternion and a translation vector, and if interpolating a rigid transformations they would slerp the quat and linearly interpolate the translation. So I'm not sure what the advantage of a dual quaternion would be in this context, or do you use dual quaternions in some completely different way?
Thanks for the questions. Indeed many animation libraries store the quaternion and translation as separate components. There are a few reasons I use dual-quaternions in my own code. First, because I can "slerp" them, this means that when I compress keyframes, and can perform better quality fits (potentially less error and fewer keyframes needed). The dual-quaternion has uses in skinning which I'm sure you're aware of, but if the base transformation is a dual quaternion, I can more efficiently morph neighboring vertices as well (I've ported the dual-quaternion application to shader code as well). One optimization that GA makes clear is the ability to factor out terms when applying a dual quaternion to a number of entities all at once which makes it almost as efficient as a quat-translation while conserving energy as well.
Finally, the dual-quat representation is beneficial when modeling kinematic motion specifically (not necessarily artist-authored) which can be useful in contexts beyond games (e.g. robotics, deep-learning, computer vision), but also inverse kinematics (which unfortunately I haven't had time to write about yet)
Geometric algebra looks cool, and this library seems like exactly what is needed for graphics programmers to use it.
What I'd really like to see is a comprehensive cheat sheet with formulas for common tasks in computer graphics with an absolute minimum of theory and jargon; even less than this article. Of course it's great to learn the theory too, but most people just call slerp in a quaternion library without learning the theory of quaternions. It should be possible to use a geometric algebra library in a similar way.
Original author here, it is absolutely my goal that the library should be usable without needing to understand the ins and outs of GA. To this end, I've started adding a bunch of "helper" functions that do tasks like projecting a point onto a plane, or identifying the line through a pointer parallel to another line, etc.
I've been (slowly) working on additional documentation in the meantime and didn't expect to see the animation article hit the frontpage :). That said, in the meantime, there is a GREAT cheatsheet for all the relevant formulae here: https://bivector.net/tools.html (scroll down to the bottom). You can get the PDF version here: https://bivector.net/3DPGA.pdf
I was wondering, once you've abstracted from the GA bits enough, is there any point of using GA at all? I like GA as well, just wondering what it gives you once you've abstracted it away. Or in other words, are there aspects of GA that cannot be abstracted away like that?
It took me a long time to actually decide to invest in GA because the sentiment I had was "it just replaces what I already know" and what I knew at the time was matrices, quaternions, and dual quaternions.
It turns out, I was pretty wrong in that respect. For example, in the current predominant formulism, it's awkward to rotate a line with a quaternion, then identify the dual quaternion that maps that line to yet another line, then apply that dual quaternion to a point. In GA, this just works (mind exploding gif). Or, I can construct a line between two points, then find the quaternion that maps a different line to that one, and convert it to a matrix to do "look at" transforms in a shader. Also just works.
I think the more I use GA, the more elegant I find it, and it takes me well past the formulism I used to know (which is still useful from time to time, but far less expressive). While I could provide helpers for all the common operations, the operators in GA will always have their use because... there's just so much you can do with it. At some point, the library will just because unwieldy/large. I haven't necessarily found the sweet spot yet for size/convenience, but I hope to converge there over time. Provide enough to be usable for most people, while at the same time being a launchpad for learning more about the abstraction itself.
From an implementation point of view, I've found a number of optimizations that were made easier (or even possible) with GA that I hadn't identified despite working with quaternions for years before.
Yup, now that I've "swallowed the red pill" so to speak, I can't even look at quats/dual-quats in the same way. They are very much a small cross-section of something much bigger (more expressive/powerful/etc).
I guess you can abstract away a lot, but there will always be questions that require you to go back to the math. For example: a use would be to set up a transformation that projects points onto a plane and a library could cover that. But consider the question of having a bunch of points and (paired with them) projected points and given the task of computing the original projection transform. If the library doesn't contain that operation you'd have to do it yourself.
Maybe you want to check out a javascript implementation of GA math with Ganja.js. While not yet comprehensive to all the tasks you probably would want to see, it does have some good examples that you can play around with
I tried to reverse-engineer it in order to write a SIMD-optimised Rust version. But fuck me. It's like disassembling the machine code of an obfuscated anti-cheat library. Even with good tooling and industrial-strength refactoring, I couldn't make enough sense of it to make any useful headway.
What saddens me is that every other library I looked at was ancient and no longer maintained. Half wouldn't even compile. Most started with an explicit assumption that only 2D, 3D, or non-degenerate metrics are needed. Very few have efficient code-generation, and those that do are invariably C++ only, but I'm never going back there, even at gunpoint. Just shoot me now, I'd rather eat a bullet than face another STL compilation error that I have to decode from a linker error to do with __malloc() or some garbage I don't care about.
Enki Mute's Ganja.js is the only recent GA library I've seen that ticks all the checkboxes, but when I opened it up, I faced only the unspeakable horror of yet another dead end.
GA is going nowhere because everyone cooks up their own special version, the terminology is unique and special to each researcher, and most libraries stop just short of being useful.
What we need is standardisation around a well-documented and extensible library with polyglot code-gen. Something with expression simplification, SIMD, and both maths-centric and 3D graphics optimised capabilities.
I think calling this stringly typed is unfair. Basis names appear to be strings with some densly coded information in them, and can sometimes take the values "-1", "0" or "1". But they're not integers, and it matches the mathematical notation used very closely.
I see plenty of 1 character variable names, but the vast majority are either loop variables, or have a comment near the top of the file explaining their meaning, or are the only argument on a commented/named function.
I see plenty of regexes, but they are all extremely short matching patterns.
So it looks pretty good quality to me. Extremely densely written, typical for the "genius mathematician" programmer, but with some effort put into clarity.
The comments are all of the style "now, this is the thing that is the thing". None explain anything at all other than to give names to variables or functions. Which you know... can already be named using identifiers in the language.
What are the matrices of constants? Where do they come from? What do they mean? What is their purpose? What are the random indexes into arrays? What do they do?
This is one of the first "comments":
// Documentation below is for implementors. I'll assume you know about Clifford Algebra's, grades, its products, etc ..
// I'll also assume you are familiar with ES6. My style may feel a bith mathematical, advise is to read slow.
I don't know about you, but whenever I see a comment littered with typos that says "this is a bit hard to read", it's a sure sign that whatever is to follow is of low quality. Not reusable. Not suitable for widespread use. Not extensible. Not useful at all.
To reiterate: this makes me sad. I really wish it didn't, because GA is one of my favourite things, and this Enki Mute guy is clearly one of the few people that also "gets it" and wants to spread the good work. Clearly, his heart is in the right place.
I know people like this guy. I went to University with a chap who would casually litter his Haskell code with 5 dimensional arrays of functions. Now I'm sure that made sense in his head, and his code actually worked, but no human being on Earth other than him could read it. He couldn't explain to me even verbally, let alone in comments.
Unfortunately, while Enki Mute could have made a great contribution, his methodology has not helped GA become more approachable.
All the major arrays are named after mathematical constructs you can find defined elsewhere. There's examples of them in the docs, and the describe function dumps them out for you.
The hairiest parts of the code and where he deviates from mathematical convention have more in depth comments (e.g. simplify, simplify_bits, inline).
Much of meaning and purpose is explained by that top coment - go read about Clifford algebras elsewhere. That seems an entirely reasonable approach to me. Indeed, I read the wikipedia page briefly, and already the code made a great deal more sense to me. So I think his position is justified.
So I really cannot see how you see this falling short.
Perhaps this is about expectations. You obviously wanted code that teaches, as well as functions. Maybe you were also expecting more object orientation, more spread out code? Well, those were not part of the authors plan, but don't alone make it bad code.
Seeing as this functions as a code generator, frankly, the output is a better teaching tool - one can look at the rust generated for, say complex numbers and dual numbers, and immediately see which parts are in common, and which parts are different. That makes you think about what other things could fit the same template, which is basically what clifford algebra attempts to answer.
Ganja.js is a personal project that got quite out of hand. Its primary goal was to lower the threshold for people to discover Geometric Algebra through examples and see its coordinate-free approach to geometry in action on the web. (since there was, and is, literally nothing else out there.)
Javascript is not the ideal language for that. Without operator overloading, much of the charm is lost - because of this, ganja contains a minimal transpiler (which is what all the regular expressions are for). This is purely out of necessity, as in practice I feel one needs a language with operator overloading for a GA implementation to be useful.
Furthermore, to be able to provide demo's in a wide range of Algebras, ganja contains three different algebra generators. (each of which produces the code that actually implements the algebra). This is another choice that typically does not exist for any specific use case (one would pick an approach and stick to it - like e.g. the Klein library) - and that adds a lot of complexity.
To visualize results, it also contains a range of different visualizers (2D, 3D, projective, conformal, SVG, GL, implicit, ..), none of which would be needed in a generic implementation. This again adds complexity that has no place in a 'reference' implementation. (which ganja was never intended to be).
In short, a lot of trickery was needed for ganja to reach its primary goal: clean examples that showcase how GA can simplify a wide range of applications. It certainly is not intended as a 'how-to' or reference for an Algebra generator, and when preparing for the Siggraph course, I saw no opportunity to use it as such. Instead, I opted to create separate reference implementations that are available at https://bivector.net/tools.html. (for c++, rust, python, c#)
With the increased interest, I did start a rewrite of ganja.js, and one that is not for my brain only.
I agree, this code is horrendous! It is like trying to read one of those code golf answers. Author seems to pride themselves on a proficiency for packing as much as possible in to one line, which is not a good thing in my opinion. I do think it was reasonably well commented though compared to code that I am used to working on (in games). At least they expressed basically what they were trying to do before each block of code, with references to specific algorithm names etc. The single letter variables didn't bother me as much in this context since a lot of those seemed to be loop indices which are only used in a small scope, or mathematical quantities that you would be familiar with from reading some algorithms standard description but they don't have an easy way to express in English. Definitely agree with you about all the regex nonsense though. To me that has no place in a math related library
As an aside: I knew a maths major student who would keep his entire year of handwritten lecture notes on a single A4 page of paper. It always fit! The Ganja.js coding style reminds me of that guy.
On a more serious note, GA computing has several orthogonal aspects to it, some of which have very different programming requirements:
* Converting GA expressions, e.g.: "x ^ e_o times y ^ e_1" into a single expression.
* The above requires either an expression parser, or an AST accessible from code, or both.
* A general multivector type at compile time to compute the results of those expressions. This one doesn't require any special optimisation.
* An expression simplification library, like a mini computer algebra system (CAS) to simplify the resulting elements after all of the high-level geometric products are carried out. This is important to eliminate a bunch of multiplications by zero, double negation, etc...
* A code-generation module to produce the final, optimised library for the runtime. This has to have a bunch of features to be competitive with Vector algebra 3D libraries. Many of these features are output language dependent. For example, it makes sense to have packed multi-vectors, sparse multivectors, a native array-of-multivectors type, etc...
In my mind, there are two main types of code in such a library: The first is the pure functional maths stuff, which is mostly the computation of some lookup tables and lists of lists of things. This is mostly static and needs standardisation. The second type of code is typically impure and needs to have a clean API to make it extensible/pluggable: parsing, code-gen, SIMD, optimisation, etc... E.g.: SIMD changes over time, there may need to be multiple optimisation passes, you may want to interact with an imperative compiler interface like LLVM or Roslyn, etc...
One of the issues I have with Ganja.js (that isn't about syntax formatting) is that is interleaves these largely orthogonal concepts. The strings from the parser flow through much of the code, making the entire thing a stringly-typed mess.
Enki Mute is clearly a mathematician, not a software developer. I can tell he's never had to write code intended to be used by others.
While these disciplines have a lot of overlap, CS is mostly about cooperating successfully with other humans. Mathematics is mostly about correctness... and that's about it. You can publish whatever you want, it doesn't have to have doc-comments, it doesn't need to be modular, or reusable, or anything other than not wrong and maybe interesting.
Jeebus, I agree. There’s a lot in there that I’d never pass in a code review.
There’s no tests, either. As in, if those were in place it would be an arduous but straightforward task to deobfuscate the mess and make sure the tests pass.
Ganja.js is exactly the opposite direction from what I want. The generality is not useful, the performance will be abysmal for graphics code, and the non-standard syntax is totally bonkers. It's a really cool experiment but not suitable for production use.
My goals for authoring Klein was to provide a library for performing all manner of geometric operations using the language of Geometric Algebra. The benefits are that the formulism is exception-free (meaning, for example, parallel planes have a well-defined line of intersection, that projections to higher/lower grade entities make sense, etc), and works equally well on points, lines, and planes. Practitioners coming from robotics/animation will also find the entirety of the Lie algebra/group inside GA as well for smooth interpolation, etc.
As a graphics engineer, I found most libraries out there unsuitable because of performance reasons. We're used to having nicely packed SIMD optimized quaternions for example. Klein fills this gap and (hopefully) in a manner where you can use it even if you don't understand the Geometric Algebra (yet!). Over time, I'd like to round out the documentation to explain the underlying theory, which I find unreasonably elegant and has shifted my thinking in the last few years.
Let me know if you have any questions about Klein or geometric algebra!