Geometric Algebra for Computer Science (Revised Edition)

Geometric Algebra for Computer Science (Revised Edition)

An Object-Oriented Approach to Geometry

1st Edition - February 24, 2009

Write a review

  • Authors: Leo Dorst, Daniel Fontijne, Stephen Mann
  • Hardcover ISBN: 9780123749420
  • eBook ISBN: 9780080958798

Purchase options

Purchase options
Available
DRM-free (PDF)
Sales tax will be calculated at check-out

Institutional Subscription

Free Global Shipping
No minimum order

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.

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

Product details

  • No. of pages: 664
  • Language: English
  • Copyright: © Morgan Kaufmann 2009
  • Published: February 24, 2009
  • Imprint: Morgan Kaufmann
  • Hardcover ISBN: 9780123749420
  • eBook ISBN: 9780080958798

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

Ratings and Reviews

Write a review

Latest reviews

(Total rating for all reviews)

  • Pingchen H. Thu Jan 13 2022

    Very cool

    Geometric algebra has been underrated but once you start to unlearn the old and know now more about it, you get infected with it. I like the confident and assertive way the author presents the materials - you are stunned when you first read his statements, but only to find out what he say is nothing but truth.