News for hackers. Stuff that matters.
Re:Let's remove Quaternions from every 3D Engine by modeless on Friday November 02, 2018 @05:16PM (#18366851)
Hmm, the word "interpolate" does not appear in the article. One of the main applications of quaternions in games is interpolating rotations. Does this representation interpolate well?

Also, I've seen several articles trying to convince me that alternative transformation representations like these are better, but I haven't seen much code. Has anyone written a library using these concepts that could replace a traditional vector math library like https://glm.g-truc.net/ for games?

Re:Let's remove Quaternions from every 3D Engine by nanofortnight on Friday November 02, 2018 @05:50PM (#18367054)
Yes, it does, because it is an identical representation to quaternions. Except it actually explains all the weirdness in quaternions without resorting to 4-space.

This is because quaternions are a subalgebra of geometric algebra in 3-space.

Re:Let's remove Quaternions from every 3D Engine by MerryMage on Friday November 02, 2018 @06:08PM (#18367150)
Yes.

You can prove, for two rotors R1 and R2, that slerp(R1, R2, t) = R1 (R1^-1 R2)^t.

Re:Let's remove Quaternions from every 3D Engine by enriquto on Friday November 02, 2018 @06:37PM (#18367293)
there is nothing weird about 4-space, what do you mean?
Re:Let's remove Quaternions from every 3D Engine by glenneroo on Friday November 02, 2018 @11:16PM (#18368477)
Re-read what you are replying to - they didn't say 4D-space is weird but rather that quaternions are weird:

> all the weirdness in quaternions without resorting to 4-space

Re:Let's remove Quaternions from every 3D Engine by marctenbosch on Friday November 02, 2018 @05:44PM (#18367011)
Yes, anything you can do on quaternions you can do on rotors. (Updated the article)

I have not seen a clean version of the code online but it is almost the same as for a quaternion.

Re:Let's remove Quaternions from every 3D Engine by scotty79 on Friday November 02, 2018 @07:36PM (#18367606)
Great post although it made me hungry for explanation what are the actual implementation differences between rotors and quaternions because I got the impression that we use exactly same real numbers to do exactly same things. We just imagine basis of this transformation space not as some 4 orthogonal vectors, just 3 orthogonal unit planes plus one real number for scaling.

Those bivectors just explain (incredibly, amazingly well) what quaternions are and why they have properties they have. It doesn't seem to change how you crunch the numbers to get what you want.

...

It's really great that you wrote that post. I feel like for the first time I truly understand rotations in 3D and know why I felt something fishy was going on with results of vector product and expressing rotations with them.

Re:Let's remove Quaternions from every 3D Engine by marctenbosch on Friday November 02, 2018 @08:04PM (#18367740)
99% of the time this is true.
Re:Let's remove Quaternions from every 3D Engine by forrestthewoods on Friday November 02, 2018 @08:34PM (#18367907)
I’d love to see a small GitHub repo that contains Rotators and Quaternions with compared results.
Re:Let's remove Quaternions from every 3D Engine by jacobolus on Friday November 02, 2018 @08:41PM (#18367934)
The results are going to be the same. The arithmetic involved is literally identical.

The real power of the GA version is that you can more clearly geometrically explain what is going on, and you can generalize everything to pseudo-Euclidean spaces or to lower or higher dimensions. GA gives you some more algebraic tools to work with, so when you are trying to write your proofs they are clearer and more concise.

Re:Let's remove Quaternions from every 3D Engine by forrestthewoods on Friday November 02, 2018 @08:53PM (#18367984)
I believe you.

I work in code all day. I have a lot of code that works. I’d love to see code that also works but is easier to understand.

If someone wants to remove something from every 3d engine then I’m going to need to see what the replacement looks like. In actual code.

Re:Let's remove Quaternions from every 3D Engine by halfjoking on Friday November 02, 2018 @11:46PM (#18368568)
I don't believe him.

I got a C- in Linear Algebra in college... I remember my Linear Algebra prof saying "maybe I'm being pedantic" when explaining a concept and I was like "wtf are you even talking about?"

I avoid all Math - and I think black boxes are great. The few times I've used functions with quaternions in game programming (I'm not a game programmer) they seemed really easy to use. I'm skeptical that a concept that is easy to understand for people with a Math background is easier to use in code for people like me.

Re:Let's remove Quaternions from every 3D Engine by Mindless2112 on Saturday November 03, 2018 @08:05AM (#18369817)
> The arithmetic involved is literally identical.

So to "remove Quaternions from every 3D Engine" all we need to do is rename the "Quaternion" datatypes to "Rotor" and we're done?

Re:Let's remove Quaternions from every 3D Engine by PeterisP on Saturday November 03, 2018 @05:14AM (#18369346)
If the results are going to be the same, then what's the possible benefit for any user of a 3D engine?

Things like the ability to "generalize everything to pseudo-Euclidean spaces or to lower or higher dimensions", algebraic tools and writing proofs are not relevant to the needs that a 3D engine serves - 3D engines are written to fulfil requirements of engine users (not even engine writers), who won't be doing such things, that's below the abstraction level that's handled by the engine. So from that perspective we're comparing GA-filled black box with a quaternion-filled black box, and either (a) the GA box has better performance; or (b) the GA box has different results that are arguably more correct; or (c) the GA box has a substantially easier API; or (d) the GA box is useless.

It seems to me that you might be aiming at the (c) benefit with all the arguments that this math is easier to understand, but I'm not entirely convinced based on the article; perhaps an illustration of the expected code differences in using a non-quaternion GA-based engine (are there any?) would be helpful. If we can have an engine/API that's easier to understand for beginners and that makes all the basic tutorials simpler, then that would be a nice thing to have.

Re:Let's remove Quaternions from every 3D Engine by vanderZwan on Saturday November 03, 2018 @05:52AM (#18369437)
> If the results are going to be the same, then what's the possible benefit for any user of a 3D engine?

If it is going to be compiled down to the same binary code, what's the possible benefit of any higher level language?

Re:Let's remove Quaternions from every 3D Engine by PeterisP on Saturday November 03, 2018 @06:13AM (#18369491)
From the possible options I listed above, (c), a substantially easier API.

On the other hand, if it's not exposed to the user, it doesn't particularly matter what structures and math that higher-level language uses behind the scenes to do what it does; most aspects of compiler theory are irrelevant for users of high-level languages.

Re:Let's remove Quaternions from every 3D Engine by vanderZwan on Saturday November 03, 2018 @10:12AM (#18370220)
If the people maintaining the black boxes I rely upon have an easier job keeping it functioning and correct, I would say that is very relevant to me
Re:Let's remove Quaternions from every 3D Engine by jayshua on Friday November 02, 2018 @05:52PM (#18367063)
Don't know if the article has been updated since your post, but Interpolation and Gimbal Lock are both called out as working with Rotors in the 5th paragraph.

> The change is simple and the code remains almost the same. Anything you can do with a Quaternion, such as Interpolation and avoiding Gimbal lock, you can do on a Rotor. But the understanding grows a lot.

Re:Let's remove Quaternions from every 3D Engine by boinkers on Saturday November 03, 2018 @02:28AM (#18369010)
> Has anyone written a library using these concepts

Yes, the C++ library you're looking for is here http://versor.mat.ucsb.edu/

Re:Let's remove Quaternions from every 3D Engine by modeless on Saturday November 03, 2018 @02:40AM (#18369037)
Neat, thanks!
Re:Let's remove Quaternions from every 3D Engine by defen on Friday November 02, 2018 @05:54PM (#18367071)
You can take the logarithm of a rotor in order to do interpolation. If you want a transformation represented by a rotor R to happen in N steps, you can apply R ^ (1/N) N times. The Nth root of R is exp(log(R)/N)
Re:Let's remove Quaternions from every 3D Engine by jacobolus on Friday November 02, 2018 @07:56PM (#18367712)
And if you don’t want to take the logarithm per se, you can bisect the rotation A by taking the sum of your rotor + 1, and then normalizing the result by dividing by the magnitude, (A + 1) / |A + 1|. Or if you have two rotors A and B, you can interpolate halfway between by taking (A + B) / |A + B|. This requires seven additions, four multiplications, one division, and one square root.
Re:Let's remove Quaternions from every 3D Engine by raphlinus on Friday November 02, 2018 @08:08PM (#18367767)
I would replace the last two operations by another multiplication and one reciprocal square root. There is extensive SIMD support for very fast approximations, and getting better in newer chips.
Re:Let's remove Quaternions from every 3D Engine by jacobolus on Friday November 02, 2018 @08:20PM (#18367836)
Yes of course. I just mean, conceptually that is what is required. You can replace a bunch of the multiplications and additions by FMA instructions as well.

By the way Raph, I think you might be interested in this draft paper I have been working on (well, not working on for the past two months, but anyway...)

https://beta.observablehq.com/d/e639659056145e88

Re:Let's remove Quaternions from every 3D Engine by raphlinus on Friday November 02, 2018 @08:40PM (#18367930)
Very cool! Some of the later sections are broken. The fact that this is interactive is great, maybe I'll get around to putting my stuff in this form.
Re:Let's remove Quaternions from every 3D Engine by jacobolus on Friday November 02, 2018 @08:44PM (#18367951)
The broken parts are intentionally commented out, either now redundant or not finished yet. (Observable isn’t the best for version control / etc. yet.)

There are still a bunch of diagrams to make but I got a bit stalled on the project after going on a trip (and taking care of a toddler full time).

There are still a couple of research problems to figure out. In particular how to best set the tangent and curvature at the knots. Just fitting circles through triples of points isn’t the best method.

But I think this thing should compare favorably to Spiro curves for some use cases: in particular it is pretty local, a bit more robust to pathological inputs, and a lot simpler to compute (and explain). (But of course isn’t going to be globally optimizing for some smoothness metric, and isn’t extensional.)

Edit: sorry to bystanders for a completely off-topic conversation.

Re:Let's remove Quaternions from every 3D Engine by raphlinus on Friday November 02, 2018 @09:04PM (#18368032)
Agreed. And (as was largely the point of my thesis) these things are tradeoffs, a spline that's perfect in all these ways is not possible. I played around a bit and am not feeling that they'd be great for font design (they play pretty similarly to Séquin's circle splines, which of course you cite, though I think better).

We're now pretty far afield from the subject of the superiority of Rust over C++^W^W^W tau over pi^W^W^W geometric algebra over quaternions. I'd be more than happy to continue the discussion somewhere else.

Re:Let's remove Quaternions from every 3D Engine by BenFrantzDale on Friday November 02, 2018 @06:12PM (#18367169)
The same is true (with lower performance, I suspect) with the 3x3 matrix representation.
Re:Let's remove Quaternions from every 3D Engine by jacobolus on Friday November 02, 2018 @07:53PM (#18367693)
Matrices for rotation have the problem that you are using a 9-dimensional representation for a 3-dimensional quantity, so it is easy to make matrices that are not rotations (indeed the vast majority of the possible space of matrices consists of transformations that are not anywhere close to a pure rotation). Composing matrices leads to rounding errors. It is more complicated to invert matrices. As you say the matrix logarithm is more complicated. Etc.

If you use a scalar + bivector “rotor” representation, that is only a 4-dimensional representation, which is easy to normalize to unit magnitude.

Re:Let's remove Quaternions from every 3D Engine by jcagalawan on Friday November 02, 2018 @08:57PM (#18367999)
Isn’t the inversion a trivial transpose for rotations since they’re orthogonal?
Re:Let's remove Quaternions from every 3D Engine by gugagore on Friday November 02, 2018 @08:24PM (#18367851)
It's beautiful to see that the logarithm of a rotation matrix is a skew-symmetric matrix. The skew-symmetric matrices correspond to angular velocity, which behave like vectors. You can add and interpolate as you expect. Rotation matrices multiply. Skew-symmetric matrices add. The logarithmic and exponential map moves between the two spaces.

Just letting you know that I think it's valuable to bring up matrices into this discussion, even if they do have problems in practice with rounding errors and efficiency.

Re:Let's remove Quaternions from every 3D Engine by senderista on Friday November 02, 2018 @08:38PM (#18367920)
That’s because skew-symmetric matrices are the Lie algebra of the Lie group of rotation matrices (and the exponential map takes a Lie algebra to a Lie group). In physics we call them the “infinitesimal generators” of the rotation group.
Re:Let's remove Quaternions from every 3D Engine by gugagore on Saturday November 03, 2018 @12:15PM (#18370930)
I love knowing about Lie algebras and groups, but I think I disagree about the "because". The matrix exponential and logarithm just are. You can define and compute them without invoking anything about Lie groups.

I didn't know the term "infinitesimal generator". Thanks!

Re:Let's remove Quaternions from every 3D Engine by BenFrantzDale on Saturday November 03, 2018 @10:35PM (#18373768)
Indeed. And certainly since rotation matrices and quaternions are both representations of rotation, they should have a log that is isomorphic.

Wilder still is the log of a 4x4 transformation matrix has the same tangent-vector properties, giving a coordinate-system-invariant rotation and translation.

Re:Let's remove Quaternions from every 3D Engine by marctenbosch on Friday November 02, 2018 @08:29PM (#18367880)
Skew symmetric matrices are isomorphic to bivectors :)