Brief Introduction to Conformal Geometric Algebra

Modern day graphics systems are an amalgam of matrix, vector, and tensor algebras. These algebras runs fast in computers, but the intricacies of the algebraic representation makes it difficult the geometric insight. Within the last decade, Geometric Algebra has emerged as a powerful alternative to classical matrix, vector and tensor algebras as a comprehensive conceptual language and computational system for computer science. Great research has been done demonstrating its powers of synthesis, especially with regards to control systems generated by twist groups and motor algebras, but little research focuses on their applications to computer graphics, so its use remains a relatively esoteric exercise. As a result, many of its formal characteristics have yet to be explored. The aim of this post is to encourage the reader for use geometric algebra in modeling applications and computer graphics.

Geometric Algebra can be defined as the subset of Clifford Algebra that has geometric interpretation. In Conformal Geometric Algebra (CGA), rigid body motions can be represented as compact (multi-)vectors called Motors. Unlike homogeneous matrices, motors are linear transformations. All multivectors can be transformed by motors in a covariant and linear way. CGA motors can be efficiently interpolated for generating continuously deformed motions, and that is one of the main features that we should exploit in computer graphics. On the other hand, the interpolation of matrices is difficult and expensive. The logarithm of a matrix can be defined but is not elementary and not in closed form. A straightforward way to compute it is to take the eigenvalue decomposition of the rigid body motion matrix in the homogeneous coordinate framework, and take the Nth root of the diagonal matrix. Such numerical techniques makes the matrix logarithm expensive to compute and hard to analyze.

3D Geometric Algebra

Outer Product

It is well known that a vector \mathbf x may be interpreted geometrically as representing a direction in space. If the space has a metric, then the magnitude of \mathbf x is interpreted as its length. The introduction of the outer product enables us to extend the entities of the space to higher dimensions. The outer product of two vectors \mathbf x_0 \wedge \mathbf x_1, called a bivector, may be visualized as the two-dimensional analogue of a direction, that is, a planar direction. Neither vectors nor bivectors are interpreted as being located anywhere since they do not possess sufficient information to specify independently both a direction and a position. If the space has a metric, then the magnitude of \mathbf x_0 \wedge \mathbf x_1 is interpreted as its area \|\mathbf x_0 \wedge \mathbf x_1\| = \|\mathbf x_0\| \|\mathbf x_1\| \sin \theta, and similarly for higher order products.

The bivector \mathbf x_0 \wedge \mathbf x_1 is not a vector, and so does not belong to the original linear space. In fact the bivectors form their own linear space. The fundamental defining characteristic of the exterior product is its anti-symmetry. That is, the product changes sign if the order of the factors is reversed.

\mathbf x_0 \wedge \mathbf x_1 = -\mathbf x_1 \wedge \mathbf x_0

that means the orientation of the bivector \mathbf x_0 \wedge \mathbf x_1 is reversed when we take the product in the opposite order i.e., the plane normal would point in the opposite direction. This property also implies that \mathbf x_0 \wedge \mathbf x_0 = \mathbf x_1 \wedge \mathbf x_1 = 0, whose interpretation is that a new subspace (a plane for example) cannot be created from linearly dependent vectors.

Other properties of the outer product are:

\mathbf a \wedge (\mathbf b + \mathbf c) = (\mathbf a \wedge \mathbf b) + (\mathbf a \wedge \mathbf c)
\mathbf a \wedge (\mathbf b \wedge \mathbf c) = (\mathbf a \wedge \mathbf b) \wedge \mathbf c
\mathbf a \wedge (\beta \mathbf b) = \beta (\mathbf a \wedge \mathbf b)
\beta \wedge \mathbf b = \mathbf b \wedge \beta = \beta \mathbf b

We can express the bivector \mathbf a \wedge \mathbf b in terms of its basis. Given a orthonormal basis of vectors denoted as \{ \mathbf e_1, \mathbf e_2, \mathbf e_3\} and the vectors \mathbf a = a_1 \mathbf e_1 + a_2 \mathbf e_2 + a_3 \mathbf e_3 and \mathbf b = b_1 \mathbf e_1 + b_2 \mathbf e_2 + b_3 \mathbf e_3 the bivector \mathbf a \wedge \mathbf b is a linear combination of basis bivectors:

\mathbf a \wedge \mathbf b = (a_1 \mathbf e_1 + a_2 \mathbf e_2 + a_3 \mathbf e_3) \wedge (b_1 \mathbf e_1 + b_2 \mathbf e_2 + b_3 \mathbf e_3)
\mathbf a \wedge \mathbf b = \alpha \ \mathbf e_1 \wedge \mathbf e_2 + \beta \ \mathbf e_3 \wedge \mathbf e_1 + \gamma \ \mathbf e_2 \wedge \mathbf e_3

where \alpha = a_1 b_2 - a_2 b_1, \beta =  a_3 b_1 - a_1 b_3 and \gamma = a_2 b_3 - a_3 b_2. The scalar factors appearing here are just those which would have appeared in the usual vector cross product of \mathbf a and \mathbf b. However, there is an important difference, the outer product is valid for any number of vectors in spaces of arbitrary dimension, while the cross product is necessarily confined to products of two vectors in a space of three dimensions. We will use the notation \mathbf e_{ij} for basis bivectors \mathbf e_i \wedge \mathbf e_j, for example \mathbf e_{12} is equal to \mathbf e_1 \wedge \mathbf e_2.

High dimensional subspaces can be constructed such as the trivectors defined as \mathbf a \wedge \mathbf b \wedge \mathbf c which encodes a three-dimensional subspace whose norm is the volume of the parallelepiped formed by the vectors \mathbf a, \mathbf b and \mathbf c.

\mathbf a \wedge \mathbf b \wedge \mathbf c = \lambda \ \mathbf e_1 \wedge \mathbf e_2 \wedge \mathbf e_3

where \lambda = (a_1 b_2 c_3 - a_3 b_2 c_1 + a_2 b_3 c_1 + a_3 b_1 c_2 - a_1 b_3 c_2 - a_2 b_1 c_3). A trivector in a space of three dimensions has just one component.

Grade of a vector

The outer product also defines the grade of geometric objects, for example, bivectors are grade-2 vectors and trivectors are grade-3 vectors. Euclidian vectors are grade-1 vectors, denoted as 1-vectors and scalars are 0-vectors. In general a k-vector, denoted as \mathbf A_k is a vector of grade k.

Multivectors

A multivector is a vector that can have mixed grades. Such objects are also known outside the geometric algebra, for example a quaternion is an entity made of a scalar component and a vector component, and the quaternion basis is \{1, \mathbf i, \mathbf j, \mathbf k\}. In a similar way, the basis for the 3-D geometric algebra multivectors is the following:

\{1, \ \mathbf e_1, \ \mathbf e_2, \ \mathbf e_3, \ \mathbf e_{12}, \ \mathbf e_{31}, \ \mathbf e_{23}, \ \mathbf I_3 = \mathbf e_{123}\}

The k-vector of highest grade is known as pseudoscalar i.e., In 3-D geometric algebra the trivector \mathbf I_3 = \mathbf e_{123} is the pseudoscalar.

Reverses

An important algebraic operation applied to multivectors is reversion. This plays an analogous role to transposition in matrix algebra. The reverse of a k-vector \mathbf B_k = \mathbf e_1 \wedge \mathbf e_2 \wedge ... \wedge \mathbf e_k is defined as \mathbf{\tilde B_k} = \mathbf e_k \wedge \mathbf e_{k-1} \wedge ... \wedge \mathbf e_1. Also can be defined as \mathbf{\tilde B_k} = (-1)^{k(k-1)/2} \mathbf B_k.

Inner Product

The inner product of two vectors \mathbf a and \mathbf b is defined as usual \mathbf a \cdot \mathbf b = \|\mathbf a\| \|\mathbf b\| \cos \theta, and similarly, the inner product of two k-vectors \mathbf A_k and \mathbf B_k is defined as \mathbf A_k \cdot \mathbf B_k = \|\mathbf A_k\| \|\mathbf B_k\| \cos \theta. The inner product of a vector \mathbf c and a bivector \mathbf B is defined as \mathbf c \cdot \mathbf B = \mathbf c \cdot (\mathbf a \wedge \mathbf b) = (\mathbf c \cdot \mathbf a) \wedge \mathbf b - \mathbf a \wedge (\mathbf c \cdot \mathbf b) that is also a vector. More precisely, \mathbf c \cdot \mathbf B is a vector that lies in the \mathbf B plane and is orthogonal to the projection of the \mathbf c vector on the \mathbf B plane, i.e., \mathbf c \cdot (\mathbf c \cdot \mathbf B) = 0. The inner product of a vector \mathbf d and a trivector \mathbf a \wedge \mathbf b \wedge \mathbf c is defined as \mathbf d \cdot (\mathbf a \wedge \mathbf b \wedge \mathbf c) = (\mathbf d \cdot \mathbf a) \wedge \mathbf b \wedge \mathbf c - \mathbf a \wedge (\mathbf d \cdot \mathbf b) \wedge \mathbf c + \mathbf a \wedge \mathbf b \wedge (\mathbf d \cdot \mathbf c) that is a bivector. That is \mathbf d \cdot (\mathbf a \wedge \mathbf b \wedge \mathbf c) is the bivector orthogonal to the vector \mathbf d. The inner product of a bivector \mathbf d \wedge \mathbf e and a trivector \mathbf a \wedge \mathbf b \wedge \mathbf c is defined as (\mathbf d \wedge \mathbf e) \cdot (\mathbf a \wedge \mathbf b \wedge \mathbf c) = \mathbf d \cdot (\mathbf e \cdot (\mathbf a \wedge \mathbf b \wedge \mathbf c)) that is a vector perpendicular to the bivector \mathbf d \wedge \mathbf e.

In general, the inner product of a k-vector and a n-vector where n > k gives as a result an element of grade n - k that is perpendicular to the k-vector.

The inner product properties:

\alpha \cdot \mathbf A = \alpha \mathbf A
(\mathbf A + \mathbf B) \cdot \mathbf C = \mathbf A \cdot \mathbf C + \mathbf B \cdot \mathbf C
\mathbf C \cdot (\mathbf A + \mathbf B)= \mathbf C \cdot \mathbf A + \mathbf C \cdot \mathbf B
\mathbf A_k \cdot \mathbf C_n = (\mathbf A_{k-1} \wedge \mathbf a) \cdot \mathbf C_n = \mathbf A_{k-1} \cdot (\mathbf a \cdot \mathbf C_n)
\mathbf a \cdot \mathbf C_n = \sum_{i=1}^{n}{(-1)^{i-1} \mathbf c_1 \wedge ... \wedge (\mathbf a \cdot \mathbf c_i) \wedge ... \wedge \mathbf c_n}

Dualization

The inner product of a k-vector and the reverse of the pseudoscalar \mathbf {\tilde I_n} gives as a result an element of grade n - k that is perpendicular to the k-vector. That operation is called dualization and is denoted with an asterisk (\ast) superscript, for example the dual of a vector \mathbf a is \mathbf a^{\ast} = \mathbf a \cdot \mathbf{\tilde I_3} that is a bivector perpendicular to the vector \mathbf a. A notorious dualization is the bivector dual (\mathbf a \wedge \mathbf b)^{\ast} = \mathbf a \times \mathbf b that is the cross product of vectors \mathbf a and \mathbf b.

Geometric Product

The geometric product of two vectors \mathbf a and \mathbf b is defined as:

\mathbf a \ \mathbf b = \mathbf a \cdot \mathbf b + \mathbf a \wedge \mathbf b

under the geometric product, orthogonal vectors anticommute and parallel vectors commute. The product therefore encodes the basic geometric relationships between vectors. Similarly the geometric product of a vector \mathbf a and a bivector \mathbf B is \mathbf a \mathbf B = \mathbf a \cdot \mathbf B + \mathbf a \wedge \mathbf B.

The inner and outer products are not fundamental as we can define them in terms of the geometric product. We can take the k-vector part of a multivector using the k grade selection operator \langle \ \rangle_k. For example the grade-2 part of the product \mathbf a \mathbf b is \langle \mathbf a \mathbf b \rangle_2 = \mathbf a \wedge \mathbf b and the grade-0 part is \langle \mathbf a \mathbf b \rangle_0 = \mathbf a \cdot \mathbf b.

The geometric product is distributive over addition and is also associative but is not commutative in general. Although, the pseudoscalar commutes with all multivectors in the algebra. Also notice that the pseudoscalar satisfies:

\mathbf I^2 = -1

this also is true for the basis bivectors as \mathbf e_{12}^2 = \mathbf e_{31}^2 = \mathbf e_{23}^2 = -1.

Inverses

The inverse of a k-vector \mathbf A_k is defined as \mathbf A_k^{-1} = \frac{\mathbf{\tilde A_k}}{\|\mathbf A_k\|^2}, where \|\mathbf A_k\|^2 = \mathbf A_k \mathbf{\tilde A_k}. So the product \mathbf A_k \mathbf A_k^{-1} = 1

Rotors

In geometric algebra a special transformation, applied to an arbitrary multivector A, can be written in the form

A \mapsto R \ A \tilde R

Here R is an even-grade multivector (grades 0 and 2) satisfying R \tilde R = 1. The element R is called a Rotor. Every rotor can be written in terms of the exponential of a unit bivector \mathbf B as:

e^{-\mathbf B \theta / 2}= \cos (\theta / 2) - \mathbf B \sin (\theta / 2)

In 3-D geometric algebra, rotors are isomorphic to quaternions and they behave in the exact same way. In fact, rotors are the generalization of quaternions to the n-D spaces.

Conformal Geometric Algebra

The conformal group is the group of transformations that preserve angles. These include the rigid (euclidean) transformations. The conformal group on R^3 has a natural representation in terms of rotations in a 5-D space, with signature R^{4, 1} which means 4 basis vectors have a positive square, and 1 have a negative square. So, in the same way that projective transformations are linearised by working in a 4-D homogeneous space, conformal transformations are linearised in a 5-D space.

The main advantage of basing the description in a conformal setting is that distance is encoded simply. The euclidean distance of two points p and q is defined as its inner product:

p \cdot q = -\frac{1}{2} \|\mathbf p - \mathbf q\|^2

so, points in conformal geometric algebra are null vectors i.e., a point p has null square:

p^2 = 0

because the distance to itself is zero. The existence of null vectors is guaranteed by the fact that the conformal vector space has mixed signature. The conformal vector space poses the three vectors \mathbf e_1, \mathbf e_2 and \mathbf e_3 and we add to these the vectors \mathbf e_0 and \mathbf e_4, so that all 5 vectors are orthonormal. The new vectors satisfy:

\mathbf e_0^2 = -1 \ \ \ \mathbf e_4^2 = +1

From the two extra vectors we define the two null vectors o = \frac{1}{2} (\mathbf e_4 + \mathbf e_0) and \infty = \mathbf e_4 - \mathbf e_0, so that o \cdot o = 0, \infty \cdot \infty = 0. The new basis vectors o and \infty (also called Minkowski basis) are not orthogonal anymore so that o \cdot \infty = -1 but are still orthogonal to the euclidean basis vectors \mathbf e_1, \mathbf e_2 and \mathbf e_3, so that o \cdot \mathbf e_i = \infty \cdot \mathbf e_i = 0. The o vector can be interpreted as the point at the origin and the \infty as the point at infinity.

A general null vector p can be constructed in the new basis \{ o, \mathbf e_1, \mathbf e_2, \mathbf e_3, \infty \}, given a euclidean vector \mathbf p as:

p = o + \mathbf p + \frac{1}{2} \|\mathbf p\|^2 \infty

This null vector p can be interpreted as a euclidean point. Note that if \mathbf p is at the origin \mathbf p = 0 e_1 + 0 e_2 + 0 e_3 then the point p = o, and if \mathbf p is far from the origin the point p approaches the point at infinity \infty.

Geometric Primitives

Round objects such as spheres and circles can be constructed easily from null points. A circle C that pass through the points x_0, x_1 and x_2 is given by:

C = x_0 \wedge x_1 \wedge x_2

And the sphere S that pass through the points x_0, x_1, x_2 and x_3 is given by:

S = x_0 \wedge x_1 \wedge x_2 \wedge x_3

Flat objects such as planes and lines can be constructed easily as well since they are just round objects passing through the point at infinity \infty. A line L that pass through points x_0 and x_1 is given by:

L = x_0 \wedge x_1 \wedge \infty

And the plane P that pass through the points x_0, x_1 and x_2 is given by:

P = x_0 \wedge x_1 \wedge x_2 \wedge \infty

We also can construct the line L passing through the point x_0 and with direction vector \mathbf v as L = x_0 \wedge \mathbf v \wedge \infty and we can construct the plane P passing through the origin o having the direction bivector \mathbf B as P = o \wedge B \wedge \infty.

The dual representations of rounds and flats is useful for the construction of geometric objects when we have certain parameters instead of points. For instance if we have the center and radius for circles and spheres or the normal vector and distance to the origin in the case of flats, it is more convenient to use the dual representation.

CGA Motors

A conformal tranformation R is an even-grade multivector satisfying R \tilde R = 1 and can be written as the exponential of a unit bivector B:

R = e^B

For example a euclidean translation is given by T_{\mathbf v} = e^{ -\frac{1}{2} \mathbf v \wedge \infty }, where \mathbf v is the translation vector. The rotation rotor is given by R_{\mathbf B \theta} = e^{ -\frac{1}{2} \mathbf B \theta } where \mathbf B is the rotation (euclidean) bivector. The scaling rotor is given by S_{\gamma} = e^{ -\frac{1}{2} \gamma o \wedge \infty } where \gamma is the positive scaling factor.

A general rigid body motion (or motor) can be represented as:

M = T_{\mathbf v} R_{B \theta}

where T_{\mathbf v} is a translation rotor and R_{B \theta} is a rotation rotor.

Motor Interpolation

Conformal transformations can be applied gradually to any object by splitting the conformal motor R = e^B in n equal parts through R^{1/n} = e^{B/n} and then applying them in n time steps. A simple way to get the linear interpolation between two motors R_1 = e^{B_1} and R_2 = e^{B_2} is R_{\alpha} = e^{(1 - \alpha) B_1 + \alpha B_2}. This formulation requires to take the motor logarithms B_1 = \log (R_1) and B_2 = \log (R_2).

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s