Geometric Algebra for Computer Science (Revised Edition)
An Object-Oriented Approach to GeometryBy
- Leo Dorst
- Daniel Fontijne
- Stephen Mann
Until recently, 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.
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.
Hardbound, 664 Pages
Published: March 2009
Imprint: Morgan Kaufmann
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
- 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