Efficient implementation of geometric algebra

Contents......Page 5
List Of Figures......Page 9
List Of Tables......Page 11
Origin Of Chapters......Page 12
Introduction......Page 13
1.1 Using Linear Algebra To Encode Geometry......Page 15
1.2 The Alternative: Geometric Algebra......Page 17
1.4 Contributions Of The Thesis......Page 18
1.5 Overview Of The Thesis......Page 19
Introduction To Geometric Algebra......Page 21
2.2.1 Fonts......Page 22
2.3 Vector Spaces......Page 23
2.4 The Outer Product......Page 25
2.4.3 Interpretation of Blades......Page 26
2.4.5 Containment of Blades......Page 27
2.4.7 Adding Blades, Multivectors......Page 28
2.4.8 A Basis for Multivectors......Page 30
2.5 The Metric Products......Page 31
2.5.2 Metric Matrix......Page 32
2.5.4 Definition of the Left Contraction\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 34
2.5.5 Intuitive interpretation of the Left Contraction......Page 35
2.6.1 An Invertible Product of Vectors?......Page 36
2.6.2 Definition of the Geometric Product\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 38
2.6.3 Intuitive Interpretation of the Geometric Product......Page 39
2.6.4 Computing with the Geometric Product......Page 40
2.6.6 Reversion and Inversion......Page 41
2.6.7 Norms......Page 42
2.7 From Geometric Product To Subspace ProdUcts......Page 43
2.7.1 Relationships Between the Products......Page 44
2.8 Basic Constructions In Geometric Algebra......Page 45
2.8.1 Dualization......Page 46
2.8.3 Orthogonal Projection......Page 47
2.8.4 Intersection of Blades......Page 48
2.8.5 Reciprocal Frames......Page 49
2.8.6 Gram-Schmidt Orthogonalization......Page 50
2.9.1 Re ection......Page 51
2.9.2 Rotations......Page 52
2.9.3 Rotors as Exponentials of Bivectors......Page 54
2.10.1 Blades in the Homogeneous Model......Page 56
2.10.2 In nite Points and Attitudes......Page 60
2.11 The Conformal Model......Page 61
2.11.1 The Basis and Metric......Page 62
2.11.2 Representation of Points......Page 63
2.11.3 Conformal Blades and their Interpretation......Page 64
2.11.4 Transformations......Page 67
2.12 Outermorphisms......Page 70
2.13 Meet And Join......Page 72
2.13.1 Basic Properties of the meet and join......Page 73
2.14.3 Blades and the Outer Product......Page 74
2.14.4 Versors and the Geometric Product......Page 75
2.14.7 Dualization......Page 76
2.14.10 Basis......Page 77
2.14.12 Non-Linear Products......Page 78
Implementation Of Geometric Algebra On An Additive Basis......Page 79
Unknown......Page 0
3.0.1 A Note on Time Complexity......Page 80
3.1 The Basis And Operations On Basis Blades......Page 81
3.1.2 The Bitmap Representation of Basis Blades......Page 82
3.1.4 The Outer Product of Basis Blades......Page 83
3.1.5 The Geometric Product of Basis Blades in an Orthogonal Metric......Page 84
3.1.6 The Geometric Product of Basis Blades in nonOrthogonal Metrics......Page 86
3.1.7 The Metric Products of Basis Blades......Page 88
3.2 Representing Multivectors And Coordinate Compression......Page 89
3.3.1 The Linear Algebra Approach......Page 91
3.3.2 The `List of Basis Blades\' Approach......Page 95
3.3.3 Time Complexity of Linear Operations......Page 96
3.4 Non-linear Operations On Multivectors......Page 97
3.4.2 Inverse of Multivectors......Page 98
3.4.3 Exponential, Sine and Cosine of Multivectors......Page 99
3.4.5 Multivector Classi cation......Page 100
3.4.6 Blade Factorization......Page 103
3.4.7 meet and join of Blades......Page 105
3.5 Discussion And Summary......Page 109
Optimizing The Additive Implementation......Page 111
4.1 Existing Additive Implementations......Page 112
4.2 Issues In E Cient Implementation......Page 113
4.3 Resolving The Issues......Page 114
4.3.1 Overview of Our Implementation Approach......Page 115
4.4 Generative Programming......Page 116
4.6 Implementation: Speci Cation Of The Algebra......Page 117
4.6.1 Low-level Code Generation Details......Page 118
4.6.4 Specialized Multivector Types......Page 119
4.6.5 Generated Specialized Multivector Types......Page 121
4.6.7 Outermorphism Matrix Representations......Page 122
4.7.1 Code Generation Details......Page 123
4.7.2 Implementation of the General Multivector Class......Page 126
4.7.3 Implementation of the Specialized Multivector Classes......Page 130
4.7.4 Implementation of the General Outermorphism Class......Page 132
4.7.5 Implementation of Specialized Outermorphism Classes......Page 134
4.7.6 Parsing and Pretty Printing of Multivectors......Page 135
4.8 Implementation: Dsl Functions......Page 136
4.8.2 DSL Functions Parsing......Page 139
4.8.3 DSL Expression Parsing......Page 142
4.8.4 High-Level Optimization of DSL Functions......Page 143
4.8.5 Expanding Multivector Variables on the Basis......Page 144
4.8.7 Tight Return Type......Page 146
4.8.8 DSL Function Code Generation......Page 148
4.9 Implementation: Pro Ling......Page 149
4.11 Discussion......Page 153
Implementation Of Geometric Algebra On A Multiplicative Basis......Page 157
5.1 Introduction......Page 158
5.2.1 Blade Representation......Page 159
5.2.3 Inner Product of Two Blades of the Same Grade, using a Euclidean Metric......Page 160
5.2.4 Outer Product......Page 161
5.2.5 Creating a Blade from a Matrix......Page 162
5.2.7 Representation of Metric......Page 163
5.2.8 Dual using an Arbitrary Metric......Page 164
5.2.10 join......Page 165
5.2.12 Addition......Page 166
5.3.1 Versor Representation......Page 167
5.3.2 Conversion from Blade Representation to Versor Representation......Page 168
5.3.5 Versor Inverse......Page 169
5.3.7 Exponentials of Bivectors......Page 170
5.4 Simplifying Versor Representations......Page 171
5.4.1 Versor Representation: Extra Administration......Page 172
5.4.3 Factoring out the Dependent Factor......Page 173
5.4.4 Removing the Dependent Factor......Page 176
5.4.5 Modi cations for Signatures Rn1;1 and R1;n1......Page 177
5.5.2 Time Complexity......Page 179
5.7 Benchmarks......Page 181
5.9 Discussion......Page 183
Case Study: Using The Algebra To Implement A Ray Tracer......Page 185
6.1 Ray Tracing Basics......Page 187
6.2 The Ray Tracing Algorithm......Page 188
6.3 Representing Meshes......Page 189
6.4 Modeling The Scene......Page 194
6.5.1 The Representation of Rays......Page 196
6.5.2 Casting Rays......Page 198
6.5.3 Ray-Model Intersection......Page 200
6.6 Shading......Page 203
6.7 Evaluation......Page 204
Benchmarks......Page 205
7.1.1 First Generation Ray Tracer......Page 206
7.1.2 Second Generation Ray Tracer......Page 207
7.2 Inverse Kinematics......Page 209
7.3.2 Choice of Basis......Page 210
7.4.2 Gaigen 1 and Gaigen 2 Compared to CLU......Page 211
7.4.4 Gaigen 1 Compared to MV......Page 212
7.5 Discussion And Conclusion......Page 213
Discussion And Conclusion......Page 215
8.2 Gaigen 2......Page 216
8.4 Conformal Model......Page 218
Appendix A: Subspace Products From The Geometric Product......Page 221
A.1 Outer Product From Geometric Product (for Vectors)......Page 222
A.2 Left Contraction From Geometric Product (for Vectors)......Page 223
A.4 The Metric Products From The Geometric Product (general)......Page 224
Appendix B: Ray Tracer Tables......Page 227
Appendix C: Samenvatting......Page 231
Appendix D: Abstract......Page 235
Bibliography......Page 237
Acknowledgements......Page 241