Collision Detection for Interactive Graphics Appli

CollisionDetectionforInteractiveGraphicsApplicationsPhilipM.HubbardDepartmentofComputerScienceBrownUniversityProvidence,RhodeIsland02912CS-95-08April1995CollisionDetectionforInteractiveGraphicsApplicationsbyPhilipMartynHubbardA.B.,HarvardUniversity,1988Sc.M.,BrownUniversity,1991ThesisSubmittedinpartialfulllmentoftherequirementsfortheDegreeofDoctorofPhilosophyintheDepartmentofComputerScienceatBrownUniversity.Submitted:October1994Revised:March1995cCopyright1995byPhilipMartynHubbardAllrightsreserved.ErrataSection6.3describeshowtobuildatreeofspheresthatapproximateapolyhedron.Onestep,describedinSection6.3.2,takesatreethatroughlycoversapolyhedronandmakesthetreecoverthepolyhedronconservatively.Thisstepshouldensurethateachsetofchildrenspheresatleveljcoversthepartofthepolyhedroncoveredbytheparentsphereatlevelj1.Myimplementation,however,usedadierentcriteria.Itensuredthatforeachlevelj,theunionofallspheresatthatlevelcoversthepolyhedron;thepseudocodefromFigure6.26alsousesthisapproach.Thus,aparent’sniecesmaycoverwhatitschildrenshouldcover.Intheory,thisoversightcouldproducetreesthatcausethecollision-detectionalgorithmfromFigure5.4tomisscollisions.IntheempiricaltestsfromSection7.2,though,thisproblemdidnotoccur,asthealgorithmfromFigure5.4foundeverycollisionfoundbyareferencealgorithm.AppendixBassertsthatndingintersectionsbetweentwo-dimensionalshapes(undermildre-strictions)isasymptoticallyasecientasndingintersectionsbetweentheshapesboundingboxes.Thisconjecturestillseemsplausible,buttheproofsketchedinAppendixBdoesnotcoverallcases.Fortunately,thisconjectureismerelyadigression,andnoresultsofthisdissertationdependonit.AbstractSolidobjectsintherealworlddonotpassthrougheachotherwhentheycollide.Enforcingthispropertyof\solidnessisimportantinmanyinteractivegraphicsapplications;forexample,solid-nessmakesvirtualrealitymorebelievable,andsolidnessisessentialforthecorrectnessofvehiclesimulators.Theseapplicationsuseacollision-detectionalgorithmtoenforcethesolidnessofob-jects.Unfortunately,previouscollision-detectionalgorithmsdonotadequatelyaddresstheneedsofinteractiveapplications.Toworkintheseapplications,acollision-detectionalgorithmmustrunatreal-timerates,evenwhenmanyobjectscancollide,anditmusttolerateobjectswhosemotionisspecied\ontheybyauser.Thisdissertationdescribesanewcollision-detectionalgorithmthatmeetsthesecriteriathroughapproximationandgracefuldegradation,elementsoftime-criticalcomputing.Thealgorithmisnotonlyfastbutalsointerruptible,allowinganapplicationtotradeaccuracyforspeedasneeded.Thealgorithmusestwoformsofapproximategeometry.Therstisafour-dimensionalstructurecalledaspace-timebound.Thisstructureprovidesaconservativeestimateofwhereanobjectmaybeintheimmediatefuturebasedonestimatesoftheobject’sacceleration.Thealgorithmusesspace-timeboundstofocusitsattentiononobjectsthatarelikelytocollide.Thesecondformofapproximategeometryisasphere-tree.Thisstructurecontainsahierarchyofunionsofspheres,eachunionapproximatingthethree-dimensionalsurfaceofanobjectatadierentlevelofdetail.Sphere-treesallowthealgorithmtoquicklyndapproximatecontactsbetweenobjects,andtheyallowtheapplicationtointerruptthealgorithminordertomeetreal-timeperformancegoals.Automaticallybuildingsphere-treesisaninterestingprobleminitself,andthisdissertationdescribesseveralapproaches.Thesimplestapproachisbasedonoctrees,andmoresophisticatedapproachesusesimulatedannealingandapproximatemedial-axissurfaces.Severalofthestepsinthesealgorithmsarethemselvessignicant.Onestepisasimplealgorithmforcheckingwhetheraunionoftwo-dimensionalshapescoversapolygon.AnotherstepbuildsVoronoidiagramsforthree-dimensionaldatapoints,anddoessomorerobustlyandaccuratelythanpreviousalgorithms.Animplementationofthecollision-detectionalgorithmrunssignicantlyfasterthanapreviousalgorithminempiricaltests.Inparticular,thisimplementationallowsreal-timeperformanceinasampleapplication(asimpleightsimulator)thatistooslowwiththepreviousalgorithm;insomecases,theperformanceimprovesbymorethantwoordersofmagnitude.Experiencewiththissampleapplicationsuggeststhattime-criticalcomputingisnotalwayssimpletoapply,butitprovidesenoughbenetsthatitdeservesfurtherexplorationinothercontexts.iiiAcknowledgementsAlltherecentmembersoftheBrownUniversityComputerGraphicsGroupcontributedtothiswork,whethertheyrealizeitornot.Thegroupisintenseandexciting,anditisdiculttospendmuchtimeinthegroupwithoutfeelingapermanentinuence.Certainmembersofthegroupstandoutfortheirparticularimportancetome.HenryKaufman,MikeNatkin,andPaulStrausshelpedmesettleintothegroupduringmyrstyear.BrookConner,CindyGrimm,KenHerndon,NateHuang,BrianKnep,TomMeyer,DanRobbins,ScottSnibbe,MatthiasWlokaandBobZeleznikspentcountlesshourssharingtheirideaswithmeandhelpingmeclarifymyown.IparticularlythankScottforimplementingtheinteractivesystemthatletmeplaywithtwo-dimensionalVoronoidiagrams,andformodifyingittohelpmegeneratethediagramsthatappearinthisdissertation.DanandKenalsodeservespecialmentionforansweringallmyvideoquestions.LoriAgrestihelpedwithmanyadministrativeproblems,andthe