[HN Gopher] Exponentially Better Rotations (2022)
___________________________________________________________________
Exponentially Better Rotations (2022)
Author : fanf2
Score : 266 points
Date : 2024-06-14 20:42 UTC (1 days ago)
(HTM) web link (thenumb.at)
(TXT) w3m dump (thenumb.at)
| tmiku wrote:
| I've had a long work week and it's almost over and using the
| sliders to rotate this cow is exactly what I needed. I feel
| serene. Thank you.
| normcoreashore wrote:
| Lol yeah same. Glossed right over that wall of numbers
| romwell wrote:
| Then you may like playing with this too (if you're on the
| desktop):
|
| Press 1-6 on the keyboard for cubes to go all spinny
|
| https://romankogan.net/math/arcball_js/index.html
| totetsu wrote:
| I feel a low effort ios cashcow game is begging to be made
| banku_brougham wrote:
| Slidy-Cow
| beardbandit wrote:
| I can't describe how fast my eyes glazed over seeing all those
| numbers. The cow was very cute.
| GreedCtrl wrote:
| This is awesome. I was looking for a solution for averaging
| multiple rotations, and I found
| https://mathweb.ucsd.edu/~sbuss/ResearchWeb/spheremean/paper...
|
| This method looks a lot easier than that paper, at least at my
| level of math.
| romwell wrote:
| What's your context for _averaging_ multiple rotations?
|
| Averages are something that you can do with sums, where order
| of composition doesn't matter.
|
| Rotations don't commute, so the concept of _average_ as we
| understand it doesn 't normally apply to them.
|
| If you're holding a phone: rotate the screen _away_ from you
| 180deg (so you 'd be seeing the back), then clockwise 90deg
| relative to the ground (around vertical axis).
|
| Your camera will be facing your left.
|
| Now hold the phone normally, and do the same rotations in the
| opposite order. Your camera will now be facing your right.
|
| _Question_ : where should the camera be facing in the
| "average" of these two rotations?
|
| There's no single answer -- it depends on what you need from
| the average.
| stirfish wrote:
| Maybe it's Friday and my brain is cooked, but my camera keeps
| facing left in both cases.
| jonlong wrote:
| If you start with the phone _upright_ and rotate the screen
| away from you by turning the phone around the vertical
| axis, then both rotations are around the same axis and of
| course they do commute.
|
| My _guess_ is that romwell is holding the phone _flat_ , so
| that the rotation away from you is about a horizontal axis;
| then you should experience the noncommutativity.
|
| (The resulting orientations are 180 degrees apart, which
| indeed makes it difficult to say that any one orientation
| should be the unique average. But this is due to the
| geodesic structure of the space of rotations, not the
| noncommutative product that happened to construct these
| points, see above.)
| crote wrote:
| Draw a line on the screen from top to bottom. You
| interpreted "rotate away" as turning it around this axis,
| which is the _same_ axis you used for the 90-degree
| clockwise turn. You end up with the screen right-side-up,
| just facing away from you. It 's the same thing I
| intuitively did.
|
| Now draw a line on the screen from left to right. "Rotate
| away" by turning the phone around this new axis - so the
| top of the phone moves away from you, and the bottom of the
| phone moves closer to you. You end up with the screen
| upside-down, and also facing away from you.
| TeMPOraL wrote:
| Can confirm. Followed instructions, got the camera facing
| the same in both cases (left, with phone upside down). I
| interpreted the 180 part as flipping the phone around the
| horizontal axis.
| jonlong wrote:
| The most widely-used concept of "average" is surely a point
| that minimizes the sum of squared distances to each of a list
| of input points. Distances are canonically defined in the
| space of rotations, and so are averages in this sense (not
| always uniquely).
|
| Commutativity has nothing to do with this; do not confuse the
| typical formula for averaging with the reason for doing so!
| Of course, there are other senses of "average" (which
| generally do continue to apply to the space of rotations as
| well).
|
| The application for this given by GreedCtrl's reference is to
| spline interpolation. Another is in robotics, when combining
| multiple noisy observations of the orientation of an object.
| romwell wrote:
| _> Distances are canonically defined in the space of
| rotations_
|
| I am sorry, but this is simply not true.
|
| There are many distance/metric definitions that are
| applicable to the space of rotations, and the best _choice_
| of metric is defined by the application, which is why I
| asked that question.
|
| None of them is any more "canonical" than the other. See
| [1][2][3] for an introduction and comparison.
|
| [1] https://www.cs.cmu.edu/~cga/dynopt/readings/Rmetric.pdf
|
| [2] https://rotations.berkeley.edu/geodesics-of-the-
| rotation-gro...
|
| [3] https://lucaballan.altervista.org/pdfs/IK.pdf
|
| One will find there at least four "canonical" distance
| definitions, and applications ranging from optometry to
| computer graphics to IK (which is what you referred to).
|
| _> The most widely-used concept of "average" is surely a
| point that minimizes the sum of squared distances...Of
| course, there are other senses of "average" (which
| generally do continue to apply to the space of rotations as
| well)._
|
| I know this, not all of the readers may.
|
| What I don't know is what context the parent is coming
| from.
|
| Maybe all they need is interpolating between two camera
| positions - which is a much simpler problem than the paper
| they found (and what we're discussing) is addressing.
|
| _> The application for this given by GreedCtrl's reference
| is to spline interpolation. _
|
| It is not clear that the reference that they have found is
| actually the best for their application - they only said it
| was _something they found_ , and that the article we're
| discussing looks "simpler" for their level of mathematics.
|
| The article we are discussing does _not_ provide any means
| of "averaging" any more than two rotations, though, which
| motivated my question.
| chombier wrote:
| > >Distances are canonically defined in the space of
| rotations
|
| > I am sorry, but this is simply not true.
|
| It is true, there _is_ a canonical choice given by the
| bi-invariant Riemannian metric on compact Lie groups,
| such as rotations (in this case the shortest angle
| between rotations)
|
| Whether or not you want this metric in practice is
| another problem, of course.
|
| > The article we are discussing does not provide any
| means of "averaging" any more than two rotations,
|
| The Karcher/Frechet mean described in the original
| article does average more than two rotations
| jonlong wrote:
| The bi-invariant metric as pointed out by chombier is
| what I have in mind. I agree that a _non-canonical_
| metric may be the right one for some applications, but
| those are the exceptional ones. The bi-invariant metric
| (which has a simple, geometric meaning given by Euler 's
| rotation theorem) is the right starting point for
| thinking about distances in this space.
|
| (Your reference [2] supports this point of view: read
| "simplest" as "canonical". Your reference [1] claims five
| distinct bi-invariant metrics, but this is wrong. The
| argument given is that any metric related to a bi-
| invariant metric by a "positive continuous strictly
| increasing function" is itself bi-invariant, which is not
| true.)
| GreedCtrl wrote:
| I'm making a video game, and I want to map a joystick
| position to a rotation (of a sword). I have a set of
| keyframes for certain joystick positions, and I want to
| interpolate between the three nearest ones to create a
| continuous function from joystick position to sword rotation.
| chombier wrote:
| > Rotations don't commute, so the concept of average as we
| understand it doesn't normally apply to them.
|
| It does apply, considering that the Euclidean mean minimizes
| the sum of squared lengths to samples there's a fairly
| obvious generalization to Riemannian manifolds using geodesic
| distance.
|
| There are some reasonable assumptions to be made on the
| manifold and/or sample distribution to ensure convergence but
| in practice it works pretty well.
| lihaoyi wrote:
| The technique you are looking for is SLERP
| nine_k wrote:
| This is great. (Not only the cow part.).
|
| What I additionally appreciated is the fact that the methods end
| up computing a standard rotation matrix. If you need to rotate a
| million vectors, all you need to do is to apply these interesting
| calculations once, and then run your highly optimized matrix
| multiplication pipeline.
| romwell wrote:
| This talks about one of my pet peeves with a lot of 3D software:
| they don't use Arcball[1] interface for rotation.
|
| Autodesk products do (3DSmax, Maya), but Blender and OpenSCAD
| don't. And when I worked at Roblox, I couldn't convince the PM to
| let me implement it, because the users got by with whatever was
| there -- and if they wanted more, they could use _something else_
| (...which they did, and Roblox stock reflected that in 2022).
|
| Arcball is based on quaternions[2] (using exp for interpolation).
|
| It's the _only_ interface with these properties:
|
| 1. _Any_ rotation can be accomplished with a _single drag_
|
| 2. No gimbal locks
|
| 3. Tracing a closed loop with a sequence of drags results in
| coming back to where you started
|
| Once you formalize this, you can prove it mathematically
| (ultimately, this comes from unit quaternions giving a 2-cover of
| SO(3) in the same way unit complex numbers giving exactly the
| rotations of a circle).
|
| For anyone interested, here is my reference implementation of
| Quaternions / Arcball that you can play with on the page:
|
| https://romankogan.net/math/arcball_js/index.html
|
| The code is very-commented Java (Processing library, running in
| JavaScript by the magic of ProcessingJS).
|
| It's one way you can _feel_ the fancy math.
|
| Your hands and body will understand quaternions before your brain
| does.
|
| If you ever work on 3D software, _please_ use this, and thanks in
| advance <3
|
| [1] Arcball:
| http://courses.cms.caltech.edu/cs171/assignments/hw3/hw3-not...
|
| [2] Quaternions for rotations:
| https://en.wikipedia.org/wiki/Quaternions_and_spatial_rotati...
|
| [3] Arcball in Processing:
| https://romankogan.net/math/arcball_js/index.html
| Nathanba wrote:
| why does it feel so much worse when you don't drag from the
| middle and instead from the e.g right side? It feels stuck and
| sometimes it snaps. If the point from which rotations are
| calculated changes then I think it should somehow be visually
| obvious what this means for the rotation and be shown on the
| screen
| romwell wrote:
| Thanks for the feedback!
|
| Imagine you're spinning a globe with your finger. Obviously
| not much would happen if you poked _outside_ the globe.
|
| And while your finger is _on_ the globe, you can 't point at
| the sky (unless you finger is, well, stuck to the globe while
| you're rotating it - pointing to the sky would let go of the
| globe).
|
| This is what you're doing here, and absolutely, I should add
| a visual representation for the globe and where you're poking
| it when you hold the mouse button down.
|
| You feel "stuck" when the cursor attempts to leave the globe.
| And moving the cursor around that boundary is how you rotate
| around the axis facing poking from the screen.
|
| This behavior can be changed/customized to an extent, I
| picked what felt good to me here.
| nox101 wrote:
| > Imagine you're spinning a globe with your finger.
| Obviously not much would happen if you poked outside the
| globe.
|
| And this is why arcball is not a good solution. I'm not
| putting my finger on a global. I'm spinning a world,
| terrain, airplane, etc. There's no "ball" so arc"ball"
| doesn't fit.
|
| It gets worse. What if there is a ball but it's say 4 cm
| across on my screen. When I rotate with "arcball" am I
| touch that ball or some imaginary ball much larger than the
| visible ball. This problem exists all over depending on the
| thing I'm trying to rotate, arcball won't match.
| crote wrote:
| Oooh, yeah. This really bothered me too! Its behaviour is
| really intuitive when you strat with a drag from the middle,
| but even starting on the edge of the pink cube really makes
| it freak out.
|
| This essentially forces you to start from the middle, but
| then you don't seem to be able to do any rotation around the
| axis pointing out of the screen. To do that rotation your
| best bet is to click and drag around an inscribed circle -
| but that in turn means you can't rotate around any _other_
| axis in the same movement without running into freak-out
| behaviour. And anything between those two extremes doesn 't
| really behave intuitively.
| romwell wrote:
| Well, FWIW I increased the radius of the gizmo to 1/3 from
| 1/4, and made it visible.
|
| I'm still not handling drags outside the canvas area -
| those will cause jumps, but everything else should feel
| better.
| edflsafoiewq wrote:
| You probably clicked outside the ball. You can't see it, but
| the radius is 1/4 of the canvas width.
| kragen wrote:
| thank you for the arcball information! i didn't know about this
| Eduard wrote:
| any chance to make this work on mobile?
|
| I'm on mobile right now;
| https://asliceofrendering.com/camera/2019/11/30/ArcballCamer...
| helped me understand what arkball is about
| romwell wrote:
| >any chance to make this work on mobile?
|
| I wrote it a while ago with ProcessingJS, whose support for
| touch events was lacking.
|
| Will try to fix it and/or rewrite in P5JS, stay tuned :)
| Jarmsy wrote:
| Here's a nice arcball demo that does work on mobile (and also
| uses multi touch, which allows you to do things which are a
| pain with the single cursor of a mouse, like rotating about
| the camera axis)
| https://threejs.org/examples/misc_controls_arcball.html
| 6gvONxR4sf7o wrote:
| The lie group/lie algebra correspondence is one of the coolest
| things i wish i'd been taught in school. It's the exponential and
| log map in the article, but in a super reusable setting.
|
| You take some totally abstract thing you want to work with[0],
| say 3D rotations, but totally avoiding any details of specific
| coordinates that might get you into trouble. That's the lie
| group.
|
| Then you can derive representations of it in coordinates that
| behave nicely. This is called the corresponding lie algebra. Then
| for free you get a way to go back and forth between the
| coordinates and the abstract thing[1], and ways to compose them
| and stuff. Turns out that this is the exponential map and the log
| map talked about in the article. What's even cooler is that you
| can then compose them on either side, the abstract side or the
| coordinate side in a way that plays nicely. You get interpolation
| and averaging and all that in a fairly sensible way too in most
| cases you'll deal with as an engineer. And best of all, when you
| can phrase your problem as a combination of lie groups, you can
| just google for what their algebras are and get lots of work for
| free that would be tons of time to do yourself.
|
| [0] the thing has to be something with a notion of smooth change,
| plus a bit more structure it probably has.
|
| [1] going back and forth has some 'connected components' issues
| sometimes, but that's just another reason it's great to piggyback
| on known results.
| wyager wrote:
| > unit quaternions also don't form a vector space
|
| Unit quaternions are the lie group. If you want something you can
| add willy-nilly, you want the lie algebra of all quaternions,
| which represent rotational velocities, just as axis-angle
| represents rotational velocities.
|
| Comparing unit quaternions to axis-angle is a bit of a category
| error - it would be more appropriate to compare unit quaternions
| to rotation matrices, and all quaternions to axis-angle.
|
| > One advantage of using quaternions is how easy the exponential
| map is to compute--if you don't need a rotation matrix, it's a
| good option.
|
| You rarely need a rotation matrix at all when using quaternions.
| As mentioned in the article, you can compute rotations using
| `pqp^-1`.
|
| I think the easiest way to understand quaternions is just to read
| about geometric algebra. It took hundreds of years to invent
| quaternions, but once you understand geometric algebra (which is
| shockingly simple), you can invent quaternions in just a few
| minutes. I found this article to be a good intro several years
| ago: https://crypto.stanford.edu/~blynn/haskell/ga.html
| blt wrote:
| When you say "all quaternions" did you mean "pure imaginary
| quaternions"?
| wyager wrote:
| Oops, yes I did.
|
| For curious readers: `2` is a quaternion, but `exp(2)`
| doesn't generate a rotation, it generates 7.389... just like
| normal exponentiation on reals. So if you have a real term in
| your lie algebra, it will generate things that scale the
| object as well as rotating it.
|
| So instead you want only `ai + bj + ck`, as `exp(ai + bj +
| ck)` will always have magnitude 1
| cyber_kinetist wrote:
| I think the exponential map is still the most robust way to
| think about rotations, since it gives you tools to deal with
| the Lie group of SO(3) in the most straightforward way
| (switching between coordinates, dealing with differentiation
| and tangent spaces, etc.)
|
| Even when going through all the formulations with geometric
| algebra, you still land on using rotors (isomorphic to
| quaternions) and motors (isomorphic to dual quaternions) to
| represent SO(3) / SE(3) spaces - but I think for that purpose
| 3x3 rotation matrices / 4x4 transformation matrices with
| exponential maps are still much more useful. (Quaternions do
| have an advantage that it stores up less space and also faster
| to multiply with each other - but when you want to transform
| points with it then matrices are still faster. In overall in
| terms of efficiency it really depends on the situation.)
| deutschepost wrote:
| One of the coolest things I learned in university was that you
| can just put rotation matrices inside the state of a Kalman
| filter if you just override the + operator to take a matrix and a
| change in vector space and the -- operator to take two matrices.
| This allows you to estimate rotations without the fear of gimbal
| lock.
|
| https://openslam-org.github.io/MTK
| heavenlyblue wrote:
| Looks like gibberish advertising for the project
| deutschepost wrote:
| It's pretty hard to explain in short. But estimation
| algorithms don't work on angles for example. For an algorithm
| an angle is just a number. So the difference between 359 and
| 1 degree looks pretty big. It is also not possible to just
| put a rotation matrix inside a state, because the algorithm
| has no concept of orthonormality. But if you define the
| change of a state in terms of vectors and the state itself as
| a rotation matrix you can just use off the shelf estimation
| algorithms like least squares and Kalman filters. You just
| need to redefine the plus and minus operators. Which is
| nothing you need a project for. You can just do it yourself.
| KeplerBoy wrote:
| Then you have some reading to do.
|
| Sometimes technobabble is appropriate.
| roger_ wrote:
| Do you mean the tangent space of SO(2) as a state?
| deutschepost wrote:
| For simple angles you can use an element of SO(2) as your
| state. But if the algorithm calls for a difference of two
| states, the result would have to be an element of a real
| vector space (in this case a single number between -pi and
| pi). Analogue to this an addition of a state manifold and a
| vector also results in a state manifold. You can switch
| between those representations using the exp and log
| functions. In the papers these ,,new" operators are described
| as boxplus and boxminus. And the elegant thing of this
| approach is that in most cases you just would replace plus
| with boxplus and minus with boxminus and it just works(tm)
| porphyra wrote:
| Yeah implementing the "+" operator on the tangent space is
| pretty common not just for Kalman filters but also nonlinear
| optimization in general. The Ceres library supports
| LocalParameterization which does that.
| deutschepost wrote:
| Yeah LocalParametrization is exactly what they describe. The
| main contribution is a pretty slick mathematical model. When
| you use it everything just seems to work out.
|
| Also ceres is pretty great. LocalParametrization in
| combination with jets works like a treat for EKFs. You never
| have to worry about calculating jacobians on manifolds ever
| again.
| vendiddy wrote:
| It took me a long time to realize that, in the field of math,
| people come up with abstractions in the same way you might think
| of an abstraction in software engineering.
|
| I was confused as a kid. Why create imaginary numbers? What is
| the point of matrixes?
|
| It wasn't until later I realized that these representations were
| designed. If you make up this thing called an imaginary number,
| these calculations become easier. If you write linear equations
| like a matrix, it's a lot easier to reason about than writing out
| the full thing.
|
| It sounds obvious but nobody ever told me this!
|
| Just me?
| ndriscoll wrote:
| This continues to be true when you study more abstract math.
| e.g. "group" is an interface, and "a group" is any type with an
| operation that implements the 3 required properties/methods.
| Likewise with vector space, ring, metric space, category, etc.
| Math is full of interfaces as a "design pattern".
|
| (Interfaces in math are more like type classes and not
| inheritance in programming. e.g. the same set/type can be a
| group in more than one way.)
| delta_p_delta_x wrote:
| Awesome blog.
|
| Then I clicked on the author's profile, read another of their
| posts, and saw:
|
| > I first encountered programming sometime around 2010, when I
| was 9 years old.
|
| I was 13 in 2010, and trying to stuff secondary school maths and
| science into my head. Every time I see a cool computer graphics-
| related blog post, it's by someone younger and _way_ more
| talented than me.
|
| I feel extremely inadequate; my inner voice immediately went to
| something I can't really publicly say in case I get a dozen help-
| lines in response.
| anonymoushn wrote:
| It's not over for you, I self-taught some niche skills in the
| last couple years that some bigco apparently wants to pay for.
| I'm 35ish. Of course, I don't have any advice about how to do
| this, because I did it by really liking the thing and doing it
| all the time. But presumably some sort of structured practice
| would work too.
| Certhas wrote:
| I don't get the love of quaternions in this context. How are
| quaternions more intuitive than matrices?
|
| A matrix acts on a vector. Rotations act on vectors. What could
| be more natural than to look at rotations as matrices?
|
| The matrix exponential then makes all this intuitive to work
| with, if you connect it to solutions of ODEs: dx/dt = Ax has
| solution exp(t A). If A is skew symmetric, then the change in x
| is orthogonal to x at all times. So it's a rotation that doesn't
| change the length. (Alternative: apply a small orthogonal change
| over and over: (1 + delta A)^N x)
|
| Lie Groups/Algebras vastly generalize this, and you can call skew
| symmetric matrices geometric algebra, but that's not important.
| Important is that you generate rotations by continuously making
| orthogonal changes, and that the exponential map describes this
| process. I find this picture far more geometric and intuitive
| than anything else.
| setopt wrote:
| Might be worth pointing out that quaternions themselves are
| often represented as matrices as well: That's the Pauli
| matrices, widely used to model quantum spin.
|
| One advantage of quaternions is that it's (IMO) easier to
| calculate things with them using only pen and paper than it is
| to do equivalent matrix multiplications by hand.
|
| Personally I find them "intuitive" in the same sense as complex
| numbers are intuitive: They seemed weird on first exposure, but
| they now feel simpler to use and reason about than the
| alternatives I know.
| adgjlsfhk1 wrote:
| One advantage of quaternians from a computational perspective
| is that they are 4 numbers vs 9 for a 3x3 matrix (and applying
| the rotations has a similar reduction in flops)
| dahart wrote:
| The article explained a major advantage of quaternions over
| matrices. Quaternions interpolate well and matrices don't. This
| property is very important for animation and other things in
| computer graphics, like computing frames along a 3d spline
| curve.
| blt wrote:
| If you are referring to slerp, the matrix version is trivial
| using the log and exp maps. slerp(A, B, t)
| = exp(t log(B A^T)) A
|
| Something more complex like splines, I am not familiar with
| the algorithms used for quaternions. I would bet they use Lie
| algebraic operations, but do they actually use anything
| specific to quaternions?
|
| Not disagreeing that quaternions have some computational
| advantages over matrices, but most of the points people
| repeat as "advantages of quaternions" are really "advantages
| of proper Lie group/algebra operations over Euler angles"
| that are independent of matrix vs. quaternion representation.
| Certhas wrote:
| Very well put.
| Certhas wrote:
| The article also explains that the natural way to look at
| this property is in terms of matrix exponentials/logarithm.
|
| The space of rotation matrices is not a linear space. It's
| obvious that interpolation is meaningless there. The space of
| skew symmetric matrices is linear, so you can interpolate the
| generators of rotations naturally.
|
| Without this perspective, how do you even begin to understand
| what this interpolation does or what it actually means?
| porphyra wrote:
| The main advantage of quaternions is composing rotations.
|
| The analogy would be to 2D rotations with complex numbers. When
| you multiply two complex numbers, you're composing the
| rotations (in the 2D case: it ends up just adding the arg, or
| the phase angle). Likewise, multiplying two quaternions lets
| you compose the 3D rotations. This is a lot more efficient than
| multiplying two 3x3 matrices.
|
| For intuition, quaternions are closely related to the axis-
| angle representation which is the same as the Lie algebra
| so(3).
|
| As for acting on vectors, you can just think of different
| rotation parameterizations as implementations of the same
| abstract Rotation trait. A Rotation acts on vectors, composes,
| etc, in exactly the same way regardless if the underlying
| implementation is a matrix, a quaternion, euler vector, euler
| angles, gibbs vector, etc.
___________________________________________________________________
(page generated 2024-06-15 23:01 UTC)