Publications

On this page you find a list of our GA-related publications in approximate chronological order (latest first). We also have a list of talks and a separate page with the three computer graphics and applications tutorials.

Publication Titles:

Publication Details:

An Algebraic Foundation for Object-Oriented Euclidean Geometry pdf, ps.gz

Leo Dorst, Daniel Fontijne.
In preparation for ITM 2003 proceedings.

The conformal model of Euclidean geometry in Geometric Algebra pro- vides a compact way to characterize Euclidean objects such as spheres, planes, circles, lines, etc. as blades. The algebraic structure of the model provides a `grammar' for these objects and their relationships. In this rather informal paper we explore this grammar, developing a new geo- metric intuition to use it eectively. This results in the identification of two important construction products, the known meet and the new plunge. These provide compact specification techniques to parametrize operators and objects directly in terms of other objects.

First order error propagation of the Procrustes method for 3-D attitude estimation pdf, ps.gz

Leo Dorst.
Accepted for IEEE-PAMI, 2004.

The well known Procrustes method determines the optimal rigid body motion that registers two point clouds by minimizing the square distances of the residuals. In this paper we perform a complete error analysis of this method for the 3D case, fully specifying how directional noise in the point clouds affects the estimated parameters of the rigid body motion. These results are much more specific than the error bounds which have been established in numerical analysis. We provide an intuitive understanding of the outcome to facilitate direct use in applications.

Combining orientation estimates pdf, ps.gz

Leo Dorst.
Accepted for Phil.Trans.Royal Soc.London, 2004.

Orientation measurements estimate relative rotations of objects. Such estimates may need to be averaged according to their covariances, e.g. for a Kalman filter. The non-commutative algebra of rotations makes transference of techniques inspired by the usual vector-based approaches for translations non-trivial. This paper shows in tutorial fashion how the rotor representation of rotations (which is an embedded form of the quaternion representation) permits straightforward computations with rotation estimates, from averaging and interpolation to filtering. We characterise rotational noise and present a way to combine estimates of orientations which minimises error covariance.

Interface Specification and Implementation Internals of a Program Module for Geometric Algebra

M.D. Zaharia, L. Dorst.
Accepted for Journal of Logic and Algebraic Programming, 2003

This paper describes a method to implement the main abstract opera- tions characteristic for Clifford algebra. The design goal was to maintain the algorithms simple, their specifications correspond (most frequently) to the basic definitions. The article is addressed to those who want to un- derstand the low-level processing mechanisms underlying the abstract con- cepts of geometric algebra. Efficiency considerations did not prevail in the present implementation. The package presented is freely available (at source level) and may assist the development of C/C++ applications us- ing the geometric algebra formalism. It could be easily extended in order to fit the specific requirements of a given application.

Modeling and Visualization of 3D Polygonal Mesh Surfaces using Geometric Algebra

M.D. Zaharia, L. Dorst,
Accepted for Computers & Graphics, 2003.

The language of geometric algebra can be used in the development of computer graphics applications. This paper proposes a method to describe a 3D polygonal mesh model using a representation technique based on geometric algebra and the conformal model of the 3D Euclidean space. It describes also the stages necessary to develop an application that uses this formalism. The current application was used to validate the implementation of the main abstract operations characteristic to a geometric algebra computational environment (programming module GAP). The data structures that characterize this geometric algebra based modelling approach as well as the implementation of geometric algebra based methods for model visual- ization/transformation are developed in detail. The paper emphasizes the elegance and generality of the geometric algebra approach referring also to the necessary computational resources.

Invertible Homogeneous Versors are Blades pdf, ps.gz

T.A. Bouma, G. Memowich.
This paper proves the theorem "Invertible Homogeneous Versors are Blades" for finite dimensional Geometric Algebras. This implies for Euclidean and Anti-Euclidean spaces that all homogeneous versors are blades. Furthermore, since an element is a blade regardless of the metric and since there are easy tests to determine if an element is homogeneous or a versor in a Euclidean space this translates directly into an easy test to determine if an arbitrary element is a blade.

Performance and elegance of five models of 3D Euclidean geometry in a ray tracing application pdf

Daniel Fontijne, Leo Dorst
Appeared in CG&A March/April 2003.
Computations of 3D Euclidean geometry can be performed using various computational models of different effectiveness. In this paper we compare five alternatives: 3D linear algebra, 3D geometric algebra, a mix of 4D homogeneous coordinates and Pluecker coordinates, a 4D homogeneous model using geometric algebra, and the 5D conformal model using geometric algebra. Higher dimensional models and models using geometric algebra can express geometric primitives, computations and constructions more elegantly, but this elegance may come at a performance penalty.
We explore these issues using the implementation of a simple ray tracer as our practical goal and guide. We show how to implement the most important geometric computations of the ray tracing algorithm using each of the five models and benchmark each implementation.

Applications of Geometric Algebra in Computer Science and Engineering

L. Dorst, C. Doran, J. Lasenby (editors)
Birkhauser, Boston, ISBN 0-8176-4267-6, 2002

Geometric algebra has established itself as a powerful and valuable mathematical tool for solving problems in computer science, engineering, physics, and mathematics. The articles in this volume, written by experts in various fields, reflect an interdisciplinary approach to the subject, and highlight a range of techniques and applications. Relevant ideas are introduced in a self-contained manner and only a knowledge of linear algebra and calculus is assumed.

Geometric Algebra: a computational framework for geometrical applications (part II: applications) pdf

Stephen Mann, Leo Dorst
Appeared in CG&A July/August 2002.
Geometric algebra is a consistent computational framework in which to define geometric primitives and their relationships. This algebraic approach contains all geometric operators and permits coordinate-free specification of computational constructions. It contains primitives of any dimensionality (rather than just vectors). This second paper on the subject uses the basic products to represent rotations (naturally incorporating quaternions), intersections, and differentiation. It shows how using well-chosen geometric algebra models, we can eliminate special cases in incidence relationships, yet still have the efficiency of the Pluecker coordinate intersection computations.

Geometric Algebra: a computational framework for geometrical applications (part I: algebra). pdf

Leo Dorst, Stephen Mann
Appeared in CG&A May/June 2002.
Geometric algebra is a consistent computational framework in which to define geometric primitives and their relationships. This algebraic approach contains all geometric operators and permits specification of constructions in a coordinate-free manner. Thus, the ideas of geometric algebra are important for developers of CAD systems. This paper gives an introduction to the elements of geometric algebra, which contains primitives of any dimensionality (rather than just vectors), and an introduction to three of the products of geometric algebra, the geometric product, the inner product, and the outer product. These products are illustrated by using them to solve simple geometric problems.

The Inner Products of Geometric Algebra pdf, ps.gz

Leo Dorst.
Appeared in the book 'Applications of Geometric Algebra in Computer Science and Engineering' (Dorst, Doran, Lasenby, eds), Birkhauser, 2002.

Making derived products out of the geometric product requires care in consistency. We show how a split based on outer product and scalar product necessitates a slightly different inner product than usual. We demonstrate the use and geometric significance of this contraction, and show how it simplifies treatment of meet and join. We also derive the sufficient condition for covariance of expressions involving outer, inner and scalar products.

Generalized Projection Operators in Geometric Algebra pdf, ps.gz

T.A. Bouma, L. Dorst and H.G.J. Pijls
Acta Mathematicae Applicandae, pp. 285-300, 2002

The set theory relations [todo] and [todo] have corollaries in subspace relations. Geometric Algebra is introduced as a useful framework to explore these subspace operations. The relations [todo] are easily subsumed by Geometric Algebra for Euclidean metrics. A short computation shows that the meet [todo] and join [todo] are resolved in a projection operator representation with the aid of one additional product beyond the standard Geometric Algebra products. The result is that the join can be computed even when the subspaces have a common factor, and the meet can be computed without knowing the join. All of the operations can be defined and computed in any signature (including degenerate signatures) by transforming the problem to an analogous problem in a different algebra through a transformation induced by a linear invertible function (a LIFT to a different algebra). The new results, as well as the techniques by which we reach them, add to the tools available for subspace computations.

Vehicle Ego-Motion Estimation with Geometric Algebra

W. van der Mark, D. Fontijne, L. Dorst, F.C.A. Groen
Proceedings IEEE Intelligent Vehicle Symposium, Versailles, France, May 18-20, 2002.

Honing geometric algebra for its use in the computer sciences pdf, ps.gz

Leo Dorst.
Published in the book Geometric Computing with Clifford Algebras, ed. G. Sommer, Springer 2001, Chapter 6, pp. 127-152. (The book version lacks some symbols in the figures.)

A computer scientist first pointed to geometric algebra as a promising way to `do geometry' is likely to find a rather confusing collection of material, of which very little is experienced as immediately relevant to the kind of geometrical problems occurring in practice. Literature ranges from highly theoretical mathematics to highly theoretical physics, with relatively little in between apart from some papers on the projective geometry of vision. After perusing some of these, the computer scientist may well wonder what all the fuss is about, and decide to stick with the old way of doing things, i.e. in every application a bit of linear algebra, a bit of differential geometry, a bit of vector calculus, each sensibly used, but ad hoc in their connections. That this approach tends to split up actual issues in the application into modules that match this traditional way of doing geometry (rather than into natural divisions matching the nature of the problem) is seen as `the way things are'. However, if one spends at least a year in absorbing this material, a different picture emerges. One obtains increased clarity and prowess in handling geometry. This is due to being able to do computations without using coordinates; and by having elements of computation which are higher-dimensional than vectors, and thus collate geometrical coherence. The operators that can be applied are at the same time more limited in number, and more powerful in purity and general validity. Through this, one obtains the confidence to tackle higher-dimensional parameter spaces with the intuition obtained from 3-dimensional geometry. Programs written are magically insensitive to the dimensionality of the embedding space, or of the objects they act on. The concept of a `split' endows the limited set of operators with a varied semantics, which begins to suggests an applicability to all geometries one is likely to encounter.

The Making of GABLE,
a Geometric AlgeBra Learning Environment in Matlab pdf, ps.gz

Stephen Mann, Leo Dorst, and Tim Bouma
in 'Geometric Algebra with Applications in Science and Engineering' E. Bayro-Corrochano, G. Sobczyk, eds, Birkhauser, ISBN 0-8176-4199-8, 2001, Chapter 24, pp. 491-511.

Geometric algebra extends Clifford algebra with geometrically meaningful operators, and its purpose is to facilitate geometrical computations. Present textbooks and implementation do not always convey this geometrical flavor or the computational and representational convenience of geometric algebra, so we felt a need for a computer tutorial in which representation, computation and visualization are combined to convey both the intuition and the techniques of geometric algebra. Current software packages are either Clifford algebra only (such as CLICAL and CLIFFORD) or do not include graphics, so we decide to build our own. The result is GABLE (Geometric Algebra Learning Environment) a hands-on tutorial on geometric algebra that should be accessible to the second year student in college.

Objects in contact:
the common 'wave propagation' geometry of collision detection, object growing and milling pdf, ps.gz

Leo Dorst.
In: 'Geometric Algebra with Applications in Science and Engineering', E. Bayro-Corrochano, G. Sobczyk, eds, Birkhauser, 2001, ISBN 0-8176-4199-8, 2001, Chapter 17, pp. 349-370.

We provide representations in geometric algebra for m­dimensional boundaries, to describe and analyze the geometry of wave propagation. This operation also is the essence of collision avoidance in robotics, object growing in graphics, and milling. The most promising result is to represent boundaries as versors in an (m + 1; 1)­dimensional Minkowski space; wave propagation then becomes a geometric product of versors.