Chapter 64: Exterior Algebra
This chapter is based on a GDC talk called “Fundamentals of Grassman Algebra” by Eric Lengyel.
Exterior Algebra is the basis for the geometric algebra we use in computer graphics. By understanding these fundamentals, we will understand:
- Where the cross product comes from and why it behaves the way it does
- Where the dot product comes from
The Clifford Algebras describe a set of algebras extending the real numbers. In this context, we’re discussing “an algebra” which refers to something like a number system - a mathematic structure that includes some sort of number and a multiplication operation between them. This is different from the general term “algebra” which describes math involving variables.
In n dimensions, take the real numbers and add n special units Then, choose whether each squares to 0, 1, or -1.
Complex Numbers are an example of a Clifford Algebra - specifically, the one dimensional numbers with a single unit , usually called , that squares to . Another example that comes up the Dual Numbers, one dimensional numbers where squares to 0.
Grassman Algebra or Exterior Algebra is an n dimensional algebra where all of the square to 0.
The Wedge Product
Also known as the progressive product or the exterior product, the wedge product is the basis for a lot of the math we do in 3D computer graphcs.
The wedge product operates on scalars, vectors, and more. Operations involving scalars should be very familiar:
The first interesting part of the wedge product is that a vector wedged with itself is 0.
This leads to what’s called anti-commutivity for this operation on vectors.
Another property of the wedge product is that the product of two vectors is not a vector - it is something else, specifically a bivector. Bivectors are distinct from scalars and vectors, and represents an oriented 2D area (whereas a vector represents an oriented 1D direction and scalars are zero-dimensional values).
The orientation of this area is sometimes called the “winding” and can be described as clockwise or counterclockwise. This also illustrates the anticommutivity of the wedge product - changing the order of operands reverses the orientation of the bivector.
Bivectors in 3D
Start with 3 orthonormal basis vectors . Then, a 3D vector can be expressed as
from this we can see that:
Multiply through and cancel out every product with itself:
Then group parts with the same wedge products:
These three bivectors, , , and , form the basis for any bivector. That is, any bivector can be written as a linear combination of these three bivectors.
This is a little unwieldy to write so we use shorthand notation for these bivectors:
Using that same notation we can write out the wedge product a little more compactly:
This looks quite a bit similar to the cross product, but it is a bit more than a cross product. The cross product is only defined in 3D, and is not associative.
Conversely, the wedge product is both associate and defined in all dimensions. This comes from the fact that the wedge between two vectors is not a vector - it’s a bivector.
Similarly, the wedge product of three vectors produces a trivector. Trivectors represent a 3D oriented volume.
If one of the vectors is reversed, the opposite (negated) volume is produced.
A 3D trivector only has one component:
And the magnitude is:
(This is where the determinant comes from - it is derived from exterior algebra).
Because a trivector is a simple component, it looks a lot like a scalar. As such it is also called an antiscalar. It transforms differently than scalars though - it will negate under reflection.
Trivectors are the end for 3D. If we try to throw another vector into the mix, we’ll just get zero.
This is because we’ll always have a duplicated term in each part of the product, e.g. , which of course is zero.
All of these entities in exterior algebra have a grade, which is really just “how many vectors were wedged to get this?”
- Scalars have grade 0
- Vectors have grade 1
- Bivectors have grade 2
- Trivectors have grade 3
In 3D algebra, we can’t get higher than trivectors. In any n dimensional exterior algebra, you can’t have entities with grade greater than n.
Each entity in the algebra has a number of elements, or components, as we have seen:
- 1 scalar element
- 3 vector elements
- 3 bivector elements
- 1 trivector element
The fact that vectors and bivectors have the same number of elements is one of the reasons we don’t usually hear about bivectors - they look so similar to vectors.
In four dimensions, we have four basis vectors , and a fifth entitiy - quadvectors (with grade 4).
However, the elements follow a different pattern:
- 1 scalar element
- 4 vector elements
- 6 bivector elements
- 4 trivector elements
- 1 quadvector element
In general, the number of elements for each grade follows Pascal’s triangle.
1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1
The symmetric nature of this structure is important. For every n dimensional algebra, there are vector entities with n elements as well as a matching higher-grade entity with n elements as well. In 3D, this relationship exists between vectors and bivectors, so let’s take a closer look.
Antivectors and Antiscalars
As we mentioned, in 3D trivectors are somtimes called antiscalars due to them only having a single element.
Bivectors are similarily related to vectors, in that they both have three components, so they are sometimes called antivectors. Note how a vector has three elements each using exactly one of the spatial directions (). Comparatively, an antivector has three elements using all except one of the spatial directions ().
There’s a correspondance between these basis elements - e.g. the first vector element contains only while the first bivector element contains everything but . So, we use a notation that reflects this:
The order here is specifically chosen such that:
in all cases (and with extension to any n dimensions).
The wedge product between a vector and an antivector is the dot product - and it produces an antiscalar.
And this is what we do in shading - - here is an antivector (or bivector).
What are the consequences of this? Well, an antiscalar is different from a scalar in that it flips sign under certain transforms, such as a mirror transform. If you take a 3D model and mirror it, all of the faces will be pointing inwards and your shading will be reversed. Of course we know this will happen since mirroring the mesh will reverse the normals. However, we don’t need to “recompute” to know that it will be flipped by this transformation, so long as we understand that it’s an antiscalar.