Collision detection - Wikipedia

Collision detection is the computational problem of detecting the intersection of two or ... Collision detection algorithms can be divided into operating on 2D and 3D ... Collisiondetection FromWikipedia,thefreeencyclopedia Jumptonavigation Jumptosearch Termincomputerscience Thisarticleisaboutcollisiondetectionincomputationalgeometry.Forcollisiondetectionincomputernetworks,seecarrier-sensemultipleaccesswithcollisiondetection. Thisarticle'stoneorstylemaynotreflecttheencyclopedictoneusedonWikipedia.SeeWikipedia'sguidetowritingbetterarticlesforsuggestions.(August2014)(Learnhowandwhentoremovethistemplatemessage) Collisiondetectionisthecomputationalproblemofdetectingtheintersectionoftwoormoreobjects.Collisiondetectionisaclassicissueofcomputationalgeometryandhasapplicationsinvariouscomputingfields,primarilyincomputergraphics,computergames,computersimulations,roboticsandcomputationalphysics.Collisiondetectionalgorithmscanbedividedintooperatingon2Dand3Dobjects.[1] Contents 1Overview 2Collisiondetectionincomputersimulation 2.1Aposteriori(discrete)versusapriori(continuous) 3Optimization 3.1Exploitingtemporalcoherence 3.2Pairwisepruning 3.3Exactpairwisecollisiondetection 3.4Aprioripruning 3.5Spatialpartitioning 3.6Boundingboxes 3.7Trianglecentroidsegments 4Videogames 4.1Hitbox 5Seealso 6References 7Externallinks Overview[edit] Billiardsballshittingeachotherareaclassicexampleapplicablewithinthescienceofcollisiondetection. Thisarticleiswrittenlikeamanualorguidebook.Pleasehelprewritethisarticlefromadescriptive,neutralpointofview,andremoveadviceorinstruction.(March2020)(Learnhowandwhentoremovethistemplatemessage) Inphysicalsimulation,experimentssuchasplayingbilliards,areconducted.Thephysicsofbouncingbilliardballsarewellunderstood,undertheumbrellaofrigidbodymotionandelasticcollisions.Aninitialdescriptionofthesituationwouldbegiven,withaveryprecisephysicaldescriptionofthebilliardtableandballs,aswellasinitialpositionsofalltheballs.Givenaforceappliedtothecueball(probablyresultingfromaplayerhittingtheballwiththeircuestick),wewanttocalculatethetrajectories,precisemotionandeventualrestingplacesofalltheballswithacomputerprogram.Aprogramtosimulatethisgamewouldconsistofseveralportions,oneofwhichwouldberesponsibleforcalculatingthepreciseimpactsbetweenthebilliardballs.Thisparticularexamplealsoturnsouttobeillconditioned:asmallerrorinanycalculationwillcausedrasticchangesinthefinalpositionofthebilliardballs. Videogameshavesimilarrequirements,withsomecrucialdifferences.Whilecomputersimulationneedstosimulatereal-worldphysicsaspreciselyaspossible,computergamesneedtosimulatereal-worldphysicsinanacceptableway,inrealtimeandrobustly.Compromisesareallowed,solongastheresultingsimulationissatisfyingtothegameplayers. Collisiondetectionincomputersimulation[edit] Physicalsimulatorsdifferinthewaytheyreactonacollision.Someusethesoftnessofthematerialtocalculateaforce,whichwillresolvethecollisioninthefollowingtimestepslikeitisinreality.DuetothelowsoftnessofsomematerialsthisisveryCPUintensive.Somesimulatorsestimatethetimeofcollisionbylinearinterpolation,rollbackthesimulation,andcalculatethecollisionbythemoreabstractmethodsofconservationlaws. Someiteratethelinearinterpolation(Newton'smethod)tocalculatethetimeofcollisionwithamuchhigherprecisionthantherestofthesimulation.CollisiondetectionutilizestimecoherencetoallowevenfinertimestepswithoutmuchincreasingCPUdemand,suchasinairtrafficcontrol. Afteraninelasticcollision,specialstatesofslidingandrestingcanoccurand,forexample,theOpenDynamicsEngineusesconstraintstosimulatethem.Constraintsavoidinertiaandthusinstability.Implementationofrestbymeansofascenegraphavoidsdrift. Inotherwords,physicalsimulatorsusuallyfunctiononeoftwoways,wherethecollisionisdetectedaposteriori(afterthecollisionoccurs)orapriori(beforethecollisionoccurs).Inadditiontotheaposterioriandaprioridistinction,almostallmoderncollisiondetectionalgorithmsarebrokenintoahierarchyofalgorithms.Oftentheterms"discrete"and"continuous"areusedratherthanaposterioriandapriori. Aposteriori(discrete)versusapriori(continuous)[edit] Thisarticle'stoneorstylemaynotreflecttheencyclopedictoneusedonWikipedia.SeeWikipedia'sguidetowritingbetterarticlesforsuggestions.(July2018)(Learnhowandwhentoremovethistemplatemessage) Intheaposterioricase,thephysicalsimulationisadvancedbyasmallstep,thencheckedtoseeifanyobjectsareintersectingorvisiblyconsideredintersecting.Ateachsimulationstep,alistofallintersectingbodiesiscreated,andthepositionsandtrajectoriesoftheseobjectsare"fixed"toaccountforthecollision.Thismethodiscalledaposterioribecauseittypicallymissestheactualinstantofcollision,andonlycatchesthecollisionafterithasactuallyhappened. Intheapriorimethods,thereisacollisiondetectionalgorithmwhichwillbeabletopredictverypreciselythetrajectoriesofthephysicalbodies.Theinstantsofcollisionarecalculatedwithhighprecision,andthephysicalbodiesneveractuallyinterpenetrate.Thisiscalledaprioribecausethecollisiondetectionalgorithmcalculatestheinstantsofcollisionbeforeitupdatestheconfigurationofthephysicalbodies. Themainbenefitsoftheaposteriorimethodsareasfollows.Inthiscase,thecollisiondetectionalgorithmneednotbeawareofthemyriadofphysicalvariables;asimplelistofphysicalbodiesisfedtothealgorithm,andtheprogramreturnsalistofintersectingbodies.Thecollisiondetectionalgorithmdoesn'tneedtounderstandfriction,elasticcollisions,orworse,nonelasticcollisionsanddeformablebodies.Inaddition,theaposteriorialgorithmsareineffectonedimensionsimplerthantheapriorialgorithms.Anapriorialgorithmmustdealwiththetimevariable,whichisabsentfromtheaposterioriproblem. Ontheotherhand,aposteriorialgorithmscauseproblemsinthe"fixing"step,whereintersections(whicharen'tphysicallycorrect)needtobecorrected.Moreover,ifthediscretestepistoolarge,thecollisioncouldgoundetected,resultinginanobjectwhichpassesthroughanotherifitissufficientlyfastorsmall. Thebenefitsoftheapriorialgorithmsareincreasedfidelityandstability.Itisdifficult(butnotcompletelyimpossible)toseparatethephysicalsimulationfromthecollisiondetectionalgorithm.However,inallbutthesimplestcases,theproblemofdeterminingaheadoftimewhentwobodieswillcollide(givensomeinitialdata)hasnoclosedformsolution—anumericalrootfinderisusuallyinvolved. Someobjectsareinrestingcontact,thatis,incollision,butneitherbouncingoff,norinterpenetrating,suchasavaserestingonatable.Inallcases,restingcontactrequiresspecialtreatment:Iftwoobjectscollide(aposteriori)orslide(apriori)andtheirrelativemotionisbelowathreshold,frictionbecomesstictionandbothobjectsarearrangedinthesamebranchofthescenegraph. Optimization[edit] Theobviousapproachestocollisiondetectionformultipleobjectsareveryslow. Checkingeveryobjectagainsteveryotherobjectwill,ofcourse,work,butistooinefficienttobeusedwhenthenumberofobjectsisatalllarge.Checkingobjectswithcomplexgeometryagainsteachotherintheobviousway,bycheckingeachfaceagainsteachotherface,isitselfquiteslow.Thus,considerableresearchhasbeenappliedtospeeduptheproblem.[2] Exploitingtemporalcoherence[edit] Thisarticlemaybetootechnicalformostreaderstounderstand.Pleasehelpimproveittomakeitunderstandabletonon-experts,withoutremovingthetechnicaldetails.(March2020)(Learnhowandwhentoremovethistemplatemessage) Thisarticle'stoneorstylemaynotreflecttheencyclopedictoneusedonWikipedia.SeeWikipedia'sguidetowritingbetterarticlesforsuggestions.(March2020)(Learnhowandwhentoremovethistemplatemessage) Inmanyapplications,theconfigurationofphysicalbodiesfromonetimesteptothenextchangesverylittle.Manyoftheobjectsmaynotmoveatall. Algorithmshavebeendesignedsothatthecalculationsdoneinaprecedingtimestepcanbereusedinthecurrenttimestep,resultinginfastercompletionofthecalculation. Atthecoarselevelofcollisiondetection,theobjectiveistofindpairsofobjectswhichmightpotentiallyintersect.Thosepairswillrequirefurtheranalysis.AnearlyhighperformancealgorithmforthiswasdevelopedbyMingC.LinattheUniversityofCalifornia,Berkeley[1],whosuggestedusingaxis-alignedboundingboxesforallnbodiesinthescene. Eachboxisrepresentedbytheproductofthreeintervals(i.e.,aboxwouldbe I 1 × I 2 × I 3 = [ a 1 , b 1 ] × [ a 2 , b 2 ] × [ a 3 , b 3 ] {\displaystyleI_{1}\timesI_{2}\timesI_{3}=[a_{1},b_{1}]\times[a_{2},b_{2}]\times[a_{3},b_{3}]} ).Acommonalgorithmforcollisiondetectionofboundingboxesissweepandprune.Observethattwosuchboxes, I 1 × I 2 × I 3 {\displaystyleI_{1}\timesI_{2}\timesI_{3}} and J 1 × J 2 × J 3 {\displaystyleJ_{1}\timesJ_{2}\timesJ_{3}} intersectif,andonlyif, I 1 {\displaystyleI_{1}} intersects J 1 {\displaystyleJ_{1}} , I 2 {\displaystyleI_{2}} intersects J 2 {\displaystyleJ_{2}} and I 3 {\displaystyleI_{3}} intersects J 3 {\displaystyleJ_{3}} .Itissupposedthat,fromonetimesteptothenext, I k {\displaystyleI_{k}} and J k {\displaystyleJ_{k}} intersect,thenitisverylikelythatatthenexttimesteptheywillstillintersect.Likewise,iftheydidnotintersectintheprevioustimestep,thentheyareverylikelytocontinuenottoo. Sowereducetheproblemtothatoftracking,fromframetoframe,whichintervalsdointersect.Wehavethreelistsofintervals(oneforeachaxis)andalllistsarethesamelength(sinceeachlisthaslength n {\displaystylen} ,thenumberofboundingboxes.)Ineachlist,eachintervalisallowedtointersectallotherintervalsinthelist.Soforeachlist,wewillhavean n × n {\displaystylen\timesn} matrix M = ( m i j ) {\displaystyleM=(m_{ij})} ofzeroesandones: m i j {\displaystylem_{ij}} is1ifintervals i {\displaystylei} and j {\displaystylej} intersect,and0iftheydonotintersect. Byourassumption,thematrix M {\displaystyleM} associatedtoalistofintervalswillremainessentiallyunchangedfromonetimesteptothenext.Toexploitthis,thelistofintervalsisactuallymaintainedasalistoflabeledendpoints.Eachelementofthelisthasthecoordinateofanendpointofaninterval,aswellasauniqueintegeridentifyingthatinterval.Then,wesortthelistbycoordinates,andupdatethematrix M {\displaystyleM} aswego.It'snotsohardtobelievethatthisalgorithmwillworkrelativelyquicklyifindeedtheconfigurationofboundingboxesdoesnotchangesignificantlyfromonetimesteptothenext. Inthecaseofdeformablebodiessuchasclothsimulation,itmaynotbepossibletouseamorespecificpairwisepruningalgorithmasdiscussedbelow,andann-bodypruningalgorithmisthebestthatcanbedone. Ifanupperboundcanbeplacedonthevelocityofthephysicalbodiesinascene,thenpairsofobjectscanbeprunedbasedontheirinitialdistanceandthesizeofthetimestep. Pairwisepruning[edit] Thisarticlemaybetootechnicalformostreaderstounderstand.Pleasehelpimproveittomakeitunderstandabletonon-experts,withoutremovingthetechnicaldetails.(March2020)(Learnhowandwhentoremovethistemplatemessage) Thisarticle'stoneorstylemaynotreflecttheencyclopedictoneusedonWikipedia.SeeWikipedia'sguidetowritingbetterarticlesforsuggestions.(March2020)(Learnhowandwhentoremovethistemplatemessage) Oncewe'veselectedapairofphysicalbodiesforfurtherinvestigation,weneedtocheckforcollisionsmorecarefully.However,inmanyapplications,individualobjects(iftheyarenottoodeformable)aredescribedbyasetofsmallerprimitives,mainlytriangles.Sonow,wehavetwosetsoftriangles, S = S 1 , S 2 , … , S n {\displaystyleS={S_{1},S_{2},\dots,S_{n}}} and T = T 1 , T 2 , … , T n {\displaystyleT={T_{1},T_{2},\dots,T_{n}}} (forsimplicity,wewillassumethateachsethasthesamenumberoftriangles.) Theobviousthingtodoistocheckalltriangles S j {\displaystyleS_{j}} againstalltriangles T k {\displaystyleT_{k}} forcollisions,butthisinvolves n 2 {\displaystylen^{2}} comparisons,whichishighlyinefficient.Ifpossible,itisdesirabletouseapruningalgorithmtoreducethenumberofpairsoftrianglesweneedtocheck. Themostwidelyusedfamilyofalgorithmsisknownasthehierarchicalboundingvolumesmethod.Asapreprocessingstep,foreachobject(inourexample, S {\displaystyleS} and T {\displaystyleT} )wewillcalculateahierarchyofboundingvolumes.Then,ateachtimestep,whenweneedtocheckforcollisionsbetween S {\displaystyleS} and T {\displaystyleT} ,thehierarchicalboundingvolumesareusedtoreducethenumberofpairsoftrianglesunderconsideration.Forsimplicity,wewillgiveanexampleusingboundingspheres,althoughithasbeennotedthatspheresareundesirableinmanycases.[citationneeded] If E {\displaystyleE} isasetoftriangles,wecanprecalculateaboundingsphere B ( E ) {\displaystyleB(E)} .Therearemanywaysofchoosing B ( E ) {\displaystyleB(E)} ,weonlyassumethat B ( E ) {\displaystyleB(E)} isaspherethatcompletelycontains E {\displaystyleE} andisassmallaspossible. Aheadoftime,wecancompute B ( S ) {\displaystyleB(S)} and B ( T ) {\displaystyleB(T)} .Clearly,ifthesetwospheresdonotintersect(andthatisveryeasytotest),thenneitherdo S {\displaystyleS} and T {\displaystyleT} .Thisisnotmuchbetterthanann-bodypruningalgorithm,however. If E = E 1 , E 2 , … , E m {\displaystyleE={E_{1},E_{2},\dots,E_{m}}} isasetoftriangles,thenwecansplititintotwohalves L ( E ) := E 1 , E 2 , … , E m / 2 {\displaystyleL(E):={E_{1},E_{2},\dots,E_{m/2}}} and R ( E ) := E m / 2 + 1 , … , E m − 1 , E m {\displaystyleR(E):={E_{m/2+1},\dots,E_{m-1},E_{m}}} .Wecandothisto S {\displaystyleS} and T {\displaystyleT} ,andwecancalculate(aheadoftime)theboundingspheres B ( L ( S ) ) , B ( R ( S ) ) {\displaystyleB(L(S)),B(R(S))} and B ( L ( T ) ) , B ( R ( T ) ) {\displaystyleB(L(T)),B(R(T))} .Thehopehereisthattheseboundingspheresaremuchsmallerthan B ( S ) {\displaystyleB(S)} and B ( T ) {\displaystyleB(T)} .And,if,forinstance, B ( S ) {\displaystyleB(S)} and B ( L ( T ) ) {\displaystyleB(L(T))} donotintersect,thenthereisnosenseincheckinganytrianglein S {\displaystyleS} againstanytrianglein L ( T ) {\displaystyleL(T)} . Asaprecomputation,wecantakeeachphysicalbody(representedbyasetoftriangles)andrecursivelydecomposeitintoabinarytree,whereeachnode N {\displaystyleN} representsasetoftriangles,anditstwochildrenrepresent L ( N ) {\displaystyleL(N)} and R ( N ) {\displaystyleR(N)} .Ateachnodeinthetree,wecanprecomputetheboundingsphere B ( N ) {\displaystyleB(N)} . Whenthetimecomesfortestingapairofobjectsforcollision,theirboundingspheretreecanbeusedtoeliminatemanypairsoftriangles. Manyvariantsofthealgorithmsareobtainedbychoosingsomethingotherthanaspherefor B ( T ) {\displaystyleB(T)} .Ifonechoosesaxis-alignedboundingboxes,onegetsAABBTrees.OrientedboundingboxtreesarecalledOBBTrees.Sometreesareeasiertoupdateiftheunderlyingobjectchanges.Sometreescanaccommodatehigherorderprimitivessuchassplinesinsteadofsimpletriangles. Exactpairwisecollisiondetection[edit] Oncewe'redonepruning,weareleftwithanumberofcandidatepairstocheckforexactcollisiondetection. Abasicobservationisthatforanytwoconvexobjectswhicharedisjoint,onecanfindaplaneinspacesothatoneobjectliescompletelyononesideofthatplane,andtheotherobjectliesontheoppositesideofthatplane.Thisallowsthedevelopmentofveryfastcollisiondetectionalgorithmsforconvexobjects. Earlyworkinthisareainvolved"separatingplane"methods.Twotrianglescollideessentiallyonlywhentheycannotbeseparatedbyaplanegoingthroughthreevertices.Thatis,ifthetrianglesare v 1 , v 2 , v 3 {\displaystyle{v_{1},v_{2},v_{3}}} and v 4 , v 5 , v 6 {\displaystyle{v_{4},v_{5},v_{6}}} whereeach v j {\displaystylev_{j}} isavectorin R 3 {\displaystyle\mathbb{R}^{3}} ,thenwecantakethreevertices, v i , v j , v k {\displaystylev_{i},v_{j},v_{k}} ,findaplanegoingthroughallthreevertices,andchecktoseeifthisisaseparatingplane.Ifanysuchplaneisaseparatingplane,thenthetrianglesaredeemedtobedisjoint.Ontheotherhand,ifnoneoftheseplanesareseparatingplanes,thenthetrianglesaredeemedtointersect.Therearetwentysuchplanes. Ifthetrianglesarecoplanar,thistestisnotentirelysuccessful.Onecanaddsomeextraplanes,forinstance,planesthatarenormaltotriangleedges,tofixtheproblementirely.Inothercases,objectsthatmeetataflatfacemustnecessarilyalsomeetatanangleelsewhere,hencetheoverallcollisiondetectionwillbeabletofindthecollision. Bettermethodshavesincebeendeveloped.Veryfastalgorithmsareavailableforfindingtheclosestpointsonthesurfaceoftwoconvexpolyhedralobjects.EarlyworkbyMingC.Lin[3]usedavariationonthesimplexalgorithmfromlinearprogramming.TheGilbert-Johnson-Keerthidistancealgorithmhassupersededthatapproach.Thesealgorithmsapproachconstanttimewhenappliedrepeatedlytopairsofstationaryorslow-movingobjects,whenusedwithstartingpointsfromthepreviouscollisioncheck. Theendresultofallthisalgorithmicworkisthatcollisiondetectioncanbedoneefficientlyforthousandsofmovingobjectsinrealtimeontypicalpersonalcomputersandgameconsoles. Aprioripruning[edit] Wheremostoftheobjectsinvolvedarefixed,asistypicalofvideogames,apriorimethodsusingprecomputationcanbeusedtospeedupexecution. Pruningisalsodesirablehere,bothn-bodypruningandpairwisepruning,butthealgorithmsmusttaketimeandthetypesofmotionsusedintheunderlyingphysicalsystemintoconsideration. Whenitcomestotheexactpairwisecollisiondetection,thisishighlytrajectorydependent,andonealmosthastouseanumericalroot-findingalgorithmtocomputetheinstantofimpact. Asanexample,considertwotrianglesmovingintime v 1 ( t ) , v 2 ( t ) , v 3 ( t ) {\displaystyle{v_{1}(t),v_{2}(t),v_{3}(t)}} and v 4 ( t ) , v 5 ( t ) , v 6 ( t ) {\displaystyle{v_{4}(t),v_{5}(t),v_{6}(t)}} .Atanypointintime,thetwotrianglescanbecheckedforintersectionusingthetwentyplanespreviouslymentioned.However,wecandobetter,sincethesetwentyplanescanallbetrackedintime.If P ( u , v , w ) {\displaystyleP(u,v,w)} istheplanegoingthroughpoints u , v , w {\displaystyleu,v,w} in R 3 {\displaystyle\mathbb{R}^{3}} thentherearetwentyplanes P ( v i ( t ) , v j ( t ) , v k ( t ) ) {\displaystyleP(v_{i}(t),v_{j}(t),v_{k}(t))} totrack.Eachplaneneedstobetrackedagainstthreevertices,thisgivessixtyvaluestotrack.Usingarootfinderonthesesixtyfunctionsproducestheexactcollisiontimesforthetwogiventrianglesandthetwogiventrajectory.Wenoteherethatifthetrajectoriesoftheverticesareassumedtobelinearpolynomialsin t {\displaystylet} thenthefinalsixtyfunctionsareinfactcubicpolynomials,andinthisexceptionalcase,itispossibletolocatetheexactcollisiontimeusingtheformulafortherootsofthecubic.Somenumericalanalystssuggestthatusingtheformulafortherootsofthecubicisnotasnumericallystableasusingarootfinderforpolynomials.[citationneeded] Spatialpartitioning[edit] Alternativealgorithmsaregroupedunderthespatialpartitioningumbrella,whichincludesoctrees,binaryspacepartitioning(orBSPtrees)andother,similarapproaches.Ifonesplitsspaceintoanumberofsimplecells,andiftwoobjectscanbeshownnottobeinthesamecell,thentheyneednotbecheckedforintersection.SinceBSPtreescanbeprecomputed,thatapproachiswellsuitedtohandlingwallsandfixedobstaclesingames.Thesealgorithmsaregenerallyolderthanthealgorithmsdescribedabove. Boundingboxes[edit] Boundingboxes(orboundingvolumes)aremostoftena2Drectangleor3Dcuboid,butothershapesarepossible.AboundingboxinavideogameissometimescalledaHitbox. Theboundingdiamond,theminimumboundingparallelogram,theconvexhull,theboundingcircleorboundingball,andtheboundingellipsehaveallbeentried,butboundingboxesremainthemostpopularduetotheirsimplicity.[4]Boundingboxesaretypicallyusedintheearly(pruning)stageofcollisiondetection,sothatonlyobjectswithoverlappingboundingboxesneedbecomparedindetail. Trianglecentroidsegments[edit] Atrianglemeshobjectiscommonlyusedin3Dbodymodeling.Normallythecollisionfunctionisatriangletotriangleinterceptoraboundingshapeassociatedwiththemesh.Atrianglecentroidisacenterofmasslocationsuchthatitwouldbalanceonapenciltip.Thesimulationneedonlyaddacentroiddimensiontothephysicsparameters.Givencentroidpointsinbothobjectandtargetitispossibletodefinethelinesegmentconnectingthesetwopoints. Thepositionvectorofthecentroidofatriangleistheaverageofthepositionvectorsofitsvertices.SoifitsverticeshaveCartesiancoordinates ( x 1 , y 1 , z 1 ) {\displaystyle(x_{1},y_{1},z_{1})} , ( x 2 , y 2 , z 2 ) {\displaystyle(x_{2},y_{2},z_{2})} and ( x 3 , y 3 , z 3 ) {\displaystyle(x_{3},y_{3},z_{3})} thenthecentroidis ( ( x 1 + x 2 + x 3 ) 3 , ( y 1 + y 2 + y 3 ) 3 , ( z 1 + z 2 + z 3 ) 3 ) {\displaystyle\left({\frac{(x_{1}+x_{2}+x_{3})}{3}},{\frac{(y_{1}+y_{2}+y_{3})}{3}},{\frac{(z_{1}+z_{2}+z_{3})}{3}}\right)} . Hereisthefunctionforalinesegmentdistancebetweentwo3Dpoints. d i s t a n c e = ( z 2 − z 1 ) 2 + ( x 2 − x 1 ) 2 + ( y 2 − y 1 ) 2 {\displaystyle\mathrm{distance}={\sqrt{(z_{2}-z_{1})^{2}+(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}}} Herethelength/distanceofthesegmentisanadjustable"hit"criteriasizeofsegment.Astheobjectsapproachthelengthdecreasestothethresholdvalue.Atrianglespherebecomestheeffectivegeometrytest.Aspherecenteredatthecentroidcanbesizedtoencompassallthetriangle'svertices. Videogames[edit] Videogameshavetosplittheirverylimitedcomputingtimebetweenseveraltasks.Despitethisresourcelimit,andtheuseofrelativelyprimitivecollisiondetectionalgorithms,programmershavebeenabletocreatebelievable,ifinexact,systemsforuseingames[citationneeded]. Foralongtime,videogameshadaverylimitednumberofobjectstotreat,andsocheckingallpairswasnotaproblem.Intwo-dimensionalgames,insomecases,thehardwarewasabletoefficientlydetectandreportoverlappingpixelsbetweenspritesonthescreen.[5]Inothercases,simplytilingthescreenandbindingeachspriteintothetilesitoverlapsprovidessufficientpruning,andforpairwisechecks,boundingrectanglesorcirclescalledhitboxesareusedanddeemedsufficientlyaccurate. Three-dimensionalgameshaveusedspatialpartitioningmethodsfor n {\displaystylen} -bodypruning,andforalongtimeusedoneorafewspheresperactual3Dobjectforpairwisechecks.Exactchecksareveryrare,exceptingamesattemptingtosimulaterealityclosely.Eventhen,exactchecksarenotnecessarilyusedinallcases. Becausegamesdonotneedtomimicactualphysics,stabilityisnotasmuchofanissue.Almostallgamesuseaposterioricollisiondetection,andcollisionsareoftenresolvedusingverysimplerules.Forinstance,ifacharacterbecomesembeddedinawall,theymightbesimplymovedbacktotheirlastknowngoodlocation.Somegameswillcalculatethedistancethecharactercanmovebeforegettingembeddedintoawall,andonlyallowthemtomovethatfar. Inmanycasesforvideogames,approximatingthecharactersbyapointissufficientforthepurposeofcollisiondetectionwiththeenvironment.Inthiscase,binaryspacepartitioningtreesprovideaviable,efficientandsimplealgorithmforcheckingifapointisembeddedinthesceneryornot.Suchadatastructurecanalsobeusedtohandle"restingposition"situationgracefullywhenacharacterisrunningalongtheground.Collisionsbetweencharacters,andcollisionswithprojectilesandhazards,aretreatedseparately. Arobustsimulatorisonethatwillreacttoanyinputinareasonableway.Forinstance,ifweimagineahighspeedracecarvideogame,fromonesimulationsteptothenext,itisconceivablethatthecarswouldadvanceasubstantialdistancealongtheracetrack.Ifthereisashallowobstacleonthetrack(suchasabrickwall),itisnotentirelyunlikelythatthecarwillcompletelyleapoverit,andthisisveryundesirable.Inotherinstances,the"fixing"thatposteriorialgorithmsrequireisn'timplementedcorrectly,resultinginbugsthatcantrapcharactersinwallsorallowthemtopassthroughthemandfallintoanendlessvoidwheretheremayormaynotbeadeadlybottomlesspit,sometimesreferredtoas"blackhell","bluehell",or"greenhell",dependingonthepredominantcolor.Thesearethehallmarksofafailingcollisiondetectionandphysicalsimulationsystem.BigRigs:OvertheRoadRacingisaninfamousexampleofagamewithafailingorpossiblymissingcollisiondetectionsystem. Hitbox[edit] AdebugdialogueboxinGearheadscontrollinganobject'shitbox ThehitboxofaGearheadstoy,controlledbytheabovescreen Ahitboxisaninvisibleshapecommonlyusedinvideogamesforreal-timecollisiondetection;itisatypeofboundingbox.Itisoftenarectangle(in2Dgames)orcuboid(in3D)thatisattachedtoandfollowsapointonavisibleobject(suchasamodelorasprite).Circularorspheroidialshapesarealsocommon,thoughtheyarestillmostoftencalled"boxes".Itiscommonforanimatedobjectstohavehitboxesattachedtoeachmovingparttoensureaccuracyduringmotion.[6][unreliablesource?] Hitboxesareusedtodetect"one-way"collisionssuchasacharacterbeinghitbyapunchorabullet.Theyareunsuitableforthedetectionofcollisionswithfeedback(e.g.bumpingintoawall)duetothedifficultyexperiencedbybothhumansandAIinmanagingahitbox'sever-changinglocations;thesesortsofcollisionsaretypicallyhandledwithmuchsimpleraxis-alignedboundingboxesinstead.Playersmayusetheterm"hitbox"torefertothesetypesofinteractionsregardless. Ahurtboxisarelatedterm,usedtodifferentiate"objectthatdealsdamage"from"objectthatreceivesdamage".Forexample,anattackmayonlylandifthehitboxaroundanattacker'spunchconnectswithoneoftheopponent'shurtboxesontheirbody,whileopposinghitboxescollidingmayresultintheplayerstradingorcancellingblows,andopposinghurtboxesdonotinteractwitheachother.Thetermisnotstandardizedacrosstheindustry;somegamesreversetheirdefinitionsof"hitbox"and"hurtbox",whileothersonlyuse"hitbox"forbothsides. Seealso[edit] Hit-testing Boundingvolume Gamephysics Gilbert–Johnson–Keerthidistancealgorithm MinkowskiPortalRefinement Physicsengine Lubachevsky–Stillingeralgorithm Ragdollphysics References[edit] ^Teschner,M.;Kimmerle,S.;Heidelberger,B.;Zachmann,G.;Raghupathi,L.;Fuhrmann,A.;Cani,M.-P.;Faure,F.;Magnenat-Thalmann,N.;Strasser,W.;Volino,P.(2005)."CollisionDetectionforDeformableObjects".ComputerGraphicsForum.24:61–81.doi:10.1111/j.1467-8659.2005.00829.x.S2CID 1359430. ^ Jaume,J;Galli,R;Mas,R;Mascaro-Oliver,M(1995)(1995)."Real-timeCollisionCheckingfor3DObjectPositioninginSparseEnvironments".ImageProcessingforBroadcastandVideoProduction.WorkshopsinComputing.ImageProcessingforBroadcastandVideoProduction;Springer-Verlag.pp. 216–225.doi:10.1007/978-1-4471-3035-2_18.ISBN 978-3-540-19947-2.{{citebook}}:CS1maint:multiplenames:authorslist(link) ^Lin,MingC(1993)."EfficientCollisionDetectionforAnimationandRobotics(thesis)"(PDF).UniversityofCalifornia,Berkeley.Archivedfromtheoriginal(PDF)on2014-07-28. ^Caldwell,DouglasR.(2005-08-29)."UnlockingtheMysteriesoftheBoundingBox".USArmyEngineerResearch&DevelopmentCenter,TopographicEngineeringCenter,ResearchDivision,InformationGenerationandManagementBranch.Archivedfromtheoriginalon2012-07-28.Retrieved2014-05-13. ^"ComponentsoftheAmiga:TheMC68000andtheAmigaCustomChips"(Referencemanual)(2.1 ed.).Chapter1.Archivedfromtheoriginalon2018-07-17.Retrieved2018-07-17.Additionally,youcanusesystemhardwaretodetectcollisionsbetweenobjectsandhaveyourprogramreacttosuchcollisions. ^"Hitbox".ValveDeveloperCommunity.Valve.Retrieved18September2011. Externallinks[edit] UniversityofNorthCarolinaatChapelHillcollisiondetectionresearchwebsite Prof.StevenCameron(OxfordUniversity)websiteoncollisiondetection HowtoAvoidaCollisionbyGeorgeBeck,WolframDemonstrationsProject. Boundingboxesandtheirusage SeparatingAxisTheorem Unity3dCollison GodotPhysicsCollison Authoritycontrol:Nationallibraries UnitedStates Retrievedfrom"https://en.wikipedia.org/w/index.php?title=Collision_detection&oldid=1095435735" Categories:ComputationalgeometryComputergraphicsVideogamedevelopmentRoboticsComputerphysicsenginesHiddencategories:CS1maint:multiplenames:authorslistArticleswithshortdescriptionShortdescriptionmatchesWikidataWikipediaarticleswithstyleissuesfromAugust2014AllarticleswithstyleissuesWikipediaarticleswithstyleissuesfromMarch2020WikipediaarticleswithstyleissuesfromJuly2018WikipediaarticlesthataretootechnicalfromMarch2020AllarticlesthataretootechnicalAllarticleswithunsourcedstatementsArticleswithunsourcedstatementsfromJune2008ArticleswithunsourcedstatementsfromAugust2014AllarticleslackingreliablereferencesArticleslackingreliablereferencesfromMarch2018ArticleswithLCCNidentifiers Navigationmenu Personaltools NotloggedinTalkContributionsCreateaccountLogin Namespaces ArticleTalk English Views ReadEditViewhistory More Search Navigation MainpageContentsCurrenteventsRandomarticleAboutWikipediaContactusDonate Contribute HelpLearntoeditCommunityportalRecentchangesUploadfile Tools WhatlinkshereRelatedchangesUploadfileSpecialpagesPermanentlinkPageinformationCitethispageWikidataitem Print/export DownloadasPDFPrintableversion Languages ČeštinaDeutschEspañolFrançais日本語NorskbokmålPolskiPortuguêsРусскийSimpleEnglishไทยУкраїнська粵語中文 Editlinks