Until recently, almost all of the interactions between objects in virtual 3D worlds have been based on calculations performed using linear algebra. Linear algebra relies heavily on coordinates, however, which can make many geometric programming tasks very specific and complex-often a lot of effort is required to bring about even modest performance enhancements. Although linear algebra is an efficient way to specify low-level computations, it is not a suitable high-level language for geometric programming.

Geometric Algebra for Computer Science presents a compelling alternative to the limitations of linear algebra. Geometric algebra, or GA, is a compact, time-effective, and performance-enhancing way to represent the geometry of 3D objects in computer programs. In this book you will find an introduction to GA that will give you a strong grasp of its relationship to linear algebra and its significance for your work. You will learn how to use GA to represent objects and perform geometric operations on them. And you will begin mastering proven techniques for making GA an integral part of your applications in a way that simplifies your code without slowing it down.

### Key Features

* The first book on Geometric Algebra for programmers in computer graphics and entertainment computing* Written by leaders in the field providing essential information on this new technique for 3D graphics

* This full colour book includes a website with GAViewer, a program to experiment with GA

**Leo Dorst**, Informatics Institute, Faculty of Sciences, University of Amsterdam, The Netherlands;

**Daniel Fontijne**, Intelligent Autonomous Systems, University of Amsterdam, The Netherlands; and

**Stephen Mann**, University of Waterloo, Ontario, Canada

CHAPTER 1. WHY GEOMETRIC ALGEBRA?

An Example in Geometric Algebra

How It Works and How It’s Different

Vector Spaces as Modeling Tools

Subspaces as Elements of Computation

Linear Transformations Extended

Universal Orthogonal Transformations

Objects are Operators

Closed-Form Interpolation and

Perturbation

Programming Geometry

You Can Only Gain

Software Implementation

The Structure of This Book

Part I: Geometric Algebra

Part II: Models of Geometry

Part III: Implementation of Geometric

Algebra

The Structure of the Chapters

PART I GEOMETRIC ALGEBRA

CHAPTER 2. SPANNING ORIENTED SUBSPACES

Vector Spaces

Oriented Line Elements

Properties of Homogeneous Lines

Visualizing Vectors

Oriented Area Elements

Properties of Planes

Introducing the Outer Product

Visualizing Bivectors

Visualizing Bivector Addition

Oriented Volume Elements

Properties of Volumes

Associativity of the Outer Product

Visualization of Trivectors

Quadvectors in 3-D Are Zero

Scalars Interpreted Geometrically

Applications

Solving Linear Equations

Intersecting Planar Lines

Homogeneous Subspace Representation

Parallelness

Direct Representation of Oriented

Weighted Subspaces

Nonmetric Lengths, Areas, and Volumes

The Graded Algebra of Subspaces

Blades and Grades

The Ladder of Subspaces

k-Blades Versus k-Vectors

The Grassmann Algebra of Multivectors

Reversion and Grade Involution

Summary of Outer Product Properties

Further Reading

Exercises

Drills

Structural Exercises

Programming Examples and Exercises

Drawing Bivectors

Exercise: Hidden Surface Removal

Singularities in Vector Fields

CHAPTER 3. METRIC PRODUCTS OF SUBSPACES

Sizing Up Subspaces

Metrics, Norms, and Angles

Definition of the Scalar Product*

The Squared Norm of a Subspace

The Angle Between Subspaces

From Scalar Product to Contraction

Implicit Definition of Contraction

Computing the Contraction Explicitly

Algebraic Subtleties

Geometric Interpretation of the Contraction

The Other Contraction

Orthogonality and Duality

Nonassociativity of the Contraction

The Inverse of a Blade

Orthogonal Complement and Duality

The Duality Relationships

Dual Representation of Subspaces

Orthogonal Projection of Subspaces

The 3-D Cross Product

Use of the Cross Product

The Cross Product Incorporated

Application: Reciprocal Frames

Further Reading

Exercises

Drills

Structural Exercises

Programming Examples and Exercises

Orthonormalization

Exercise: Implementing the Cross

Product

Reciprocal Frames

Color Space Conversion

CHAPTER 4. LINEAR TRANSFORMATIONS OF

SUBSPACES

Linear Transformations of Vectors

Outermorphisms: Linear Transformation of

Blades

Motivation of the Outermorphism

Examples of Outermorphisms

The Determinant of a Linear

Transformation

Linear Transformation of the Metric

Products

Linear Transformation of the Scalar

Product

The Adjoint of a Linear Transformation

Linear Transformation of the

Contraction

Orthogonal Transformations

Transforming a Dual Representation

Application: Linear Transformation of

the Cross Product

Inverses of Outermorphisms

Matrix Representations

Matrices for Vector Transformations

Matrices for Outermorphisms

Summary

Suggestions for Further Reading

Structural Exercises

Programming Examples and Exercises

Orthogonal Projection

Orthogonal Projection, Matrix

Representation

Transforming Normal Vectors

CHAPTER 5. INTERSECTION AND UNION OF

SUBSPACES

The Phenomenology of Intersection

Intersection Through Outer Factorization

Relationships Between Meet and Join

Using Meet and Join

Join and Meet are Mostly Linear

Quantitative Properties of the Meet

Linear Transformation of Meet and Join

Offset Subspaces

Further Reading

Exercises

Drills

Structural Exercises

Programming Examples and Exercises

The Meet and Join

Efficiency

Floating Point Issues

CHAPTER 6. THE FUNDAMENTAL PRODUCT OF

GEOMETRIC ALGEBRA

The Geometric Product for Vectors

An Invertible Product for Geometry

Symmetry and Antisymmetry

Properties of the Geometric Product

The Geometric Product for Vectors on

a Basis

Dividing by a Vector

Ratios of Vectors as Operators

The Geometric Product of Multivectors

Algebraic Definition of the Geometric

Product

Evaluating the Geometric Product

Grades and the Geometric Product

The Subspace Products Retrieved

The Subspace Products from Symmetry

The Subspace Products as Selected

Grades

Geometric Division

Inverses of Blades

Decomposition: Projection to Subspaces

The Other Division: Reflection

Further Reading

Exercises

Drills

Structural Exercises

Programming Examples and Exercises

Exercise: Subspace Products Retrieved

Gram-Schmidt Orthogonalization

CHAPTER 7. ORTHOGONAL TRANSFORMATIONS AS

VERSORS

Reflections of Subspaces

Rotations of Subspaces

3-D Rotors as Double Reflectors

Rotors Perform Rotations

A Sense of Rotation

Composition of Rotations

Multiple Rotations in 2-D

Real 2-D Rotors Subsume Complex

Numbers

Multiple Rotations in 3-D

Visualizing 3-D Rotations

Unit Quaternions Subsumed

The Exponential Representation of Rotors

Pure Rotors as Exponentials of 2-D

Blades

Trigonometric and Hyperbolic Functions

Rotors as Exponentials of Bivectors

Logarithms

Subspaces as Operators

Reflection by Subspaces

Subspace Projection as Sandwiching

Transformations as Objects

Versors Generate Orthogonal Transformations

The Versor Product

Even and Odd Versors

Orthogonal Transformations are Versor

Products

Versors, Blades, Rotors, and Spinors

The Product Structure of Geometric Algebra

The Products Summarized

Geometric Algebra Versus Clifford

Algebra

But-is it Efficient?

Further Reading

Exercises

Drills

Structural Exercises

Programming Examples and Exercises

Reflecting in Vectors

Two Reflections Equal One Rotation

Matrix-Rotor Conversion 1

Exercise: Matrix-Rotor Conversion 2

Julia Fractals

Extra Example: Rotations Used for

Example User Interface

CHAPTER 8. GEOMETRIC DIFFERENTIATION

Geometrical Changes by Orthogonal

Transformations

Transformational Changes

The Commutator Product

Rotor-Induced Changes

Multiple Rotor-Induced Changes

Transformation of a Change

Change of a Transformation

Parametric Differentiation

Scalar Differentiation

Application: Radius of Curvature of a

Planar Curve

Directional Differentiation

Table of Elementary Results

Application: Tilting a Mirror

Vector Differentiation

Elementary Results of Vector

Differentiation

Properties of Vector Differentiation

Multivector Differentiation

Definition

Application: Estimating Rotors

Optimally

Further Reading

Exercises

Drills

Structural Exercises

PART II MODELS OF GEOMETRIES

CHAPTER 9. MODELING GEOMETRIES

CHAPTER 10. THE VECTOR SPACE MODEL: THE

ALGEBRA OF DIRECTIONS

The Natural Model for Directions

Angular Relationships

The Geometry of Planar Triangles

Angular Relationships in 3-D

Rotation Groups and Crystallography

Computing with 3-D Rotors

Determining a Rotor from Rotation

Plane and Angle

Determining a Rotor from a Frame

Rotation in 3-D

The Logarithm of a 3-D Rotor

Rotor Interpolation

Application: Estimation in the Vector Space

Model

Noisy Rotor Estimation

External Camera Calibration

Convenient Abuse: Locations as Directions

Further Reading

Programming Examples and Exercises

Interpolating Rotations

Crystallography Implementation

External Camera Calibration

CHAPTER 11. THE HOMOGENEOUS MODEL

Homogeneous Representation Space

All Points are Vectors

Finite Points

Infinite Points and Attitudes

Addition of Points

Terminology: from Precise to

Convenient

All Lines are 2-Blades

Finite Lines

Lines at Infinity

Don’t Add Lines

All Planes are 3-Blades

k-Flats as (k+1)-Blades

Finite k-Flats

Infinite k-Flats

Parameters of k-Flats

The Number of Parameters of an Offset

Flat

Direct and Dual Representations of Flats

Direct Representation

Dual Representation

Incidence Relationships

Examples of Incidence Computations

Relative Orientation

Relative Lengths: Distance Ratio and

Cross Ratio

Linear Transformations: Motions, and More

Linear Transformations on Blades

Translations

Rotations Around the Origin

General Rotation

Rigid Body Motion

Constructing Elements Through Motions

Rigid Body Motion Outermorphisms as

Matrices

Affine Transformations

Projective Transformations

Coordinate-Free Parameterized Constructions

Metric Products in the Homogeneous Model

Non-Euclidean Results

Nonmetric Orthogonal Projection

Further Reading

Exercises

Drills

Structural Exercises

Programming Examples and Exercises

Working with Points

Intersecting Primitives

Don’t Add Lines

Perspective Projection

CHAPTER 12. APPLICATIONS OF THE

HOMOGENEOUS MODEL

Homogeneous Plücker Coordinates in 3-D

Line Representation

The Elements in Coordinate Form

Combining Elements

Matrices of Motions in Plücker

Coordinates

Sparse Usage of the 24 Dimensions

Imaging by Multiple Cameras

The Pinhole Camera

Homogeneous Coordinates as Imaging

Cameras and Stereo Vision

Line-based Stereo Vision

Further Reading

Exercises

Structural Exercises

Programming Examples and Exercises

Loading Transformations into OpenGL

Transforming Primitives with OpenGL

Matrices

Marker Reconstruction in Optical

Motion Capture

CHAPTER 13. THE CONFORMAL MODEL:

OPERATIONAL EUCLIDEAN GEOMETRY

The Conformal Model

Representational Space and Metric

Points as Null Vectors

General Vectors Represent Dual Planes

and Spheres

Euclidean Transformations as Versors

Euclidean Versors

Proper Euclidean Motions as Even

Versors

Covariant Preservation of Structure

The Invariance of Properties

Flats and Directions

The Direct Representation of Flats

Correspondence with the Homogeneous

Model

Dual Representation of Flats

Directions

Application: General Planar Reflection

Rigid Body Motions

Algebraic Properties of Translations

and Rotations

Screw Motions

Logarithm of a Rigid Body Motion

Application: Interpolation of Rigid Body

Motions

Application: Differential Planar

Reflections

Further Reading

Exercises

Drills

Structural Exercises

Programming Examples and Exercises

Metric Matters

Exercise: The Distance Between Points

Loading Transformations in OpenGL,

Again

Interpolation of Rigid Body Motions

CHAPTER 14. NEW PRIMITIVES FOR EUCLIDEAN

GEOMETRY

Rounds

Dual Rounds

Direct Rounds

Oriented Rounds

Tangents as Intersections of Touching

Rounds

Euclid’s Elements

From Blades to Parameters

A Visual Explanation of Rounds as Blades

Point Representation

Circle Representation

Euclidean Circles Intersect as Planes

Application: Voronoi Diagrams

Application: Fitting a Sphere to Points

The Inner Product Distance of Spheres

Fitting a Sphere to Points

Application: Kinematics

Forward Kinematics

Inverse Kinematics

Further Reading

Exercises

Drills

Structural Exercises

Programming Examples and Exercises

Voronoi Diagrams and Delaunay

Triangulations

Exercise: Drawing Euclid’s Elements

Conformal Primitives and Intersections

Fitting a Sphere to a Set of Points

CHAPTER 15. CONSTRUCTIONS IN EUCLIDEAN

GEOMETRY

Euclidean Incidence and Coincidence

Incidence Revisited

Co-Incidence

Real Meet or Plunge

The Plunge of Flats

Euclidean Nuggets

Tangents Without Differentiating

Carriers, Tangent Flat

Surrounds, Factorization of Rounds

Affine Combinations

Euclidean Projections

Application: All Kinds of Vectors

Application: Analysis of a Voronoi Cell

Edge Lines

Edge Point

Edge Length

Conversion to Classical Formulas

Further Reading

Exercises

Drills

Structural Exercises

Programming Examples and Exercises

The Plunge

Affine Combinations of Points

Euclidean Projections

CHAPTER 16. CONFORMAL OPERATORS

Spherical Inversion

Applications of Inversion

The Center of a Round

Reflection in Spheres and Circles

Scaling

The Positive Scaling Rotor

Reflection in the Origin: Negative

Scaling

Positively Scaled Rigid Body Motions

Logarithm of a Scaled Rigid Body

Motion

Transversions

Transformations of the Standard Blades

General Conformal Transformations

Loxodromes

Circular Rotations

Möbius Transformations

Non-Euclidean Geometries

Hyperbolic Geometry

Spherical Geometry

Further Reading

Exercises

Drills

Structural Exercises

Programming Examples and Exercises

Homogeneous 4X4 Matrices to

Conformal Versors

Logarithm of Scaled Rigid Body Motion

Interpolation of Scaled Rigid Body

Motions

The Seashell

CHAPTER 17. OPERATIONAL MODELS FOR

GEOMETRIES

Algebras for Geometries

PART III IMPLEMENTING GEOMETRIC ALGEBRA

CHAPTER 18. IMPLEMENTATION ISSUES

The Levels of Geometric Algebra

Implementation

Who Should Read What

Alternative Implementation Approaches

Isomorphic Matrix Algebras

Irreducible Matrix Implementations

Factored Representations

Structural Exercises

CHAPTER 19. BASIS BLADES AND OPERATIONS

Representing Unit Basis Blades with Bitmaps

The Outer Product of Basis Blades

The Geometric Product of Basis Blades in an

Orthogonal Metric

The Geometric Product of Basis Blades in

Nonorthogonal Metrics

The Inner Products of Basis Blades

Commutator Product of Basis Blades

Grade-Dependent Signs on Basis Blades

CHAPTER 20. THE LINEAR PRODUCTS AND

OPERATIONS

A Linear Algebra Approach

Implementing the Linear Operations

Implementing the Linear Products

The List of Basis Blades Approach

Structural Exercises

CHAPTER 21. FUNDAMENTAL ALGORITHMS FOR

NONLINEAR PRODUCTS

Inverse of Versors (and Blades)

Inverse of Multivectors

Exponential, Sine, and Cosine of

Multivectors

Logarithm of Versors

Multivector Classification

Blade Factorization

The Meet and Join of Blades

Structural Exercises

CHAPTER 22. SPECIALIZING THE STRUCTURE FOR

EFFICIENCY

Issues in Efficient Implementation

Generative Programming

Resolving the Issues

The Approach

Implementation

Algebraic Specification

Implementation of the General

Multivector Class

Implementation of the Specialized

Multivector Classes

Optimizing Functions Over the Algebra

Outermorphisms

Optimizing the Nonlinear Functions

Benchmarks

A Small Price to Pay

Exercises

CHAPTER 23. USING THE GEOMETRY IN A RAY-

TRACING APPLICATION

Ray-Tracing Basics

The Ray-Tracing Algorithm

Representing Meshes

Modeling the Scene

Scene Transformations

Tracing the Rays

The Representation of Rays

Spawning Rays

Ray-Model Intersection

Reflection

Refraction

Shading

Evaluation

PART IV APPENDICES

A METRICS AND NULL VECTORS

The Bilinear Form

Diagonalization to Orthonormal Basis

General Metrics

Null Vectors and Null Blades

Rotors in General Metrics

B CONTRACTIONS AND OTHER INNER PRODUCTS

Other Inner Products

The Dot Product

Hestenes’ Inner Product

Near Equivalence of Inner Products

Geometric Interpretation and Usage

Equivalence of the Implicit and Explicit

Contraction Definitions

Proof of the Second Duality

Projection and the Norm of the Contraction

C SUBSPACE PRODUCTS RETRIEVED

Outer Product from Peometric Product

Contractions from Geometric Product

Proof of the Grade Approach

D COMMON EQUATIONS

BIBLIOGRAPHY

INDEX