next »

[JobLeonard]

Slideshow & audio of Eric Lengyel’s keynote in the 2012 WSCG conference in Plzeň, Czechia, on geometric algebra for computer graphics.

Not sure if this deserves its own topic, but it doesn't really fit into any of the existing conversations of the first two pages; it's not about programming, for example.

Might be useful if you ever have to figure out complex 3D mathematics for your own engine, or somesuch.

(mods, please merge if you know where this is supposed to go)

EDIT: HN discussion where I found this, with some useful comments:

https://news.ycombinator.com/item?id=15180518

I encountered geometric algebra only few weeks ago and it is one of the most interesting, intriguing and elegant things I saw in my life. It almost feels too beauty to be true. I cannot understand why GA is not more popular - especially as it is backwards compatible with linear algebra.
There is very interesting library: https://github.com/enkimute/ganja.js

In mathematics, there’re more general operators besides cross and dot products. Wedge product = exterior product, the symbol is ^. And anti-wedge product = interior product, the symbol is ⨼. When applied to vectors, they produce not just vectors but various more interesting things.
In 3D space, vector ^ vector makes a bi-vector. In 3D, it contains 3 scalar components just like a vector, but the meaning is different (can be interpreted as an oriented area), and multiplication by matrix has different formula. That different formula’s the reason why normals need different formula to transform by a matrix.
In 4D homogenous space things become even more interesting. vector ^ vector produces a bi-vector. In 4D space, that thing has 6 scalar components, and its projection to W=1.0 3D space is a directed infinite line. Bi-vector ^ vector = a tri-vector, that thing has 4 scalar components, and its projection to W=1.0 3D space is an infinite oriented plane. Then, anti-wedge product can be used to find intersection of these things, tri-vector ⨼ tri-vector = bi-vector = the line intersecting two planes, tri-vector ⨼ bi-vector = vector = the point where line intersected a plane, and so on.
Mathematically, these operators are quite simple and therefore fast to compute, e.g. for 3D vectors ^ is same as cross product.
https://en.wikipedia.org/wiki/Exterior_algebra

At the ~one hour mark there's a summary slide:

Code:

    Old school                              | New school
    ----------------------------------------|-------------------------------------
    Cross product -> axial vector           | Wedge product -> bivector
    Dot product                             | Antiwedge vector / antivector
    Scalar triple product                   | Triple wedge product
    Plücker coordinates                     | 4D bivectors
    Operations in Plücker coordinates       | 4D wedge / antiwedge products
    Transform normals with inverse tranpose | Transform antivectors with adjugate transpose

reply

[qMopey]

I keep seeing this stuff pop up. Does anyone have any experience applying this kind of knowledge in a practical way? I've only briefly looked at it, so don't have much of an opinion yet.

[enkimute]

Hiya,

I'm the author of ganja.js .. just added a whwole bunch of examples demonstrating things like inverse kinematics and seperating axis test collision testing .. in 4 and 7 lines of code respectively ..

ganja.js inverse kinematics example.

ganja.js separating axis example.

GA, and for applications in gaming, PGA, changes .. everything .. everywhere you now use vectors, quaternions, complex numbers, dual quaternions, lines, points, planes, circles or spheres .. you can simplify your math often to single ascii character expressions.

If there's any other samples that would make convincing arguments - I'd be happy to add some more ..

Cheers,

e.

[JobLeonard]

Wow, cool demos!

Is that similar to what is used in constraint-based environments like http://aprt.us/ ?

[enkimute]

No, Unfortunately that aprt thing is based on 'the other mathematics' .. but .. you could not have picked a better example to demonstrate the difference ..

for example .. there's an IK solver on the aprt page to :

aprt Inverse Kinematics solver

open it, drag around with some of the boxes and watch the lack of smooth movement, flips and jumps going on, all clear indicators of improper handling of edge cases of classical ways of solving these problems .. i.e. using euler angles, matrices, cyclic descent, etc ..

Geometric Algebra IK solver

Compare that to the response of the Geometric Algebra IK example on my page. There's no flips, jumps or unexpected behavior. The implementation contains not a single 'if' statement. This can only be done in GA, where for example lines always intersect (parallel lines intersect in infinity), where all elements and linear operators are of the same type, and where a true coordinate free (no .x .y or .z in my code ..) and chirality free (no left/right hand rule needed in GA), pay of in much easier formulas and much much shorter code. (and that's on top of the fact that many problems are near impossible to solve when working directly with matrices or eulers or take your pick .. )

Geometric Algebra should be a lot more popular than it is. But its inventor (Clifford) died at an early age, leaving room for Hamilton to advertise and push his vector algebra down everyone's throat .. it took 100 years for people to pick up GA again and it still hasn't gained the momentum it should. (just anecdotal, Maxwell's 4 famous equations reduce to a single compact, simple and readable equation when expressed within the framework of GA.)

I could go on about the advantages of GA over its alternatives. Everything you learn in 2D will work exactly the same way in XD, not like a cross product that for example does not exist in 4D or 2D.

For games and graphics, GA, and in particular PGA checks all the boxes to eliminate our use of matrices in graphics, physics, game and AI engines alltogether and recently has gained popularity in the robotics and computer vision communities.

The saddest part of it al is that it is actually a lot easier to learn than the mixup of vector, matrix, quaternion and ad-hoc math you need to strugle through to be any good in the gaming sector today.

My advise ? if you plan to ever in your life do any math, work with vectors, matrices, complex numbers, or count stuff with your fingers, then you will do yourself a big favor by LEARNING GEOMETRIC ALGEBRA FIRST !!!!!

:D

Enki.

[JobLeonard]

Could the fact that the aprt IKS has three links while yours has five (and also different constraints) not be part of the problem here?

So they use "the other mathematics" (hahaha, so you're that kind of principled mathematician, eh? ), but does that mean that GA wouldn't be applicable in a constraint based style of editor like the one demonstrated in this video?

My advise ? if you plan to ever in your life do any math, work with vectors, matrices, complex numbers, or count stuff with your fingers, then you will do yourself a big favor by LEARNING GEOMETRIC ALGEBRA FIRST !!!!!

Not really a fair expectation if I am just beginning and don't know what to look for

Blame the teachers!

[enkimute]

On the GA example, you can change the number of links by changing l=6 on line 17 to l=4. It's just as smooth and flip-free. The inverse kinematics problem actually becomes harder to solve as you add more links. (in fact if you have just two links, an analytical solution exists). The more links the more remaining degrees of freedom that you need to fill in. The GA example does this by minimizing the difference to the previous pose. For CG and gaming applications - that's exactly what you want. For robotics, a slightly modified version would optimise for used electricity or total time.

A graphical system like APRT would actualy benefit greatly from doing their mathematics in a PGA or even CGA setting. Formulas would simplify greatly, and building a generic solver that satisfies these types of geometric constraints is much simpler in GA (although - the people writing the solver would need to understand what they are doing .. its a lot simpeler than in the linear algebra setting, but its not simpeler than copying someone elses solver - which to many people do)

Pardon my condescending reference to the 'other mathematics' in my previous post. I'm quite familar with vector and linear algebra as for me to this is what I had been thought in school and through professional experience. (with quite familiar I mean the following - all my code : javascript character cloth physics and IBL rendering). Since discovering GA however it becomes easy to feel a little dirty battling gimbal lock, matrix decompositions, coordinate system problems, non-orthogonal matrices, and physics solvers drifting of in a plethora of dimensions I didn't really need to begin with.

But fair point, the teachers realy are to blame. And unfortunately as is often the case with 'newish' science, the existing material is often highly technical and requires a mathematical background. But if you are interested, there are certainly a number of good introductionary texts around. (Jaap Sutter's jaapsuter.com/geometric-algebra.pdf introduction comes to mind.).

It'll take a bit of persistence, but the reward is well worth it ..

Cheers,

Enki

   

[JobLeonard]

Another angle for this mathematics to break through would a "killer app" where it's too useful to be ignored.

I'm not saying your library isn't impressive, and it does make it super-easy to demonstrate it (just open a website!), but there is also the matter of how many people do geometric calculations in the browser...

Maybe porting your ganja.js to a C# / C++ library and putting it on the Unity asset store (and whatever the equivalent Unreal engine is) would help?

[enkimute]

Hi JobLeonard,

Sorry for the late reply - totally missed your follow-up. Unfortunately, to provide the type of integration it does, ganja.js relies on the ability to translate code at a source level. Neither C++ or C# offer that feature. (C# has reflection features but not at source level). Without those features it is a lot more difficult to implement an efficient and syntax friendly GA library. (several attempts exist for both those languages but they imho lack the simplicity and true-to-the-math syntax ganja.js can offer.)

I also appreciate your sentiment re 'killer app' but the situation is much more profound. A while back I told a friend I was studying GA and he asked me where I would use it - at that point to me it sounded like someone asking me where I was planning to use negative numbers.

That analogy also nicely illustrates the type of impact these new geometric numbers, this geometric algebra has. Before negative numbers were generally accepted (nobody ever held -3 lemons or weighed something that was -2 kilo - it's not _that_ obvious), we already had solutions for a whole bunch of equations (including quadratic ones!).

Say we don't know about negative numbers .. only unsigned ints available, and we come across the following equation:

Code:

a + x = b

Where a and b are given and our task is to find X. Without signed integers you can still solve this problem - it's easy :

Code:

if (b > a) x = b-a; 
      else x = a-b;  // also remember we moved it to the other side of the equal sign ..

Furthermore, wherever we use the resulting x, we'd have to also keep track of what type of x it is, further complicating all code that uses these values.

So negative numbers don't really allow you to do something you couldn't before .. what they do is allow us to program it like this :

Code:

x=b-a

Which again doesn't just simplify this one line of code but also all the code that uses the resulting values.

Geometric Algebra adds in three new numbers (and their scalar multiples) with an impact even more profound than that of the negative numbers. (these new types are all non-real square roots of -1,0 or 1 - combinations of them form just about all algebras we ever studied, including complex,hyperbolic,dual,quaternion,dual-quaternion,vectors,minkowski, and much more). It brings tremendous simplifications in all fields of science that deal with our universe or representations of it - it shows up just as often as negative numbers and in many cases the simplifications are much more profound - not only producing less equations in simpler forms, but often providing new insights that were previously hidden beneath the complexity of the math.

Even if you don't plan on using GA immediately, studying it will bring your understanding on all of its sub-algebras to a whole new level. Never again will you think of a quaternion as a point on a 4D hypersphere (you could - its 4 numbers and normalized - but its about the most idiotic representation you could pick if you want to gain an intuitive understanding of what a quaternion is).

There is tremendous value in studying this top-down mathematical model - understanding the ingredients many other algebras (and probably our universe) is build from.

// Dramatic intermezzo

One ring to rule them all. 

// End Dramatic intermezzo

(that's a movie quote - geometric algebra generally is non commutative so its not technically a ring )

[JobLeonard]

I'm going through this playlist now:





If you have any other recommendations I'm all ears

[JobLeonard]

Unfortunately, to provide the type of integration it does, ganja.js relies on the ability to translate code at a source level. Neither C++ or C# offer that feature. (C# has reflection features but not at source level). Without those features it is a lot more difficult to implement an efficient and syntax friendly GA library. (several attempts exist for both those languages but they imho lack the simplicity and true-to-the-math syntax ganja.js can offer.)

You might like Julia. It's specifically designed to make custom mathematical operations easy to implement.

The only existing GA package for it hasn't been updated in five years, meaning it's probably broken and you still have a niche to carve out if you want to

EDIT: I keep mistakenly using MarkDown links here...

[Crimsontide]

I'm going through this playlist now:





If you have any other recommendations I'm all ears

Did I miss something?  He went through the whole wedge product explanation, properties, etc... and didn't show what e1 ^ e2 is.

[JobLeonard]

He did kind of skip over that, yeah. I didn't notice because I already understood the Wedge product from the first video in this topic.

[enkimute]

Hi Guys,

I'll be looking into Julia and their GA implementation. For those interested in exploring the subject of GA in a context of computer graphics or game engine programming, here's a short list of wacht-out-and-keep-in-mind :

1. The main 'school' in GA (Hestenes and co) - disregards the degenerate metric as 'inconvenient'
2. The degenerate metric is key to efficiently implement Projective Eucledian GA.
3. Projective GA is the smallest matrix-free euclidean model. (smallest = most performant).

The projective euclidean model gives you :

* direct algebraic representations of points, lines, planes.
* direct algebraic representations of rotations, translations, dilations.

so elements in 3D PGA as used in my examples can be :
 0-dimensional : scalars.
 1-dimensional : planes
 2-dimensional : lines.
 3-dimenaional : points.
 4-dimensional : pseudo-scalar.

The even subalgebra (elements with a 0-dimensional and a 2-dimensional component) represents rotations, translations, dilations.

Without degenerate metric, translations are not available and Hestenes and co use matrices instead and many authors that follow these conventions call their PGA (which would be elliptic or hyperbolic with a non-degenerate metric) euclidean while it is not. Then they'll tell you PGA isn't enough and you have to do CGA (for translations) .. don't be fooled by this.

CGA is a 2-up model. (requiring twice the storage and computing) .. the conformal model gives you :

* direct algebraic representations of points, lines, planes, point-pairs, circles, spheres
* direct algebraic representations of rotations, translations, dilations and boosts.

If you need to solve a problem where it is crucial to have a linear representation of circles/spheres, then the conformal model is the thing you need. (e.g. you have a bunch of points and need to find the circle that best matches them). Or for example a complex lens model (real lenzes often have dozens of rounded parts), will benefit greatly from CGA math. However - if you just need a model that does translations - CGA is total overkill.

For a rigorous introduction that does not ignore the degenerate metric, look for the work of Charles Gunn. (and note that Clifford himself also introduced the dual quaternions which are very much so dependent on a degenerate metric.)

I'm also happy to try and help out where I can.

Cheers,

Enki

-- without having seen the linked video, the key insight for 'e1^e2' is summarized by noticing that 'e1^e2' is not a scalar, its also not an 'e1' amount of 'e2' or an 'e2' amount of 'e1' - so its not of type 'scalar', or type 'e1', or type 'e2' - it is a new type of number - which we typically write as 'e12' but only because we're to lazy to keep writing 'e1^e2' .. repeating the procedure you would note that for example in R2 - that's where it ends .. wedging further will no longer create new types of numbers but just the types you already had. So the amount of types you can create like this is limited by the dimensionality of the space you're doing it in. (i.e. you can't fit a 3D object in a 2D space. (if this keeps bugging you look at the matrix representation of the minkowski plane - the basis matrices there correspond to scalar, e1, e2, e12 (and e21) - it is easy to see from the symmetries in those matrices how it works) --

-- sidenote .. the first video in this post - which I haven't watched either - has a very dubious statement on its title screen. A bivector is not two directions and a magnitude. A bivector is one two-dimensional thing - some authors say oriented area - it is a weighted (scaled) rotation in a plane. (translation if you rotate around infinity) .. the difference is important, as there are a whole set of vectors that when wedged create the same bivector - so  you can't extract the generating vectors from a bivector - and thus a bivector is not two directions .. its a whole family of two directions if you must put it like that. -- 

[Zaphos]

Geometric Algebra IK solver

Compare that to the response of the Geometric Algebra IK example on my page. There's no flips, jumps or unexpected behavior.

This is just a different algorithm -- sounds essentially like position based dynamics / the old hitman verlet ragdoll thing; I think people do this sort of thing often without GA, though I'm sure the code looks different.  BTW I think there's probably a degenerate case where it fails to follow the target correctly if the target is kept exactly collinear with the arm.

Also wow overloading scientific notation is ... uh ... wow

[enkimute]

This is just a different algorithm -- sounds essentially like position based dynamics / the old hitman verlet ragdoll thing; I think people do this sort of thing often without GA, though I'm sure the code looks different.  BTW I think there's probably a degenerate case where it fails to follow the target correctly if the target is kept exactly collinear with the arm.

Absolutely - its all about the how - not about the what. Implementing it without coordinates, chirality, and directly usable in any dimensionality.

Also wow overloading scientific notation is ... uh ... wow

lol - its the hacker in me - but you have to admit - for this its a match made in heaven

Cheers,

e.

[Morgarten]

I know that this will sound very child-ish, (It makes sense when you look at my age), but through the evolution of, let's take consoles for example, when the Atari 2600 came out, you would code it by doing this

XXXXXXXXX
0X0000XX0
XXX00X0XX
XXX00XX00

and so on...
And each "x" was a single pixel. Now, if you look at the poorly done example, that makes fairly large pixels, which meant less data it would take up on a single cartridge. And when the NES came out, there was much more data/memory on a single cartridge, which meant smaller pixels on a single screen.Pretty much every console after that just got more memory on a cartridge/disc until today, when a single disc for a PlayStation 4 could hold up to a few hundred thousand Gigabytes. So really you can't stray from the fact that the reason for video game evolution is just how much memory the system/cartridge/disc has. So, really, you could just throw the equation out the front door into a fire pit, and just focus on adding more memory onto the discs for games. But, now that I think about it, video games are already at the peak of realism, that's why Indie Games are getting popular, because people want a break from the realism. Again, I'm only 11, so don't judge my stupid thinking.

[enkimute]

I know that this will sound very child-ish, (It makes sense when you look at my age), but through the evolution of, let's take consoles for example, when the Atari 2600 came out, you would code it by doing this

XXXXXXXXX
0X0000XX0
XXX00X0XX
XXX00XX00

and so on...
And each "x" was a single pixel. Now, if you look at the poorly done example, that makes fairly large pixels, which meant less data it would take up on a single cartridge. And when the NES came out, there was much more data/memory on a single cartridge, which meant smaller pixels on a single screen.Pretty much every console after that just got more memory on a cartridge/disc until today, when a single disc for a PlayStation 4 could hold up to a few hundred thousand Gigabytes. So really you can't stray from the fact that the reason for video game evolution is just how much memory the system/cartridge/disc has. So, really, you could just throw the equation out the front door into a fire pit, and just focus on adding more memory onto the discs for games. But, now that I think about it, video games are already at the peak of realism, that's why Indie Games are getting popular, because people want a break from the realism. Again, I'm only 11, so don't judge my stupid thinking.

Hi Morgarten,

Never apologize for thinking. And keep doing it. There's much more going on than just a lot of data .. video games are only possible because a lot of mathematics gets inserted in between. But the amount of data we can process - which as you note keeps growing - is an important factor. However .. if we were to store the output - which is what you are suggesting - we would need immensely more storage than you'd think. For example, to output 1 second of full HD graphics data, your video card must output 1920*1080*4*60 = 497664000 bytes. That's 500 megabytes. Filling a DVD like that gives you about 10 seconds of 60fps full HD output. Lower the resolution and compress it really badly and a DVD will fit a couple of hours. That would be only one particular path/view/scenario .. in-game you like to move around, and shoot and whatnot .. so the total amount of data quickly becomes to much. The only way to do it is to calculate what needs to be on the screen as it happens .. and yes .. over the years the data we process while doing just that has grown .. we can process more polygons, more textures, more sounds, but even tho a PS4 disc may seem like a lot of data - it's really nothing compared to a couple of hours of game-play.

Keep thinking, and pay attention in math class !!

[Morgarten]

I knew someone would say that because I never really pay attention in math class, just mostly code on Khan Academy when we are supposed to be doing math, or math homework.

[Morgarten]

Pretty much what I meant to say was that gamer's don't need more realistic games, just better quality games, so this algebraic equation isn't really needed that much for modern and future games.