Homogeneous Geometric Algebra

Suppose we wish to manipulate a rectangular image. We might use Cartesian coordinates, defining, say, the bottom left corner to be the origin, and the \(\newcommand{\vv}[1]{\mathbf{#1}} \newcommand{\x}{\vv{x}} \newcommand{\y}{\vv{y}} \newcommand{\z}{\vv{z}} x\) and \(y\) axes to be the horizontal and vertical directions. We call this the vector space model of 2D space; the vector \((x, y)\) represents a point.

We can scale, shear, reflect, or rotate with a linear transformation, but never translate. A linear transformation must fix the origin, and a nonzero translation must not.

The trick is to work in a plane not containing the origin, which requires one more dimension. The equations are simplest if we move to a plane that is one unit away from the origin, that is, points of the form \((x, y, 1)\). We can trivially rewrite 2D linear transformations in 3D so they preserve the \(z\) coordinate, and furthermore, with appropriate 3D shear transformations, we can translate our picture.

What about points outside this plane? For any nonzero \(\lambda\), we define \((\lambda x, \lambda y, \lambda)\) to represent the same 2D point as \((x, y, 1)\). With this interpretation, perspective projection is also a linear transformation. We call this the homogeneous model of 2D space.

This trick generalizes to any dimension. For example, in the homogeneous model, every vertex of our unit cube gains a 4th coordinate of 1:

Before we introduce the geometric algebra homogeneous model, we fulfill some promises. We’ve been praising the multivectors of \(\mathbb{G}^n\) because they have useful geometric interpretations. We now reveal the details.

We have the usual interpretations of vectors (1-vectors) and scalars (0-vectors), but that’s unimpressive.

Recall from our discussion of 3D rotations that a plane is represented by the product of two orthonormal vectors it contains. Thus we can geometrically interpret a bivector (2-vector) if it happens to be the product of two orthonormal vectors.

More generally, a k-blade \(\newcommand{\B}{\vv{B}} \B\) or blade of grade \(k\) is the product of \(k\) orthogonal vectors \(\vv{b}_1 …​ \vv{b}_k\), and it represents a \(k\)-dimensional subspace, namely the subspace generated by \(\vv{b}_1,…​,\vv{b}_k\). For example, pseudoscalars like \(\vv{I}\) represent the entire space. Positive multiples of a blade represent the same subspace, while negative multiples represent the same subspace with the opposite orientation, analogous to the anticommutativity of the cross product.

In vector algebra, the norm of the cross product of two vectors is the area of the parallelogram they define. More generally, The norm of \(\B\) is \(|\B| = |\vv{b}_1| …​ |\vv{b}_2|\), and is the \(k\)-volume of a parallelepiped defined by the \(\vv{b}_i\) vectors. We will later build blades from any number of linearly independent vectors, justifying our use of the word "parallelepiped" instead of merely "box".

Recall also with 3D rotations, we multiplied a normal of a plane by \(\vv{I}\) to find the equivalent bivector. More generally, for any dimension, define the dual of a multivector \(A\) to be:

\[ A^* = A \vv{I}^{-1} \]

In \(n\) dimensions, the dual of a \(k\)-blade \(\B\) is the \((n - k)\)-blade \(\B^*\), which represents the orthogonal complement of \(\B\). This, along with many other results, can be seen by choosing the orthonormal basis of \(\mathbb{R}^n\) to include the vectors of \(\B\). We say \(\B\) is the direct representation of the subspace, and \(\B^*\) is the dual representation of the subspace. The dual operation is self-inverse up to sign.

In 3D, a normal vector indirectly represents a plane, that is, a 1-blade is a dual representation of a 2-blade. More generally, in \(n\)-dimensions, all \((n-1)\)-vectors are \((n-1)\)-blades, which we prove with a "double negative": the dual of an \((n-1)\)-vector is a sum of vectors, which is a single vector, whose dual is an \((n-1)\)-blade. We generalize this further to subspaces later.

Thus in 3D, we have \((\vv{u} \wedge \vv{v})^* = \vv{u} \times \vv{v}\), hence as promised, the cross product arises naturally in geometric algebra.

[Multiplication by any unit pseudoscalar results in the orthogonal complement. I’m not sure why right multiplication by \(\vv{I}^{-1}\) is the official dual operation.]

The above table shows some possible geometric interpretations of multivectors. Depending on context, we may attach different meanings, just as vectors in vector algebra are variously interpreted as points, directions, or line segments.

Unlike vector algebra, geometric algebra possesses straightforward notation for subspaces and their orthogonal complements.

In 3D, we had claimed the decomposition of a vector with respect to a plane is "readily computed". Let us make an even bolder boast: in any dimension, the decomposition of a vector with respect to a blade is readily computed. To see how, we generalize the inner and outer products.

For a multivector \(A\), write \(\langle A \rangle_k\) for the \(k\)-vector part of \(A\), that is:

There are several ways to generalize the inner and outer products. The following is a natural choice for the outer product. For a \(j\)-vector \(A\) and a \(k\)-vector \(B\), we define:

\[ A \wedge B = \langle AB \rangle_{j+k} \]

We extend this definition to arbitrary multivectors by linearity, that is:

We follow Macdonald (who cites Dorst) and choose the left contraction for the inner product:

\[ A \cdot B = \langle AB \rangle_{k-j} \]

For any multivectors \(A\) and \(B\), the inner and outer products are dual:

\[ \begin{array}{lll} A \cdot B^* &=& (A \wedge B)^* \\ A \wedge B^* &=& (A \cdot B)^* \end{array} \]

We also have the extended fundamental identity: for any vector \(\vv{a}\) and any blade \(\B\):

\[ \vv{a} \B = \vv{a} \cdot \B + \vv{a} \wedge \B \]

Now we justify our boast. Given a vector \(\vv{a}\) and a blade \(\B = \vv{b}_1 …​ \vv{b}_k\), suppose we wish to find the unique solution to:

\[ \vv{a} = \vv{a}_\parallel + \vv{a}_\perp \]

where \(\vv{a}_\parallel \in \B\) is the projection and \(\vv{a}_\perp \perp \B\) is the rejection.

Then if \(\vv{a}_\parallel \cdot \B = \vv{a}_\parallel \B\) is nonzero, then it is a \((k-1)\)-blade in \(\B\), and \(\vv{a}_\parallel \wedge \B = 0\).

Dually, if \(\vv{a}_\perp \wedge \B = \vv{a}_\perp \B\) is nonzero, then it is a \((k+1)\)-blade in \(\B\) representing the span of \(\vv{a}_\perp\) and \(\B\), and \(\vv{a}_\perp \cdot \B = 0\).

Since every non-zero vector has an inverse, the blade \(\B\) has an inverse (it is some multiple of \(\vv{b}_k…​\vv{b}_1\)). We have:

\[ \begin{array}{lll} \vv{a}_\parallel &=& (\vv{a} \cdot \B) \B^{-1} \\ \vv{a}_\perp &=& (\vv{a} \wedge \B) \B^{-1} \end{array} \]

Thus the projection and rejection of a vector with respect to a given blade is indeed readily computed.

We also have a test for subspace membership given its direct or dual representation:

\[ \vv{a} \in \B \iff \vv{a} \wedge \B = 0 \iff \vv{a} \cdot \B^* = 0 \]

Recall the geometric product of two vectors is a scalar (the inner product) and a bivector (the outer product) which represents the plane the two vectors lie in. Using our new terminology, we can say if \(\vv{u}_1, \vv{u}_2\) are linearly independent (and not necessarily orthogonal) then \(\vv{u}_1 \wedge \vv{u}_2\) is the 2-blade they generate.

Gram-Schmidt orthogonalization generalizes this. Given linearly independent \(\vv{u}_1,…​,\vv{u}_k\), the \(k\)-blade they generate is \(\vv{u}_1\wedge…​\wedge\vv{u}_k\).

We sketch a geometric algebra proof. The \(k = 1\) case is vacuously true. We’ll show how the \(k = 2\) case implies the \(k = 3\) case and leave the rest to the reader. By inductive assumption, \(\vv{u}_1\wedge\vv{u}_2 = \vv{b}_1 \vv{b}_2\) for some \(\vv{b}_1 \perp \vv{b}_2\). Let \(\vv{b}_3 = \vv{u}_3 \wedge \vv{u}_1 \wedge \vv{u}_2 / (\vv{u}_1 \wedge \vv{u}_2)\), that is, the rejection of \(\vv{u}_3\) by the blade \(\vv{b}_1 \vv{b}_2\). Then \(\vv{b}_3\) is nonzero because the \(\vv{u}_i\) are linearly independent, and:

\[ \vv{u}_1\wedge\vv{u}_2\wedge\vv{u}_3 = (\vv{u}_1\wedge\vv{u}_2)\wedge\vv{b}_3 = \vv{b}_1\vv{b}_2\wedge\vv{b}_3 = \vv{b}_1\vv{b}_2\vv{b}_3 \]

Thus we may view a blade as a geometric product of orthogonal vectors, or as the outer product of linearly independent vectors.

The geometric algebra homogeneous model for \(\mathbb{R}^n\) begins in lockstep with its vector algebra cousin.

Define a unit vector \(e\) orthogonal to \(\mathbb{R}^n\). (We write \(e\) with italics to emphasize its special nature; vectors in \(\mathbb{R}^n\) remain in bold.) We use \(\mathbb{G}^{n+1}\) to represent \(\mathbb{R}^n\).

A point \(P \in \mathbb{R}^n\) is represented by the vector \(\newcommand{\p}{\vv{p}} e + \p\), where \(\p\) is the vector from the origin to \(P\). The representation \(e + \p\) is normalized; for any nonzero scalar \(\lambda\), \(\lambda(e + \p)\) also represents \(P\).

The following functions convert back and forth from coordinates of a 3D point and its representation in the geometric algebra homogeneous model. The return journey is hazardous because we must normalize, and also because no point is represented by a vector with no \(e\) component. (Actually, nonzero vectors with a zero \(e\) component represent points at infinity, but these lie outside \(\mathbb{R}^3\).)

How about lines and planes? Here, vector algebra takes a turn for the worse. In computer graphics, typically \(n = 3\), so the homogeneous model has 4 dimensions. Unfortunately, vector algebra is tied to three dimensions because of the cross product, so either we convert back and forth from 3D to deal with normal vectors, or we have to learn Plücker coordinates. [And what of higher dimensions?]

Meanwhile, geometric algebra seems impossibly simple. Our definitions work in any dimension, so four dimensions presents no particular difficulties. In fact, the extra dimension required by the homogeneous model works in our favour.

Two distinct points define a line. In the homogeneous model, a point \(\p\) is represented by scalar multiples of \(p = e + \p\), that is, a line going through \(p\) and the origin. Thus the line defined by the two points \(\p, \vv{q}\) is represented by the plane going through \(p\), \(q\), and the origin, that is, the subspace spanned by \(p\) and \(q\). Therefore, in geometric algebra, the oriented line passing through \(p\) and \(q\) is:

\[ p \wedge q \]

Similarly, three distinct points define a plane. In geometric algebra an oriented plane through \(p\), \(q\) and \(r\) is:

\[ p \wedge q \wedge r \]

These turn out to be exactly the Plücker coordinates of lines and planes. As claimed, Plücker coordinates arise naturally in geometric algebra.

We can extend this construction to higher dimensions: we represent a \(k\)-blade simply by taking the outer product of the \(k\) vectors representing linearly independent points defining the subspace.

Why was there no analogous construction before? What stops us taking the outer product of two points to represent a line in the vector model?

Answer: in the vector model, points are represented by 1-blades (vectors), but for \(k \ge 1\), \(k\)-blades represent \(k\)-blades. If we take the outer product of two 1-blades representing two points, we wind up with a 2-blade, which represents a 2-blade (plane), and not a 1-blade (line).

In the homogeneous model, \(k\)-blades are represented by \((k+1)\)-blades for all \(k\). The outer product of two linearly independent 1-blades is a 2-blade, so from two representations of points we get a representation of a line. The outer product of three linearly independent 1-blades is a 3-blade, so three points yield a plane. And so on. In this way, the extra dimension of the homogeneous model works to our advantage.

Let \(f\) be a linear transformation. Then the line defined by \(p\) and \(q\) is mapped to the line defined by \(f(p)\) and \(f(q)\), thus:

\[ f(p\wedge q) = f(p) \wedge f(q) \]

Similarly, we know where \(f\) maps a given plane if we know where it maps three of its points:

\[ f(p\wedge q\wedge r) = f(p) \wedge f(q) \wedge f(r) \]

This extends to blades of any dimension, that is, \(f\) commutes with the outer product. For this reason, in geometric algebra, a linear transformation is termed an outermorphism.

Hence with geometric algbra, we can readily compute the effect of any linear transformation on any subspace.

Contrast this with vector algebra, where linearly transforming a plane does not in general transform its normal vector in the same way. For example, a shear may preserve a plane but distort its normal vector, or vice versa.

The join of blades \(\vv{A}\) and \(\vv{B}\) is the smallest subspace containing both blades, and we denote it by \(\vv{A} \cup \vv{B}\).

The meet of blades \(\vv{A}\) and \(\vv{B}\) is the largest subspace contained by both blades, and we denote it by \(\vv{A} \cap \vv{B}\).

For this section we follow the notation in Geometric Algebra for Subspace Operations by Bouma, Dorst, and Pijls. Macdonald writes the vee operator for the meet, but I’m worried this will make it seem it’s closely related to the outer product. Commandeering the union and intersection symbols from set theory does deprive them of their usual meaning, but this is seldom missed in geometric algebra.

While efficiently computable (see above paper), neither the join or meet have a simple general geometric algebra formula. However, one can be easily written in terms of the other. If \(\vv{J} = \vv{A} \cup \vv{B}\) then:

\[ \vv{A} \cap \vv{B} = \vv{A} \vv{J}^{-1} \cdot \vv{B} \]

In practice, we often encounter special cases where the join is trivially determined. Frequently, two blades only have the origin in common, in which case their join is simply their outer product.

Another common case is when two blades span the whole space:

\[ \vv{A} \cap \vv{B} = \vv{A}^* \cdot \vv{B} \]

There’s an issue involving the scalar multiplier possessed by a meet or join, which we blissfully ignore. It means that the sign of our result might be flipped, but this is automatically corrected when normalizing homogeneous coordinates.

This equation is reminiscent of De Morgan’s law: a point is a member of \(\vv{A} \cap \vv{B}\) if and only if it is orthogonal to both \(\vv{A}^\) and \(\vv{B}^\), that is, it lies in $(\vv{A}^* \wedge \vv{B}⁾$. Duality of the inner and outer products implies we may replace this with \(\vv{A}^* \cdot \vv{B}\).

In Haskell, for the homogeneous model of \(\mathbb{R}^3\):

We’re working in a projective space, so if given a line parallel to a plane in 3D, meet will return the point at infinity for the direction of the line. This feature is unneeded so we simply use our fromHGA function to remove these answers.

Despite their elegance and simplicity, the above equations are practical. We use them to solve our problem.

To find the cross-section produced by slicing a plane through a cube, for each edge, we compute its point of intersection with the given plane by finding the meet of the plane and the line defined by the points of the edge. We ignore intersection points that lie outside the cube, and the remaining points determine the polygon we see.

Let’s try this for one particular plane containing the axis through (0, 1/2, 0) and (1, 1/2, 1):

These are the vertices of a regular hexagon.

Next, let’s find the cutting plane for any given angle. We’ll use matrices so we define functions familiar to anyone with experience in computer graphics: embedding a 3x3 matrix into a 4x4 matrix for the homoegeneous model, matrix multiplication by another matrix or by a vector, and building a translation matrix:

We still cling to geometric algebra for the rotations. After computing the rotor from the axis and angle of rotation, we derive the rotation matrix by observing where the rotor sends our basis vectors.

We start with the plane defined by (0, 0, 0), (0, 0, 1), and (1, 0, 1). Rotating this around the axis going through the origin and (1, 0, 1), then translating it by 0.5 along the \(y\)-axis is equivalent to the rotating plane from our problem.

We use an outermorphism to compute where a matrix maps a plane, that is, we apply the matrix to the three points that define the plane, then compute their outer product.

Thus the following gives the coordinates of the polygon resulting from cutting the cube with the plane rotated to the given angle:

We throw together some code toanimate our rotating plane cutting a cube at the top of this very webpage:

With one more dimension, we can do much more.