11 ms·

Basic skeletal animation with geometric algebra

170 points by atomlib 7y ago

bufferoverflow 7y ago
How do you write an article on skeletal animation, and have zero examples of what that skeletal animation looks like?
- ninepoints 7y ago
  Working on them! That said though, the audience of this article was originally meant to be animation engineers that have already "earned some stripes" and wanted to see the GA formulation.
  - uglycoyote 7y ago
    I'm in the intended audience group then, as a game developer who works on animation regularly but only has a passing familiarity with geometric algebra. You could say I am "GA curious". But I'm afraid I didn't get much out of that article. I had hoped I would get more information about the benefits of using GA over standard matrix and quaternion methods. Instead, at the first mention of something GA related (which was motors) it was glossed over, as a hand wavy "don't worry about this". Later, pages of difficult math (which I skimmed over trying to find the punch line) were devoted to, if I understood, trying to do the equivalent of slerp that everyone is familiar with and is easy with quaternions (though perhaps just as complicated to derive). What I would have liked to have seen is an article that starts off with some motivation about what benefit one gets from looking at skeletal animation through this lense, for example, are there problems that vex people using standard methods which just don't occur when using GA?
    - ninepoints 7y ago
      Thanks for the feedback. You may find https://www.jeremyong.com/klein/geometry-potpourri/ https://www.jeremyong.com/klein/geometry-potpourri/ more approachable but I admit I don't have finalized material I'm completely satisfied with showing yet :( The math is definitely more easy to grok if you've seen/used Lie Algebra/Group formalisms before so that's another shortcoming, but the main thing GA gives us here is a "dual-quaternion slerp" which I literally could not find an implementation of anywhere! The formula for a quaternion slerp is actually not too hard to derive, but a dual-quaternion slerp is far more difficult. Part of the point of the post was that this was somewhat surprising to me (both that GA makes it approachable, and that dual-quaternion slerp implementations didn't exist in the wild).
      - uglycoyote 7y ago
        Thanks! I'm curious what motivated you to want to use a dual quaternion or why you want a slerp algorithm for that. I have yet to run across a use for a dual quaternion. Wikipedia says that they are used in mechanics to represent rigid transformations. That sounds useful for animation but most animation or computer graphics people would represent a rigid transformations with a quaternion and a translation vector, and if interpolating a rigid transformations they would slerp the quat and linearly interpolate the translation. So I'm not sure what the advantage of a dual quaternion would be in this context, or do you use dual quaternions in some completely different way?
        ninepoints 7y ago
        Thanks for the questions. Indeed many animation libraries store the quaternion and translation as separate components. There are a few reasons I use dual-quaternions in my own code. First, because I can "slerp" them, this means that when I compress keyframes, and can perform better quality fits (potentially less error and fewer keyframes needed). The dual-quaternion has uses in skinning which I'm sure you're aware of, but if the base transformation is a dual quaternion, I can more efficiently morph neighboring vertices as well (I've ported the dual-quaternion application to shader code as well). One optimization that GA makes clear is the ability to factor out terms when applying a dual quaternion to a number of entities all at once which makes it almost as efficient as a quat-translation while conserving energy as well. Finally, the dual-quat representation is beneficial when modeling kinematic motion specifically (not necessarily artist-authored) which can be useful in contexts beyond games (e.g. robotics, deep-learning, computer vision), but also inverse kinematics (which unfortunately I haven't had time to write about yet)
  - modeless 7y ago
    Might I suggest some WebGL demos? You should be able to compile Klein with emscripten fairly easily.
    - ninepoints 7y ago
      Yup that's a good suggestion. I actually don't even need to compile to wasm for much of it (I have it partially ported to GLSL already)
modeless 7y ago
Geometric algebra looks cool, and this library seems like exactly what is needed for graphics programmers to use it. What I'd really like to see is a comprehensive cheat sheet with formulas for common tasks in computer graphics with an absolute minimum of theory and jargon; even less than this article. Of course it's great to learn the theory too, but most people just call slerp in a quaternion library without learning the theory of quaternions. It should be possible to use a geometric algebra library in a similar way.
- iod 7y ago
  Maybe you want to check out a javascript implementation of GA math with Ganja.js. While not yet comprehensive to all the tasks you probably would want to see, it does have some good examples that you can play around with https://enkimute.github.io/ganja.js/examples/coffeeshop.html#pga2d_inverse_kinematics https://enkimute.github.io/ganja.js/examples/coffeeshop.html...
  - jiggawatts 7y ago
    That library pisses me off on a visceral level. The author "Enki Mute" is no doubt a brilliant mathematician, his library looks awesome, the online demos are unreal, but he's squandered his talent. The code he writes is unreadable gibberish. Zero useful comments. One-character variable names. Stringly-typed programming. Regex soup. It's psychotic. I tried to reverse-engineer it in order to write a SIMD-optimised Rust version. But fuck me. It's like disassembling the machine code of an obfuscated anti-cheat library. Even with good tooling and industrial-strength refactoring, I couldn't make enough sense of it to make any useful headway. Just try and read this. Seriously: https://github.com/enkimute/ganja.js/blob/master/ganja.js https://github.com/enkimute/ganja.js/blob/master/ganja.js What saddens me is that every other library I looked at was ancient and no longer maintained. Half wouldn't even compile. Most started with an explicit assumption that only 2D, 3D, or non-degenerate metrics are needed. Very few have efficient code-generation, and those that do are invariably C++ only, but I'm never going back there, even at gunpoint. Just shoot me now, I'd rather eat a bullet than face another STL compilation error that I have to decode from a linker error to do with __malloc() or some garbage I don't care about. Enki Mute's Ganja.js is the only recent GA library I've seen that ticks all the checkboxes, but when I opened it up, I faced only the unspeakable horror of yet another dead end. GA is going nowhere because everyone cooks up their own special version, the terminology is unique and special to each researcher, and most libraries stop just short of being useful. What we need is standardisation around a well-documented and extensible library with polyglot code-gen. Something with expression simplification, SIMD, and both maths-centric and 3D graphics optimised capabilities. Ganja.js is not it, unfortunately.
ninepoints 7y ago
I'm the author of Klein and was surprised to see a sudden burst of traffic so I checked the usual suspects and ended up here :) My goals for authoring Klein was to provide a library for performing all manner of geometric operations using the language of Geometric Algebra. The benefits are that the formulism is exception-free (meaning, for example, parallel planes have a well-defined line of intersection, that projections to higher/lower grade entities make sense, etc), and works equally well on points, lines, and planes. Practitioners coming from robotics/animation will also find the entirety of the Lie algebra/group inside GA as well for smooth interpolation, etc. As a graphics engineer, I found most libraries out there unsuitable because of performance reasons. We're used to having nicely packed SIMD optimized quaternions for example. Klein fills this gap and (hopefully) in a manner where you can use it even if you don't understand the Geometric Algebra (yet!). Over time, I'd like to round out the documentation to explain the underlying theory, which I find unreasonably elegant and has shifted my thinking in the last few years. Let me know if you have any questions about Klein or geometric algebra!
- throwaway17_17 7y ago
  I saw a post in the last month or so on the front page of HN that linked a video lecture and a paper/presentation on GA, it’s still sitting in my watch/read folder unfortunately. So, since you volunteered for questions, I’ll ask a few: - is there a generally accepted, or just personally approved, set of introductory materials on GA, to get one up to speed? I have a decent mathematics background, but I have been focusing on other areas recently so I am a bit rusty. - I think your goals for Klein look interesting, and since you are a graphics engineer, I assume you are aware of the prior art (your comment indicates this is correct), so, is the main draw of using GA as an implementation theory the elegance of the underlying math alone, or does the math create a new space for potential optimization in the graphics space (I am assuming that your mention of performance penalty in existing implementations is due to a lack of focus on performance not unsuitability of GA to a performance domain).
  - throwaway17_17 7y ago
    As a quick note: I think your last comment up thread answered my second question reasonably well, it posted while I was writing my comment. But any additional details you want to share will be welcome.
enkimute 7y ago
Just a heads up - @ninepoints let me know he got rate limited and will answer as soon as allowed again ;)
duchess_toffee 7y ago
Ninepoints is getting repeatedly rate-limited. He invites anyone with questions to ask questions in the Klein discord (https://discord.gg/gkbfnNy https://discord.gg/gkbfnNy)
- ninepoints 7y ago
  The mods emailed me a couple hours ago and said my account was mistakenly flagged as a "spam" account but its been since corrected. Thanks!

170 points by atomlib 7y ago

bufferoverflow 7y ago

How do you write an article on skeletal animation, and have zero examples of what that skeletal animation looks like?

ninepoints 7y ago
Working on them! That said though, the audience of this article was originally meant to be animation engineers that have already "earned some stripes" and wanted to see the GA formulation.
- uglycoyote 7y ago
  I'm in the intended audience group then, as a game developer who works on animation regularly but only has a passing familiarity with geometric algebra. You could say I am "GA curious". But I'm afraid I didn't get much out of that article. I had hoped I would get more information about the benefits of using GA over standard matrix and quaternion methods. Instead, at the first mention of something GA related (which was motors) it was glossed over, as a hand wavy "don't worry about this". Later, pages of difficult math (which I skimmed over trying to find the punch line) were devoted to, if I understood, trying to do the equivalent of slerp that everyone is familiar with and is easy with quaternions (though perhaps just as complicated to derive). What I would have liked to have seen is an article that starts off with some motivation about what benefit one gets from looking at skeletal animation through this lense, for example, are there problems that vex people using standard methods which just don't occur when using GA?
  - ninepoints 7y ago
    Thanks for the feedback. You may find https://www.jeremyong.com/klein/geometry-potpourri/ https://www.jeremyong.com/klein/geometry-potpourri/ more approachable but I admit I don't have finalized material I'm completely satisfied with showing yet :( The math is definitely more easy to grok if you've seen/used Lie Algebra/Group formalisms before so that's another shortcoming, but the main thing GA gives us here is a "dual-quaternion slerp" which I literally could not find an implementation of anywhere! The formula for a quaternion slerp is actually not too hard to derive, but a dual-quaternion slerp is far more difficult. Part of the point of the post was that this was somewhat surprising to me (both that GA makes it approachable, and that dual-quaternion slerp implementations didn't exist in the wild).
    - uglycoyote 7y ago
      Thanks! I'm curious what motivated you to want to use a dual quaternion or why you want a slerp algorithm for that. I have yet to run across a use for a dual quaternion. Wikipedia says that they are used in mechanics to represent rigid transformations. That sounds useful for animation but most animation or computer graphics people would represent a rigid transformations with a quaternion and a translation vector, and if interpolating a rigid transformations they would slerp the quat and linearly interpolate the translation. So I'm not sure what the advantage of a dual quaternion would be in this context, or do you use dual quaternions in some completely different way?
      - ninepoints 7y ago
        Thanks for the questions. Indeed many animation libraries store the quaternion and translation as separate components. There are a few reasons I use dual-quaternions in my own code. First, because I can "slerp" them, this means that when I compress keyframes, and can perform better quality fits (potentially less error and fewer keyframes needed). The dual-quaternion has uses in skinning which I'm sure you're aware of, but if the base transformation is a dual quaternion, I can more efficiently morph neighboring vertices as well (I've ported the dual-quaternion application to shader code as well). One optimization that GA makes clear is the ability to factor out terms when applying a dual quaternion to a number of entities all at once which makes it almost as efficient as a quat-translation while conserving energy as well. Finally, the dual-quat representation is beneficial when modeling kinematic motion specifically (not necessarily artist-authored) which can be useful in contexts beyond games (e.g. robotics, deep-learning, computer vision), but also inverse kinematics (which unfortunately I haven't had time to write about yet)
- modeless 7y ago
  Might I suggest some WebGL demos? You should be able to compile Klein with emscripten fairly easily.
  - ninepoints 7y ago
    Yup that's a good suggestion. I actually don't even need to compile to wasm for much of it (I have it partially ported to GLSL already)

modeless 7y ago

Geometric algebra looks cool, and this library seems like exactly what is needed for graphics programmers to use it. What I'd really like to see is a comprehensive cheat sheet with formulas for common tasks in computer graphics with an absolute minimum of theory and jargon; even less than this article. Of course it's great to learn the theory too, but most people just call slerp in a quaternion library without learning the theory of quaternions. It should be possible to use a geometric algebra library in a similar way.

iod 7y ago
Maybe you want to check out a javascript implementation of GA math with Ganja.js. While not yet comprehensive to all the tasks you probably would want to see, it does have some good examples that you can play around with https://enkimute.github.io/ganja.js/examples/coffeeshop.html#pga2d_inverse_kinematics https://enkimute.github.io/ganja.js/examples/coffeeshop.html...
- jiggawatts 7y ago
  That library pisses me off on a visceral level. The author "Enki Mute" is no doubt a brilliant mathematician, his library looks awesome, the online demos are unreal, but he's squandered his talent. The code he writes is unreadable gibberish. Zero useful comments. One-character variable names. Stringly-typed programming. Regex soup. It's psychotic. I tried to reverse-engineer it in order to write a SIMD-optimised Rust version. But fuck me. It's like disassembling the machine code of an obfuscated anti-cheat library. Even with good tooling and industrial-strength refactoring, I couldn't make enough sense of it to make any useful headway. Just try and read this. Seriously: https://github.com/enkimute/ganja.js/blob/master/ganja.js https://github.com/enkimute/ganja.js/blob/master/ganja.js What saddens me is that every other library I looked at was ancient and no longer maintained. Half wouldn't even compile. Most started with an explicit assumption that only 2D, 3D, or non-degenerate metrics are needed. Very few have efficient code-generation, and those that do are invariably C++ only, but I'm never going back there, even at gunpoint. Just shoot me now, I'd rather eat a bullet than face another STL compilation error that I have to decode from a linker error to do with __malloc() or some garbage I don't care about. Enki Mute's Ganja.js is the only recent GA library I've seen that ticks all the checkboxes, but when I opened it up, I faced only the unspeakable horror of yet another dead end. GA is going nowhere because everyone cooks up their own special version, the terminology is unique and special to each researcher, and most libraries stop just short of being useful. What we need is standardisation around a well-documented and extensible library with polyglot code-gen. Something with expression simplification, SIMD, and both maths-centric and 3D graphics optimised capabilities. Ganja.js is not it, unfortunately.

ninepoints 7y ago

I'm the author of Klein and was surprised to see a sudden burst of traffic so I checked the usual suspects and ended up here :) My goals for authoring Klein was to provide a library for performing all manner of geometric operations using the language of Geometric Algebra. The benefits are that the formulism is exception-free (meaning, for example, parallel planes have a well-defined line of intersection, that projections to higher/lower grade entities make sense, etc), and works equally well on points, lines, and planes. Practitioners coming from robotics/animation will also find the entirety of the Lie algebra/group inside GA as well for smooth interpolation, etc. As a graphics engineer, I found most libraries out there unsuitable because of performance reasons. We're used to having nicely packed SIMD optimized quaternions for example. Klein fills this gap and (hopefully) in a manner where you can use it even if you don't understand the Geometric Algebra (yet!). Over time, I'd like to round out the documentation to explain the underlying theory, which I find unreasonably elegant and has shifted my thinking in the last few years. Let me know if you have any questions about Klein or geometric algebra!

throwaway17_17 7y ago
I saw a post in the last month or so on the front page of HN that linked a video lecture and a paper/presentation on GA, it’s still sitting in my watch/read folder unfortunately. So, since you volunteered for questions, I’ll ask a few: - is there a generally accepted, or just personally approved, set of introductory materials on GA, to get one up to speed? I have a decent mathematics background, but I have been focusing on other areas recently so I am a bit rusty. - I think your goals for Klein look interesting, and since you are a graphics engineer, I assume you are aware of the prior art (your comment indicates this is correct), so, is the main draw of using GA as an implementation theory the elegance of the underlying math alone, or does the math create a new space for potential optimization in the graphics space (I am assuming that your mention of performance penalty in existing implementations is due to a lack of focus on performance not unsuitability of GA to a performance domain).
- throwaway17_17 7y ago
  As a quick note: I think your last comment up thread answered my second question reasonably well, it posted while I was writing my comment. But any additional details you want to share will be welcome.

enkimute 7y ago

Just a heads up - @ninepoints let me know he got rate limited and will answer as soon as allowed again ;)

duchess_toffee 7y ago

Ninepoints is getting repeatedly rate-limited. He invites anyone with questions to ask questions in the Klein discord (https://discord.gg/gkbfnNy https://discord.gg/gkbfnNy)

ninepoints 7y ago
The mods emailed me a couple hours ago and said my account was mistakenly flagged as a "spam" account but its been since corrected. Thanks!