# Geometric Algebra for Computer Science (Revised Edition)

## 1st Edition

### An Object-Oriented Approach to Geometry

**Authors:**Leo Dorst Daniel Fontijne Stephen Mann

**Hardcover ISBN:**9780123749420

**eBook ISBN:**9780080958798

**Imprint:**Morgan Kaufmann

**Published Date:**24th February 2009

**Page Count:**664

**View all volumes in this series:**The Morgan Kaufmann Series in Computer Graphics

## Table of Contents

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

## Description

*Geometric Algebra for Computer Science (Revised Edition)* presents a compelling alternative to the limitations of linear algebra.

Geometric algebra (GA) is a compact, time-effective, and performance-enhancing way to represent the geometry of 3D objects in computer programs. This book explains GA as a natural extension of linear algebra and conveys its significance for 3D programming of geometry in graphics, vision, and robotics. It systematically explores the concepts and techniques that are key to representing elementary objects and geometric operators using GA. It covers in detail the conformal model, a convenient way to implement 3D geometry using a 5D representation space. Numerous drills and programming exercises are helpful for both students and practitioners. A companion web site includes links to GAViewer, a program that will allow you to interact with many of the 3D figures in the book; and Gaigen 2, the platform for the instructive programming exercises that conclude each chapter.

The book will be of interest to professionals working in fields requiring complex geometric computation such as robotics, computer graphics, and computer games. It is also be ideal for students in graduate or advanced undergraduate programs in computer science.

## Key Features

- Explains GA as a natural extension of linear algebra and conveys its significance for 3D programming of geometry in graphics, vision, and robotics.
- Systematically explores the concepts and techniques that are key to representing elementary objects and geometric operators using GA.
- Covers in detail the conformal model, a convenient way to implement 3D geometry using a 5D representation space.
- Presents effective approaches to making GA an integral part of your programming.
- Includes numerous drills and programming exercises helpful for both students and practitioners.
- Companion web site includes links to GAViewer, a program that will allow you to interact with many of the 3D figures in the book, and Gaigen 2, the platform for the instructive programming exercises that conclude each chapter.

## Readership

Professionals working in fields requiring complex geometric computation such as robotics, computer graphics, and computer games. Students in graduate or advanced undergraduate programs in computer science.

## Details

- No. of pages:
- 664

- Language:
- English

- Copyright:
- © Morgan Kaufmann 2009

- Published:
- 24th February 2009

- Imprint:
- Morgan Kaufmann

- Hardcover ISBN:
- 9780123749420

- eBook ISBN:
- 9780080958798

## Reviews

Within the last decade, Geometric Algebra (GA) has emerged as a powerful alternative to classical matrix algebra as a comprehensive conceptual language and computational system for computer science. This book will serve as a standard introduction and reference to the subject for students and experts alike. As a textbook, it provides a thorough grounding in the fundamentals of GA, with many illustrations, exercises and applications. Experts will delight in the refreshing perspective GA gives to every topic, large and small.

-David Hestenes, Distinguished research Professor, Department of Physics, Arizona State University

Geometric Algebra is becoming increasingly important in computer science. This book is a comprehensive introduction to Geometric Algebra with detailed descriptions of important applications. While requiring serious study, it has deep and powerful insights into GA’s usage. It has excellent discussions of how to actually implement GA on the computer.

-Dr. Alyn Rockwood, CTO, FreeDesign, Inc. Longmont, Colorado

## Ratings and Reviews

## About the Authors

### Leo Dorst

### Affiliations and Expertise

Informatics Institute, Faculty of Sciences, University of Amsterdam, The Netherlands

### Daniel Fontijne

Daniel Fontijne holds a Master’s degree in artificial Intelligence and a Ph.D. in Computer Science, both from the University of Amsterdam. His main professional interests are computer graphics, motion capture, and computer vision.

### Affiliations and Expertise

Intelligent Autonomous Systems, University of Amsterdam, The Netherlands

### Stephen Mann

### Affiliations and Expertise

University of Waterloo, Ontario, Canada