Geometric Tools for Computer Graphics TheMorganKaufmannSeriesinComputerGraphicsandGeometricModeling SeriesEditor:BrianA.Barsky,UniversityofCalifornia,Berkeley GeometricToolsforComputerGraphics Andrew Glassner’s Notebook: Recreational Computer PhilipSchneiderandDavidEberly Graphics AndrewS.Glassner LevelofDetailfor3DGraphics David Luebke, Martin Reddy, Jonathan D. Cohen, WarpingandMorphingofGraphicalObjects Amitabh Varshney, Benjamin Watson, and Robert Jonas Gomes, Lucia Darsa, Bruno Costa, and Luiz Huebner Velho JimBlinn’sCorner:DirtyPixels Texturing&Modeling:AProceduralApproach, JimBlinn ThirdEdition DavidS.Ebert,F.KentonMusgrave,DarwynPeachey, Rendering with Radiance: The Art and Science of KenPerlin,andStevenWorley LightingVisualization GregWardLarsonandRobShakespeare JimBlinn’sCorner:Notation,Notation,Notation JimBlinn IntroductiontoImplicitSurfaces EditedbyJulesBloomenthal UnderstandingVirtualReality JimBlinn’sCorner:ATripDowntheGraphicsPipeline WilliamShermanandAlanCraig JimBlinn DigitalVideoandHDTVAlgorithmsandInterfaces InteractiveCurvesandSurfaces:AMultimediaTutorial CharlesPoynton onCAGD Pyramid Algorithms: A Dynamic Programming Ap- AlynRockwoodandPeterChambers proachtoCurvesandSurfacesforGeometricModeling WaveletsforComputerGraphics:TheoryandApplica- RonGoldman tions EricJ.Stollnitz,TonyD.DeRose,andDavidH.Salesin Non-PhotorealisticComputerGraphics:Modeling, Rendering,andAnimation PrinciplesofDigitalImageSynthesis ThomasStrothotteandStefanSchlechtweg AndrewS.Glassner CurvesandSurfacesforCAGD:APracticalGuide, Radiosity&GlobalIllumination FifthEdition Franc¸oisX.SillionandClaudePuech GeraldFarin Knotty:AB-SplineVisualizationProgram JonathanYen SubdivisionMethodsforGeometricDesign:A ConstructiveApproach UserInterfaceManagementSystems:Modelsand JoeWarrenandHenrikWeimer Algorithms DanR.Olsen,Jr. ComputerAnimation:AlgorithmsandTechniques MakingThemMove:Mechanics,Control,and RickParent AnimationofArticulatedFigures TheComputerAnimator’sTechnicalHandbook Edited by Norman I. Badler, Brian A. Barsky, and LynnPocockandJudsonRosebush DavidZeltzer AdvancedRenderMan:CreatingCGIforMotionPictures GeometricandSolidModeling:AnIntroduction AnthonyA.ApodacaandLarryGritz ChristophM.Hoffmann CurvesandSurfacesinGeometricModeling:Theoryand AnIntroductiontoSplinesforUseinComputerGraphics Algorithms andGeometricModeling JeanGallier RichardH.Bartels,JohnC.Beatty,andBrianA.Barsky Geometric Tools for Computer Graphics Philip J. Schneider David H. Eberly PublishingDirector DianeCerra PublishingServicesManager EdwardWade SeniorDevelopmentalEditor BelindaBreyer ProjectManagement ElisabethBeller CoverDesign RossCarronDesign CoverImage Getty/SpencerJones TextDesign RebeccaEvans&Associates Composition WindfallSoftware,usingZzTEX TechnicalIllustrationandFigureRevision DartmouthPublishing,Inc. Copyeditor KenDellaPenta Proofreader JenniferMcClain Indexer SteveRath Printer TheMaple-VailBookManufacturingGroup Designationsusedbycompaniestodistinguishtheirproductsareoftenclaimedastrademarks orregisteredtrademarks.InallinstancesinwhichMorganKaufmannPublishersisawareofa claim,theproductnamesappearininitialcapitalorallcapitalletters.Readers,however,should contacttheappropriatecompaniesformorecompleteinformationregardingtrademarksand registration. MorganKaufmannPublishers AnimprintofElsevierScience 340PineStreet,SixthFloor SanFrancisco,CA94104-3205 www.mkp.com ©2003byElsevierScience(USA) Allrightsreserved PrintedintheUnitedStatesofAmerica 07 06 05 04 03 5 4 3 2 1 Nopartofthispublicationmaybereproduced,storedinaretrievalsystem,ortransmittedin anyformorbyanymeans—electronic,mechanical,photocopying,recording,orotherwise— withoutthepriorwrittenpermissionofthepublisher. LibraryofCongressControlNumber:2002107242 ISBN:1-55860-594-0 Thisbookisprintedonacid-freepaper. Tomywife,Suzanne,andmysons,DakotaandJordan —PS Tomywife,Shelly,forherpatiencethroughyetanotherbook —DE Foreword EricHaines OnmyshelfisanoldbookcalledAProgrammer’sGeometry,byBowyerandWood- wark.Itwaspublishedin1983,reprintedtwicein1984and1985,butthendiscontin- ued.OvertheyearsIhaveguardedmycopy,keepingcarefultrackofwhoborrowed it.CheckingontheWebtoday,Ifoundsixusedcopiesranginginpricefrom$50to $100.Thisisahighpricerangeforapaperbackbookonly140pagesinlength.The reasonthebookisworththismuchisthatitdescribeshowtoprogramvariousop- erationsrelatedto2Dgeometry.Itdoesnotjustpresentgeometricformulae;italso describesefficientwaystoaccomplishtasksandgivescodesnippets(inFORTRAN). Now,almosttwodecadeslater,wehaveaworthysuccessortothatslimvolume. Thebookbeforeyoudistillsahugeamountofliteratureongeometryintothatwhich ismostusefultoprogrammers.Thefieldofcomputergraphicshasevolvedconsid- erably since 1983, and this volume reflects those advances. Due to the continuing improvement in computer processor performance, operations that once were only part of offline analysis packages are now commonly done in interactive programs. Polygontriangulation,collisiondetectionandresponse,andsurfacemodellingand modificationarenowpossibleatreal-timerates.Thisbookgivessolidexplanations andcodetoperformtheseandmanyotheralgorithms. Beyondprovidingasolidreferenceforawiderangeofgeometry-relatedtasks,this volumealsopresentstheunderpinningsofthetheorybehindthealgorithms.Rather thanemployapurecookbookapproach, whichcanleavethereaderwithrunnable codeandnocomprehensionofhowitworks,theauthorsexplainkeyconcepts.This approachmakeseachalgorithmatoolthat,furtheron,canberecombinedwithother tools. Thedynamicnatureofcomputergraphicsmakesitaparticularlyinterestingarea of study. Research and implementation of rendering methods respond to changes in the underlying hardware. For example, in the field of interactive rendering, the emergingprogrammablenatureofthegraphicsacceleratorhaschangedtherelative costsofdifferenttechniques.Onabroaderscale,theevolutionoftheCPUhasmade memory access and caching rise in importance, compared to the older practice of minimizingthenumberofoperations(e.g.,countingmultipliesandadds).However, theunderlyingtheoryandalgorithmsfor,say,findingtheconvexhullofanobjectare considerably more long-lasting, less affected by changes. Of course, more efficient algorithmsarefoundovertime,andhardwareinfluenceswhichmethodcurrentlyis consideredthefastest,butthebasicprinciplesremainthesame.Yearsafteryouhave vii viii Foreword shedyourbooksonDirectX9orIntel’s64-bitItaniumarchitecture,youarelikelyto havesomeeditionofthisbookonyourshelf. AnotherreasonthisbookwillhaveincreasedstayingpoweristheInternet.Iam thearchivistforthe“GraphicsGems”seriescoderepository.Thecodeforthisseries ofbooks, includingcodebyPhilipSchneider, waswiselymadefreeforreusewhen theserieswaspublishedintheearly1990s.Overtheyearsreadershavesentinbug fixes and improvements to the code base, so benefiting all. Similarly, Dave Eberly hascarefullymaintainedhis“MagicSoftware”Website(www.magic-software.com), whichincludesworkingversionsofmanyofthealgorithmspresentedinthisvolume. Called “a national treasure” by a leading researcher in computer graphics, this site allows addenda and corrigenda to be made available instantly whenever they are needed. Code does not rust; it improves with age when properly supported. This is particularly true for algorithms in this book as they are not tied to particular hardware,networkprotocols,orothertransientobjects. OvertheyearsIandmanyothershaveusedalgorithmsandcodebytheauthors inproductsandresearchprojects.Anhourofaprogrammer’stimeoftencostsmore than the price of a book. By this measure, you hold a volume potentially worth thousandsofdollars.ThatitcanbepurchasedforafractionofthiscostIconsider amodernmiracle.Theamountofinformationcrammedintothisbookisincredible. Themathematicsmaybeslowgoingattimes,butthealternativewouldbetoinclude wordier and less precise descriptions of fewer algorithms. If you are looking for a lightweight text you can read through and check off your list, keep searching. This book sometimes requires effort and struggle to fully comprehend but then, so do mostoftheworthwhilethingsintheworld. 1 Introduction ..................................................................... 1 How to Use This Book ............................................................ 1 Issues of Numerical Computation........................................... 2 Low-Level Issues................................................................................. 2 High-Level Issues................................................................................ 4 A Summary of the Chapters ................................................... 6 2 Matrices and Linear Systems......................................... 9 Introduction ............................................................................. 9 Motivation ............................................................................................ 9 Organization ........................................................................................ 13 Notational Conventions ....................................................................... 14 Tuples..................................................................................... 14 Definition.............................................................................................. 15 Arithmetic Operations.......................................................................... 16 Matrices .................................................................................. 16 Notation and Terminology ................................................................... 17 Transposition....................................................................................... 17 Arithmetic Operations.......................................................................... 18 Matrix Multiplication............................................................................. 20 Linear Systems ....................................................................... 24 Linear Equations.................................................................................. 24 Linear Systems in Two Unknowns ...................................................... 26 General Linear Systems...................................................................... 29 Row Reductions, Echelon Form, and Rank......................................... 30 Square Matrices...................................................................... 32 Diagonal Matrices................................................................................ 32 Triangular Matrices.............................................................................. 34 The Determinant.................................................................................. 34 Inverse................................................................................................. 38 Linear Spaces......................................................................... 41 Fields................................................................................................... 41 Definition and Properties ..................................................................... 42 Subspaces........................................................................................... 43 Linear Combinations and Span........................................................... 43 Linear Independence, Dimension, and Basis...................................... 44 Linear Mappings ..................................................................... 45 Mappings in General ........................................................................... 45 Linear Mappings .................................................................................. 47 Matrix Representation of Linear Mappings.......................................... 49 Cramer’s Rule...................................................................................... 50 Eigenvalues and Eigenvectors ............................................... 52 Euclidean Space..................................................................... 54 Inner Product Spaces.......................................................................... 54 Orthogonality and Orthonormal Sets................................................... 55 Least Squares......................................................................... 56 Recommended Reading......................................................... 60 3 Vector Algebra................................................................. 63 Vector Basics.......................................................................... 63 Vector Equivalence.............................................................................. 63 Vector Addition .................................................................................... 64 Vector Subtraction............................................................................... 65 Vector Scaling ..................................................................................... 65 Properties of Vector Addition and Scalar Multiplication....................... 66 Vector Space .......................................................................... 69 Span.................................................................................................... 70 Linear Independence........................................................................... 71 Basis, Subspaces, and Dimension...................................................... 71 Orientation ........................................................................................... 73 Change of Basis .................................................................................. 75 Linear Transformations........................................................................ 76 Affine Spaces.......................................................................... 80 Euclidean Geometry............................................................................ 84 Volume, the Determinant, and the Scalar Triple Product .................... 94 Frames ................................................................................................ 96 Affine Transformations............................................................ 98 Types of Affine Maps........................................................................... 103 Composition of Affine Maps................................................................. 103 Barycentric Coordinates and Simplexes................................. 104 Barycentric Coordinates and Subspaces ............................................ 106 Affine Independence ........................................................................... 106 4 Matrices, Vector Algebra, and Transformations .......... 109 Introduction ............................................................................. 109 Matrix Representation of Points and Vectors ......................... 110 Addition, Subtraction, and Multiplication................................. 113 Vector Addition and Subtraction.......................................................... 113 Point and Vector Addition and Subtraction.......................................... 114 Subtraction of Points ........................................................................... 115 Scalar Multiplication............................................................................. 115 Products of Vectors ................................................................ 115