Live data from Hacker News

Let's remove Quaternions from every 3D Engine

marctenbosch.com

151–160 of 184 posts

Re: Let's remove Quaternions from every 3D Engine

#151

Earlier quoted context omitted.

There is an N-dimensional generalisation for complex numbers, quaternions and hypercomplex numbers called Clifford algebra. I'm not an expert in that field (coming from physics and optics) but apparently it's not by chance that quaternions are connected with the rotation group SO(3) and complex numbers with SO(2). You can generalize to SO(n) with Clifford algebra.

This is closely related to the exterior algebra, which is where bivectors live. But I don't know much about Clifford algebras either. I didn't know that they are more directly connected to Quaternions. Thanks!

The 'geometric product' mentioned in the article is just Clifford's product. The 'geometric algebra' is the same thing as the Clifford algebra induced by the scalar product.

Re: Let's remove Quaternions from every 3D Engine

#152

Earlier quoted context omitted.

You might enjoy https://arxiv.org/abs/1205.5935

As someone unable to fathom the enthusiasm for geometric algebra... at least this defines this product: It's the sum of an inner product and a wedge product. Acting on two vectors these give a scalar and a 2-form. Why is adding these different objects a good idea? Don't they have different units (like, a pure number vs meters squared)?

It's analogous to the real and imaginary parts of a complex number. Does it makes sense to add a real number and a purely imaginary number? Aren't they different kinds of things? Yes, and yes!

Re: Let's remove Quaternions from every 3D Engine

#153

Earlier quoted context omitted.

As someone unable to fathom the enthusiasm for geometric algebra... at least this defines this product: It's the sum of an inner product and a wedge product. Acting on two vectors these give a scalar and a 2-form. Why is adding these different objects a good idea? Don't they have different units (like, a pure number vs meters squared)?

It's analogous to the real and imaginary parts of a complex number. Does it makes sense to add a real number and a purely imaginary number? Aren't they different kinds of things? Yes, and yes!

It would really helpful if the article had some worked examples of this arithmetic, with actual numbers, the kind with digits and decimal points in. Then, things like the structure of a geometric product would be absolutely clear.

Let me have a go. I'll use an asciified version of the symbols, with * to mean multiplication of two scalars,, to mean raising one scalar to the power of another, and _ to mean taking a component of a vector.

  ab = a.b + a^b
  
  a.b = a_x * b_x + a_y * b_y + a_z * b_z
  
  a^b = (a_x * b_y - b_x * a_y) (x^y)
      + (a_x * b_z - b_x * a_z) (x^z)
      + (a_y * b_z - b_y * a_z) (y^z)
  
  ab = (a_x * b_x + a_y * b_y + a_z * b_z)
     +             (a_x * b_y - b_x * a_y) (x^y)
     +             (a_x * b_z - b_x * a_z) (x^z)
     +             (a_y * b_z - b_y * a_z) (y^z)
So if a = (1, 2, 3) and b = (4, 5, 6):

  ab = (1 * 4 + 2 * 5 + 3 * 6)
     +         (1 * 5 - 4 * 2) (x^y)
     +         (1 * 6 - 4 * 3) (x^z)
     +         (2 * 6 - 5 * 3) (y^z)
  
     = 32 + -3 (x^y) + -6 (x^z) + -3 (y^z)
The dot product makes a scalar, the wedge product makes a bivector, and the geometric product makes a scalar plus a bivector

You will note that the scalar part is much bigger than the coefficients of the bivector part. That's because the input vectors are actually quite similar - pointing z-by-y-z, with a little bit of x. Hence, their projection onto each other is large, whereas the parallelogram they form is quite small (long and thin). The dot product measures the former, the wedge product the latter.

Have i got that right?

EDIT And to clarify this:

> For any basis vector, such as the x axis, the result [of taking the geometric product with itself] is 1

That '1' isn't the scalar number 1, it's the scalar-plus-bivector 1 + 0 (x^y) + 0 (x^z) + 0 (y^z).

Re: Let's remove Quaternions from every 3D Engine

#154

Earlier quoted context omitted.

> 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?

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.

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

#155
post #141

Tangential: Back in 2000 there was some debate about dropping quaternions in favor of a set of equivalent operations on plain matrices. https://www.gamedev.net/articles/programming/math-and-physic... The debate petered out when the proponents finished optimizing their implementation and found they had produced exactly the same code as the existing quaternion implementations. The only difference was the approach used…

In high level programming, the code is for humans, the optimized compiler output is for the computer.

you're greatly overestimating how much the compiler can optimize code.

Re: Let's remove Quaternions from every 3D Engine

#156
post #132

Quats can be represented with (x, y, z, w). Rotors require a vector, bivector and angle (vec_x, vec_y, vec_z, bivec_x, bivec_y, bivec_z, theta). If you are storing or transmitting a quaternion it consumes less space and in 3D simulations or games a quaternion is therefore advantageous. 3D file formats would explode in size if rotors were used. And, more network packet fragments would be needed to encapsulate a world…

No. 3D rotors are represented exactly the same way as quaternions- 4 scalars. The operations are the same as well, only the explanation is different.

Partially true, internally libraries represent the rotor as just four scalars and can convert these to a quaternion. However, to actually make use of the rotor to do anything useful, e.g. interpolate, which is a power quaternion math has innately, you need to provide a lot more external information; plane origin vector, bivector, angle. A 3D file format storing the transformations between joints of the skeleton of a character for example would have to provide these extra bits of information in order to store the frames to perform inverse kinematics.

Likewise, if you needed to store or transmit spherical camera interpolations or non-player or player character transitions over a network this information would also have to be provided. You could perhaps do some optimization, e.g. only sometimes transmitting the origin once and then only sending the bivectors and angles in some cases which still would waste bytes and increase complexity. And, sometimes you couldn't so you'd have to send the whole thing.

But, with a quaternion you get this for free without any logical gymnastics via the previous four scalars to the next four scalars between delta frames. And, in the case of slerp only the lambda of time.

Now you can argue that a rotor could be used locally and then when storage/transmission is required you could convert to and use quaternion math to perform the necessary interpolations and thereby get the space savings. However, this article is specifically asking for the complete removal of quaternions from the field of computer science.

Unless I'm misunderstanding. Though I haven't seen a code example where rotors don't require this extra information. For example, in libvsr they have examples that require all these pieces for each frame. However, maybe that is an inefficient or naive implementation.

I did find this: http://geometry.mrao.cam.ac.uk/wp-content/uploads/2015/02/01...

Which provided a formula for rotor slerp: R(lambda) = (1.0 / sin(theta)) * (sin((1 - lambda) * theta) * R0 + sin(lambda * theta) * R1)

If that is the case, then the bare minimum information required is still more than a quaternion. We'd require the lambda, theta, and R0 (4 scalars), R1 (4 scalars).

Re: Let's remove Quaternions from every 3D Engine

#157

I do love Geometric Albegra and hope it gets further adoption. In my field (physics), the project of moving to geometric algebra currently looks hopeless due to the inertia of other formalisms and lack of interest from established physicists. The real shame is that the best opportunity to introduce physicists to geometric algebra was a hundred years ago when we were first discovering spinors. First the Pauli algebra…

Can I ask you (and keldaris) what precisely you mean by geometric algebra, and how you would propose to teach it?

I'm a math professor. To me "geometric algebra" refers to any use of geometry in mathematics to illuminate algebraic principles. There are very very many of these -- this article illustrates one good example. I try to incorporate intuition from geometry into my teaching whenever possible.

It seems that the two of you are referring to some particular unifying framework, and/or set of definitions and notation. Could I ask you to elaborate on what you mean?

Thanks.

Re: Let's remove Quaternions from every 3D Engine

#158
post #141

Tangential: Back in 2000 there was some debate about dropping quaternions in favor of a set of equivalent operations on plain matrices. https://www.gamedev.net/articles/programming/math-and-physic... The debate petered out when the proponents finished optimizing their implementation and found they had produced exactly the same code as the existing quaternion implementations. The only difference was the approach used…

In high level programming, the code is for humans, the optimized compiler output is for the computer.

But the article is about 3D graphics programming, which is often performance-sensitive.

Re: Let's remove Quaternions from every 3D Engine

#160

Earlier quoted context omitted.

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 th…

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.

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!

Post reply on HN