# Geometric Algebra for Computer Science

## 1st Edition

### An Object-Oriented Approach to Geometry

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

**Hardcover ISBN:**9780123694652

**Imprint:**Morgan Kaufmann

**Published Date:**19th April 2007

**Page Count:**664

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

## Table of Contents

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

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

## 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 2007

- Published:
- 19th April 2007

- Imprint:
- Morgan Kaufmann

- Hardcover ISBN:
- 9780123694652

## 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