Search

This article compares five models of 3D Euclidean geometry-not theoretically, but by demonstrating how to implement a simple recursive ray tracer in each of them. It's meant as a tangible case study of the profitability of choosing an appropriate model, discussing the trade-offs between elegance and performance for this particular application. The models we compare are 3D linear algebra, 3D geometric algebra, 4D linear algebra, 4D geometric algebra, and 5D geometric algebra.

This chapter starts afresh and introduces the basics of Clifford algebra to develop a powerful geometric algebra. This geometric algebra incorporates operators on subspaces into the framework and permits to displace the constructions of the subspace algebra in a structure-preserving manner. The crucial construction is to unify the qualitative and quantitative subspace products into a single geometric product, more fundamental than either. The geometric product is invertible, and it allows manipulating and solving of equations about geometrical quantities almost as if they were regular arithmetical expressions. The true power of this geometric product will become clear in the next chapter, when it is used to define the versor product construction for operators. This chapter defines the geometric product, first for vectors and then for general multi-vectors. Subsequently, this chapter shows how the geometric product indeed subsumes the earlier products (which is a bit of tedious but necessary algebra), and ending up with the use of its invertibility to define general projection and rejection operations through geometric division.

The outer product of the previous chapter can span subspaces. It also enables to compare lengths on a line, areas in the same plane, and volumes in the same space. There clearly is a need to compare lengths on different lines and areas in different planes. The non-metrical outer product cannot do that, so this chapter extends the subspace algebra with a real-valued scalar product to serve this (geo)metric need. It generalizes the familiar dot product between vectors to act between blades of the same grade. Then it carries the algebra further and investigates how the scalar product and the outer product interact. This automatically leads to an inner product between subspaces of different dimensionality called the “contraction.” The contraction of subspace A onto subspace B computes the part of B least like A. That also gives a dual way to characterize subspaces through blades denoting their orthogonal complement. With these metric products, it is easy to compute geometrically useful operations like the orthogonal projection and determine reciprocal frames for non-orthonormal coordinate systems. They can even be used to embed the 3-D cross product, although strong arguments are provided for using geometric algebra constructs instead.

Publisher Summary Even with all the new techniques for Euclidean geometry in the previous three chapters, the possibilities of the conformal model are not exhausted. There are more versors in it, and they represent other useful transformations. Euclidean motions were just a special case of doing conformal transformations, which preserve angles. These also include reflection in a sphere and uniform scaling. All conformal transformations are generated by versor products using the elementary vectors of the conformal model. Whereas the Euclidean motions of the previous chapter involved using the vectors representing dual planes, it now uses the dual spheres. In the classical literature on conformal operations, one introduces the operation of transversion. This may be defined as the triple composition of an inversion in the unit sphere, followed by a translation, followed by another inversion in the unit sphere. An important operation that can then be put into rotor form is uniform scaling, which permits a closed-form solution to the interpolation of rigid body motions with scaling. The fact that the general conformal transformations can be represented as versors finally explains the name of the conformal model.

Publisher Summary Geometric algebra contains operations to determine the union and intersection of subspaces, the join and meet products. When applied to the subspaces at the origin, meet and join generalize some specific formulas from 3-D linear algebra into a more unified framework, and extend them to subspaces intersecting in n-dimensional space. The join is often more easily determined than the meet, since the most interesting intersections and unions of subspaces tend to occur when they are in general position within some subspace with a known pseudoscalar (two planes in space, a line, and a plane in space). Then the join is just the pseudoscalar of that common subspace, and gives the meet. Once the join has been selected, the formula for the meet shows that the meet is linear in two planes, A and B, since it can be expressed by contraction products, which are clearly linear. If we change A and/or B such that the join does not change, this remains true, which implies that the meet is mostly linear. If the join is normalized then the value of the meet can be interpreted as proportional to the sine between A and its projection on B.

The linear products used in this book are the geometric product, the outer product, the contraction inner products, the scalar product, and the commutator product. They are all linear in their arguments. Examples of unary linear operations that are discussed in this chapter are addition, reversion, grade involution, and grade extraction of multi-vectors. This chapter presents two ways to implement the linear products and operations of geometric algebra. Both implementation approaches are based on the linearity and distributivity of these products and operations. The first approach uses linear algebra to encode the multiplying element as a square matrix acting on the multiplied element, which is encoded as a column matrix. This approach is presented because the matrix ideas are familiar to many people because it is convenient, and because it works for general Clifford algebras. However, it does not exploit the sparseness of most elements in geometric algebra, and is not used much in practice. The second approach is effectively a sparse matrix approach and uses the basis blades idea of the previous chapter, storing multi-vectors as lists of weighted basis blades and literally distributing the work of computing the products and operations to the level of basis blades.

The homogeneous model of Euclidean geometry is reasonably effective since it linearizes Euclidean transformations, and geometric algebra extends the classical homogeneous coordinate techniques nicely through its outermorphisms. In the next few chapters, the book presents the new conformal model for Euclidean geometry, which can represent Euclidean transformations as orthogonal transformations. Encoding those as versors gets the full power of geometric algebra, including the structure preservation of all constructions. This chapter starts the exposition by defining the new representational space (which has two extra dimensions and a degenerate metric) and showing what its vectors represent. The two extra dimensions are geometrically interpretable as the point at the origin (as in the homogeneous model) and the point at infinity (which nicely closes Euclidean geometry, making translations into rotations around infinity). It then focuses on how to represent the familiar flats and directions already present in the homogeneous model and how to move them around. As first applications, it uses the versor representation to provide straightforward closed-form interpolation of rigid body motions and universally valid constructions for the reflection of arbitrary elements. The natural coordinate-free specification of elements and operations in the conformal model is best appreciated using the interactive illustrations.

Publisher Summary While the 3-D vector space model can nicely model directions, it is usually considered to be inadequate for use in 3-D computer graphics, primarily because of a desire to treat points and vectors as different elements that are transformed differently by translations. Instead, people commonly use an extension of linear algebra known as homogeneous coordinates. This is often described as augmenting a 3-D vector v with coordinates (v1,v2,v3)T to a 4-vector (v1,v2,v3,1)T. This extension makes nonlinear operations such as translations implementable as linear mappings. For the homogeneous model in geometric algebra, the modeling principle is the same: it embeds the n-dimensional base space Rn in an (n +1)-dimensional representational vector space Rn+1, of which it then uses the inherent algebra. That produces a complete algebraic framework, which is well suited to compute with oriented flats, subspaces offset from the origin in Rn represented as blades in Rn+1. The algebra of Rn+1 provides generally applicable formulas for translation, rotation, and even affine and projective transformations in the base space Rn. The operations of meet and join always return sensible results for incidences of flats. Some of the incidence constructions are cross ratios and can be interpreted as defining motion-invariant measures. Then motions and transformations are studied and show that all direct flats are moved by the same linear transformation and all dual flats by another. This simplifies the code even more.

This chapter shows that a vector space is much more than merely a space of vectors, and that it is straightforward and useful to extend it computationally. The crucial idea here is to make the subspaces of vector space explicit elements of computation. To build the algebra of subspaces, the familiar lines and planes are revisited through the origin. This chapter investigates their geometrical properties carefully and formalizes those by the aid of a new algebraic outer product, which algebraically builds subspaces from vectors. The structure it produces is considered for the Grassmann space of subspaces of a vector space R n , and defines many terms to describe its features. Throughout this chapter, it considers a real n-dimensional vector space R n , but has no need for a metric; additionally, it only treats its homogeneous subspaces (i.e., subspaces containing the origin). The chapter starts with an n-dimensional vector space. However, the definition of a vector space in linear algebra is more general than what is needed in this book, being defined over arbitrary fields of scalars. To develop thinking about subspaces, the homogeneous subspaces of a 3-D space are considered.

Linear transformations of a vector space R n change its vectors. When this happens, the blades spanned by those vectors change quite naturally to become the spans of the transformed vectors. That defines the extension of a linear transformation to the full subspace algebra. This embedding provides more powerful tools to apply linear transformations immediately to subspaces without needing to first decompose those subspaces into vectors. This chapter studies the resulting structure. The algebra dictates how the outer products and contractions of transformed blades should be done, and in that way gives the transformation formulas for the products themselves. Transforming contractions is a lot more involved than transforming outer products, since it involves the metric of the space; however, the effort pays off by providing a compact coordinate-free formula for the inverse of a linear transformation. This book is mostly interested in orthogonal transformations. Some of their properties can easily be derived and it can be seen why they are special in this chapter (they are the only transformations that are structure-preserving for the contraction). Their real importance and ease of representation will be revealed in later chapters.

Publisher Summary This chapter puts the algebra to work by using it to implement a ray tracer in the C++ programming language. A ray tracer is a program that takes as input the description of a scene (including light sources, models, and camera) and produces an image of that scene as seen from the camera. The chapter shows how the conformal model of Euclidean geometry is very useful for the specification and computation of the basic operations. All geometrical elements occurring in this problem have a natural representation in that model. When really trying to optimize the speed of the ray tracer, it is argued that one may want to deviate from the natural all-purpose representation to a more dedicated choice, which anticipates the typical ray tracing operations that are going to be performed on the data. That is, some of the elegance of the conformal model is traded off for added efficiency. Even then, each of these choices can be described and compared within the conformal model, which moreover always supplies the necessary transformations in its versor representation. The resulting compromise between algebraic elegance and practical performance is probably typical of many applications. In the process, a graphical user interface is written to manipulate objects in a viewport, as well as the camera that produces the view. This is another application in which the conformal model shows its power by giving directly executable expressions connecting mouse coordinates to the simulated motions. Here, practical performance and algebraic elegance coincide in a satisfying manner.

The previous chapter looked at how to implement the linear products in geometric algebra. The linearity of these products allows implementation of them using linear algebra or through a simple double loop. However, there are other operations in geometric algebra that are nonlinear (such as inverse, meet, join, and factorization). These cannot be implemented in the same way. This chapter discusses the implementation of such nonlinear geometric algebra operations. The nonlinearity results in more complex algorithms, still reasonably efficient but typically an order of magnitude more time-consuming than linear operations. One needs to compute the inverse of the elements that are constructed in geometric algebra. Those are almost exclusively blades or versors (the only exceptions were the bi-vectors in an exponent, and there is no need to invert those). Invertible blades are always versors, since a k-blade (the outer product of k vectors) can always be written as the geometric product of k vectors (i.e., a k-versor). So if a versor V is inverted, it can also invert blades and thus most of the elements constructed. This chapter gives algorithms for the inverse, for exponentiation, for testing whether multi-vector is a blade or a versor, for blade factorization, and for the efficient computation of meet and join.

Publisher Summary Differentiation is the process of computing with changes in quantities. When the changes are small, those computations can be linear to a good approximation, and it is not difficult to develop a calculus for geometry by analogy to classical analysis. When formulated with geometric algebra, it becomes possible to differentiate not only with respect to a scalar (as in real calculus) or a vector (as in vector calculus), but also with respect to general multivectors and k-blades. Parametric differentiation is concerned with changes in elements in their dependence on their defining constituents. As such, it generalizes both the usual scalar differentiation and the derivative from vector calculus. All differentiation is based on functional dependence of scalar functions. Geometric algebra offers a way of computing with derivatives without using coordinates in the first place, by developing a calculus to apply them to its elements constructed using its products. The different forms of differentiation can be extended beyond vectors to general multivectors, though for geometric algebra, the extension to differentiation with respect to blades and versors is most useful. Another extension is the differentiation with respect to a linear function of multivectors, which finds uses in optimization.

Publisher Summary More complicated geometrical objects do not require new operations or techniques in geometric algebra, merely the standard computations in a higher-dimensional space, followed by an interpretation step. The geometric algebra approach considerably extends the classical techniques of homogeneous coordinates, so it pays to redevelop this fairly well-known material. The better model to treat the metric aspects of Euclidean geometry is a representation that can make full use of the power of geometric algebra. That is the conformal model which requires two extra dimensions. It provides an isometric model of Euclidean geometry. In this representation, all Euclidean transformations become representable as versors, and are therefore manifestly structure-preserving. This gives a satisfyingly transparent structure for dealing with objects and operators, far transcending the classical homogeneous coordinate techniques. Initially, it shows how this indeed extends the homogeneous model with metric capabilities, such as the smooth interpolation of rigid body motions. Then it is found that there are other elements of Euclidean geometry naturally represented as blades in this model: spheres, circles, point pairs, and tangents. These begin to suggest applications and algorithms that transcend the usual methods. In the last chapter on the conformal model, the reason behind its name is found: all conformal (angle-preserving) transformations are versors, and this now also gives the possibility to smoothly interpolate rigid body motions with scaling. In all of these chapters, the use of the interactive software is important to convey how natural and intuitive these new tools can become.

Publisher Summary The homogeneous model of Euclidean geometry is reasonably effective since it linearizes Euclidean transformations, and geometric algebra extends the classical homogeneous coordinate techniques nicely through its outermorphisms. In the next few chapters, the book presents the new conformal model for Euclidean geometry, which can represent Euclidean transformations as orthogonal transformations. Encoding those as versors gets the full power of geometric algebra, including the structure preservation of all constructions. This chapter starts the exposition by defining the new representational space (which has two extra dimensions and a degenerate metric) and showing what its vectors represent. The two extra dimensions are geometrically interpretable as the point at the origin (as in the homogeneous model) and the point at infinity (which nicely closes Euclidean geometry, making translations into rotations around infinity). It then focuses on how to represent the familiar flats and directions already present in the homogeneous model and how to move them around. As first applications, it uses the versor representation to provide straightforward closed-form interpolation of rigid body motions and universally valid constructions for the reflection of arbitrary elements. The natural coordinate-free specification of elements and operations in the conformal model is best appreciated using the interactive illustrations.

Publisher Summary This chapter provides an introduction to geometric algebra, a powerful computational system used to describe and solve geometrical problems. The main features of geometric algebra includes that vectors can be used to represent aspects of geometry, but the precise correspondence is a modeling choice. Geometric algebra offers three increasingly powerful models for Euclidean geometry. Geometric algebra has products to combine vectors to new elements of computation. They represent oriented subspaces of any dimension, and they have rich geometric interpretations within the models. A linear transformation on the vector space dictates how subspaces transform; this augments the power of linear algebra in a structural manner to the extended elements. Geometric objects and operators are represented on a par and are exchangeable: objects can act as operators, and operators can be transformed such as geometrical objects. Geometric algebra focuses on the subspaces of a vector space as elements of computation. It constructs these systematically from the underlying vector space and extends the matrix techniques to transform them, even supplanting those completely when the transformations are orthogonal. In the vector space model and the conformal model, orthogonal transformations are used to represent basic motions of Euclidean geometry. This makes that type of linear transformation fundamental to doing geometry in the models.

The meet is greatly extended in its capabilities to intersect arbitrary flats and rounds (though always with the same formula X ∩ Y = Y∗˩X), or to compute other incidences. The results can be real or imaginary, or even the infinitesimal tangents. The dual of the meet provides a novel operation: the plunge, which constructs the simplest element intersecting a given group of elements perpendicularly. Once recognized, it is easy to spot it in many constructions, and it enables one to quickly write down correct expressions for, say, the contour circle of a sphere seen from a given point. This chapter shows how all the various concepts of a vector in classical geometry find their specific expression in the conformal model. Normal vectors, position vectors, free vectors, line vectors, and tangent vectors now all automatically move in the correct way under the same Euclidean rotors. This clearly demonstrates that the conformal model performs both the geometrical computations and the “data type management” required in Euclidean geometry. It is concluded with a sample analysis of some involved planar geometry (the geometry of a Voronoi cell), and compare the coordinate-free conformal solution to the many parameters involved in even just specifying the classical solution.

Reflection in a line is represented by a sandwiching construction involving the geometric product. Though that may have seemed like a curiosity in the previous chapter, it is crucial to the representation of operators in geometric algebra. Geometrically, all orthogonal transformations can be considered as multiple reflections. Algebraically, this leads to their representation as a geometric product of unit vectors. An even number of reflection gives a rotation, represented as a rotor—the geometric product of an even number of unit vectors. This chapter shows that rotors encompass and extend complex numbers and quaternions, and present a real 3-D visualization of the quaternion product. Rotors transcend quaternions in that they can be applied to elements of any grade, in a space of any dimension. The distinction between subspaces and operators fades when it is realized that any subspace generates a reflection operator, which can act on any element. The concept of a versor (a product of vectors to be used as an operator in a sandwiching product) combines all these representations of orthogonal transformations. This chapter shows that versors preserve the structure of geometric constructions and can be universally applied to any geometrical element. This is a unique feature of geometric algebra and it can simplify code considerably. The chapter ends with a discussion of the difference between geometric algebra and Clifford algebra, and a preliminary consideration of issues in efficient implementation to convince users of the practical usability of the versor techniques in writing efficient code for geometry.

All geometric algebra implementations that represent multi-vectors as a weighted sum of basis blades will, at some point, have to compute products of basis blades. Among the various products, the capability to compute the geometric product (also for non-Euclidean metrics) is clearly the minimum requirement, as the outer product and various flavors of the inner products can be derived from it by using the (anti-) symmetry or grade selection techniques. This chapter describes how to implement this geometric product of basis blades through a convenient representation of basis blades. The algorithms described are quite simple, yet intricate enough that we need (pseudo)code to describe them precisely. Instead of introducing a unique pseudocode language, this chapter opted to simply use Java. The code in this chapter therefore corresponds well to the reference implementation at the web site http://www.geometricalgebra.net, although it is sometimes slightly polished for presentation. Conceptually, the basis blades representation uses a list of booleans and applies boolean logic to the elements of that list. But in practice, the list of booleans is implemented using bitmaps and the bitwise boolean operators. To correspond more directly to the actual implementation, that is how the representation and its operators are presented in this chapter.

Now that the conformal model of Euclidean geometry has been described and its effectiveness has been seen, it is useful to take a step back and look in a more abstract manner at what has actually been done and why it works so well. Doing so will provide a tentative glimpse of future developments in this way of encoding geometries. Geometry (affine, Euclidean, conformal, projective, or any other kind) is characterized by certain operators that act on the objects of the geometry. These objects can range from geometrical entities such as a triangle to properties such as length, so they may have various dimensionalities (which we call “grades”). In order to use this structural capability for a given geometry, a good representational space has to be found which then uses the geometric algebra. In this representational space, the symmetries should become isometries. Isometries are distance-preserving transformations; they are the orthogonal transformations in the representational space that can be represented by versors in the corresponding geometric algebra. Such a model of geometry is called an operational model, since it is fully designed around the operational symmetry that defines the geometry.

The homogeneous model is well-suited to applications in which incidences of offset flat subspaces are central, but less so when metric properties are also important. In this, it plays a role similar to Grassmann-Cayley algebra. This chapter gives details on its direct use in applications. In the first part, it discusses the coordinate representations of the homogeneous elements. This naturally embeds the powerful Plucker coordinates for line computations, which are seen to be are a natural extension of homogeneous point coordinates (using the outer product). This chapter shows how to master them and derive new application formulas simply. Those coordinates for lines, as well as points and planes, permit compact formulation of the affine transformations as matrices. In the second part, it gives an advanced application of the homogeneous model. It is well-suited to encode the projective geometry involved in the imaging of the world by one or more pinhole cameras. The homogeneous model permits easy specification of how observations in the various cameras are connected, which permits using observations by one camera to guide the search for corresponding features in another camera. This chapter treats the fairly advanced subjects of stereo-vision based on point and line matches in 2 or 3 cameras. Both subjects of this chapter are incidental to the main flow of the book, though the section on Plucker coordinates prepares for the implementation of geometric algebra in Part III.

This chapter continues the development of the conformal model of Euclidean geometry. It can be seen in the previous chapter how the model includes flats and directions as blades and Euclidean transformations on them as versors. That more or less copied the capabilities of the more familiar homogeneous model, though in a structure-preserving form, which permits metrically significant interpolation. This chapter shows that the blades of the conformal model can represent many more elements that are useful in Euclidean geometry: They give us spheres, circles, point pairs, and tangents as direct elements of computation. Having those available extends the range of computations that can be done by the basic products of geometric algebra, which is the subject of the next chapter. Here, the chapter carefully develops the representation of these new elements and shows how to retrieve their parameters. For instance, one will see that the sphere through the four points, p, q, r, and s is the blade p ∧ q ∧ r ∧ s, and that can immediately be read off its center and radius from the dual sphere (p ∧ q ∧ r ∧ s) ∗ .

Publisher Summary When geometric algebra was developed in the first part of this book, it illustrated the principles with pictures in which vectors are represented as arrows at the origin, bi-vectors as area elements at the origin, and so on. This is the purest way to show the geometric properties corresponding to the algebra. The examples show this algebra of the mathematical vector space Rn can already be used to model useful aspects of Euclidean geometry, for it is the algebra of directions of n-dimensional Euclidean space. Some more properties of this model are explored in this chapter, with special emphasis on computations with directions in 2-D and 3-D. Most topics are illustrated with programming exercises at the end of the chapter. First, this chapter shows how the vector space model can be used to derive fundamental results in the mathematics of angular relationships. It gives the basic laws of trigonometry in the plane and in space, and shows how rotors can be used to label and classify the crystallographic point groups. Then it computes with 3-D rotations in their rotor representation, establishing some straightforward techniques to construct a rotor from a given geometrical situation, either deterministically or in an optimal estimation procedure. The logarithm of a 3-D rotor enables it to interpolate rotations. Finally, external camera calibration is given an application to show how the vector space model can mix directional and locational aspects.

Publisher Summary An efficient geometric algebra implementation uses symbolic manipulations only to bootstrap the implementation, and not during actual run-time computations. All multivectors can be decomposed as a sum of basis blades. A k-blade only contains elements of grade k, and therefore has many zero entries in its coefficient vector, making the representation by 2n elements rather wasteful. This effect becomes stronger in higher dimensions. By taking the sum of basis blade implementation as the core approach, a geometric algebra implementation naturally splits into four levels. The levels include selecting the basis blades and implementing the basic operations on them, implementing linear operations for multivectors, implementing nonlinear operations on multivectors, and the application level. Geometric algebra contains some important operations that are elementary but not linear or distributive. As a consequence, the approach used in the middle-level implementation cannot be used here. These operations are implemented using specialized algorithms, which are actually largely independent of the middle-level implementation. The linearity and associativity of geometric algebra suggests representing the whole algebra with its geometric product by single matrix algebra: all elements become represented as 2n × 2n matrices, and the geometric product is represented as the matrix product.

Geometric Algebra (GA) is an algebra that encodes geometry much better than standard techniques, which are mainly based on linear algebra with various extensions. Compared to standard techniques, GA has clearer semantics and a richer, more consistent language. This expresses itself, among others, in a much greater genericity of functions over the algebra. Exploiting this genericity efficiently is a problem that can be solved through generative programming.This paper describes our Geometric Algebra Implementation Generator Gaigen 2. Gaigen 2 synthesizes highly efficient GA implementations from the specification of the algebra. Functions over such algebras can be defined in a high-level coordinate-free domain-specific language, and Gaigen 2 transforms these functions into low-level coordinate-based code. This code can be emitted in any target language through a custom back-end. Benchmarks of our implementation show that the combination of GA and Gaigen 2 can rival the performance of standard geometry techniques, despite the greater abstraction and genericity of GA.To obtain this high performance, Gaigen 2 must adapt the generated code to the program that links to it. This is done via a profiling feedback loop. While running, the generated code makes a connection to the code generator. The generated code sends information about functions that should be optimized. The code generator registers this information and sends back new type information. After the program terminates, the code is regenerated according to the recorded profile. This profiling feedback technique may also be useful to implement other types of algebras.

A method for estimating ego-motion with vehicle mounted stereo cameras is presented. This approach is based on finding corresponding features in stereo images and tracking them between succeeding stereo frames. Our approach estimates stereo ego-motion with geometric algebra techniques. Starting with a simple linear estimate of the ego-motion, estimates for the motion and reconstructed positions of features in space are updated incrementally. With simple algebraic operations it is possible to improve towards a high precision motion estimate. Accuracy of our algorithm has been measured with simulated data. These tests show improvement in motion estimation accuracy. Random sample consensus is used to safeguard the estimator against wrongly tracked features and influences of independently moving objects. We show the application of our approach in the real world by estimating the driven path of a vehicle in rough terrain from recorded stereo image sequences. © 2003 IEEE.