Tuesday , May 11 2021

Projective Geometric Algebra Done Right, Hacker News

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 a b joins objects a and b into the higher-dimensional space that they span, how the antiwedge product a b calculates the lower-dimensional space where objects
a and
b
meet, and how the geometric product extends the wedge product for vectors
a
and b to give
(ab) (=
) ∧ b a b . A particular fact used below is that for two planes f = f x
e
f y f

z e (f w (and g =(g x e 321 g y e g z g w in projective Grassmann algebra, the antiwedge product
f (∨ g gives the line where (f and g intersect.

Recall that the quaternions constitutes the even-graded elements of the 3D geometric algebra. A unit-length quaternion q is called a rotor . , and it rotates an object x with the sandwich product q x
, where the tilde indicates the conjugate or reverse of
(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 (q ). Importantly, a quaternion can be built out of two reflections through unit vectors
a and b lying in the plane of rotation and separated by half the angle of rotation. The first reflection through a is given by a ( x
) , and the second reflection through b is given by (b
( a) x
a
) b =ba
x
ab . Two reflections produce a rotation that we represent by the quaternion q = 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 q x , which would also allow us to rotate about arbitrary lines, we need to move up to dual quaternions. Dual quaternions constitution the even-graded elements of the 4D geometric algebra ℝ 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 (e) (1) , e 2 , (3) , and (e) 4 , we have (e 1)

(2) (e 2) 2 = e (3 ) (2)=1 and (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 (q r ε q d , where
(q
) r is called the real part, q d is called the dual part, and ε= e squares to zero. Dual quaternions operate on an object x through the same kind of sandwich product used by quaternions: (
q r ε (q) (d) ) x ( q̃ r ε d ), where multiplication is the geometric product. When the dual part q d is zero, a dual quaternion just performs the rotation represented by the real part (q) r . To get a translation by the vector t , we construct the dual quaternion 1 ε ( (i t x / 2
j
t y / 2 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 p with a dual quaternion is to first turn p into the dual quaternion 1 ε i p

x ε j (p) (y) ε (k p (z , evaluate the product ( q r ε (q d ) (1 ε i p (x) ε j p (y ε k (p) (z ) ( (q̃ ε
q̃ d
), and then pick off the coefficients of the ε i , ε j , and ε k terms to retrieve the result. This is a hack. What it’s really doing is casting p as a translation operator, transforming that operator with the dual quaternion, and then casting back to a point. It does not extend to the richer set of geometric objects available in ℝ 3.0,1 , which include vectors, bivectors, points, lines, and planes. With a dual quaternion Q , what we really want is the ability to evaluate the product (Q x
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 Payeer course “Geometric Algebra for Computer Graphics” , the presenters point out that general
Q x
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.) This way of doing things is a giant kludge that misses an important part of the big picture, and I find it particularly disagreeable due to 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 kludges is found in the formula f g producing the line where the planes f and g 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 ∧ whereas the meet of two planes is derived from the antiwedge product ∨. The geometric product works fine for ordinary quaternions where two reflections through vectors
a and b produce a rotation in the bivector a
b , but it’s not the correct product where two reflections through planes (f
and
g produce a rotation about the line f g . 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 ⟑ and ⟇ 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 Q from a pair of reflections through the planes (f

and g is by calculating Q =(f g . This calculates the line f
g
and adds the value ( f x g x f y g (y f (z) (g) (z) ) to it. If the planes f and
g
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 f and
g
are parallel, then Q represents a translation along the normal direction by twice the distance separating the planes. In general, a unit-length dual quaternion R having the form

R =( a (x
(e)

a y (e ( a z e ) sin ( θ / 2) e) cos ( θ / 2)

is a pure rotation through the angle θ about the axis ( a (x , a (y , a z ). A dual quaternion T having the form

T =( t (x / 2) (e ( t y / 2) e ( ( t z / 2)
e

is a pure translation by the vector
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 is a point, line, plane, or any other member of ℝ 3,0,1 , is transformed by a dual quaternion Q Using the same sandwich product Q x
.

I’ve whipped up a poster-sized

quick reference guide for projective geometric algebra in ℝ 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.

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 most things work from a purely computational perspective, the quirks in their model are 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 should be one-dimensional, and planes should be three-dimensional. The projection into 3D space removes a dimension and should naturally make 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 ∧ corresponds to a dimension-decreasing meet operation and ∨ 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
    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 e 4 coordinate is one, a line is normalized when its ( e e , (e ) direction has length one, and a plane is normalized when its ( e 321 ,
  • ,
    normal has length one. This also applies to a dual quaternion, which is normalized when its ( e 43 , ) (e rotor part has length one. In general, the magnitude of the collection of components involving the projective basis element
    e 4 has to be one. However, in the dual construction model, its the components that don’t involve e .

  • This awkward mess is instantly cleaned up by using the product that naturally performs reflection through planes, the geometric antiproduct ⟇. 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 in the quick reference guide , and I will be dedicating an entire chapter to this subject in FGED3, where I will also cover its application to skinning.

    A couple additional notes:

  • I am not suggesting that the geometric antiproduct replace all uses of the geometric product. I’m only stating that the geometric antiproduct is the natural choice for reflecting through planes and thus for use with dual quaternions.

      I have considered exponentials, and everything works just fine. A dual quaternions can still be expressed as an exponential – it just needs to be carried out with respect to the geometric antiproduct.

      Read More

      About admin

      Leave a Reply

      Your email address will not be published. Required fields are marked *