Dorst / Fontijne / Mann Geometric Algebra for Computer Science

An Object-Oriented Approach to Geometry
1. Auflage 2010
ISBN: 978-0-08-055310-8
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 664 Seiten

Reihe: The Morgan Kaufmann Series in Computer Graphics

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. * 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

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.

Autoren/Hrsg.

Dorst, Leo

Fontijne, Daniel

Mann, Stephen

Inhaltsverzeichnis

1;Front Cover;1
2;Geometric Algebra for Computer Science: An Object-oriented Approach to Geometry;4
3;Copyright Page;5
4;Contents;6
5;LIST OF FIGURES;21
6;LIST OF TABLES;27
7;LIST OF PROGRAMMING EXAMPLES;29
8;PREFACE;32
9;CHAPTER 1. WHY GEOMETRIC ALGEBRA?;38
9.1;1.1 An Example in Geometric Algebra;38
9.2;1.2 How It Works and How It’s Different;44
9.3;1.3 Programming Geometry;52
9.4;1.4 The Structure of This Book;54
9.5;1.5 The Structure of the Chapters;56
10;PART I: GEOMETRIC ALGEBRA;58
10.1;CHAPTER 2. SPANNING ORIENTED SUBSPACES;60
10.1.1;2.1 Vector Spaces;61
10.1.2;2.2 Oriented Line Elements;62
10.1.3;2.3 Oriented Area Elements;64
10.1.4;2.4 Oriented Volume Elements;70
10.1.5;2.5 Quadvectors in 3-D Are Zero;74
10.1.6;2.6 Scalars Interpreted Geometrically;74
10.1.7;2.7 Applications;76
10.1.8;2.8 Homogeneous Subspace Representation;79
10.1.9;2.9 The Graded Algebra of Subspaces;81
10.1.10;2.10 Summary of Outer Product Properties;87
10.1.11;2.11 Further Reading;88
10.1.12;2.12 Exercises;88
10.1.13;2.13 Programming Examples and Exercises;90
10.2;CHAPTER 3. METRIC PRODUCTS OF SUBSPACES;102
10.2.1;3.1 Sizing Up Subspaces;103
10.2.2;3.2 From Scalar Product to Contraction;108
10.2.3;3.3 Geometric Interpretation of the Contraction;112
10.2.4;3.4 The Other Contraction;114
10.2.5;3.5 Orthogonality and Duality;115
10.2.6;3.6 Orthogonal Projection of Subspaces;120
10.2.7;3.7 The 3-D Cross Product;123
10.2.8;3.8 Application: Reciprocal Frames;126
10.2.9;3.9 Further Reading;128
10.2.10;3.10 Exercises;128
10.2.11;3.11 Programming Examples and Exercises;130
10.3;CHAPTER 4. LINEAR TRANSFORMATIONS OF SUBSPACES;136
10.3.1;4.1 Linear Transformations of Vectors;137
10.3.2;4.2 Outermorphisms: Linear Transformations of Blades;138
10.3.3;4.3 Linear Transformation of the Metric Products;145
10.3.4;4.4 Inverses of Outermorphisms;150
10.3.5;4.5 Matrix Representations;151
10.3.6;4.6 Summary;154
10.3.7;4.7 Suggestions for Further Reading;154
10.3.8;4.8 Structural Exercises;155
10.3.9;4.9 Programming Examples and Exercises;157
10.4;CHAPTER 5. INTERSECTION AND UNION OF SUBSPACES;162
10.4.1;5.1 The Phenomenology of Intersection;162
10.4.2;5.2 Intersection through Outer Factorization;164
10.4.3;5.3 Relationships Between Meet and Join;165
10.4.4;5.4 Using Meet and Join;166
10.4.5;5.5 Join and Meet are Mostly Linear;168
10.4.6;5.6 Quantitative Properties of the Meet;169
10.4.7;5.7 Linear Transformation of Meet and Join;170
10.4.8;5.8 Offset Subspaces;173
10.4.9;5.9 Further Reading;173
10.4.10;5.10 Exercises;174
10.4.11;5.11 Programming Examples and Exercises;175
10.5;CHAPTER 6. THE FUNDAMENTAL PRODUCT OF GEOMETRIC ALGEBRA;178
10.5.1;6.1 The Geometric Product for Vectors;179
10.5.2;6.2 The Geometric Product of Multivectors;184
10.5.3;6.3 The Subspace Products Retrieved;188
10.5.4;6.4 Geometric Division;191
10.5.5;6.5 Further Reading;196
10.5.6;6.6 Exercises;196
10.5.7;6.7 Programming Examples and Exercises;198
10.6;CHAPTER 7. ORTHOGONAL TRANSFORMATIONS AS VERSORS;204
10.6.1;7.1 Reflections of Subspaces;205
10.6.2;7.2 Rotations of Subspaces;206
10.6.3;7.3 Composition of Rotations;213
10.6.4;7.4 The Exponential Representation of Rotors;219
10.6.5;7.5 Subspaces as Operators;225
10.6.6;7.6 Versors Generate Orthogonal Transformations;228
10.6.7;7.7 The Product Structure of Geometric Algebra;233
10.6.8;7.8 Further Reading;238
10.6.9;7.9 Exercises;239
10.6.10;7.10 Programming Examples and Exercises;241
10.7;CHAPTER 8. GEOMETRIC DIFFERENTIATION;250
10.7.1;8.1 Geometrical Changes by Orthogonal Transformations;251
10.7.2;8.2 Transformational Changes;252
10.7.3;8.3 Parametric Differentiation;258
10.7.4;8.4 Scalar Differentiation;258
10.7.5;8.5 Directional Differentiation;261
10.7.6;8.6 Vector Differentiation;267
10.7.7;8.7 Multivector Differentiation;272
10.7.8;8.8 Further Reading;276
10.7.9;8.9 Exercises;277
11;PART II: MODELS OF GEOMETRIES;280
11.1;CHAPTER 9. MODELING GEOMETRIES;282
11.2;CHAPTER 10. THE VECTOR SPACE MODEL: THE ALGEBRA OF DIRECTIONS;284
11.2.1;10.1 The Natural Model for Directions;285
11.2.2;10.2 Angular Relationships;285
11.2.3;10.3 Computing with 3-D Rotors;293
11.2.4;10.4 Application: Estimation in the Vector Space Model;297
11.2.5;10.5 Convenient Abuse: Locations as Directions;300
11.2.6;10.6 Further Reading;301
11.2.7;10.7 Programming Examples and Exercises;302
11.3;CHAPTER 11. THE HOMOGENEOUS MODEL;308
11.3.1;11.1 Homogeneous Representation Space;309
11.3.2;11.2 All Points Are Vectors;311
11.3.3;11.3 All Lines Are 2-Blades;315
11.3.4;11.4 All Planes Are 3-Blades;320
11.3.5;11.5 k-Flats as (k + 1)-Blades;322
11.3.6;11.6 Direct and Dual Representations of Flats;323
11.3.7;11.7 Incidence Relationships;329
11.3.8;11.8 Linear Transformations: Motions, and More;339
11.3.9;11.9 Coordinate-Free Parameterized Constructions;346
11.3.10;11.10 Metric Products in the Homogeneous Model;349
11.3.11;11.11 Further Reading;352
11.3.12;11.12 Exercises;353
11.3.13;11.13 Programming Examples and Exercises;357
11.4;CHAPTER 12. APPLICATIONS OF THE HOMOGENEOUS MODEL;364
11.4.1;12.1 Homogeneous Plücker Coordinates in 3-D;365
11.4.2;12.2 Imaging by Multiple Cameras;373
11.4.3;12.3 Further Reading;383
11.4.4;12.4 Exercises;384
11.4.5;12.5 Programming Examples and Exercises;385
11.5;CHAPTER 13. THE CONFORMAL MODEL: OPERATIONAL EUCLIDEAN GEOMETRY;392
11.5.1;13.1 The Conformal Model;393
11.5.2;13.2 Euclidean Transformations as Versors;401
11.5.3;13.3 Flats and Directions;407
11.5.4;13.4 Application: General Planar Reflection;414
11.5.5;13.5 Rigid Body Motions;416
11.5.6;13.6 Application: Interpolation of Rigid Body Motions;422
11.5.7;13.7 Application: Differential Planar Reflections;423
11.5.8;13.8 Further Reading;425
11.5.9;13.9 Exercises;425
11.5.10;13.10 Programming Examples and Exercises;427
11.6;CHAPTER 14. NEW PRIMITIVES FOR EUCLIDEAN GEOMETRY;434
11.6.1;14.1 Rounds;435
11.6.2;14.2 Tangents as Intersections of Touching Rounds;441
11.6.3;14.3 A Visual Explanation of Rounds as Blades;447
11.6.4;14.4 Application: Voronoi Diagrams;452
11.6.5;14.5 Application: Fitting a Sphere to Points;454
11.6.6;14.6 Application: Kinematics;457
11.6.7;14.7 Further Reading;463
11.6.8;14.8 Exercises;464
11.6.9;14.9 Programming Examples and Exercises;465
11.7;CHAPTER 15. CONSTRUCTIONS IN EUCLIDEAN GEOMETRY;474
11.7.1;15.1 Euclidean Incidence and Coincidence;475
11.7.2;15.2 Euclidean Nuggets;481
11.7.3;15.3 Euclidean Projections;486
11.7.4;15.4 Application: All Kinds of Vectors;488
11.7.5;15.5 Application: Analysis of a Voronoi Cell;492
11.7.6;15.6 Further Reading;497
11.7.7;15.7 Exercises;497
11.7.8;15.8 Programming Examples and Exercises;499
11.8;CHAPTER 16. CONFORMAL OPERATORS;502
11.8.1;16.1 Spherical Inversion;502
11.8.2;16.2 Applications of Inversion;505
11.8.3;16.3 Scaling;506
11.8.4;16.4 Transversions;512
11.8.5;16.5 Transformations of the Standard Blades;514
11.8.6;16.6 General Conformal Transformations;514
11.8.7;16.7 Non-Euclidean Geometries;517
11.8.8;16.8 Further Reading;520
11.8.9;16.9 Exercises;520
11.8.10;16.10 Programming Examples and Exercises;523
11.9;CHAPTER 17. OPERATIONAL MODELS FOR GEOMETRIES;534
11.9.1;17.1 Algebras for Geometries;534
12;PART III: IMPLEMENTING GEOMETRIC ALGEBRA;538
12.1;CHAPTER 18. IMPLEMENTATION ISSUES;540
12.1.1;18.1 The Levels of Geometric Algebra Implementation;541
12.1.2;18.2 Who Should Read What;543
12.1.3;18.3 Alternative Implementation Approaches;543
12.1.4;18.4 Structural Exercises;546
12.2;CHAPTER 19. BASIS BLADES AND OPERATIONS;548
12.2.1;19.1 Representing Unit Basis Blades with Bitmaps;549
12.2.2;19.2 The Outer Product of Basis Blades;550
12.2.3;19.3 The Geometric Product of Basis Blades in an Orthogonal Metric;552
12.2.4;19.4 The Geometric Product of Basis Blades in Nonorthogonal Metrics;553
12.2.5;19.5 The Inner Products of Basis Blades;555
12.2.6;19.6 Commutator Product of Basis Blades;555
12.2.7;19.7 Grade-Dependent Signs on Basis Blades;555
12.3;CHAPTER 20. THE LINEAR PRODUCTS AND OPERATIONS;558
12.3.1;20.1 A Linear Algebra Approach;559
12.3.2;20.2 The List of Basis Blades Approach;563
12.3.3;20.3 Structural Exercises;564
12.4;CHAPTER 21. FUNDAMENTAL ALGORITHMS FOR NONLINEAR PRODUCTS;566
12.4.1;21.1 Inverse of Versors (and Blades);566
12.4.2;21.2 Inverse of Multivectors;567
12.4.3;21.3 Exponential, Sine, and Cosine of Multivectors;568
12.4.4;21.4 Logarithm of Versors;569
12.4.5;21.5 Multivector Classification;569
12.4.6;21.6 Blade Factorization;570
12.4.7;21.7 The Meet and Join of Blades;573
12.4.8;21.8 Structural Exercises;577
12.5;CHAPTER 22. SPECIALIZING THE STRUCTURE FOR EFFICIENCY;578
12.5.1;22.1 Issues in Efficient Implementation;578
12.5.2;22.2 Generative Programming;580
12.5.3;22.3 Resolving the Issues;581
12.5.4;22.4 Implementation;583
12.5.5;22.5 Benchmarks;591
12.5.6;22.6 A Small Price to Pay;593
12.5.7;22.7 Exercises;593
12.6;CHAPTER 23. USING THE GEOMETRY IN A RAY-TRACING APPLICATION;594
12.6.1;23.1 Ray-Tracing Basics;595
12.6.2;23.2 The Ray-Tracing Algorithm;596
12.6.3;23.3 Representing Meshes;597
12.6.4;23.4 Modeling the Scene;603
12.6.5;23.5 Tracing the Rays;610
12.6.6;23.6 Shading;617
12.6.7;23.7 Evaluation;618
13;PART IV: APPENDICES;620
13.1;APPENDIX A. METRICS AND NULL VECTORS;622
13.1.1;A.1 The Bilinear Form;622
13.1.2;A.2 Diagonalization to Orthonormal Basis;623
13.1.3;A.3 General Metrics;623
13.1.4;A.4 Null Vectors and Null Blades;624
13.1.5;A.5 Rotors in General Metrics;624
13.2;APPENDIX B. CONTRACTIONS AND OTHER INNER PRODUCTS;626
13.2.1;B.1 Other Inner Products;626
13.2.2;B.2 Equivalence of the Implicit and Explicit Contraction Definitions;628
13.2.3;B.3 Proof of the Second Duality;631
13.2.4;B.4 Projection and the Norm of the Contraction;632
13.3;APPENDIX C. SUBSPACE PRODUCTS RETRIEVED;634
13.3.1;C.1 Outer Product from Peometric Product;634
13.3.2;C.2 Contractions from Geometric Product;635
13.3.3;C.3 Proof of the Grade Approach;636
13.4;APPENDIX D. COMMON EQUATIONS;640
14;BIBLIOGRAPHY;646
15;INDEX;650