Euclidean Geometry and Geometric Algebra

Image showing a motor orbit. Code available at enkimute.github.io.

If you prefer, you can download a PDF version of this article, slightly expanded with better typesetting.

Introduction

Geometric algebra is a very natural language for describing concepts in Euclidean geometry, but one aspect that can confuse people at first is that there is no single unique way to work. Different problems can require different algebras for their optimal solution and new uses for geometric algebras are being discovered constantly. In a recent SIGGRAPH presentation Charles Gunn and Steven De Keninck described a framework for Euclidean geometry based on planes as geometric primitives, which they call PGA.

This article describes how PGA relates to other geometric algebras, and explains why it may be the ultimate algebra for graphics.

Most introductions to geometric algebra (GA) start with a picture of vectors as rays out from a common origin. These have an inner product, the traditional scalar product, and an outer product that encodes the plane swept out by the two vectors. These are united in a geometric product in the famous relationship

$\displaystyle ab = a \!\cdot\! b + a \!\wedge\! b.$

The geometric product is the simplest product we can construct that is invertible. Given ab and a, we can recover b simply by multiplying the right-hand side by a/(a²).

Building out the algebra of 2D vectors leads us to `invent’ complex numbers, and in 3D to the discovery of the quaternion algebra. Indeed, the quaternions should be understood via their embedding in the geometric algebra of space, where they represent planes and generate rotations about the origin.

The fact that quaternions are the optimal algebra for working with rotations is well known to graphics and games programmers, and most game engines have an optimised quaternion library buried somewhere in their code (typically in the physics engine). But there are at least two further structures that are often employed in graphics code that do not sit obviously in this framework: projective geometry and dual quaternions.

Projective Geometry

Projective geometry lies at the heart of the graphics pipeline and solves a fundamental problem. If we fix an origin and a frame, and compute the coordinates of a vector x in this frame we find three numbers (x, y ,z). We can encode rotations (inefficiently) as 3X3 matrices acting on these coordinates, but translations cannot be encoded as a linear transformation. We want to combine rotations and translations to get from object space to world space to camera space and would like to do this in a simple, unified way. The trick is to introduce a fourth coordinate and work with 4-dimensional vectors with coordinates (x,y,z,1). In GA we write this as working with the vector X:

$\displaystyle X = \mathbf{x} + e_4.$

Projective geometry linearises translations and from this starting point a very rich algebra can be developed, although most of this is irrelevant in graphics, which only requires the unification of rotations and translations. The line L between two points is described by their outer product $L = X_1 \wedge X_2$ and these inhabit a 6-dimensional space. Similarly, the outer product of three points defines a plane. The somewhat mysterious concept of projective duality is encoded simply as multiplication by the highest-grade element or pseudoscalar, which interchanges outer and inner products. This simplifies many intersection calculations.

The projective representation is homogeneous, so X and 2X represent the same point. This ensures intersection algorithms are robust against special cases. For example, two parallel planes meet in a `line at infinity’, which has a finite representation. Many important geometric theorems can be proved efficiently in this setup, and duality often gives you two proofs for the price of one. Most of the main results were worked out by Hestenes and Ziegler (1991), which built on a rich literature on exterior theory and duality going back to the 19th century.

But one aspect of this work remains disappointing: projective transformations exist as operations outside the algebra. One of the key unifying principles of 3D GA is that vectors and the operations on them are all part of the same algebra. That is lost in the projective setup. The reason for this is projective transformations do not preserve angles, so do not naturally sit inside GA. A consequence of this is that there is very little use for the geometric product, except at intermediate steps in derivations. All results usually involve exterior products or duality.

Dual Quaternions

There is a way to perform Euclidean transformations using GA elements that was introduced by Clifford himself, and that is via the dual quaternions. These are not as widely used in the graphics community as quaternions, but they are used for skinning operations in animation, and are sometimes employed in rigid body physics solvers. A dual quaternion is made up from a pair of quaternions:

$\displaystyle D = q_1 + \epsilon q_2$ .

Here $\epsilon$ is an algebraic entity invented solely to have the property that

$\displaystyle \epsilon^2 = 0.$

We then find that normalised dual quaternions, which satisfy

$\displaystyle D D^\dagger = 1$ ,

form a group that includes rotations and translations. These act on elements quaternion elements via an expression that requires an artificial-looking sign flip on the $\epsilon$ term. None of this is very obvious or looks very natural, and dual quaternions have tended to be a niche topic.

Conformal GA

In 2000 a new use for geometric algebra started to evolve based on conformal geometry. This is now known as conformal geometric algebra (CGA). The building blocks of CGA had also been around since the 19th century, but it wasn’t until the start of the 21st century that all of the elements were pulled together. The starting point for CGA is to represent the Euclidean point x as the vector

$\displaystyle X = \mathbf{x} + m - \frac{1}{2} \mathbf{x}^2 n$

where m and n are a pair of new vectors, orthogonal to $\mathbf{x}$ , that satisfy:

$\displaystyle m^2 = n^2 = 0, \quad m \cdot n = 1.$

Vectors with a zero norm are called `null’ vectors. They may be unfamiliar to some, but are a standard feature of special relativity. These definitions ensure that

$\displaystyle X^2 = 0$ .

So points are also represented as null vectors in a space 2 dimensions higher.

The key concept behind the conformal model is that the inner product of two points is related to the distance between them:

$\displaystyle X \cdot Y = - \frac{1}{2}(\mathbf{x}^2 + \mathbf{y}^2 - 2 \mathbf{x} \cdot \mathbf{y}) = -\frac{1}{2} (\mathbf{x}-\mathbf{y})^2.$

This explains why points need to be null vectors: the distance between a point and itself must be 0! Euclidean transformations must leave distances unchanged, so in CGA they must preserve the inner product. Transformations that achieve this can always be built from elements in the algebra. The transformation must also leave the point at infinity, n invariant, which means that they are built from even elements that commute with n. With a bit of work one finds that elements satisfying this latter requirement have the form

$\displaystyle M = q_1 + e_1 e_2 e_3 n q_2$

where $q_1$ and $q_2$ are quaternions in the 3D Euclidean algebra. We have rediscovered precisely the dual quaternions, and the mysterious $\epsilon$ turns out to be a null 4-vector

$\displaystyle I_3 n = e_1 e_2 e_3n.$

Normalised elements, $M M^\dag = 1$ are called rotors (sometimes `motors’) and these act on points of the form X to perform rotations and translations.

This is another unification. In the same way that quaternions are best understood in 3D GA, dual quaternions arise naturally in the 5D CGA. The CGA has many other wonderful features. Points, lines, planes, circles and spheres all have simple expressions, as do intersection algorithms, and both the objects and the operations on them are contained in the same algebra.

CGA clearly has much to offer graphics, but there is a problem. The underlying representation is built on a 5D vector space, which is quite verbose and for many cases not as efficient as simple projective geometry. For example, the line-plane intersection returns a point pair, with one of the points at infinity. This is technically correct, but an unwanted complication in practice. Returning to the representation of X we see that the origin is represented by m, and in many applications we can drop the n term. But it is n that appears in the dual quaternions that drive transformations. It looks very much like you need both m and n, hence the full 5D algebra, to combine the advantages of projective geometry and dual quaternions.

PGA

It turns out there is a way to work entirely in a 4D space, with points lines and planes and the generators of rotations and translations all in the one algebra, and retaining the benefits of a homogeneous representation. The idea originated in the robotics community, and it is this idea, PGA, that Gunn and De Keninck descibed at SIGGRAPH.

We can motivate the algebra by going back to the CGA form of dual quaternions and noting that they are constructed entirely in an algebra generated by $\{e_1, e_2, e_3, n\}$ . So we ask the obvious question: what objects can we build in CGA that contain only these 4 generators? First look at vectors. We suspect that we really want to kill off the n term so we form,

$\displaystyle X \wedge n = x \wedge n + m \wedge n.$

This still contains a factor of m. However, if we dualise in 5D space with

$\displaystyle I_5 = I_3 (m \wedge n),$

we form

$\displaystyle I_5 (X \wedge n) = -I_3 \mathbf{x} n + I_3.$

This is great! We now have an object constructed entirely from our basis elements $\{e_1, e_2, e_3, n\}$ . Euclidean rotors will commute with both $I_5$ and n so this object will transform correctly as a point under Euclidean transformations. In components

$\displaystyle I_5 (X \wedge n) = n(x e_3 e_2 + y e_3 e_1 + z e_2 e_1) + e_1 e_2 e_3$

which is precisely the representation used by PGA. Of course, this object is a trivector, which is an unusual thing to choose to represent a point, but let’s see where this thinking leads us.

Next consider a line between x and y. In CGA we form $X \wedge Y \wedge n$ and we know what to do now. We dualise this in CGA to form

$\displaystyle I_5 X \wedge Y \wedge n = -(I_3 \mathbf{x} \wedge \mathbf{y}) n + I_3 (\mathbf{x} - \mathbf{y})$

and again we are back in the algebra generated by $\{e_1, e_2, e_3, n\}$ . This time lines are represented as bivectors. So a pattern is starting to emerge.

Finally we look at the plane formed by three points, $X \wedge Y \wedge Z \wedge n$ and dualising this we get a vector of the form

$\displaystyle I_5 X \wedge Y \wedge Z \wedge n = d_0 n + \mathbf{d}$

where d is a Euclidean vector normal to the plane. We have planes as grade 1 objects, so everything is `dual’ to the usual representation. But we have an algebra with all the properties we want for graphics. Points, lines and planes are all represented, and rotations and translations on these objects are performed by even elements in the same algebra. The representation is homogeneous and immediately consistent with the projective representation in graphics. Even better, given a line L as a bivector, rotations about that line are formed simply be exponentiating it! (See the SIGGRAPH course notes for more details.)

There are many useful identities that fall out from this algebra, but a key point is that it successfully captures concepts like orthogonality, which are harder to capture in standard projective geometry. To see this consider the product of two normalised planes

$\displaystyle p_1 p_2 = p_1 \cdot p_2 + p_1 \wedge p_2 = \cos \theta + L \sin \theta$

where $\theta$ is the dihedral angle between the planes, and L is the line of intersection. Clearly both parts of the product are geometrically relevant.

So we have an algebra that does everything we want, and all we had to do was make the `4th’ vector in projective geometry a null vector. Why is this not more widely known? Part of the answer is that the idea that points should be represented as trivectors seems unnatural at first. There is also a price you pay for having a null basis element, which is that the pseudoscalar now squares to zero. You lose the natural concept of duality as multiplication by the pseudoscalar. PGA does have a simple notion of duality, which is required for the join operation, though it is not performed by an element in the algebra. But this is a small price to pay, particularly as at the data level the duality operation is a trivial re-labeling. There is an important point here. This duality operation does not commute with transformations. If you take a point, dualise it to a plane, transform the plane, and dualise back you do not get the same result as transforming the point. For practical applications we have to fix the representation with planes as grade 1, lines grade 2 and points grade 3. Again, this is not a problem in practice, and the fact that there is only one way to work is helpful as it uniquely fixes your data types.

This leads on to the key point that PGA is very hardware friendly. In applications you always work with elements that are purely even or purely odd. These are 8 dimensional objects, so the absolute worse case multiplication operation takes 8 x 8 = 64 operations. The same as 4 by 4 matrix multiplication. But in practice a number of these products are zero so you usually end up doing better. Also everything fits neatly into 4 slots, which is good for both GPU and SIMD implementations. The underlying products can be blocked up in 4s, and most boil down to quaternion multiplication. If you already have an optimised quaternion library then the products are extremely fast. Finally, the entire algebra sits within the CGA, so it is easy to jump up to the full CGA should we need to take advantage of some of the operations there. This could be handy when using constructs like bounding sphere hierarchies.

After much searching, it does finally look like we have found the optimal algebra for 3D geometry computation.

Resources

Bivector.net Multiple resources on PGA
Klein. Production ready C++ library with a hand-optimized SSE implementation of PGA.
PDF version of this article, slightly expanded with better typesetting.