Video Game Physics Tutorial Part II: Collision Detection - Toptal

The algorithm computes the closest points between shapes A and B, draws a vector from one point to the other, and projects the velocity on this vector to ... DevelopersHiring?Toptalhandpickstopgamedeveloperstosuityourneeds.Top3%WhyClientsEnterpriseCommunityBlogAboutUsFollowusonLogInGotoYourProfileEngineeringAllBlogsIconChevronIconCloseSearchFilterbyAllEngineeringDesignFinanceProjectsProductToptalInsightsViewallresultsEngineeringDesignFinanceProjectsProductToptalInsightsTechnology21minutereadVideoGamePhysicsTutorial-PartII:CollisionDetectionforSolidObjectsInPartIofthisthree-partseriesongamephysics,weexploredrigidbodiesandtheirmotions.Inthatdiscussion,however,objectsdidnotinteractwitheachother.Withoutsomeadditionalwork,thesimulatedrigidbodiescangorightthrougheachother. InPartII,wewillcoverthecollisiondetectionstep,whichconsistsoffindingpairsofbodiesthatarecollidingamongapossiblylargenumberofbodiesscatteredarounda2Dor3Dworld. AuthorAuthorNilsonSoutoNilson(dualBCS/BScTech)beenaniOSdevand2D/3Dartistfor8+years,focusingonphysicsandvehiclesimulations,games,andgraphics. SHARESHAREThisisPartIIofourthree-partseriesonvideogamephysics.Fortherestofthisseries,see: PartI:AnIntroductiontoRigidBodyDynamics PartIII:ConstrainedRigidBodySimulation InPartIofthisseries,weexploredrigidbodiesandtheirmotions.Inthatdiscussion,however,objectsdidnotinteractwitheachother.Withoutsomeadditionalwork,thesimulatedrigidbodiescangorightthrougheachother,or“interpenetrate”,whichisundesirableinthemajorityofcases. Inordertomorerealisticallysimulatethebehaviorofsolidobjects,wehavetocheckiftheycollidewitheachothereverytimetheymove,andiftheydo,wehavetodosomethingaboutit,suchasapplyingforcesthatchangetheirvelocities,sothattheywillmoveintheoppositedirection.Thisiswhereunderstandingcollisionphysicsisparticularlyimportantforgamedevelopers. InPartII,wewillcoverthecollisiondetectionstep,whichconsistsoffindingpairsofbodiesthatarecollidingamongapossiblylargenumberofbodiesscatteredarounda2Dor3Dworld.Inthenext,andfinal,installment,we’lltalkmoreabout“solving”thesecollisionstoeliminateinterpenetrations. Forareviewofthelinearalgebraconceptsreferredtointhisarticle,youcanrefertothelinearalgebracrashcourseinPartI. CollisionPhysicsinVideoGames Inthecontextofrigidbodysimulations,acollisionhappenswhentheshapesoftworigidbodiesareintersecting,orwhenthedistancebetweentheseshapesfallsbelowasmalltolerance. Ifwehavenbodiesinoursimulation,thecomputationalcomplexityofdetectingcollisionswithpairwisetestsisO(n2),anumberthatmakescomputerscientistscringe.Thenumberofpairwisetestsincreasesquadraticallywiththenumberofbodies,anddeterminingiftwoshapes,inarbitrarypositionsandorientations,arecollidingisalreadynotcheap.Inordertooptimizethecollisiondetectionprocess,wegenerallysplititintwophases:broadphaseandnarrowphase. Thebroadphaseisresponsibleforfindingpairsofrigidbodiesthatarepotentiallycolliding,andexcludingpairsthatarecertainlynotcolliding,fromamongstthewholesetofbodiesthatareinthesimulation.ThisstepmustbeabletoscalereallywellwiththenumberofrigidbodiestomakesurewestaywellundertheO(n2)timecomplexity.Toachievethat,thisphasegenerallyusesspacepartitioningcoupledwithboundingvolumesthatestablishanupperboundforcollision. Thenarrowphaseoperatesonthepairsofrigidbodiesfoundbythebroadphasethatmightbecolliding.Itisarefinementstepwherewedetermineifthecollisionsareactuallyhappening,andforeachcollisionthatisfound,wecomputethecontactpointsthatwillbeusedtosolvethecollisionslater. Inthenextsectionswe’lltalkaboutsomealgorithmsthatcanbeusedinthebroadphaseandnarrowphase. BroadPhase Inthebroadphaseofcollisionphysicsforvideogamesweneedtoidentifywhichpairsofrigidbodiesmightbecolliding.Thesebodiesmighthavecomplexshapeslikepolygonsandpolyhedrons,andwhatwecandotoacceleratethisistouseasimplershapetoencompasstheobject.Iftheseboundingvolumesdonotintersect,thentheactualshapesalsodonotintersect.Iftheyintersect,thentheactualshapesmightintersect. Somepopulartypesofboundingvolumesareorientedboundingboxes(OBB),circlesin2D,andspheresin3D.Let’slookatoneofthesimplestboundingvolumes:axis-alignedboundingboxes(AABB). AABBsgetalotoflovefromphysicsprogrammersbecausetheyaresimpleandoffergoodtradeoffs.A2-dimensionalAABBmayberepresentedbyastructlikethisintheClanguage: typedefstruct{ floatx; floaty; }Vector2; typedefstruct{ Vector2min; Vector2max; }AABB; Theminfieldrepresentsthelocationofthelowerleftcorneroftheboxandthemaxfieldrepresentsthetoprightcorner. TotestiftwoAABBsintersect,weonlyhavetofindoutiftheirprojectionsintersectonallofthecoordinateaxes: BOOLTestAABBOverlap(AABB*a,AABB*b) { floatd1x=b->min.x-a->max.x; floatd1y=b->min.y-a->max.y; floatd2x=a->min.x-b->max.x; floatd2y=a->min.y-b->max.y; if(d1x>0.0f||d1y>0.0f) returnFALSE; if(d2x>0.0f||d2y>0.0f) returnFALSE; returnTRUE; } Thiscodehasthesamelogicoftheb2TestOverlapfunctionfromtheBox2Dengine(version2.3.0).ItcalculatesthedifferencebetweentheminandmaxofbothAABBs,inbothaxes,inbothorders.Ifanyofthesevaluesisgreaterthanzero,theAABBsdon’tintersect. EventhoughanAABBoverlaptestischeap,itwon’thelpmuchifwestilldopairwisetestsforeverypossiblepairsincewestillhavetheundesirableO(n2)timecomplexity.TominimizethenumberofAABBoverlaptestswecanusesomekindofspacepartitioning,whichwhichworksonthesameprinciplesasdatabaseindicesthatspeedupqueries.(Geographicaldatabases,suchasPostGIS,actuallyusesimilardatastructuresandalgorithmsfortheirspatialindexes.)Inthiscase,though,theAABBswillbemovingaroundconstantly,sogenerally,wemustrecreateindicesaftereverystepofthesimulation. Thereareplentyofspacepartitioningalgorithmsanddatastructuresthatcanbeusedforthis,suchasuniformgrids,quadtreesin2D,octreesin3D,andspatialhashing.Letustakeacloserlookattwopopularspatialpartitioningalgorithms:sortandsweep,andboundingvolumehierarchies(BVH). TheSortandSweepAlgorithm Thesortandsweepmethod(alternativelyknownassweepandprune)isoneofthefavoritechoicesamongphysicsprogrammersforuseinrigidbodysimulation.TheBulletPhysicsengine,forexample,hasanimplementationofthismethodinthebtAxisSweep3class. TheprojectionofoneAABBontoasinglecoordinateaxisisessentiallyaninterval[b,e](thatis,beginningandend).Inoursimulation,we’llhavemanyrigidbodies,andthus,manyAABBs,andthatmeansmanyintervals.Wewanttofindoutwhichintervalsareintersecting. Inthesortandsweepalgorithm,weinsertallbandevaluesinasinglelistandsortitascendingbytheirscalarvalues.Thenwesweeportraversethelist.Wheneverabvalueisencountered,itscorrespondingintervalisstoredinaseparatelistofactiveintervals,andwheneveranevalueisencountered,itscorrespondingintervalisremovedfromthelistofactiveintervals.Atanymoment,alltheactiveintervalsareintersecting.(CheckoutDavidBaraff’sPh.DThesis,p.52fordetails.Isuggestusingthisonlinetooltoviewthepostscriptfile.)Thelistofintervalscanbereusedoneachstepofthesimulation,wherewecanefficientlyre-sortthislistusinginsertionsort,whichisgoodatsortingnearly-sortedlists. Intwoandthreedimensions,runningthesortandsweep,asdescribedabove,overasinglecoordinateaxiswillreducethenumberofdirectAABBintersectionteststhatmustbeperformed,butthepayoffmaybebetteroveronecoordinateaxisthananother.Therefore,moresophisticatedvariationsofthesortandsweepalgorithmareimplemented.InhisbookReal-TimeCollisionDetection(page336),ChristerEricsonpresentsanefficientvariationwherehestoresallAABBsinasinglearray,andforeachrunofthesortandsweep,onecoordinateaxisischosenandthearrayissortedbytheminvalueoftheAABBsinthechosenaxis,usingquicksort.Then,thearrayistraversedandAABBoverlaptestsareperformed.Todeterminethenextaxisthatshouldbeusedforsorting,thevarianceofthecenteroftheAABBsiscomputed,andtheaxiswithgreatervarianceischosenforthenextstep. DynamicBoundingVolumeTrees Anotherusefulspatialpartitioningmethodisthedynamicboundingvolumetree,alsoknownasDbvt.Thisisatypeofboundingvolumehierarchy. TheDbvtisabinarytreeinwhicheachnodehasanAABBthatboundsalltheAABBsofitschildren.TheAABBsoftherigidbodiesthemselvesarelocatedintheleafnodes.Typically,aDbvtis“queried”bygivingtheAABBforwhichwewouldliketodetectintersections.ThisoperationisefficientbecausethechildrenofnodesthatdonotintersectthequeriedAABBdonotneedtobetestedforoverlap.Assuch,anAABBcollisionquerystartsfromtheroot,andcontinuesrecursivelythroughthetreeonlyforAABBnodesthatintersectwiththequeriedAABB.Thetreecanbebalancedthroughtreerotations,asinanAVLtree. Box2DhasasophisticatedimplementationofDbvtintheb2DynamicTreeclass.Theb2BroadPhaseclassisresponsibleforperformingthebroadphase,anditusesaninstanceofb2DynamicTreetoperformAABBqueries. NarrowPhase Afterthebroadphaseofvideogamecollisionphysics,wehaveasetofpairsofrigidbodiesthatarepotentiallycolliding.Thus,foreachpair,giventheshape,positionandorientationofbothbodies,weneedtofindoutiftheyare,infact,colliding;iftheyareintersectingoriftheirdistancefallsunderasmalltolerancevalue.Wealsoneedtoknowwhatpointsofcontactarebetweenthecollidingbodies,sincethisisneededtoresolvethecollisionslater. ConvexandConcaveShapes Asavideogamephysicsgeneralrule,itisnottrivialtodetermineiftwoarbitraryshapesareintersecting,ortocomputethedistancebetweenthem.However,onepropertythatisofcriticalimportanceindeterminingjusthowharditis,istheconvexityoftheshape.Shapescanbeeitherconvexorconcaveandconcaveshapesarehardertoworkwith,soweneedsomestrategiestodealwiththem. Inaconvexshape,alinesegmentbetweenanytwopointswithintheshapealwaysfallscompletelyinsidetheshape.Howeverforaconcave(or“non-convex”)shape,thesameisnottrueforallpossiblelinesegmentsconnectingpointsintheshape.Ifyoucanfindatleastonelinesegmentthatfallsoutsideoftheshapeatall,thentheshapeisconcave. Computationally,itisdesirablethatallshapesareconvexinasimulation,sincewehavealotofpowerfuldistanceandintersectiontestalgorithmsthatworkwithconvexshapes.Notallobjectswillbeconvexthough,andusuallyweworkaroundthemintwoways:convexhullandconvexdecomposition. Theconvexhullofashapeisthesmallestconvexshapethatfullycontainsit.Foraconcavepolygonintwodimensions,itwouldbelikehammeringanailoneachvertexandwrappingarubberbandaroundallnails.Tocalculatetheconvexhullforapolygonorpolyhedron,ormoregenerally,forasetofpoints,agoodalgorithmtouseisthequickhullalgorithm,whichhasanaveragetimecomplexityofO(nlogn). Obviously,ifweuseaconvexhulltorepresentaconcaveobject,itwillloseitsconcaveproperties.Undesirablebehavior,suchas“ghost”collisionsmaybecomeapparent,sincetheobjectwillstillhaveaconcavegraphicalrepresentation.Forexample,acarusuallyhasaconcaveshape,andifweuseaconvexhulltorepresentitphysicallyandthenputaboxonit,theboxmightappeartobefloatinginthespaceabove. Ingeneral,convexhullsareoftengoodenoughtorepresentconcaveobjects,eitherbecausetheunrealisticcollisionsarenotverynoticeable,ortheirconcavepropertiesarenotessentialforwhateverisbeingsimulated.Insomecases,though,wemightwanttohavetheconcaveobjectbehavelikeaconcaveshapephysically.Forexample,ifweuseaconvexhulltorepresentabowlphysically,wewon’tbeabletoputanythinginsideofit.Objectswilljustfloatontopofit.Inthiscase,wecanuseaconvexdecompositionoftheconcaveshape. Convexdecompositionalgorithmsreceiveaconcaveshapeandreturnasetofconvexshapeswhoseunionisidenticaltotheoriginalconcaveshape.Someconcaveshapescanonlyberepresentedbyalargenumberofconvexshapes,andthesemightbecomeprohibitivelycostlytocomputeanduse.However,anapproximationisoftengoodenough,andso,algorithmssuchasV-HACDproduceasmallsetofconvexpolyhedronsoutofaconcavepolyhedron. Inmanycollisonsphysicscases,though,theconvexdecompositioncanbemadebyhand,byanartist.Thiseliminatestheneedtotaxperformancewithdecompositionalgorithms.Sinceperformanceisoneofthemostimportantaspectsinreal-timesimulations,it’sgenerallyagoodideatocreateverysimplephysicalrepresentationsforcomplexgraphicobjects.Theimagebelowshowsonepossibleconvexdecompositionofa2Dcarusingnineconvexshapes. TestingforIntersections-TheSeparatingAxisTheorem Theseparatingaxistheorem(SAT)statesthattwoconvexshapesarenotintersectingifandonlyifthereexistsatleastoneaxiswheretheorthogonalprojectionsoftheshapesonthisaxisdonotintersect. It’susuallymorevisuallyintuitivetofindalinein2Doraplanein3Dthatseparatesthetwoshapes,though,whichiseffectivelythesameprinciple.Avectororthogonaltothelinein2D,orthenormalvectoroftheplanein3D,canbeusedasthe“separatingaxis”. Gamephysicsengineshaveanumberofdifferentclassesofshapes,suchascircles(spheresin3D),edges(asinglelinesegment),andconvexpolygons(polyhedronsin3D).Foreachpairofshapetype,theyhaveaspecificcollisiondetectionalgorithm.Thesimplestofthemisprobablythecircle-circlealgorithm: typedefstruct{ floatcenterX; floatcenterY; floatradius; }Circle; boolCollideCircles(Circle*cA,Circle*cB){ floatx=cA->centerX-cB->centerX; floaty=cA->centerY-cB->centerY; floatcenterDistanceSq=x*x+y*y;//squareddistance floatradius=cA->radius+cB->radius; floatradiusSq=radius*radius; returncenterDistanceSq<=radiusSq; } EventhoughtheSATappliestocircles,it’smuchsimplertojustcheckifthedistancebetweentheircentersissmallerthanthesumoftheirradii.Forthatreason,theSATisusedinthecollisiondetectionalgorithmforspecificpairsofshapeclasses,suchasconvexpolygonagainstconvexpolygon(orpolyhedronsin3D). Foranypairofshapes,thereareaninfinitenumberofaxeswecantestforseparation.Thus,determiningwhichaxistotestfirstiscrucialforanefficientSATimplementation.Fortunately,whentestingifapairofconvexpolygonscollide,wecanusetheedgenormalsaspotentialseparatingaxes.Thenormalvectornofanedgeisperpendiculartotheedgevector,andpointsoutsidethepolygon.Foreachedgeofeachpolygon,wejustneedtofindoutifalltheverticesoftheotherpolygonareinfrontoftheedge. Ifanytestpasses–thatis,if,foranyedge,allverticesoftheotherpolygonareinfrontofit–thenthepolygonsdonotintersect.Linearalgebraprovidesaneasyformulaforthistest:givenanedgeonthefirstshapewithverticesaandbandavertexvontheothershape,if(v-a)·nisgreaterthanzero,thenthevertexisinfrontoftheedge. Forpolyhedrons,wecanusethefacenormalsandalsothecrossproductofalledgecombinationsfromeachshape.Thatsoundslikealotofthingstotest;however,tospeedthingsup,wecancachethelastseparatingaxisweusedandtryusingitagaininthenextstepsofthesimulation.Ifthecachedseparatingaxisdoesnotseparatetheshapesanymore,wecansearchforanewaxisstartingfromfacesoredgesthatareadjacenttothepreviousfaceoredge.Thatworksbecausethebodiesoftendon’tmoveorrotatemuchbetweensteps. Box2DusesSATtotestiftwoconvexpolygonsareintersectinginitspolygon-polygoncollisiondetectionalgorithminb2CollidePolygon.cpp. ComputingDistance-TheGilbert-Johnson-KeerthiAlgorithm Inmanycollisionsphysicscases,wewanttoconsiderobjectstobecollidingnotonlyiftheyareactuallyintersecting,butalsoiftheyareveryclosetoeachother,whichrequiresustoknowthedistancebetweenthem.TheGilbert-Johnson-Keerthi(GJK)algorithmcomputesthedistancebetweentwoconvexshapesandalsotheirclosestpoints.Itisanelegantalgorithmthatworkswithanimplicitrepresentationofconvexshapesthroughsupportfunctions,Minkowskisums,andsimplexes,asexplainedbelow. SupportFunctions AsupportfunctionsA(d)returnsapointontheboundaryoftheshapeAthathasthehighestprojectiononthevectord.Mathematically,ithasthehighestdotproductwithd.Thisiscalledasupportpoint,andthisoperationisalsoknownassupportmapping.Geometrically,thispointisthefarthestpointontheshapeinthedirectionofd. Findingasupportpointonapolygonisrelativelyeasy.Forasupportpointforvectord,youjusthavetoloopthroughitsverticesandfindtheonewhichhasthehighestdotproductwithd,likethis: Vector2GetSupport(Vector2*vertices,intcount,Vector2d){ floathighest=-FLT_MAX; Vector2support=(Vector2){0,0}; for(inti=0;ihighest){ highest=dot; support=v; } } returnsupport; } However,therealpowerofasupportfunctionisthatmakesiteasytoworkwithshapessuchascones,cylinders,andellipses,amongothers.Itisratherdifficulttocomputethedistancebetweensuchshapesdirectly,andwithoutanalgorithmlikeGJKyouwouldusuallyhavetodiscretizethemintoapolygonorpolyhedrontomakethingssimpler.However,thatmightleadtofurtherproblemsbecausethesurfaceofapolyhedronisnotassmoothasthesurfaceof,say,asphere,unlessthepolyhedronisverydetailed,whichcanleadtopoorperformanceduringcollisiondetection.Otherundesirablesideeffectsmightshowupaswell;forexample,a“polyhedral”spheremightnotrollsmoothly. Togetasupportpointforaspherecenteredontheorigin,wejusthavetonormalized(thatis,computed/||d||,whichisavectorwithlength1(unitlength)thatstillpointsinthesamedirectionofd)andthenwemultiplyitbythesphereradius. CheckGinovandenBergen’spapertofindmoreexamplesofsupportfunctionsforcylinders,andcones,amongothershapes. Ourobjectswill,ofcourse,bedisplacedandrotatedfromtheorigininthesimulationspace,soweneedtobeabletocomputesupportpointsforatransformedshape.WeuseanaffinetransformationT(x)=Rx+ctodisplaceandrotateourobjects,wherecisthedisplacementvectorandRistherotationmatrix.Thistransformationfirstrotatestheobjectabouttheorigin,andthentranslatesit.ThesupportfunctionforatransformedshapeAis: MinkowskiSums TheMinkowskisumoftwoshapesAandBisdefinedas: ThatmeanswecomputethesumforallpointscontainedinAandB.TheresultislikeinflatingAwithB. Similarly,wedefinetheMinkowskidifferenceas: whichwecanalsowriteastheMinkowskisumofAwith-B: ForconvexAandB,A⊕Bisalsoconvex. OneusefulpropertyoftheMinkowskidifferenceisthatifitcontainstheoriginofthespace,theshapesintersect,ascanbeseeninthepreviousimage.Whyisthat?Becauseiftwoshapesintersect,theyhaveatleastonepointincommon,whichlieinthesamelocationinspace,andtheirdifferenceisthezerovector,whichisactuallytheorigin. AnothernicefeatureoftheMinkowskidifferenceisthatifitdoesn’tcontaintheorigin,theminimumdistancebetweentheoriginandtheMinkowskidifferenceisthedistancebetweentheshapes. Thedistancebetweentwoshapesisdefinedas: Inotherwords,thedistancebetweenAandBisthelengthoftheshortestvectorthatgoesfromAtoB.ThisvectoriscontainedinA⊖Banditistheonewiththesmallestlength,whichconsequentlyistheoneclosesttotheorigin. ItisgenerallynotsimpletoexplicitlybuildtheMinkowskisumoftwoshapes.Fortunately,wecanusesupportmappinghereaswell,since: Simplexes TheGJKalgorithmiterativelysearchesforthepointontheMinkowskidifferenceclosesttotheorigin.Itdoessobybuildingaseriesofsimplexesthatareclosertotheoriginineachiteration.Asimplex–ormorespecifically,ak-simplexforanintegerk–istheconvexhullofk+1affinelyindependentpointsinak-dimensionalspace.Thatis,iffortwopoints,theymustnotcoincide,forthreepointstheyadditionallymustnotlieonthesameline,andifwehavefourpointstheyalsomustnotlieonthesameplane.Hence,the0-simplexisapoint,the1-simplexisalinesegment,the2-simplexisatriangleandthe3-simplexisatetrahedron.Ifweremoveapointfromasimplexwedecrementitsdimensionalitybyone,andifweaddapointtoasimplexweincrementitsdimensionalitybyone. GJKinAction Let’sputthisalltogethertoseehowGJKworks.TodeterminethedistancebetweentwoshapesAandB,westartbytakingtheirMinkowskidifferenceA⊖B.Wearesearchingfortheclosestpointtotheoriginontheresultingshape,sincethedistancetothispointisthedistancebetweentheoriginaltwoshapes.WechoosesomepointvinA⊖B,whichwillbeourdistanceapproximation.WealsodefineanemptypointsetW,whichwillcontainthepointsinthecurrenttestsimplex. Thenweenteraloop.Westartbygettingthesupportpointw=sA⊖B(-v),thepointonA⊖Bwhoseprojectionontovisclosesttotheorigin. If||w||isnotmuchdifferentthan||v||andtheanglebetweenthemdidn’tchangemuch(accordingtosomepredefinedtolerances),itmeansthealgorithmhasconvergedandwecanreturn||v||asthedistance. Otherwise,weaddwtoW.IftheconvexhullofW(thatis,thesimplex)containstheorigin,theshapesintersect,andthisalsomeanswearedone.Otherwise,wefindthepointinthesimplexthatisclosesttotheoriginandthenweresetvtobethisnewclosestapproximation.Finally,weremovewhateverpointsinWthatdonotcontributetotheclosestpointcomputation.(Forexample,ifwehaveatriangle,andtheclosestpointtotheoriginliesinoneofitsedges,wecanremovethepointfromWthatisnotavertexofthisedge.)Thenwerepeatthesesamestepsuntilthealgorithmconverges. ThenextimageshowsanexampleoffouriterationsoftheGJKalgorithm.TheblueobjectrepresentstheMinkowskidifferenceA⊖Bandthegreenvectorisv.Youcanseeherehowvhonesinontheclosestpointtotheorigin. Foradetailedandin-depthexplanationoftheGJKalgorithm,checkoutthepaperAFastandRobustGJKImplementationforCollisionDetectionofConvexObjects,byGinovandenBergen.Theblogforthedyn4jphysicsenginealsohasagreatpostonGJK. Box2DhasanimplementationoftheGJKalgorithminb2Distance.cpp,intheb2Distancefunction.ItonlyusesGJKduringtimeofimpactcomputationinitsalgorithmforcontinuouscollisiondetection(atopicwewilldiscussfurtherdown). TheChimpunkphysicsengineusesGJKforallcollisiondetection,anditsimplementationisincpCollision.c,intheGJKfunction.IftheGJKalgorithmreportsintersection,itstillneedstoknowwhatthecontactpointsare,alongwiththepenetrationdepth.Todothat,itusestheExpandingPolytopeAlgorithm,whichweshallexplorenext. DeterminingPenetrationDepth-TheExpandingPolytopeAlgorithm Asstatedabove,iftheshapesAandBareintersecting,GJKwillgenerateasimplexWthatcontainstheorigin,insidetheMinkowskidifferenceA⊖B.Atthisstage,weonlyknowthattheshapesintersect,butinthedesignofmanycollisiondetectionsystems,itisdesirabletobeabletocomputehowmuchintersectionwehave,andwhatpointswecanuseasthepointsofcontact,sothatwehandlethecollisioninarealisticway.TheExpandingPolytopeAlgorithm(EPA)allowsustoobtainthatinformation,startingwhereGJKleftoff:withasimplexthatcontainstheorigin. Thepenetrationdepthisthelengthoftheminimumtranslationvector(MTV),whichisthesmallestvectoralongwhichwecantranslateanintersectingshapetoseparateitfromtheothershape. Whentwoshapesareintersecting,theirMinkowskidifferencecontainstheorigin,andthepointontheboundaryoftheMinkowskidifferencethatisclosesttotheoriginistheMTV.TheEPAalgorithmfindsthatpointbyexpandingthesimplexthatGJKgaveusintoapolygon;successivelysubdividingit’sedgeswithnewvertices. First,wefindtheedgeofthesimplexclosesttotheorigin,andcomputethesupportpointintheMinkowskidifferenceinadirectionthatisnormaltotheedge(i.e.perpendiculartoitandpointingoutsidethepolygon).Thenwesplitthisedgebyaddingthissupportpointtoit.Werepeatthesestepsuntilthelengthanddirectionofthevectordoesn’tchangemuch.Oncethealgorithmconverges,wehavetheMTVandthepenetrationdepth. UsingGJKincombinationwithEPA,wegetadetaileddescriptionofthecollision,nomatteriftheobjectsarealreadyintersecting,orjustcloseenoughtobeconsideredacollision. TheEPAalgorithmisdescribedinthepaperProximityQueriesandPenetrationDepthComputationon3DGameObjects,alsowrittenbyGinovandenBergen.Thedyn4jblogalsohasapostaboutEPA. ContinuousCollisionDetection Thevideogamephysicstechniquespresentedsofarperformcollisiondetectionforastaticsnapshotofthesimulation.Thisiscalleddiscretecollisiondetection,anditignoreswhathappensbetweenthepreviousandcurrentsteps.Forthisreason,somecollisionsmightnotbedetected,especiallyforfastmovingobjects.Thisissueisknownastunneling. Continuouscollisiondetectiontechniquesattempttofindwhentwobodiescollidedbetweenthepreviousandthecurrentstepofthesimulation.Theycomputethetimeofimpact,sowecanthengobackintimeandprocessthecollisionatthatpoint. Thetimeofimpact(ortimeofcontact)tcistheinstantoftimewhenthedistancebetweentwobodiesiszero.Ifwecanwriteafunctionforthedistancebetweentwobodiesalongtime,whatwewanttofindisthesmallestrootofthisfunction.Thus,thetimeofimpactcomputationisaroot-findingproblem. Forthetimeofimpactcomputation,weconsiderthestate(positionandorientation)ofthebodyinthepreviousstepattimeti-1,andinthecurrentstepattimeti.Tomakethingssimpler,weassumelinearmotionbetweenthesteps. Let’ssimplifytheproblembyassumingtheshapesarecircles.FortwocirclesC1andC2,withradiusr1andr2,wheretheircenterofmassx1andx2coincidewiththeircentroid(i.e.,theynaturallyrotateabouttheircenterofmass),wecanwritethedistancefunctionas: Consideringlinearmotionbetweensteps,wecanwritethefollowingfunctionforthepositionofC1fromti-1toti Itisalinearinterpolationfromx1(ti-1)tox1(ti).Thesamecanbedoneforx2.Forthisintervalwecanwriteanotherdistancefunction: Setthisexpressionequaltozeroandyougetaquadraticequationont.Therootscanbefounddirectlyusingthequadraticformula.Ifthecirclesdon’tintersect,thequadraticformulawillnothaveasolution.Iftheydo,itmightresultinoneortworoots.Ifithasonlyoneroot,thatvalueisthetimeofimpact.Ifithastworoots,thesmallestoneisthetimeofimpactandtheotheristhetimewhenthecirclesseparate.Notethatthetimeofimpacthereisanumberfrom0to1.Itisnotatimeinseconds;itisjustanumberwecanusetointerpolatethestateofthebodiestothepreciselocationwherethecollisionhappened. ContinuousCollisionDetectionforNon-Circles Writingadistancefunctionforotherkindsofshapesisdifficult,primarilybecausetheirdistancedependsontheirorientations.Forthisreason,wegenerallyuseiterativealgorithmsthatmovetheobjectscloserandcloseroneachiterationuntiltheyarecloseenoughtobeconsideredcolliding. Theconservativeadvancementalgorithmmovesthebodiesforward(androtatesthem)iteratively.Ineachiterationitcomputesanupperboundfordisplacement.TheoriginalalgorithmispresentedinBrianMirtich’sPhDThesis(section2.3.2),whichconsiderstheballisticmotionofbodies.ThispaperbyErwinCoumans(theauthoroftheBulletPhysicsEngine)presentsasimplerversionthatusesconstantlinearandangularvelocities. ThealgorithmcomputestheclosestpointsbetweenshapesAandB,drawsavectorfromonepointtotheother,andprojectsthevelocityonthisvectortocomputeanupperboundformotion.Itguaranteesthatnopointsonthebodywillmovebeyondthisprojection.Thenitadvancesthebodiesforwardbythisamountandrepeatsuntilthedistancefallsunderasmalltolerancevalue. Itmaytaketoomanyiterationstoconvergeinsomecases,forexample,whentheangularvelocityofoneofthebodiesistoohigh. ResolvingCollisions Onceacollisionhasbeendetected,itisnecessarytochangethemotionsofthecollidingobjectsinarealisticway,suchascausingthemtobounceoffeachother.Inthenextandfinalinstallmentinthistheories,we’lldiscusssomepopularmethodsforresolvingcollisionsinvideogames. References Ifyouareinterestedinobtainingadeeperunderstandingaboutcollisionphysicssuchascollisiondetectionalgorithmsandtechniques,thebookReal-TimeCollisionDetection,byChristerEricson,isamust-have. Sincecollisiondetectionreliesheavilyongeometry,Toptal’sarticleComputationalGeometryinPython:FromTheorytoApplicationisanexcellentintroductiontothetopic. Related:AnIntroductoryRobotProgrammingTutorial TagsAnimationVideoGamesGamePhysicsCollisionDetectionSimulationsFreelancer?Findyournextjob.RemoteFreelanceJobsViewfullprofileNilsonSoutoFreelanceSoftwareDeveloperAbouttheauthorNilsonstartedprogramminginC/C++afterplayingvideogamesforthefirsttimeatayoungage.Overthelastfewyears,hehasworkedoniOSapplicationsmostly,andhe'snowfocusingongamedevelopment,computergraphics,physicssimulation,andvehiclesimulation.He'salsoa2D/3Dtechnicalartist.HireNilsonCommentsBhargavKrishnaYBgr8one:D,thanxforsharingbladeGreatarticle!I'vealwayswonderedhowexactlyBox2Dworks.There'samuchlargerstackofalgorithmsbehindthescenesthanIthought.TomoHopetosee3rdpartsoon:)DannyKorenblumassumingthatthevelocityisbounded,thencollisionscanonlyoccurattheboundariesonsufficientlysmallintegrationtimescales,soaboundaryapproximationforeachshapewouldprobablybewarrantedformostapplications.GeoffreyWadeThismightbethebestarticleIeverread!NickKowalskiwritessomeinformativestuff,andtherewasagoodc++articletoavoidmistakes,anotheroneaboutmakingthemostoutoflogs(Iagreewiththatguy)butthisisanawesome,accuratearticlesir!Verygood! Reallyallthearticlesfromthissitearegood,butthegreatsstandout! CongratsTrầnTuấnPhươngThankyou,Nilson.It'samazingtopic.I'mtryingtounderstandallyouwrote.Pietzthiswasoneawesometutorial.thankyousoverymuchDivijSoodThisisn'tanarticle,thisisathesis.MichaelSchlachterGreatwriteup!王宏亮Thankyou.Thisisreallyhelpful.commentspoweredbyDisqusWorld-classarticles,deliveredweekly.GetgreatcontentSubscriptionimpliesconsenttoourprivacypolicyThankyou!Checkoutyourinboxtoconfirmyourinvite.TrendingArticlesEngineeringIconChevronWebFront-endHarnessthePowerofWordPressHooks:ActionsandFiltersExplainedEngineeringIconChevronBack-endgRPCvs.REST:GettingStartedWiththeBestAPIProtocolEngineeringIconChevronBack-endCodeWritingCode:AnIntroductiontotheTheoryandPracticeofModernMetaprogrammingEngineeringIconChevronTechnologyEfficiencyatScale:ATaleofAWSCostOptimizationSeeourrelatedtalentGameCScientificComputingFreelancer?Findyournextjob.RemoteFreelanceJobsHiretheauthorViewfullprofileNilsonSoutoFreelanceSoftwareDeveloperReadNextEngineeringIconChevronDataScienceandDatabasesSocialNetworkAnalysisUsingPowerBIandR:ACustomVisualsGuideWorld-classarticles,deliveredweekly.SignMeUpSubscriptionimpliesconsenttoourprivacypolicyThankyou!Checkoutyourinboxtoconfirmyourinvite.World-classarticles,deliveredweekly.SignMeUpSubscriptionimpliesconsenttoourprivacypolicyThankyou!Checkoutyourinboxtoconfirmyourinvite.ToptalDevelopersAlgorithmDevelopersAngularDevelopersAWSDevelopersAzureDevelopersBigDataArchitectsBlockchainDevelopersBusinessIntelligenceDevelopersCDevelopersComputerVisionDevelopersDjangoDevelopersDockerDevelopersElixirDevelopersGoEngineersGraphQLDevelopersJenkinsDevelopersKotlinDevelopersKubernetesExpertsMachineLearningEngineersMagentoDevelopers.NETDevelopersRDevelopersReactNativeDevelopersRubyonRailsDevelopersSalesforceDevelopersSQLDevelopersSysAdminsTableauDevelopersUnrealEngineDevelopersXamarinDevelopersViewMoreFreelanceDevelopersJointheToptal®community. HireaDeveloperORApplyasaDeveloperBycontinuingtousethissiteyouagreetoourCookiePolicy.Gotit