Geometric Algebra for Computer Science: An Object-Oriented Approach to Geometry

Front Cover......Page 1
Geometric Algebra for Computer Science: An Object-oriented Approach to Geometry......Page 4
Copyright Page......Page 5
Contents......Page 6
LIST OF FIGURES......Page 21
LIST OF TABLES......Page 27
LIST OF PROGRAMMING EXAMPLES......Page 29
PREFACE......Page 32
1.1 An Example in Geometric Algebra......Page 38
1.2 How It Works and How It’s Different......Page 44
1.3 Programming Geometry......Page 52
1.4 The Structure of This Book......Page 54
1.5 The Structure of the Chapters......Page 56
PART I: GEOMETRIC ALGEBRA......Page 58
CHAPTER 2. SPANNING ORIENTED SUBSPACES......Page 60
2.1 Vector Spaces......Page 61
2.2 Oriented Line Elements......Page 62
2.3 Oriented Area Elements......Page 64
2.4 Oriented Volume Elements......Page 70
2.6 Scalars Interpreted Geometrically......Page 74
2.7 Applications......Page 76
2.8 Homogeneous Subspace Representation......Page 79
2.9 The Graded Algebra of Subspaces......Page 81
2.10 Summary of Outer Product Properties......Page 87
2.12 Exercises......Page 88
2.13 Programming Examples and Exercises......Page 90
CHAPTER 3. METRIC PRODUCTS OF SUBSPACES......Page 102
3.1 Sizing Up Subspaces......Page 103
3.2 From Scalar Product to Contraction......Page 108
3.3 Geometric Interpretation of the Contraction......Page 112
3.4 The Other Contraction......Page 114
3.5 Orthogonality and Duality......Page 115
3.6 Orthogonal Projection of Subspaces......Page 120
3.7 The 3-D Cross Product......Page 123
3.8 Application: Reciprocal Frames......Page 126
3.10 Exercises......Page 128
3.11 Programming Examples and Exercises......Page 130
CHAPTER 4. LINEAR TRANSFORMATIONS OF SUBSPACES......Page 136
4.1 Linear Transformations of Vectors......Page 137
4.2 Outermorphisms: Linear Transformations of Blades......Page 138
4.3 Linear Transformation of the Metric Products......Page 145
4.4 Inverses of Outermorphisms......Page 150
4.5 Matrix Representations......Page 151
4.7 Suggestions for Further Reading......Page 154
4.8 Structural Exercises......Page 155
4.9 Programming Examples and Exercises......Page 157
5.1 The Phenomenology of Intersection......Page 162
5.2 Intersection through Outer Factorization......Page 164
5.3 Relationships Between Meet and Join......Page 165
5.4 Using Meet and Join......Page 166
5.5 Join and Meet are Mostly Linear......Page 168
5.6 Quantitative Properties of the Meet......Page 169
5.7 Linear Transformation of Meet and Join......Page 170
5.9 Further Reading......Page 173
5.10 Exercises......Page 174
5.11 Programming Examples and Exercises......Page 175
CHAPTER 6. THE FUNDAMENTAL PRODUCT OF GEOMETRIC ALGEBRA......Page 178
6.1 The Geometric Product for Vectors......Page 179
6.2 The Geometric Product of Multivectors......Page 184
6.3 The Subspace Products Retrieved......Page 188
6.4 Geometric Division......Page 191
6.6 Exercises......Page 196
6.7 Programming Examples and Exercises......Page 198
CHAPTER 7. ORTHOGONAL TRANSFORMATIONS AS VERSORS......Page 204
7.1 Reflections of Subspaces......Page 205
7.2 Rotations of Subspaces......Page 206
7.3 Composition of Rotations......Page 213
7.4 The Exponential Representation of Rotors......Page 219
7.5 Subspaces as Operators......Page 225
7.6 Versors Generate Orthogonal Transformations......Page 228
7.7 The Product Structure of Geometric Algebra......Page 233
7.8 Further Reading......Page 238
7.9 Exercises......Page 239
7.10 Programming Examples and Exercises......Page 241
CHAPTER 8. GEOMETRIC DIFFERENTIATION......Page 250
8.1 Geometrical Changes by Orthogonal Transformations......Page 251
8.2 Transformational Changes......Page 252
8.4 Scalar Differentiation......Page 258
8.5 Directional Differentiation......Page 261
8.6 Vector Differentiation......Page 267
8.7 Multivector Differentiation......Page 272
8.8 Further Reading......Page 276
8.9 Exercises......Page 277
PART II: MODELS OF GEOMETRIES......Page 280
CHAPTER 9. MODELING GEOMETRIES......Page 282
CHAPTER 10. THE VECTOR SPACE MODEL: THE ALGEBRA OF DIRECTIONS......Page 284
10.2 Angular Relationships......Page 285
10.3 Computing with 3-D Rotors......Page 293
10.4 Application: Estimation in the Vector Space Model......Page 297
10.5 Convenient Abuse: Locations as Directions......Page 300
10.6 Further Reading......Page 301
10.7 Programming Examples and Exercises......Page 302
CHAPTER 11. THE HOMOGENEOUS MODEL......Page 308
11.1 Homogeneous Representation Space......Page 309
11.2 All Points Are Vectors......Page 311
11.3 All Lines Are 2-Blades......Page 315
11.4 All Planes Are 3-Blades......Page 320
11.5 k-Flats as (k + 1)-Blades......Page 322
11.6 Direct and Dual Representations of Flats......Page 323
11.7 Incidence Relationships......Page 329
11.8 Linear Transformations: Motions, and More......Page 339
11.9 Coordinate-Free Parameterized Constructions......Page 346
11.10 Metric Products in the Homogeneous Model......Page 349
11.11 Further Reading......Page 352
11.12 Exercises......Page 353
11.13 Programming Examples and Exercises......Page 357
CHAPTER 12. APPLICATIONS OF THE HOMOGENEOUS MODEL......Page 364
12.1 Homogeneous Plücker Coordinates in 3-D......Page 365
12.2 Imaging by Multiple Cameras......Page 373
12.3 Further Reading......Page 383
12.4 Exercises......Page 384
12.5 Programming Examples and Exercises......Page 385
CHAPTER 13. THE CONFORMAL MODEL: OPERATIONAL EUCLIDEAN GEOMETRY......Page 392
13.1 The Conformal Model......Page 393
13.2 Euclidean Transformations as Versors......Page 401
13.3 Flats and Directions......Page 407
13.4 Application: General Planar Reflection......Page 414
13.5 Rigid Body Motions......Page 416
13.6 Application: Interpolation of Rigid Body Motions......Page 422
13.7 Application: Differential Planar Reflections......Page 423
13.9 Exercises......Page 425
13.10 Programming Examples and Exercises......Page 427
CHAPTER 14. NEW PRIMITIVES FOR EUCLIDEAN GEOMETRY......Page 434
14.1 Rounds......Page 435
14.2 Tangents as Intersections of Touching Rounds......Page 441
14.3 A Visual Explanation of Rounds as Blades......Page 447
14.4 Application: Voronoi Diagrams......Page 452
14.5 Application: Fitting a Sphere to Points......Page 454
14.6 Application: Kinematics......Page 457
14.7 Further Reading......Page 463
14.8 Exercises......Page 464
14.9 Programming Examples and Exercises......Page 465
CHAPTER 15. CONSTRUCTIONS IN EUCLIDEAN GEOMETRY......Page 474
15.1 Euclidean Incidence and Coincidence......Page 475
15.2 Euclidean Nuggets......Page 481
15.3 Euclidean Projections......Page 486
15.4 Application: All Kinds of Vectors......Page 488
15.5 Application: Analysis of a Voronoi Cell......Page 492
15.7 Exercises......Page 497
15.8 Programming Examples and Exercises......Page 499
16.1 Spherical Inversion......Page 502
16.2 Applications of Inversion......Page 505
16.3 Scaling......Page 506
16.4 Transversions......Page 512
16.6 General Conformal Transformations......Page 514
16.7 Non-Euclidean Geometries......Page 517
16.9 Exercises......Page 520
16.10 Programming Examples and Exercises......Page 523
17.1 Algebras for Geometries......Page 534
PART III: IMPLEMENTING GEOMETRIC ALGEBRA......Page 538
CHAPTER 18. IMPLEMENTATION ISSUES......Page 540
18.1 The Levels of Geometric Algebra Implementation......Page 541
18.3 Alternative Implementation Approaches......Page 543
18.4 Structural Exercises......Page 546
CHAPTER 19. BASIS BLADES AND OPERATIONS......Page 548
19.1 Representing Unit Basis Blades with Bitmaps......Page 549
19.2 The Outer Product of Basis Blades......Page 550
19.3 The Geometric Product of Basis Blades in an Orthogonal Metric......Page 552
19.4 The Geometric Product of Basis Blades in Nonorthogonal Metrics......Page 553
19.7 Grade-Dependent Signs on Basis Blades......Page 555
CHAPTER 20. THE LINEAR PRODUCTS AND OPERATIONS......Page 558
20.1 A Linear Algebra Approach......Page 559
20.2 The List of Basis Blades Approach......Page 563
20.3 Structural Exercises......Page 564
21.1 Inverse of Versors (and Blades)......Page 566
21.2 Inverse of Multivectors......Page 567
21.3 Exponential, Sine, and Cosine of Multivectors......Page 568
21.5 Multivector Classification......Page 569
21.6 Blade Factorization......Page 570
21.7 The Meet and Join of Blades......Page 573
21.8 Structural Exercises......Page 577
22.1 Issues in Efficient Implementation......Page 578
22.2 Generative Programming......Page 580
22.3 Resolving the Issues......Page 581
22.4 Implementation......Page 583
22.5 Benchmarks......Page 591
22.7 Exercises......Page 593
CHAPTER 23. USING THE GEOMETRY IN A RAY-TRACING APPLICATION......Page 594
23.1 Ray-Tracing Basics......Page 595
23.2 The Ray-Tracing Algorithm......Page 596
23.3 Representing Meshes......Page 597
23.4 Modeling the Scene......Page 603
23.5 Tracing the Rays......Page 610
23.6 Shading......Page 617
23.7 Evaluation......Page 618
PART IV: APPENDICES......Page 620
A.1 The Bilinear Form......Page 622
A.3 General Metrics......Page 623
A.5 Rotors in General Metrics......Page 624
B.1 Other Inner Products......Page 626
B.2 Equivalence of the Implicit and Explicit Contraction Definitions......Page 628
B.3 Proof of the Second Duality......Page 631
B.4 Projection and the Norm of the Contraction......Page 632
C.1 Outer Product from Peometric Product......Page 634
C.2 Contractions from Geometric Product......Page 635
C.3 Proof of the Grade Approach......Page 636
APPENDIX D. COMMON EQUATIONS......Page 640
BIBLIOGRAPHY......Page 646
INDEX......Page 650