# Geometric Algebra in Swift?

I've just started looking into the fascinating subject of Geometric Algebra. AFAICS it seems to dramatically simplify computer graphics / geometry / physics code (and mental model).

(This talk is a great introduction. This is a javascript framework with runnable examples. And there are commercial applications of Geometric Algebra like this.)

I'm thinking of maybe learning more in order to rewrite my messy (2D) geometry and physics code. However, it would be nice to learn from and/or build upon any previous attempts at this, in Swift specifically.

Has anyone made such an attempt (maybe even a somewhat complete library)? (I couldn't find anything on github etc.)

If not, would anyone be interested in taking the first steps here in this thread? (I'm not even sure where to start.)

3 Likes

Regarding implementation, the following paper might be interesting:
Geometric Algebra and its Application to Computer Graphics

Here's a quote from a section called "Issues in Efficiently Implementing a Numerical Geometric Algebra Package".

There are four issues inherent to Geometric Algebra that complicate its efficient implementation. Three of these issues are a consequence of the fact that GA is a very rich mathematical language. This richness is to the advantage of GA user, but it complicates the job of the implementation developer. The issues are:

1. The large number of primitive objects: In theory, we need only one primitive in Geometric Algebra: the multivector. However, this is similar to stating the only car youāll ever need is a tank. While the multivector can contain and rep- resent any other primitive, it is usually much slower in use than specialized primitives such as a ā3D bivectorā or a ā5D versorā. Introducing specialized primitives can be useful for several reasons: it is more efficient to store and compute with such a specialization: they require less coordinates to be represented and hence less operations when computed upon. Also, the GA user thinks in terms of specific (groups of) primitives instead of the general multivector.

The first classsification of specialized primitives we make is based on grade. In 3D, we distinguish scalars (grade 0), vectors (grade 1), bivectors (grade 2) and trivectors (grade 3). The are also odd (grade 1 and 3) and even versors (grade 0 and 2).

The second class of primitives arises once we introduce basis vectors with some special meaning or inner product. For instance, in the conformal model, the special definition of points introduces a whole array of primitives (see table 7). Compare this to traditional use of linear algebra for doing geometry, where the computational primitives are limited to scalars, matrices, vectors and possibly quaternions.

2. The large number of basic operations. Table 8 lists some basic operations that every GA implementation should provide.

3. The arbitrary definition of the inner product: In Geometric Algebra, it is common to use vectors that have a 0 (i.e., null vectors) or negative inner product with themselves. Even reciprocal basisvectors are used. E.g., the conformal model uses e0 Ā·e0 = 0,eā Ā·eā = 0,e0 Ā·eā = ā1. Arbitrary definition of the inner product complicates efficient implementation because the inner products can not easily be āhard codedā.

4. The large number of coordinates required to store a high dimensional Geometric Algebra primitive with respect to a basis. A n-dimensional Geometric Algebra requires 2n coordinates. Of course, this is only a problem if the GA implementation developer chooses to represent the multivectors on such a basis instead of using some other method.

2 Likes

This is the nut of what makes GA a bit unwieldy in practice. It's a beautiful mathematical abstraction, but in practical use cases GA is generally still fundamentally representing exactly the same concrete operations that we use with quaternions, vectors, etc, and if you want to actually get the GA abstraction of putting all the objects into a single type, well, instead of 3-dimensional vectors or 4-component quaternions, now you have 8-dimensionalĀ¹ objects:

Lost in copy-paste: 2āæ. 2n wouldn't be quite so bad. Anyway, these specialized objects end up being exactly the vectors, rotations, etc that we normally model as separate types, and now we're going to end up .... modeling them as separate types for performance reasons. GA is a really nice unifying formalism, and fun to experiment with, but I haven't seen a lot of evidence that it streamlines actual implementation or use of computational geometry that much. (This is where someone interested should build a library and prove me wrong =)

Ā¹ At least. Up to 32 if you want to go all the way to a conformal GA.

3 Likes

I think the biggest problem is the lack of value parameters in Swift generics. They would offer a way of addressing the first of the issues in your list. Without it I can't think of a nice/relatively efficient way to have a general GA package which is also able to be used to generate the 2D and 3D systems, like 3D dynamics, that can be derived from it.

Apart from that Swift offers a lot of useful features, and it would be interesting to explore what could be done. But getting something out of the end that could replace your geometry and physics code seems very unlikely.

2 Likes

If you're only interested in low-dimensional GA, you can "just" build a limited Peano arithmetic in the type system to work around this limitation. It's slightly unwieldy, but not a huge obstacle. If you want to go past 3D, it's gonna get kind of ugly, though.

1 Like

I'm only interested in 2D + time, and conics (not only points and lines).

There seems to be quite a number of code generators for various languages (generate code for a given GA subset), and it is in real use in eg Enlighten, Unreal Engine:

For 2D, the dimension blowup isn't too bad (and you don't have the benefit of quaternions), so that seems manageable and worth doing.

Most of the practical uses of GA that I've looked at ended up vending an actual interface that was basically isomorphic to a "standard" vectors-and-quaternions 3d math package. The vocabulary is different, but on a practical level, the actual types and operations are basically identical (both in terms of what is possible and in terms of the concrete coordinate implementations that result). There's nothing wrong with that, but it also makes it (to me) kind of uninteresting.

It seems to have some clear advantages (as mentioned in the talk in the OP), eg less exceptions, don't have to care about epsilon etc. One concrete example: The intersection between two lines always produce a result, even for parallel lines (intersection point is at infinity in the direction of the lines). Overall, the "simpler" / more "elegant" model, with its duality etc seems to provide a more powerful / efficient mental model as well. But I don't really know, as I've just started looking into it.

I'm not that familiar w/ GeoAlg, but to handle points-at/near-infinity, homogenous coordinate works pretty well.

1 Like

Yes, homogeneous coordinates or perhaps more specifically projective geometry enables this formulation of the intersection between two lines (where the result is always point). And in GA, the same operation joins two points into a line.

This is generally true of projective coordinate systems, not unique to GA, precisely because of duality.

More generally, this touches on what I was trying to get at earlier--once you get down to coordinates, GA has to "do the same computation" as other systems, because these are linear systems, so the coordinatewise operation is fully specified by the results. GA only gives us a different abstraction over those coordinate operations.

2 Likes

Enlighten is I think based on conformal GA (that WP article is a bit of a mess but the references are good). It has advantages over GA based on projective and orthogonal geometries. It uses a higher dimensional GA to do this, structured in a particular way.

But like Vectors, Quaternions you work within a fixed dimension and a limited set of elements, not the full algebra, to make use of it. I.e. an application would use another specialisation of the full GA, where you would code just the bits you need, with the GA mostly being used as theoretical justification for it.

2 Likes

Here's an interesting talk (where the speaker mentions those four implementation challenges I quoted upstreams):

Generic programming of Generic Spaces: Compile-Time Geometric Algebra with C++11

1 Like

An excerpt from someone praising a programming language called Scopes on reddit:

Implementing a compile time typed geometric algebra library is not easy in other languages. Have a look at versor for example. It's only possible in a handful of languages anyway. It became the main criteria to judge a new programming language.

Writing such a library in scopes just took me a few weeks (including refactors after version updates) and less code. It's just the basic math yet (multiplication, addition), but it's already easier to use than versor in my opinion.

I like this: Implementing a compile time typed geometric algebra library became the main criteria to judge a new programming language.

So, if this is possible in Swift, I guess it would be even harder than in C++11 (versor is written by the guy in the talk I linked to in my previous post), and nowhere near as "easy" as in Scopes (look at that Scopes library, not much code).

1 Like

I hate this. It just throws away all the nuances between programming languages, all the language's goals, requirements, target audiences, etc. Even if GeoAlg is a good level of abstraction (which I still doubt, with how much overhead for simple structure), it still sounds like an unfalsifiable statement, which is not great for almost any kind of call-for-improvement discussion.

1 Like

OK fine, although I'm not at all sure what you mean. Scopes looks like a very approachable and interesting language. And judging by the criteria (which you don't like), it seems to have some fundamental features which makes it more expressive than many other languages, ie: Something which was very hard or impossible in other languages turned out to be not so hard in this language. I really can't see anything that seems reasonable to hate about that.

I mean, if you can do this, then you can probably add nice Unicode support or whatever too. But this is getting off topic.

1 Like

I mean, Scopes could very well be a good language. I'm not disputing that. But it'd be a good language for all the things it's trying to do (including expressibility in this case), not for the unilateral fact that it's compatible with some notational system.

Maybe because of the wording. It's fine to have rich type system that support more possibilities (with no detriment to other components of the language). And if it's rich enough to express GeoAlg, then that's great! But it shouldn't just single out GeoAlg as if it's an end-all goal. What about statistical matrix, transfer functions, etc?

Anyway, we digressed. Best be if some one try to implement it. It'd be interesting to see as well, as well as some expressibility gap Swift may have missed.

I think what made it easier in Scopes was mainly syntax / macro / meta programming features, but whatever.

AFAICT geometric algebra is a unifying concept, so it makes it easier to see and express how "everything" fits together. It seems like everyone agrees that it is an elegant theoretical / communicational tool. A naive implementation is not worth writing because of to the implied overhead in storage and computation, but that is not what the implementations I have linked to is doing, their aim is to provide a high level API (GA is a very high level abstraction) while at the same time making sure it is efficient (by efficiently computing requested subsets of GA as much as possible at compile time etc), this is what is so hard in most current programming languages, including Swift I guess.

I don't know anything about this, I just think it's fascinating, but it seems like I'll have to settle with bringing a bit of inspiration from projective geometry (which I had no idea about before) into my fragmented, badly structured, over-complicated and incorrect geometry code and move on.

1 Like

fwiw, I find it challenging defining operators. If I use `*` and `+`, it couldn't get so far as to type:

``````let a: GeometricAlgebra = (1 * .e1 * .e2 * e3 * .e1 + 2 * .e3) * (2 * .e3 + 1)
``````

without compiler (and computer) crying... Here's a github dump (disclaimer, not tested, still nailing the type system and syntaxes).

Maybe because I defined `GeometricAlgebra = Multivector<GABasis>`, and generic makes things worse.

1 Like