[HN Gopher] Look, ma, no matrices
___________________________________________________________________
Look, ma, no matrices
Author : grgrdvrt
Score : 244 points
Date : 2024-02-28 14:51 UTC (8 hours ago)
(HTM) web link (enkimute.github.io)
(TXT) w3m dump (enkimute.github.io)
| ebolyen wrote:
| The interpolation of animations at the bottom is really neat, but
| I can't help but wish the models were a little less _active_ on
| the rest of the page. Math is plenty hard without a small
| elephant cheerleader.
| orangesite wrote:
| Au contraire my friend, if it were not for the elephantine
| encouragement I would not have made it to the end of the page!
| <3
| blt wrote:
| if the author is reading this: please define the acronym PGA when
| first using it!
| at_compile_time wrote:
| Projective geometric algebra for anyone wondering. A null basis
| vector is added to the basis vectors of the space you're
| working in. This allows the algebra to represent geometric
| objects that do not pass through the origin.
| epistasis wrote:
| I've been working through a bunch of Geometric Algebra on the
| web and YouTube lectures in recent weeks. Though I guessed
| Projective Geometric Algebra, I still wasn't certain as it's
| the first time I can recall seeing the acronym!
| lupire wrote:
| This called "affine transformation" in linear algebra
| language. (Linear algebra is stretches and rotations. Affine
| (affinity?) adds translations)
|
| https://people.computing.clemson.edu/~dhouse/courses/401/not.
| ..
|
| In 2 dimensions:
|
| Rotation = multiplying by an imaginary unit.
|
| Stretches = multiplying by a real number
|
| Translation = adding a complex number.
|
| In higher dimensions, the analogy to complex numbers breaks
| down.
| xeonmc wrote:
| It is not affine transforms _per se_ but rather the
| expansion into homogeneous coordinates that enables
| translation by treating it as if it 's a shear that leaves
| the reciprocal dimension untouched.
|
| > Rotation = multiplying by an imaginary unit.
|
| This is also not quite right.
|
| Rotation is multiplying by a complex number with a
| magnitude of 1 (or perhaps you meant to say "raising a
| number to the power of i"?)
| enkimute wrote:
| done. mea maxima culpa.
| guhcampos wrote:
| Yes! The use of FPGA for "Fast PGA" was particularly confusing.
| enkimute wrote:
| Apologies. Had that joke sitting around for waaaay to long.
| Not that great in retrospect :D
| corysama wrote:
| It's fun that there have been many approaches to interpolating
| rotations (geometric algebra, quaternions, even full-matrix
| interpolation [1]). But, after hand-optimizing the code, the
| final code ends up mostly the same for all approaches. The
| difference is in your understanding of the rules and
| capabilities.
|
| From what little I know, GA seems like the most consistent and
| capable approach. It's unfamiliar. It's a bit much to take in
| getting started. But, people who clear that hurdle love it.
|
| Alternatively, everybody uses quaternions while complaining they
| don't understand them and need a whole book to visualize them.
| (Visualizing Quaternions by Andrew J. Hanson, Steve Cunningham)
|
| [1]https://www.gamedev.net/tutorials/programming/math-and-
| physi...
| lupire wrote:
| Naive Lie Theory is a great book, and the first chapter teaches
| quaternions.
|
| https://www.goodreads.com/en/book/show/4419538
| dustingetz wrote:
| also Physics from Symmetry spends 1/3 the book on lie theory
| passing through quaternions
|
| https://www.amazon.com/Physics-Symmetry-Undergraduate-
| Lectur...
| epistasis wrote:
| I'm not a mathematician, and don't have a ton of use for
| geometry in my work, but was learning GA for fun, and have
| similarly tried to learn quaternions in the past. GA is fun,
| quarternions are not fun. I _think_ I understand GA, but I
| _knew_ I did not understand quaternions after working through
| lectures and problems. Now that I know some GA, I kind of feel
| like a I know quaternions, finally.
| zoogeny wrote:
| One of my favorite math/graphics YouTube creators Freya Holmer
| did an excellent intro to Geometric Algebra not that long ago
| [1]. If you have any interest in 3d graphics (especially but no
| limited to splines/Bezier curves) then be sure to check out all
| of their videos.
|
| I personally have always struggled with linear algebra and I tend
| to find these Clifford Algebra approaches much more intuitive.
|
| 1.https://www.youtube.com/watch?v=htYh-Tq7ZBI&ab_channel=Freya...
| karmakaze wrote:
| This is who I thought this was going to be. I enjoyed this
| along with the Splines & Beziers ones. Such great presentation,
| never feels rushed but gets to the point.
| aaronblohowiak wrote:
| the splines yt video
| (https://www.youtube.com/watch?v=jvPPXbo87ds) is (IMHO) one
| of the best educational videos on a programming topic, full
| stop.
| Quekid5 wrote:
| I'd like to point out that the YT comments have some good
| (weird for YT, I know!) clarifications and questions about bits
| where she did go a bit fast or skip over things, e.g. the non-
| commutativity of products (in general) and such.
|
| Great video.
| simpaticoder wrote:
| What a wonderful talk, thanks. It reminded me of
| https://enkimute.github.io/ganja.js/ which is actually a
| library by enkimute, the OP! (It's quite a remarkable library
| too, by being a single file, no-build script that supports N
| dimensional algebras along with render support.)
| rhelz wrote:
| Geometric Algebra was a complete mystery to me until I finally
| realized: it is just polynomial multiplication, but with some
| quantities for which the order of multiplication matters, and
| which have a weird multiplication table: i*i = 1, i*j = -j*i.
| That's it. Most intros present geometric product of two vectors:
|
| (x1*i + y1*j) * (x2*i + y2*j)
|
| as some deep mysterious thing, but its just the same FOIL
| polynomial multiplication you learned in freshman algebra:
|
| (x1*i + y1*i)(x2*i+y2*j) = x1*x2*i*i + x1*y2*i*j + y1*x2*j*i +
| y1*y2*j*j
|
| = (x1*x2 + y1*y2) + (x1*y2 - y2*x1)*i*j
|
| The quantity in the first parenthesis, above, is the our old
| familiar dot product. The quantity in the second parenthesis is
| our old friend the cross product, but expressed in a new
| dimension whose basis is i*j, and which--unlike the cross product
| --generalizes to any number of dimensions. In GA its called the
| "wedge product".
|
| Once you "get" that, you find that doing things like deriving
| rotation formulas, etc, become easy, because you can apply all
| the skills you developed in algebra to solving geometric
| problems.
| skhunted wrote:
| Your comment is interesting to me. A few days ago someone asked
| why math classes don't the how and why and rather tend to just
| present the formulas for the operations and tell people to
| compute. Here you are focusing on what the operations do rather
| than on why they work. It's an interesting contrast and one
| that teachers of mathematics have to balance. The two
| questions,
|
| How does it work?
|
| Why does it work?
|
| Can't always both be answered well in a given course.
| rhelz wrote:
| // focusing on what the operations do rather than why //
|
| YMMV, of course, but in general, I always found it easier to
| understand the _why_ once I understood the _what_ and the
| _how_ , rather than the other way around.
| skhunted wrote:
| Yes. Usually, though, when someone complains about the
| teaching of mathematics they say we focus too much on how
| to do the operations and not enough on why they work the
| way they do. I agree it is much easier to understand why
| after knowing how.
| noqc wrote:
| One of the things that it takes the longest to learn in
| mathematics is that most things are defined in the dumbest way
| possible.
|
| In particular, if (over a vector space V) you want to define a
| bilinear product m:V x V -> V, this is exactly the same thing
| as deciding on m just over pairs of basis vectors. If I were to
| call that "the universal property of the tensor product", you'd
| probably say "uh huh".
| ndriscoll wrote:
| It's annoyingly one of those things that once you understand,
| you can't see how you didn't understand it before. e.g. the
| tensor algebra (aka free algebra) over a vector space is
| "just" the dumbest possible multiplication: if i and j are
| basis vectors, then i*j = i[?]j. No further simplification
| possible. j*i*i*j = j[?]i[?]i[?]j, etc. with associativity
| and distributivity and linearity: (5i+3j)*k = 5i[?]k +
| 3j[?]k, etc.
|
| Then, if you have a dot product, a Clifford algebra is "just"
| the tensor algebra with a single simple extra reduction rule:
| For a vector v, v*v = v[?]v. So now e.g. `kjiijl =
| kj(i[?]i)jl = kjjl = k(j[?]j)l = kl = k[?]l`, which can't be
| reduced further.
|
| The real magic is that it turns out you can prove[0] that
| ij=-ji for two basis vectors i,j, so e.g. (ij)^2 = ijij =
| -ijji = -ii = -1. So `ij` is a square root of -1, as is `ik`
| and `jk` (but they're different square roots of -1), and you
| get things like complex numbers or quaternions for free, and
| suddenly a ton of geometry appears (with `ij` corresponding
| to a chunk of plane in the same way a basis vector `i` is a
| chunk of line/arrow. `ijk` becomes a chunk of volume. etc.).
|
| But it's all "just" the dumbest possible multiplication plus
| v*v = v[?]v.
|
| [0] Proof: (i+j)^2 = i^2+ij+ji+j^2 = 1+ij+ji+1 = 2+ij+ji. But
| also (i+j)^2 = (i+j)[?](i+j) = i[?](i+j) + j[?](i+j) = 2. So
| 2 = 2+ij+ji, so ij=-ji.
| simpaticoder wrote:
| In another comment, they pointed out https://youtu.be/htYh-
| Tq7ZBI?si=lOmsCL2DoqUCQgh1&t=1540 in which Freya did an
| excellent job reducing the number of axioms to 1: If you define
| multiplying a vector by itself to be equal to the length of the
| vector, squared, then everything else falls out of simple
| polynomial multiplication. It's quite lovely.
| nh23423fefe wrote:
| "contraction axiom" for those looking to google
| spenczar5 wrote:
| Are these algorithms efficient even given GPUs? I have the vague
| impression that GPUs are well-tuned for matrix work. Are those
| advantages lost when using Geometric Algebra formulations, so you
| actually dont come out ahead?
|
| This is uninformed speculation, go ahead and correct me!
| buildartefact wrote:
| This is exactly what the article is about. TLDR they can be
| roughly equivalent
| rhelz wrote:
| When you are programming, you have to figure out:
|
| 1. What quantity you want to calculate, and 2. What the most
| efficient way to calculate it is.
|
| PGA (once you spend the--alas--not insubstantial overhead to
| understand it!) is a really good way of doing #1. Its virtually
| always a good idea to first try out the simplest and easiest to
| code up implementation anyways.
|
| And what you get from using PGA to do #1 will certainly be good
| enough for you to prototype out the rest of your program enough
| to be able to benchmark it and find out where the real
| bottlenecks are. Happily, in most cases it will _also_ either
| be the fastest way to calculate it, or close enough to not be
| the bottleneck.
|
| And if _is_ a bottleneck, it gives you a deep understanding of
| the problem you are trying to solve--which, IMHO, is a good
| idea to have before you just start trying to shave off cycles
| in hopes of getting it fast enough.
| hamish_todd wrote:
| It's an extremely common misconception that because GPUs have
| matrix matrix and matrix vector products in the standard, that
| means GPU companies must be accelerating them.
|
| In fact, because it is SIMD across the shader cores already,
| you can't necessarily do this. Some GPUs do, some don't
| nox101 wrote:
| GA seems great! But ...
|
| > and modern formats like Khronos' glTF use quaternions for all
| their rotation needs. Fantastic for animations, and generally
| considered worth the cost of the unavoidable conversions to and
| from matrices.
|
| Quaternions are bad for animation. Animate a clock going from 9am
| on Monday to 6pm on Friday. Euler angles this might be expressed
| as from 0 degrees to 1620 degrees. With Quaternions, nope. This
| can't be expressed in gLTF. It can be in Unreal an Unity, both of
| which default to use Eular for animation. In gLTF you're required
| to bake it into smaller turns, all less than 180 degrees.
| enkimute wrote:
| For specifying animations, you should work in the quaternion
| lie algebra, not in the group as you suggest. There you can
| represent 1620 degrees without any problem. Furthermore, in the
| quaternion Lie algebra (pure imaginary quaternions), and only
| in that space, you can take an arbitrary rotation key, multiply
| all 3 of its values with 10 and get 10 times that rotation
| without change in axis.
|
| If you rotate around just one axis, the Lie algebra feels just
| like Euler angles .. in fact its exactly the same thing, but if
| you rotate around more than one .. it keeps working intuitively
| and usably - Euler angles absolutely do not.
| hn8305823 wrote:
| Also, the use case for quaternions depends on how many times
| you will be applying the same rotation. If it's a few or
| dozens of times then maybe not the most efficient. If it's
| million or billions then you are going to want to use
| quaternions.
|
| This is mainly due to the cost of converting to and from the
| rotation vector.
| xeonmc wrote:
| i.e. keep it in vector form if you're combining them a lot,
| convert to polar form when you want to work with angles
| hamish_todd wrote:
| Unity uses quats in its object transforms?
| nox101 wrote:
| But not in it's animation data, at least not by default
|
| You key euler angles, it lerps euler angles for animation
| values, it then generates a quaternion the given the current
| value of the euler angles. Same for Unreal AFAIK
| hamish_todd wrote:
| Where in the docs does it say that? Euler angle lerps, in
| the general case (eg none of the starts or ends are 0),
| look like complete shit.
|
| You need the log quat representation. Exp( T _log(q1 /q0) )
| _ q0
| contravariant wrote:
| To be honest I've never really liked how GA results in all kinds
| of mixed elements if you're not careful what you multiply with
| what. Requiring up to 2^n terms for what was an n-dimensional
| space seems a bit hard to deal with.
|
| It seems like it should be better able to deal with geometry
| (i.e. inner products), but I've never really found a good
| argument why you wouldn't just use the wedge product and the
| hodge star (or musical isomorphisms).
|
| Even something 'magic' like turning a bivector "u^v" into a
| rotation in that plane "e^(u^v)t" is essentially just using the
| musical isomorphism to turn the 2-form u^v into a linear
| automorphism, allowing you to make sense of "e^(u^v)t" as a
| matrix exponential.
|
| Another example that often gets mentioned is the ability to turn
| maxwell's equations into a single equation, but since the use of
| differential forms already makes it possible to summarize it into
| two equations which hold for _very_ different reasons I never
| understood the utility of combining them into one equation.
| rhelz wrote:
| // Requiring up to 2^n terms for what was an n-dimensional
| space//
|
| Sometimes, the economy is illusory, e.g. normal vectors
| transform differently than position vectors do. Sure, you can,
| if you want, use the same data structure to represent both of
| them, but you'll still have to have _some_ way of keeping track
| what kind of vector it is holding, as well as sprinkle special
| cases throughout your code to handle each one differently.
|
| GA, takes the bull by the horns by having vectors use one basis
| (i,j,k) for vectors, and another basis (j*k, k*i, i*j) for the
| other.
|
| // never understood the utility of combining them into one
| equation //
|
| This is a good example of how having a higher-dimensional space
| actually gives you better economy of storage than a lower
| dimensional space does: one equation is better than two, or
| four :-)
|
| And electric fields are different from magnetic fields in quite
| the same way as vectors are different from bivectors. You can
| either "special case" them by using a different equation for
| Electric and Magnetic fields, or you can treat them uniformly
| with one.
| chombier wrote:
| A somewhat simpler way of keeping track in the case of
| normals is to use row vectors for, well, covectors, which is
| what normals are anyways.
|
| What GA brings is the ability to express linear combinations
| of scalars, vectors, bi-vectors ... Whether this is actually
| useful/desirable in practice is another story though.
| rhelz wrote:
| Yeah, but the original commenter's objection was it seems
| weird to, e.g. use a 6-dimensional space to represent
| 3-dimensional quantities.
|
| Doing it by using vectors and covectors _still_ requires
| you to keep track of 6 degrees of freedom, i.e, 6
| dimensions. Eventually everybody has to pay the piper :-)
| jacobolus wrote:
| The #1 thing that GA brings is the ability to divide by
| vectors, which makes working many things out on paper
| dramatically simpler.
| hamish_todd wrote:
| The mixed elements are the important ones!
|
| A quaternion with w=1, x,y,z=0 is just the identity.
|
| A quaternion with w=0, x=1, or perhaps w=0, x=y=0.7, those
| would only ever be rotations by 180 degrees.
|
| If you want arbitrary rotations, you need some combination of
| the two: "a little bit of 180 around this line, and a little
| bit of 0deg rotation/identity". That's what it means to have
| scalar and bivector.
|
| If you "being careful" with wedge and inner to avoid mixtures
| you are doing it wrong. Geometric product is the boss, and
| makes excellent mixtures!
| pasabagi wrote:
| What a great article! Not an area of special interest of mine,
| but the piece was a joy to read.
| enkimute wrote:
| Thank you, appreciate that!
| lawrenceyan wrote:
| This gives me PTSD
| DrDroop wrote:
| What! Why?
| turtledragonfly wrote:
| For people interested in this topic, here's a good set of slides
| going over Grassman/Clifford/Geometric algebra concepts:
| http://www.terathon.com/gdc12_lengyel.pdf
|
| And another good site: https://mattferraro.dev/posts/geometric-
| algebra
| enkimute wrote:
| don't foget the fantastic Sudgy 'A swift introduction to
| projective geometric algebra' :
| https://www.youtube.com/watch?v=0i3ocLhbxJ4
|
| and ofcourse the go-to reference https://bivector.net
|
| or join 1000+ profs, researchers and enthusiasts on the
| bivector discord here https://discord.gg/vGY6pPk
| e4m2 wrote:
| The author of that talk, Eric Lengyel, also wrote the book
| "Foundations of Game Engine Development, Volume 1:
| Mathematics". Its 4th chapter focuses on the same topics.
___________________________________________________________________
(page generated 2024-02-28 23:00 UTC)