Exponentially Better Rotations | Hacker News Reader

Exponentially Better Rotations

thenumbat.github.io

285 pointssigna1160 comments

All of this touches on maybe 1% of the potential of geometric algebra: https://bivector.net

I would strongly suggest watching some talks about it: https://bivector.net/doc.html

For example a rigid body simulator in n-D in ~40 LOC, 20 of which are boilerplate defining the points of a cube: https://youtu.be/5R2sv9GCwz0?t=371 (in an environment that defines the geometric algebra for you - but only that, it's no different than using a library that provides quaternions for you, for example). This is possible because geometric algebra is powerful enough to unify and interpolate not just rotations as one object, but generalize rotations, reflections and translations (and more) as one object (a motor), embedded in an algebra unifying position, velocity, (angular) momentum, torque and force. If it doesn't make sense how that works, watch the earlier talks in the series.

And it gets more general, the above talk is about PGA which embodies flat (object) Euclidean geometry, but CGA also embeds spheres and circles in the algebra, allowing any conformal transformation to be represented natively in the algebra. This is very powerful for (inverse) kinematics in robots with fixed rotating arms, for example: https://www.youtube.com/watch?v=j2x_TG8E3_k

The problem for me is that, as a computer scientist, I'm focused on the numerical representation of things. Geometric algebra is presented by omitting that until the last second and instead focusing on abstract concepts and how they fit together. For example, they say "A vector is an oriented scalar value" and that already confuses me. Obviously I know what a scalar is, a scalar is one number, but what is "oriented"? Is it N numbers for the e0,...,en-1 axes? Is it N^2 numbers forming a rotation matrix? Is it just N numbers for the vector and we only call it "oriented"?

I would like to see geometric algebra explained from the bottom-up - starting from the numerical representation of the objects they talk about and explaining how it gives rise to the properties they're looking for.

> Obviously I know what a scalar is, a scalar is one number

Hang on, is that a Natural number, or a signed Integer? Is it place-value, and if so what's the base? Big- or little-endian?

Is it fractional, and if so is it a rational (numerator and denominator), or fixed-point (what precision?), or float (how big's the mantissa?); maybe it's a unum? How about a sequence of continued fractions?

This is tongue-in-cheek; but from a software perspective, all those representations have the same "API" (arithmetic). Likewise, geometric algebra is an "API"; that's essentially what an algebra is.

I think the GP is trying to make the point that, a scalar in most numerical physics contexts is either a real or complex double precision floating point number(like a double), but they don't see how someone would represent a vector in this geometric algebra(a matrix in Eigen? or a vector in Eigen? myself I would just use a vector, but the GP was interested in the oriented part and seeemed confused). I believe they were looking for an example of someone using this in practice to solve a real problem and have some explanation of the choices made.

> Hang on, is that a Natural number, or a signed Integer? Is it place-value, and if so what's the base? Big- or little-endian?

I fail to see how that makes any sense. OP clearly referred to the unidimensional nature of a scalar in contrast to the n-dimensional nature of a vector, or the n*m-dimensional nature of a matrix. It makes no sense to try to go off on a tangent regarding, say, the resolution of a scalar representation. Perhaps the concept of a ray gets halfway there. Perhaps the concept of a line at infinity.

The concept of a scalar is familiar, as is the concept of a vector. Using the terms "scalar with a direction" to describe a vector makes no sense if you come from that starting point. Perhaps magnitude+direction vector rings a bell, because that's also a basic description of a vector.

Perhaps the author made a mistake, or does not have a good math background, or is filing in his knowledge gaps by coming up with definitions . Or perhaps he's actually referring to different concepts that the readership is not familiar. Who knows?

> This is tongue-in-cheek; but from a software perspective, all those representations have the same "API" (arithmetic).

This assertion is quite wrong. Both scalar and vector, in this context, are data types. Describing a data types as a data type of a data type is meaningless and does not compute.

> The concept of a scalar is familiar, as is the concept of a vector.

> Using the terms "scalar with a direction" to describe a vector makes no sense if you come from that starting point.

Now I'm confused: what is a vector, if not a "scalar with a direction" (or indeed "an oriented scalar value", as the parent quoted)?

> Both scalar and vector, in this context, are data types. Describing a data types as a data type of a data type is meaningless and does not compute.

I disagree; "scalar value" is an interface, supporting addition, multiplication, negation, etc. (e.g. https://hackage.haskell.org/package/base-4.16.1.0/docs/Prelu... https://smlfamily.github.io/Basis/real.html ). Many data structures can implement this interface (Float, Double, Rational, Fixed, Nat, Int, etc.).

Likewise, "vector" is an interface, supporting vector addition, scalar multiplication, and (crucially in this context) inner, wedge and geometric products. Many data structures can implement this interface (e.g. a tuple of scalars, as coefficient of a fixed orthonormal basis; a scalar length paired with angular spreads projected in fixed perpendicular planes; etc.)

So to make this familiar, you're probably used to traditional coordinate vectors in geometry. For example a 3D vector [x, y, z]. This seems sane enough, but is actually somewhat ambiguous. Which cardinal direction map to x, y, z respectively (e.g. is z for up/down or forwards/backwards)? What direction do the axes point, e.g. is +z away or towards us? To make it unambiguous, we can define three oriented basis vectors. That is, each basis vector defines what the unit is in that direction, and which way is "positive". So I could write [3, 2, 9] as 3*xunit + 2*yunit + 9*zunit.

Now in geometric algebra we also have oriented basis vectors. So they determine the unit, and the direction of the embedding space (note that this not necessarily map directly to points in your world space, which becomes especially clear when you start doing projective geometry, e.g. in 3D PGA you represent lines in your world as planes in the embedding space). Rather than xunit, yunit, etc, they are simply called e1, e2, ..., en.

The key difference is that geometric algebra has the exterior product, notated ^. For example, e1 ^ e2 is the exterior product of two oriented basis vectors. You can interpret this as being an oriented basis for the space spanned by e1, e2. And similarly for e1 ^ e2 ^ e3 being an oriented basis of the volume spanned by e1, e2, e3, etc. These are called basis blades.

The most general closed numerical representation of an object in geometric algebra is the multivector. Just like a traditional vector is just a bag of K coefficients for K basis vectors, a multivector is a bag of 2^K coefficients for the 2^K basis blades, one for each possible combination of the exterior product of the K basis vectors.

> So to make this familiar, you're probably used to traditional coordinate vectors in geometry. For example a 3D vector [x, y, z]. This seems sane enough, but is actually somewhat ambiguous.

The concept of a coordinate system is not ambiguous. You have dimensions, and each can be represented as a vector that complies with specific properties, such as linear independence.

> Which cardinal direction map to x, y, z respectively (e.g. is z for up/down or forwards/backwards)?

That's a function of whatever coordinate transformation you wish to apply.

Nevertheless, I vaguely recall from school the concept of an oriented vector space and direct coordinate system, whose definition was something like the cross product of consecutive director vectors resulted in a positive vector (right-hand rule) i.e., the direction of z is determined unambiguously by the direction of x and y.

> Now in geometric algebra we also have oriented basis vectors.

If I'm not mistaken, oriented referential systems are covered in intro to euclidean geometry classes.

> The key difference is that geometric algebra has the exterior product, notated ^. For example, e1 ^ e2 is the exterior product of two oriented basis vectors. You can interpret this as being an oriented basis for the space spanned by e1, e2. And similarly for e1 ^ e2 ^ e3 being an oriented basis of the volume spanned by e1, e2, e3, etc. These are called basis blades.

Sounds like a convoluted way to refer to basic concepts like direction vectors of a direct coordinate system.

Quite bluntly, this all sounds like an attempt to reinvent euclidean geometry following a convoluted way. I mean, what does all this buy you that applying a subset of affine transformations (scaling, translation, rotation) to an orthogonal coordinate system doesn't give you already?

> Quite bluntly, this all sounds like an attempt to reinvent euclidean geometry following a convoluted way

I think that's the idea.

> I mean, what does all this buy you that applying a subset of affine transformations (scaling, translation, rotation) to an orthogonal coordinate system doesn't give you already?

Well, algebra: with the geometric product one can solve geometric equations in a nice, unified way.

Can you give an example ifna nice solution to a problem?

This wikipedia page has some, e.g. https://en.wikipedia.org/wiki/Comparison_of_vector_algebra_a...

> Quite bluntly, this all sounds like an attempt to reinvent euclidean geometry following a convoluted way. I mean, what does all this buy you that applying a subset of affine transformations (scaling, translation, rotation) to an orthogonal coordinate system doesn't give you already?

It is attempting to reinvent Euclidean geometry, yes. I don't think it's convoluted though.

To give a prime example, take the article we're commenting on: interpolating rotations. Or more generally: interpolating transformations. Just doing this with rotations without suffering gimbal locks already brings you to quaternions. Are quaternions 'convoluted'?

The fact that all objects are native to the algebra means they're composable. Take for example this slide of the formula of a 4D torus in coordinates, and in 4D PGA: https://i.imgur.com/T4hofL2.png The talk in general has a bunch of example applications: https://youtu.be/tX4H_ctggYo?t=4232

Questions such as "the intersection of this line and this plane", "the line through two points" "the circle where these two spheres intersect", "the point at the intersection of three planes", "the projection of this line on this plane" and such are trivial, native (the resulting object is part of the algebra) and exception-free in geometric algebra. E.g. two planes always intersect, it just happens that the intersection is a line at infinity if they're parallel.

The exact same code used to translate and rotate a point around the origin can be used to translate and rotate a line, or a plane around the origin.

Also note that most of computer graphics already realizes that embedding our geometric space into a larger space is useful. Projective geometry (embedding 3D into 4D) is already everywhere, because it unifies translations and rotations into a single concept (matrix multiplication). Geometric algebra simply goes a step further.

Thanks for the last paragraph, I would also like to know. To me it looks as well as linear algebra with a lot of smoke and mirrors.

There's no smoke. But there surely are mirrors. (Group theory joke)

The traditional approach to explaining geometric algebra is "bottom up": first the types of things that the theory is about (building on vector spaces), then details of operations that make sense, then how to perform useful computations in the light of useful things that have been proven, then actual code (with a detailed knowledge of its specifications).

People are nitpicking you, but you’re right that the presentations do tend to omit or underemphasize concrete computation. Part of this is lineage, in that it’s related to differential geometry where much of the point is that you are abstracting away computational aspects like coordinates. But to do much of the fun stuff, you need coordinates, which the community would do well to connect better with the abstractions.

Interesting is how this applies to interpolation with industrial robotic arms.

Shortest path for each joint moving from a -> b does not create a linear path for the end-effector of the robot. Linear end-effector movements require inverse kinematics and are limited by how fast the slowest joint can move.

Quaternions are also useful because you often don’t care the particular rotation you approach and object with, just the angle/direction so you can leave theta as an arbitrary value.

I wrote another blog post on the topic, with lots of pictures and simple explanations:

Intro to Lie groups for rigid rotations https://daniel.lawrence.lu/blog/y2021m07d14/

> lots of pictures and simple explanations

Just some observations on that:

- a random picture of Le petit Prince doesn't make it easier to understand

- there's a huge difference between people that don't know that you'll end up in the same place if you keep walking on a sphere and those that won't quit at "closure: A \oplus B is still in the group".

- "Rotations in 2D" doesn't explain things, it just states them. It requires reasonable understanding of all concepts.

- There are also detractors, like "However, locally, they are like \mathbb R^1, a trivial 1-dimensional Euclidean space." It isn't clear why that is meaningful.

This is not meant as criticism, just to point out that the entry level for your blog might be higher than you think/intended.

Thanks, very useful feedback!

Is dllup able to generate equation references with named labels, like the way LaTeX uses \label and \ref? (I looked at the "References" section of the dllup documentation, and it looks like you have to know the equation number that is going to get generated, e.g., #eq3., but I'm wondering if there is alternative syntax.) If not, is there an alternative format for putting math on the web that you like that supports this?

(Just asking in case I ever move away from my ancient Wordpress installation with the QuickLaTeX plugin.)

When compiling dllup to LaTeX, it is possible to just use \label but I haven't implemented that functionality in dllup to html yet.

You can also consider pandoc's markdown flavor that supports equations and references:

https://pandoc.org/MANUAL.html#pandocs-markdown

Thanks!

Often these pieces are written for the author's benefit, to help them sort out a topic in their head, more so than as a genuine attempt at education.

Thus, they tend to be at the level of the author rather than some imagined audience. That isn't wrong or anything I think. Not every piece of written text needs to be understandable by everyone.

> - a random picture of Le petit Prince doesn't make it easier to understand

The post has 5 pictures, 4 technical pictures plus the picture of Le petit Prince that is whimsical while simultaneously illustrating a non-trivial point.

> This is not meant as criticism,

This is clearly criticism. You intend it as constructive criticism, and that's great, but it's criticism.

Thanks. That was really nice!

What made the Lie exponential click for me is the definition of exp as a limit: exp(x) = (I + x / n)^n when n goes to infinity.

A tangent vector x at the identity is split in n chunks, each chunk is added to the identity to get a matrix (I + x / n). Each of these matrices gets increasingly closer to the group as n increases, and these n matrices are composed together to approximate exp(x), in a similar fashion to forward Euler integration with n iterations and integration step 1/n.

The actual formula ends up being the usual power series and is useful for computations, but I find the limit above really captures the essence of how the exponential works.

I highly recommend this paper for a more in-depth treatment of exp/log map and the related representation of transformations:

A Micro Lie Theory by Joan Sola, Jeremie Deray, Dinesh Atchuthan https://arxiv.org/pdf/1812.01537.pdf

A warning, though: trying to switch from a mathematician's idea of Lie groups and algebras to a physicist's, or anyone else's, is not easy. I am a mathematician with a research specialty in Lie groups, and I remember being asked a question about this paper—I can't remember what it was, or I would be more specific—a while ago that was mathematically easy to answer, but where most of the time it took me to answer was spent in decoding the notation.

This treatment is closer to the mathematician's than to the physicist's, but it still has some of the physics flavor about it—for example, it at least implicitly discusses Lie groups as if they come with a preferred action, which they need not—and, if you're not in this domain already, it's good to know what difficulties you can face later if you try to move between domains.

From reading on mobile (so might have missed the clarification) it also seems to do the standard mistake in physics literature to assume the exponential map is surjective so the log map is defined on the whole group (which they call M?).

This is not always true, I think sl2(R) is an example of a connected, non compact group such that the exponential map is not surjective.

Thanks, I just realized I was also assuming exp to be surjective as well, I stand corrected.

The Wikipedia page[1] mentions the issue briefly but I was curious of the counter-examples. IIUC, matrices in SL(2) with trace < -2 have two distinct eigenvalues, one of which is negative[2], and such matrices cannot be reached by exponentiating elements of the Lie algebra sl(2) (traceless matrices).

[1] https://en.wikipedia.org/wiki/Exponential_map_(Lie_theory)#S...

[2] https://en.wikipedia.org/wiki/SL2(R)#Classification_of_eleme...

I found this nice accessible proof for the interested: https://planetmath.org/slnrisconnected

Is this part of the proposition: x=exp X, and x having a double eigenvalue implying that X has a double eigenvalue somehow clear? How do you prove it?

Yeah, about 10 years ago I was reading one of the earliest papers applying these ideas to computer vision and I was pretty confused, as I never had any exposition to Lie group/algebras in my engineering undergrad. So I tried to read mathematical texts on this subject and I was 100x more confused! Would have been useful to article like the GP's one back then.

I enjoyed this article and thought it gave a nice summary of techniques for rotation. It did leave me with a feeling of skepticism towards a few of its points.

Most of all I feel like I don't understand the usefulness of the defined map. The article does admit that computing and interpolating quaternions is very practical. The one use case given for this map over quaternions is averaging a set of rotations.

This isn't something I've regularly had to do. The closest I can think of is handling multiple competing orientation constraints in a physics solver. This is something we did at my first job and while I didn't look closely at the code I know it was neatly handled using quaternions.

I've worked a fair bit with 3D data in a robotics context, mostly from the perception side but also a tiny bit on the motion side (and grad coursework). In practice you have to deal with pretty much all the representations, they all have their pros/cons and in some cases more than one works fine, so different libraries will use different representations and you have to convert back and forth all the time (a fun source of bugs!). In an academic context, I feel like the community has converged on matrix exponential representation. One reason, I think, is that it's fairly good for optimization with gradient-based approaches, which is useful on its own but also meshes well with deep learning tools that are increasingly becoming more common for 3D perception (and motion planning) tasks.

I work with game development and used to work in medical simulation. Most projects I've been on use primarily matrices for most transforms with quaternions used to handle pure rotations, transformed to matrices at the last possible stage.

The dual-complex numbers have a similar use-case. You can use them to interpolate between two rigid body motions in 2D. There's some interesting infinity/infinitesimal phenomena there, with translations (a type of rigid body motion) being represented as rotations whose centre point is at projective infinity and whose angle of rotation is infinitesimal. The name of the number system is unfortunate though, I have to admit.

In spite of all this, I haven't heard of anyone using these for anything. I do though have a use-case for a problem I'm working on. I also wrote the Wikipedia article on DC numbers, so I'm kind of biased here.

These are also called the planar quaternions and are the even subalgebra of 2D PGA. I use and explain these (and their nD generalisations) in my SIBGRAPI 2021 talk on kinematics and dynamics in PGA.

https://youtu.be/pq9YfdPHhIo

There is also a writeup called 'may the forque be with you' available on bivector.net

Looks like there's been some progress on this front since I last looked.

Maybe Wikipedia needs to be updated.

Seeing Euler's formula [1] elegantly come into play was very satisfying! Posts like these are why I love HN.

[1] https://en.wikipedia.org/wiki/Euler's_formula

Oh you can absolutely average rotation quaternions, even weighted. You just use regular online computation of mean, express it in terms of linear mix operations (x k + (1-k) y) and then use quaternion slerp for the linear mix:

  mean = zero_rotation_quaternion
  wsum = 0
  for w,qt in zip(weights, quaternions):
    wsum += w
    # regular online mean computation:
    # delta = qt - mean
    # mean := mean + delta*w/wsum
    # express as linear mix:
    # mean := mean + qt*w/wsum - mean*w/wsum
    # mean := mean * (1-w/wsum) + qt*w/wsum
    # i.e. mean is linear mix between mean and qt, with k=w/sum
    mean = slerp(mean, qt, w/wsum)
  return mean

Except the quaternion product is non-commutative, so the result of your algorithm will depend on the ordering of your `quaternions` array (which may be acceptable in practice), whereas Karcher mean does not.

The quaternion product is non-commutative, but quaternion addition is commutative. As far as I can tell he just takes weighted averages, which is a commutative operation.

Rotations in 3D are inherently non-commutative, so whenever you work with multiple axes, the order matters. Interpolating between two rotations is a special case because you're not actually rotating the rotation operators themselves.

> As far as I can tell he just takes weighted averages, which is a commutative operation.

It works when doing LERPs (linear interpolations) but the algorithm above uses SLERPs (spherical interpolations) which can be expressed with quaternion products/exponentials/logarithms, so I think the order does matter.

A quick numerical check with 3 quaternions and uniform weights seems to confirm this.

Slerp is no binary operator, but suppose we only look at the two quaternions, then it is "commutative". You can swap both quaternions, but you must use (1-t) for the interpolation factor instead of just t.

Wikipedia[1] lists some equivalent formulas for quaternion slerp:

  slerp(q0, q1, t) = (q0 * q1^(-1))^(1-t) * q1
  slerp(q0, q1, t) = (q1 * q0^(-1))^t * q0

There you can see that quaternion products are used, yes, but the operation is also commutative, when using (1-t) instead of t.

When the order in online average computation is different, the t naturally adapts to the correct value, depending on the weights.

These arguments about commutativity and order are really just the same as for regular linear interpolation (LERP) and online average computation.

[1] https://en.wikipedia.org/wiki/Slerp#Quaternion_Slerp

Yes, SLERP is commutative along one-parameter subgroups by definition. The problem arises as soon as more than two quaternions are to be averaged using the above procedure.

Again, using 3 quaternions and uniform weights with the above algorithm gives slerp(slerp(a, b, 1/2), c, 1/3) but medians in a spherical triangle don't cross at 2:1 ratio in general.

Hm yes. I also played with a few a examples. I have to admit, the order seems to only be really irrelevant when averaging rotations around one axis to avoid triangles. Thanks for pointing out. For averaging rotations that are similar the differences are tiny, but still. What a bummer.

For anyone looking into this, Rotation Averaging by Hartley et al. (2011) is a must-read on the subject of rotation averaging: https://users.cecs.anu.edu.au/~hartley/Papers/PDF/Hartley-Tr...

I've been screwing around with a hand-crafted software rendering engine, and using a good old fashioned 4x4 matrix seems to give me everything I am looking for in this project.

I do find the math and applications of quaternions to be elegant in theory, but there is a bit of a blackbox/theoretic veil that is harder to penetrate compared to a matrix representation (at least for me). The matrix also gives me all 3 things at once - rotation/scale/transform. Somewhere in my programmer brain this abstraction feels really nice to work with.

Edit: This old & controversial article is what convinced me to stick with matrices for now: https://www.gamedev.net/tutorials/_/technical/math-and-physi...

Is the math rendering in this blogpost done using Jekyll and AcademicPages, as described here

https://kevinfossez.github.io/posts/2020/04/blog-post-1/

Or is it something else?

The real nugget in all that is the geometric algebra link towards the bottom, almost as a throwaway. It would be nice if that was expanded in the same way as the rest of the sections.

If you want an inspiring (imho) overview of the power of geometric algebra, I thoroughly enjoyed the video "A Swift Introduction to Geometric Algebra"

https://youtu.be/60z_hpEAtD8

The formulation in that of Maxwell's equations as a single simple GA equation was pretty cool. I was curious though about how it would change if magnetic monopoles were discovered, but did not pick up enough on one watching of that video to figure out how to add that myself.

A bit of Googling turned up this article [1] which includes that.

[1] https://ieeexplore.ieee.org/iel7/5/6879517/06876131.pdf

Great post. The rendering applets dont seem to work in Firefox. Safari an Chrome both work great.

Applets work well on firefox desktop for me.

Same, unusable on Chrome/Android, using the first horizontal slider scrolls the entire page, then the text rendering went completely nuts. Had to close the page.

For me, on Android, Firefox works(enough), Chrome doesn't.

Thank you for giving me spinning cows to start my day.

And Matrix math, holy cow (heh), it's been a long time since I needed that.

Ah I thought this would be a written piece about medical students' third and fourth years of their teachings :)

Reply on news.ycombinator.com