Projective Geometric Algebra Done Right

From Rigid Geometric Algebra
Revision as of 02:25, 23 October 2023 by Eric Lengyel (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

By Eric Lengyel
January 23, 2020


In the last chapter of FGED1, I provided a practical introduction to projective Grassmann algebra. Most people working in computer graphics are familiar with four-dimensional homogeneous coordinates, and projective Grassmann algebra extends this concept to a larger algebraic structure under which the wedge and antiwedge products perform geometric manipulations of points, lines, and planes. FGED1 goes on to talk about geometric algebra as well, which augments Grassmann algebra, but the discussion is pretty much limited to quaternion operations in ordinary 3D space. The projective 4D analog of a quaternion is called a dual quaternion, and I said at the bottom of page 173 that they would be covered in Volume 3 of the FGED series. However, I knew at the time that I didn’t want to present dual quaternions in the usual ways that they have always been introduced in the various papers that have popped up. I found them to be unwieldy, and I was intent on spending some time gaining a deeper understanding of them first so that I could find better ways to formulate the parts that bothered me. That time came over this past holiday break, and the results were better than I had hoped for.

I don’t want this post to get too long, so I’m going to assume some familiarity with the material in Chapter 4 of FGED1, and I’m going to be rather brief with everything I write here. The most important things to know are how the wedge product $$\mathbf a \wedge \mathbf b$$ joins objects $$\mathbf a$$ and $$\mathbf b$$ into the higher-dimensional space that they span, how the antiwedge product $$\mathbf a \vee \mathbf b$$ calculates the lower-dimensional space where objects $$\mathbf a$$ and $$\mathbf b$$ meet, and how the geometric product extends the wedge product for vectors $$\mathbf a$$ and $$\mathbf b$$ to give $$\mathbf{ab} = \mathbf a \wedge \mathbf b + \mathbf a \cdot \mathbf b$$. A particular fact used below is that for two planes $$\mathbf g = g_x \mathbf e_{423} + g_y \mathbf e_{431} + g_z \mathbf e_{412} + g_w \mathbf e_{321}$$ and $$\mathbf h = h_x \mathbf e_{423} + h_y \mathbf e_{431} + h_z \mathbf e_{412} + h_w \mathbf e_{321}$$ in projective Grassmann algebra, the antiwedge product $$\mathbf g \vee \mathbf h$$ gives the line where $$\mathbf g$$ and $$\mathbf h$$ intersect.

Recall that the quaternions constitute the even-graded elements of the 3D geometric algebra. A unit-length quaternion $$\mathbf q$$ is called a rotor, and it rotates an object $$x$$ with the sandwich product $$\mathbf q x \mathbf{\tilde q}$$, where the tilde indicates the conjugate or reverse of $$\mathbf q$$, and juxtaposition represents the geometric product. The object $$x$$ can be a vector, bivector, or even another quaternion, and the appropriate transformation is made to rotate it using the axis and angle stored in $$\mathbf q$$. Importantly, a quaternion can be built out of two reflections through unit vectors $$\mathbf a$$ and $$\mathbf b$$ lying in the plane of rotation and separated by half the angle of rotation. The first reflection through $$\mathbf a$$ is given by $$\mathbf a x \mathbf a$$, and the second reflection through $$\mathbf b$$ is given by $$\mathbf b(\mathbf a x \mathbf a)\mathbf b = \mathbf{ba} x \mathbf {ab}$$. Two reflections produce a rotation that we represent by the quaternion $$\mathbf q = \mathbf{ba}$$.

A pair of reflections through two vectors, and thus a quaternion, can rotate something only about an axis passing through the origin, and it cannot perform any kind of translation. To incorporate translations into a product like $$\mathbf q x \mathbf{\tilde q}$$, which would also allow us to rotate about arbitrary lines, we need to move up to dual quaternions. Dual quaternions constitute the even-graded elements of the 4D geometric algebra $$\mathbb R_{3,0,1}$$. The subscripts 3,0,1 come from Clifford algebra classifications, and they mean that three of the vector basis elements square to $$+1$$, none of them square to $$‒1$$, and one of them squares to $$0$$. Calling the basis elements $$\mathbf e_1$$, $$\mathbf e_2$$, $$\mathbf e_3$$, and $$\mathbf e_4$$, we have $$\mathbf e_1^2 = \mathbf e_2^2 = \mathbf e_3^2 = 1$$ and $$\mathbf e_4^2 = 0$$. There are 8 even-graded components in a dual quaternion, and we can write them as a pair of ordinary quaternions $$\mathbf q_r + \varepsilon \mathbf q_d$$, where $$\mathbf q_r$$ is called the real part, $$\mathbf q_d$$ is called the dual part, and $$\varepsilon = \mathbf e_{1234}$$ squares to zero. Dual quaternions operate on an object $$x$$ through a kind of sandwich product similar to the one used by quaternions: $$(\mathbf q_r + \varepsilon \mathbf q_d)x(\mathbf{\tilde q}_r - \varepsilon \mathbf{\tilde q}_d)$$, where multiplication is the geometric product. When the dual part $$\mathbf q_d$$ is zero, a dual quaternion just performs the rotation represented by the real part $$\mathbf q_r$$. To get a translation by the vector $$\mathbf t$$, we construct the dual quaternion $$1 + \varepsilon (\mathbf i t_x/2 + \mathbf j t_y/2 + \mathbf k t_z/2)$$. Products of dual quaternions corresponding to rotations and translations then give us the full range of rigid motions.

The conventional way in which publications teach you how to transform a point $$\mathbf p$$ with a dual quaternion is to first turn $$\mathbf p$$ into the dual quaternion $$1 + \varepsilon \mathbf i p_x + \varepsilon \mathbf j p_y + \varepsilon \mathbf k p_z$$, evaluate the product $$(\mathbf q_r + \varepsilon \mathbf q_d)(1 + \varepsilon \mathbf i p_x + \varepsilon \mathbf j p_y + \varepsilon \mathbf k p_z)(\mathbf{\tilde q}_r - \varepsilon \mathbf{\tilde q}_d)$$, and then pick off the coefficients of the $$\varepsilon \mathbf i$$, $$\varepsilon \mathbf j$$, and $$\varepsilon \mathbf k$$ terms to retrieve the result. This is a hack. What it’s really doing is casting $$\mathbf p$$ as a translation operator, transforming that operator with the dual quaternion, and then casting back to a point. It doesn’t extend to the richer set of geometric objects available in $$\mathbb R_{3,0,1}$$, which include vectors, bivectors, points, lines, and planes. With a dual quaternion $$\mathbf Q$$, what we really want is the ability to evaluate the product $$\mathbf Q x \mathbf{\tilde Q}$$ for any type of object $$x$$ and get a correctly transformed object of the same type as a result, just like we could do in 3D space with ordinary quaternions. In their SIGGRAPH 2019 course “Geometric Algebra for Computer Graphics”, the presenters point out that general $$\mathbf Q x \mathbf{\tilde Q}$$ transformations can be achieved by “turning the algebra on its head” and working with the so-called dual construction. In this formulation, homogeneous vectors represent planes, and homogeneous trivectors represent points, which is the opposite of what makes intuitive sense with respect to the dimensionality of those geometric objects. (Lines are still represented by homogeneous bivectors, but the parts that correspond to the direction and moment are reversed.) I think that requiring that things be done this way is a giant kludge that misses an important part of the big picture, and I find it disagreeable due to some of the problems that it causes. I’ll get back to those below.

The key to using dual quaternions in the proper way without having to resort to any hacks or dimensional reversals is found in the formula $$\mathbf g \vee \mathbf h$$ producing the line where the planes $$\mathbf g$$ and $$\mathbf h$$ intersect. Any rotation about an arbitrary line in 3D space can be decomposed into a pair of reflections through planes that intersect at that line, and the angle of rotation is twice the angle at which the planes meet. In order to capture information about the angle in an operator, we must use a geometric product and not just an exterior product. The problem is that the geometric product incorporates the wedge product $$\wedge$$ whereas the meet of two planes is derived from the antiwedge product $$\vee$$. The geometric product works fine for ordinary quaternions where two reflections through vectors $$\mathbf a$$ and $$\mathbf b$$ produce a rotation in the bivector $$\mathbf a \wedge \mathbf b$$, but it’s not the correct product where two reflections through planes $$\mathbf g$$ and $$\mathbf h$$ produce a rotation about the line $$\mathbf g \vee \mathbf h$$. Instead, we need the geometric analog of the antiwedge product. The existence of such a product follows from the fundamental property that everything in geometric algebra has a complement. (There is an automorphism on every geometric algebra in which elements and operations are mapped to their complements, and it produces the same structure.) The geometric antiproduct that we need complements the geometric product in the same way that the exterior antiproduct (the antiwedge product) complements the exterior product (the wedge product).

I have searched the literature for any mention of multiplication resembling the geometric antiproduct, but I have come up completely empty. As far as I know, it has never been introduced, and there is no notation for it. Unfortunately, because the geometric product is denoted by juxtaposition, we don’t have an infix operator that we can simply flip upside down like we could with the wedge and antiwedge products. I propose that we use the symbols $$\unicode{x27D1}$$ and $$\unicode{x27C7}$$ to denote the geometric product and geometric antiproduct, respectively, at least in contexts where a distinction is necessary. These symbols fittingly incorporate the fact that the geometric product between vectors combines their wedge product and dot product, and that the geometric antiproduct between antivectors combines their antiwedge product and antidot product. (The antidot product works with antivectors in the same way that the dot product works with vectors, but it produces an antiscalar quantity instead of a scalar quantity.)

The correct way to construct a dual quaternion $$\mathbf Q$$ from a pair of reflections through the planes $$\mathbf g$$ and $$\mathbf h$$ is by calculating $$\mathbf Q = \mathbf g \mathbin{\unicode{x27C7}} \mathbf h$$. This calculates the line $$\mathbf g \vee \mathbf h$$ and adds the value $$(g_xh_x + g_yh_y + g_zh_z)\mathbf e_{1234}$$ to it. If the planes $$\mathbf g$$ and $$\mathbf h$$ are normalized, then that additional antidot product is the cosine of the angle between the normal directions, which is half the angle of rotation. If $$\mathbf g$$ and $$\mathbf h$$ are parallel, then $$\mathbf Q$$ represents a translation along the normal direction by twice the distance separating the planes. In general, a unit-length dual quaternion $$\mathbf R$$ having the form

$$\mathbf R = (a_x \mathbf e_{41} + a_y \mathbf e_{42} + a_z \mathbf e_{43}) \sin(\phi/2) + \mathbf e_{1234} \cos(\phi/2)$$

is a pure rotation through the angle $$\phi$$ about the axis $$(a_x, a_y, a_z)$$. A dual quaternion $$\mathbf T$$ having the form

$$\mathbf T = (t_x/2)\mathbf e_{23} + (t_y/2)\mathbf e_{31} + (t_z/2)\mathbf e_{12} + \mathbf e_{1234}$$

is a pure translation by the vector $$\mathbf t$$. Combinations of these types of dual quaternions under the geometric antiproduct can be used to construct all rigid motions in three dimensions. Any object $$x$$, whether it be a point, line, plane, or any other member of $$\mathbb R_{3,0,1}$$, is transformed by a dual quaternion $$\mathbf Q$$ using the same sandwich product $$\mathbf Q \mathbin{\unicode{x27C7}} x \mathbin{\unicode{x27C7}} \smash{\mathbf{\underset{\Large\unicode{x7E}}{Q}}}$$. Here, the squiggle has been moved to the bottom to indicate that we are using the complement of the reverse operation, which we could call the antireverse. For dual quaternions, whether we use the reverse or antireverse doesn’t matter because they have the same effect on even-graded elements. But for other operators, such as a reflection through a single plane, or in geometric algebras for spaces of other dimensionality, it can make a difference in sign.

I’ve whipped up a poster-sized reference guide for projective geometric algebra in $$\mathbb R_{3,0,1}$$. It provides a lot of the details for geometric calculations in 4D Grassmann algebra, it contains the complete multiplication tables for both the geometric product and geometric antiproduct, and it shows explicit formulas for performing transformations with dual quaternions. (This reference guide has been doubled in size to include information from the next post, Symmetries in Projective Geometric Algebra.)

The authors of the SIGGRAPH course I mentioned earlier claimed that their dual construction was the only way to implement plane-based projective geometric algebra, but that is not true. Their failure to recognize the existence of the geometric antiproduct forced them to do many things backwards, and the result was an unnecessarily convoluted geometric model that resists intuition. While they’ve managed to make things work from a purely computational perspective, I perceive the quirks in their model as essentially aberrations derived from an incomplete picture of the mathematics. The following list summarizes the main problems that arise.

  • Their model requires that points be represented by trivectors and planes be represented by vectors. This is backwards. In 4D projective space, points are one-dimensional, and planes are three-dimensional. The projection into 3D space removes a dimension and naturally makes points zero-dimensional and planes two-dimensional, but that’s not what they have. Furthermore, swapping points and planes has serious implications for nonorthogonal change-of-basis transformations, which happen in computer graphics all the time, but they completely ignore this issue.
  • Because points and planes are backwards, the geometric meaning of the wedge and antiwedge products are also necessarily backwards. Their model requires that $$\wedge$$ corresponds to a dimension-decreasing meet operation and $$\vee$$ corresponds to a dimension-increasing join operation, but in the Grassmann algebra used by the rest of the world, the meanings are the other way around.
  • Their concept of normalization is backwards. The projective dimension is represented by the basis element $$\mathbf e_4$$, and this means that an object in the projective algebra is normalized when the part that extends into this fourth dimension has a magnitude of one. For example, a homogeneous point is normalized when its $$\mathbf e_4$$ coordinate is one, a line is normalized when its $$(\mathbf e_{41}, \mathbf e_{42}, \mathbf e_{43})$$ direction has length one, and a plane is normalized when its $$(\mathbf e_{423}, \mathbf e_{431}, \mathbf e_{412})$$ normal has length one. This also applies to a dual quaternion, which is normalized when its $$(\mathbf e_{41}, \mathbf e_{42}, \mathbf e_{43}, \mathbf e_{1234})$$ rotor part has length one. In general, the magnitude of the collection of components involving the projective basis element $$\mathbf e_4$$ has to be one. However, in the dual construction model, its the components that don’t involve $$\mathbf e_4$$ that must have a magnitude of one.

This awkwardness is instantly cleaned up by using the product that naturally performs reflection through planes, the geometric antiproduct $$\unicode{x27C7}$$. Points and planes still have the right dimensionality, the wedge product still calculates the join, the antiwedge product still calculates the meet, and normalization always involves only the projective dimension. Nothing has to be flipped upside down or turned inside out, and nonorthogonal change-of-basis transformations have the correct effect on the geometry associated with elements of every grade. The lack of problems in the model produced by the geometric antiproduct and its natural elegance make it clear to me that it is the right way to go.

Keep in mind that the description above is extremely abbreviated, and there is a lot more that can be said about using dual quaternions to perform rigid motions. There are a lot of computational details on the reference poster, which is also available as a 18×24 inch print on Amazon. I will be dedicating an entire chapter to this subject in FGED3, where I will also cover its application to skinning.

See Also