MorganKaufmannPublishersisanimprintofElsevier 30CorporateDrive,Suite400,Burlington,MA01803,USA Copyright(cid:2)c 2007byElsevierInc.Allrightsreserved. Designationsusedbycompaniestodistinguishtheirproductsareoftenclaimedastrademarksor registeredtrademarks.InallinstancesinwhichMorganKaufmannPublishersisawareofaclaim,the productnamesappearininitialcapitalorallcapitalletters.Readers,however,shouldcontactthe appropriatecompaniesformorecompleteinformationregardingtrademarksandregistration. Nopartofthispublicationmaybereproduced,storedinaretrievalsystem,ortransmittedinanyformor byanymeans—electronic,mechanical,photocopying,scanning,orotherwise—withoutpriorwritten permissionofthepublisher. PermissionsmaybesoughtdirectlyfromElsevier’sScience&TechnologyRightsDepartmentinOxford, UK:phone:(+44)1865843830,fax:(+44)1865853333,E-mail:[email protected] alsocompleteyourrequeston-lineviatheElsevierhomepage(http://elsevier.com),byselecting “Support&Contact”then“CopyrightandPermission”andthen“ObtainingPermissions.” LibraryofCongressCataloging-in-PublicationData Applicationsubmitted ISBN:978-0-12-374942-0 ForinformationonallMorganKaufmannpublications, visitourWebsiteatwww.mkp.comorwww.books.elsevier.com PrintedinChina 09 10 11 5 4 3 2 List of Figures 1.1 Exampleoftheuseofgeometricalgebra 2 1.2 CodetogenerateFigure1.1 5 1.3 Exampleoftheuseofgeometricalgebra 6 1.4 Theouterproductanditsinterpretations 11 2.1 Spanninghomogeneoussubspacesina3-Dvectorspace 25 2.2 Imaginingvectoraddition 27 2.3 Bivectorrepresentations 32 2.4 Imaginingbivectoradditionin2-Dspace 33 2.5 Bivectoradditionin3-Dspace 34 2.6 Theassociativityoftheouterproduct 35 2.7 Solvinglinearequationswithbivectors 40 2.8 Intersectinglinesintheplane 41 2.9 Codefordrawingbivectors 58 2.10 Drawingbivectorsscreenshot(Example1) 59 2.11 Theorientationoffront-andback-facingpolygons 59 2.12 Awire-frametoruswithandwithoutbackfaceculling 60 2.13 Thecodethatrendersamodelfromits2-Dvertices(Exercise2) 61 2.14 Samplingavectorfieldandsummingtrivectors 62 2.15 Codetotestforsingularity(Example3) 63 2.16 Ahelix-shapedsingularity,asdetectedbyExample3 64 3.1 Computingthescalarproductof2-blades 70 3.2 Fromscalarproducttocontraction 72 3.3 Thecontractionofavectorontoa2-blade 76 3.4 Dualityofvectorsin2-D 81 xx LIST OF FIGURES xxi 3.5 Dualityofvectorsandbivectorsin3-D 82 3.6 Projectionontoasubspace 84 3.7 Threeusesofthecrossproduct 87 3.8 Dualityandthecrossproduct 89 3.9 Orthonormalizationcode(Example1) 93 3.10 Orthonormalization 94 3.11 Reciprocalframecode 96 3.12 Colorspaceconversioncode(Example4) 97 3.13 Colorspaceconversionscreenshot 98 4.1 Thedefiningpropertiesofalineartransformation 100 4.2 Projectionontoalineaintheb-direction 104 4.3 Arotationaroundtheoriginofunitvectorsintheplane 105 4.4 Projectionofavectorontoabivector 121 4.5 Matrixrepresentationofprojectioncode 122 4.6 Transformingnormalsvector 123 5.1 Theambiguityofthemagnitudeoftheintersectionoftwoplanes 126 5.2 Themeetoftwoorientedplanes 130 5.3 Alinemeetingaplaneintheorigin 131 5.4 Whenthejoinoftwo(near-)parallelvectorsbecomesa2-blade(Example3) 140 6.1 Non-invertibilityofthesubspaceproducts 142 6.2 Ratiosofvectors 146 6.3 Projectionandrejectionofavector 156 6.4 Reflectingavectorinaline 158 6.5 Gram-Schmidtorthogonalization 163 6.6 Gram-Schmidtorthogonalizationcode(Example2) 164 7.1 Lineandplanereflection 169 7.2 ArotationinaplaneparalleltoIistworeflectionsinvectorsinthatplane 170 7.3 Arotorinaction 171 7.4 Senseofrotation 175 7.5 Theuniquerotor-basedrotationsintherange(cid:2)=[0,4π) 176 7.6 (a)Asphericaltriangle.(b)Compositionofrotationsthroughconcatenation ofrotorarcs 180 7.7 Areflectorinaction 189 7.8 TherotorproductinEuclideanspacesasaTaylorseries 197 xxii LIST OF FIGURES 7.9 InteractiveversionofFigure7.2 205 7.10 Rotationmatrixtorotorconversion 207 7.11 2-DJuliafractalcode 210 7.12 A2-DJuliafractal,computedusingthegeometricproductofrealvectors 211 7.13 3-DJuliafractal 212 8.1 Directionaldifferentiationofavectorinversion 227 8.2 Changesinreflectionofarotatingmirror 229 8.3 Thedirectionalderivativeofthesphericalprojection 241 10.1 Atrianglea+b+c=0inadirectedplaneI 249 10.2 Theanglebetweenavectorandabivector(seetext) 252 10.3 Asphericaltriangle 253 10.4 Interpolationofrotations 259 10.5 Interpolationofrotations(Example1) 266 10.6 Crystallography(Example2) 267 10.7 Externalcameracalibration(Example3) 268 11.1 Theextradimensionofthehomogeneousrepresentationspace 274 11.2 RepresentingoffsetsubspacesinRn+1 280 11.3 Definingoffsetsubspacesfullyinthebasespace 288 11.4 ThedualhyperplanerepresentationinR2andR1 290 11.5 TheintersectionoftwooffsetlinesLandMtoproduceapoint 293 11.6 Themeetoftwoskewlines 295 11.7 Therelativeorientationoforientedflats 296 11.8 Thecombinationsoffourpointstakeninthecrossratio 300 11.9 Thecombinationsoffourlinestakeninthecrossratio 301 11.10 Conicsinthehomogeneousmodel 308 11.11 Findingalinethroughapoint,perpendiculartoagivenline 310 11.12 Theorthogonalprojectioninthehomogeneousmodel(seetext) 315 11.13 Thebeginningofarowofequidistanttelegraphpoles 319 11.14 Example2inaction 323 11.15 Perspectiveprojection(Example4) 325 12.1 Plu¨ckercoordinatesofalinein3-D 329 12.2 Apinholecamera 337 12.3 Theepipolarconstraint 342 12.4 TheplaneofraysgeneratedbyalineobservationL 343 LIST OF FIGURES xxiii 12.5 Theprojectionoftheopticalcenterontoallraysgeneratesaneyeball 348 12.6 Reconstructionofmotioncapturedata 351 12.7 Reconstructionofmarkers 352 12.8 Crossinglinescode 354 13.1 Euclideantransformationsasmultiplereflectionsinplanes 366 13.2 Flatelementsintheconformalmodel 373 13.3 Planarreflectionintheconformalmodel 377 13.4 Chasles’screw 382 13.5 Computationofthelogarithmofarigidbodymotion 384 13.6 Rigidbodymotioninterpolation 385 13.7 Reflectioninarotatingmirror 387 13.8 TheoutputofthesolutiontoExample2 393 13.9 Example4inaction:theinterpolationofrigidbodymotions 394 14.1 Dualroundsintheconformalmodel 398 14.2 Intersectionoftwospheresofdecreasingradii 405 14.3 Visualizationofa2-DEuclideanpointontherepresentativeparaboloid 411 14.4 Therepresentationofacircleontherepresentativeparaboloid 412 14.5 Crosssectionoftheparabolaofnullvectors 413 14.6 Visualizationoftheintersectionofcirclesontherepresentativeparaboloid 414 14.7 AVoronoidiagramintheconformalmodel 416 14.8 Innerproductasdistancemeasure 418 14.9 Forwardkinematicsofarobotarm 421 14.10 Inversekinematicsofarobotarm 422 14.11 AVoronoidiagramofasetofpoints,ascomputedbyExample1 429 14.12 Euclid’selements(Example2) 432 14.13 Example3inaction 433 14.14 Fitting-a-spherecode 435 15.1 Themeetandplungeofthreespheres 439 15.2 Theplungeofdiverseelements 441 15.3 Themeetandplungeoftwospheresatdecreasingdistances 442 15.4 Visualizationofflatsasplunge 443 15.5 Orbitsofaduallineversor 444 15.6 Tangentsofelements 445 15.7 Factorizationofrounds 447 xxiv LIST OF FIGURES 15.8 Affinecombinationofconformalpoints 448 15.9 Affinecombinationofcirclesandpointpairs 449 15.10 OrthogonalprojectionsintheconformalmodelofEuclideangeometry 450 15.11 Variouskindsofvectorsintheconformalmodel 452 15.12 DefinitionofsymbolsfortheVoronoiderivations 456 15.13 Constructionofacontourcircle 462 15.14 ScreenshotofExample2 463 15.15 ScreenshotofExample3onprojectionandplunge 464 16.1 Inversioninasphere 467 16.2 Reflectioninasphere 469 16.3 Generationofasnailshell 472 16.4 Swappingscalingandtranslation 473 16.5 Computationofthelogarithmofapositivelyscaledrigidbodymotion 475 16.6 Loxodromes 478 16.7 Conformalorbits 479 16.8 Hyperbolicgeometry 481 16.9 Sphericalgeometry 482 16.10 Imagingbytheeye 484 16.11 Reflectioninapointpair 485 16.12 Dupincycloidastheinversionofatorusintoasphere 486 16.13 MetricalMysteryTour 487 16.14 Functionmatrix4×4 ToVersor() 489 16.15 Functionlog(const TRSversor &V) 493 16.16 ScreenshotofExample4 495 19.1 Functioncanonical ReorderingSign(int a, int b) 514 19.2 Functiongpop (BasisBlade a, BasisBlade b) 515 20.1 Matricesforgeometricproduct,outerproduct,andleftcontraction 525 20.2 Implementationoftheouterproductofmultivectors 527 21.1 Venndiagramsillustratingunion,intersection,andthedeltaproductof twosets 536 21.2 Venndiagramsillustratingmeet,join,andthedeltaproductoftwoblades 537 22.1 Basictool-chainfromsourcecodetorunningapplication 544 22.2 CodegeneratedbyGaigen 2 551 22.3 Generatedmatrix-pointmultiplicationcode 553 LIST OF FIGURES xxv 23.1 Teapotpolygonalmesh 560 23.2 Screenshotoftheuserinterfaceofthemodeler 567 23.3 Rotatinganobject 570 23.4 Thespaceballinterface 571 List of Tables 2.1 Geometricalpropertiesofasubspace 43 2.2 Pascal’striangleofthenumberofbasisk-bladesinn-dimensionalspace 45 2.3 NotationalconventionsforbladesandmultivectorsforPartIofthisbook 47 2.4 C++Operatorbindings 55 5.1 Theorderoftheargumentsforameetmayaffectthesignoftheresult 134 7.1 ReflectionofanorientedsubspaceXinasubspaceA 190 8.1 Directionaldifferentiationandvectorderivatives 226 8.2 Elementaryresultsofmultivectordifferentiation 237 10.1 Thepointgroup2H4 255 11.1 Thegeometricalgebraofthehomogeneousmodelof3-DEuclideanspace 273 11.2 Thenumberofbladesrepresentingsubspacesanddirections 287 11.3 NonzerobladesinthehomogeneousmodelofEuclideangeometry 291 11.4 Specializedmultivectortypesintheh3ga 320 12.1 CommonPlu¨ckercoordinatecomputations 330 12.2 Transformationoftheflatsinthehomogeneousmodel 335 13.1 Multiplication table for the inner product of the conformal model of 3-D EuclideangeometryE3,fortwochoicesofbasis 361 13.2 Theinterpretationofvectorsintheconformalmodel 363 13.3 Alistofthemostimportantspecializedmultivectortypesinc3ga 391 13.4 Constantsinc3ga 392 14.1 NonzerobladesintheconformalmodelofEuclideangeometry 407 16.1 Basicoperationsintheconformalmodelandtheirversors 476 16.2 Commonpropertransformationsofsomeofthestandardelementsofthe conformalmodel 477 xxvi LIST OF TABLES xxvii 18.1 MatrixrepresentationsofCliffordalgebrasofsignatures(p,q) 507 19.1 Thebitmaprepresentationofbasisblades 512 19.2 BitwisebooleanoperatorsusedinJavacodeexamples 513 19.3 Reversion,gradeinvolution,andCliffordConjugateforbasisblades 519 22.1 Performancebenchmarksfortheraytracer 555