Collision Detection - Brown CS

Two collision-detection algorithms that we are going to discuss. I-COLLIDE · Impulse-Based Dynamic Simulation. I-COLLIDE- An incremental ... COLLISIONDETECTION Importance Whyiscollisiondetectionslow? ExplosiveGrowth Usingtheformula:Numberofcollisiontests=(n²-n)/2 ObjectsCollisionTests 21 33 46 .. .. .. 20190 O(n²) EliminatingCollisionTests RedundantTests GameRules e.g.spaceshipgamewhereyoudon'twantthealienstoshooteach other,soyoudon'tcareaboutcollisiondetectionbetweenthealien misilesandalienships. Eleminationsbasedonspatialpositioningsuchasaxissortingandthesectormethod AxisSorting SpriteNumber X-Coordinate SpriteWidth 1 10 10 2 15 5 3 18 8 4 40 10 5 45 10 SectorMethod CollisionTesting BoundingBased PixelBased Tofindmoredetailedinformationonthesejustclickhere. Twocollision-detectionalgorithmsthatwearegoingto discuss I-COLLIDE Impulse-Based DynamicSimulation I-COLLIDE-Anincrementalalgorithmfor collisiondetectionbetweensolidmodels. Icollideisbasedontemporalandgeometriccoherence Whatistemporalandgeometriccoherence? Propertythatthestateoftheapplicationdoesnotchangesignificantlybetweensuccessivetimestepsorsimulationframes. Byexploitingcoherenceweareabletotrimdownthenumberofpairwise objectandfeaturetestsinvolvedineachiteration. Fornobjects,theworstcaserunningtimeforanycollisiondetectionalgorithmisO(n²)thisisalsotrueforI-collide. However,runningtimeofI-CollidefornobjectsisO(n+m)wheremisthenumberofobjectsveryclosetoeachother. Twoobjectsareverycloseiftheiraxisalignedboundingboxesoverlap. Whatareboundingboxes? Fixed-SizeBoundingCubes: Wecomputethesizeofthefixedcubetobelargeenoughtocontaintheobjectatanyorientation? Thecubeisdefinedbyacenterandradius. Easytorecomputeasthepositionchanges. Wellsuitedfordynamicenviroments.Workswellwithobjectswhicharenearlyspherical. Ateachtimestepthecubeisrecomputedasfollows: 1.Transformthecenterbyusingonevectormatrixmultiplication. 2.Computetheminandmaxx,y,zcoordinatesbysubtractingandaddingtheradiusfromthecoordinatesofthecenter. step1isonlyonevectormatrixmultiplication step2isjust3additionsand3subtructions e.g. DynamicallyRectangularBoundingBoxes: Wecomputethesizeoftherectangularboundingboxtobethethightestaxisalignedboxcontaintheobjectataparticularorientation. Itisdefinedbyitsminandmaxx,yandzcoordinates(upto6ofitsvertices).Asanobjectmoves,itsminimaandmaximaisrecalculated Foroblongobjectsrectangularobjectsfitbetterthancubesresultinginfeveroverlaps. Thisisanadvantageaslongasonlyfewobjectsoremoving. e.g. SweepandPrune Sortingtheboundingboxessurrundingtheobjectsisthekeytothesweep andpruneapproach. Itisnotintuitivelyobvioushowtosortboundingboxesin3space. Onewayisdimensionreductionapproach. Firstthingwedoistoprojecteach3-dimensionalboundingboxontothex,yandzaxes. Weareinterestedinoverlaps.Becauseapairofboundingboxescanoverlapifandonlyiftheirintervalsoverlapinallthreedimensions. Weconstruct3lists,oneforeachdimension. Eachlistcontainsthevalueoftheend-pointsoftheintervalscorrespondingtothatdimension. Bysortingtheselists,wecandeterminewhichintervalsoverlap. IngeneralsuchasortwilltakeO(nlogn)timeHoweverwecanreducethistimeifwekeepthesortedlistsfromthepreviousframe,changingonlythevaluesoftheintervalendpoints. SincetherewillberelativelysmallmovementsbetweenframesthelistswillbenearlysortedsowecansortinexpectedO(n)timeusingInsertionSort. Two-DimensionalIntersectionTests Projecteach3-dimesionalaxis-alignedboundingboxontoanyofthetwoofthex-y,y-z,x-zplanes. Eachoftheseprojectionsarerectanglesin2spacesothereare feweroverlapsofthese2-Drectanglesthanthe1-DintervalsusedbytheSweepandPruneTechnique. Incaseswhereprojectionontheone-dimensioncausesdenslyclusteredintervalsthetwodimensionatechniqueismoreefficient. OtherAlternatives: BinarySpacePartitioning(BSPtrees),octrees,etc.. Severalpracticalandefficientalgorithmsarebasedonuniformspacedivision. DivideSpaceintoUnitCells:Tocheckforcollision,examinethecellsoccupiedbyeachobject.Howeverchoosinganear-optimalcellsizeisdifficultandfailingtodosoresultsinlargememoryusageandcomputationalinefficiency Thispageiscreatedby MuratGorguner IMPULSEDBASEDSIMULATION Thetwofundamentalrequirementsyouwantindynamicsimulation: physicalaccuracy computationalefficiency-canitruninrealtime Impulsedbasedsimulationattemptstofulfillthesetworequirements Constraintbasedvs.impulsedbasedsimulation dealingwithcontact Inconstraintbasedsimulation: Example-ballrollingalongatabletop -forcewhichtableexertsonballisaconstraintforcethat doesn'tdoworkontheballbutexertsanon-penetrationconstaint -forceisn'tmodeledexplicitbutaccountedforbya constraintontheball-oneoftheball`scoordinatesisheldconstant -problem-constaintsmaychangeovertime,e.g.ballrolls offthetable,hitsanobjectonthetable -keepingtrackofthechangingconstraintsinorderto calculatethecorrectmotionoftheballcangetcomplicated -also,impactscreateimpulses,notconstraintforcesandmust behandledseparately Inimpulsedbasedsimulation Example-ballrestingontabletop -noconstraintsareplacedonmovingobjects =7F -unificationofalltypesofcontactunderasinglemodel -modelusedforcollisionscanbeusedforinstances whereanobjectisrollingorrestingonanotherobject -notnecessarytoclassifydifferentcontacttypesor dealwiththemindifferentways -intheexample,ballisexperiencingmanytinycollisions withthetable-microcollisions Doesimpulsedbasedsimulationresultinphysicallyaccuratesimulations? Yes,microcollisioncontactproducescorrectbehavior Isitfastenoughforsimulationpurposes? Yes,thelargenumberofcollisionswhichmustbecalculated doesnotprohibitreal-timesimulation Procedureforimplementingimpulsedbasedsimulation First,youassumeobjectstravelinballistictrajectorieswhennot collidingwithanything Foreachobject,aboundingboxiscreatedtoenclosethepathofan objectoveratimeinterval,thisisdoneatthebeginningofeachframe -agoodintervalistheframerate=3D1/30seconds Intersectionsbetweentheboxesarefound,calculatedtotake O(n(1+logR))timewhereRisratiooflargesttosmallestboxsize Iftwoboxesdon'tintersect,objectswon'tcollideinthenextframe sonodistanceortimeofimpactcalcuationshavetobedone Iftheydo,theLin-Cannyclosestfeaturesalgorithmisused-same oneasinI_COLLIDE -theshortestpossibletimetocollisioniscalclulated Eachpairisinsertedinaheapsortedbytimeofcollision,e.g.pairthat= =20 willcollidefirstwillbeatthe top Timestepisincerementeduntilthetimeofcollisionofthetoppair L in-Cannyalgorithmisdoneagaintofinddistancebetweenthetwoobjects- collisionwhendistancefallsbelowanepsilonwhichisatleast3ordersof magnitudesmallerthanthedimensionsoftheobjects ifcollision,docollisionresolution,calculatenewboundingvolumes= =20 fortheobjects,intersect=09 thesenewboxeswiththeothersandupdatetheheapaccordingly Drawbackstothisdetectionsystem: Sinceballistictrajectoryisassumedyoucan'thaveanyforcesallofa=20 suddenaffectan=09 object'strajectory-nouserinterfacepossibleaftertheinitialforces ThisisOKforapoolgamebutnotformostothergames Solution:=7F Calculateboundingboxthatwillencompassthemaximumdisplacementan=20 object=09 cangooverthetimeinterval Consequences: Morecollisiondetectionneededsinceboxesmaybebiggerandait's=20 possiblemost=09 oftheintersectingvolumeswillproducenocollisionswhenthoughtwas=20 expected=09 sincethepositionoftheobjectintheboxvariesontheforcesenacted ButUserInteractioncanhappen! Computingcollisionimpulses Whentwobodiescollide,animpulsemustbeappliedtoabodysothereisno= =20 interpenetration;the impulseappliedtotheotherbodyisthenegativeoftheimpulse Onceimpulseisknowm,youcancomputethelinearvelocityforcenterof=20 massandangularvelocity andalgorithcancontinune Youdon'twanttoassumefrictionlesscollisionsorperfectlyelastic=20 collisions,wewanttomodelthe realworld,unlessyou'reinspace 3assumptionsforcollisions: 1)Infinitesimalcollisiontime-Thedurationofacollisionis= =20 negligiblecomparedtothe timeoverwhichsimulatedobjectsmove. Therefore a)theconfigurationsoftwoobjectsmaybetakenasconstantoverthe= =20 entirecollision -eveninsimulations,it'sjustoverkilltocalculatethedeformityand=20 reboundingofanobjectduringa collision b)theeffectofoneobjectonanothercanbedescribedasanimpulsewhich= =20 gives risetoinstantaneouschangeinlinearandangularvelocitiesofanobject 2)Poisson'shypothesis P_total=3D(1+e)*P_max_compression e=3Dconstantbetween0and1,dependentonobject'smaterial,called= =20 coefficientof restitution P_total=3Dmagnitudeofnormalcomponentoftheimpulsedonebyone=20 objectonto theotherovertheentirecollision =09 P_max=3Dmagnitudeofnormalcomponentoftheimpulsedonebyoneobject= onto theotheruptothepointofmaximumcompression ife=3D1,collisionistotallyelastic ife=3D0,collisionistotallyplastic,objectssticktogetherafer= collision P_max_compressioniseasytocharacterize,it'sthepointatwhichthe= normal componentoftherelativecontactvelocityvanishes. 3)Coulombfriction u=3Dcontactvelocityofobject1realtivetoobject2 u_t=3Dtangentialcomponentofu u_^t=3Dunitvectorindirectionofu_t f_n=3Dnormalcomponentofforceexertedbyobject2onobject= 1 f_t=3Dtangentialcomponentofforceexertedbyobject2on= object1 m=3Dcoefficientoffriction ifu_t!=3D0---->f_t=3D-m*abs(f_n)*u_^t ifu_t=3D0c---->abs(f_t)<=3Dm*abs(f_n)