Simple AABB vs AABB collision detection - Studio Freya

What is AABB? An AABB is an axis aligned bounding box. AABB vs AABB is a box vs box or bounding box collision detection. Home>PhysicsandMath>SimpleAABBvsAABBcollisiondetection SimpleAABBvsAABBcollisiondetection ByKent,lastupdatedNovember28,2019 WhatisAABB?AnAABBisanaxisalignedboundingbox.AABBvsAABBisaboxvsboxorboundingboxcollisiondetection.It’smainlyusedinbroadphasephysicsdetection. AssumethatacenterpointandhalfwidthextentsorradiusarethebasicpropertiesofanAABB(thereareseveralmethodstorepresentAABBstructure). ThisisaC++codeexampleforAABBstructure: structAABB { AABB():c(),r(){} AABB(constPoint&center,constPoint&halfwidths) :c(center) ,r(halfwidths) {} Pointc;//centerpoint Pointr;//halfwidths }; Theboundingbox(AABB)structureusesaPointclassstructure.HereisaC++Pointclassexampleimplementation: structPoint { Point(){} Point(doublex,doubley,doublez) :x(x) ,y(y) ,z(z) {} doublex=0.0; doubley=0.0; doublez=0.0; doublew=0.0; constdoubleoperator[](constintidx)const { if(idx==0)returnx; if(idx==1)returny; if(idx==2)returnz; if(idx==3)returnw; assert(0); } }; NowwecanwriteaboundingboxcollisiondetectionexampleinC++.Weuseatesttocheckifthereisanoverlapbetweentheboundingboxes. doubleAbs(doublea) { returnstd::fabs(a); } booltestAABBAABB(constAABB&a,constAABB&b) { if(Abs(a.c[0]-b.c[0])>(a.r[0]+b.r[0]))returnfalse; if(Abs(a.c[1]-b.c[1])>(a.r[1]+b.r[1]))returnfalse; if(Abs(a.c[2]-b.c[2])>(a.r[2]+b.r[2]))returnfalse; //Wehaveanoverlap returntrue; }; Readalso:SimpleSphere-Spherecollisiondetection Update: Thereisadiscussioninthecommentsaboutthevalidityofthistest.Therewasacoupleofissuesraised. OnlydiagonallyoffsetAABBswillpassthetest Therewasatypointhetestmakingitnotcompilable,anditcouldhavebeenmisleading.Thelastparenthesisintheif-sentenceswheremissing.Thiscouldhaveledonetobelieveallaxesmustpassthetest.Thatisnottrue.Ifoneaxisisnotintersecting,bothAABBsaren’tintersectingatall.Allaxesmustoverlaptohaveanactualoverlap. Mustaccountforfloatingpointprecisionerrors Thereisnoneedtotakefloatingpointprecisionerrorsintoaccountwhenyou’renotcomparingwithequals(operator==).Whenyou’reusinglarger-thanorlesser-thanoperators,you’llonlyshifttheerrorbywhatevervalueyouchooseforyouepsilon. Readalso:SpherevsAABBcollisiondetection Incornercases,whereaxisalignedboundingboxesarealignednexttoeachother,youasaprogrammerhavetodecidethedesiredoutcome.Whereyou’resimulatingphysicswithmovingboundingboxes,thoseerrorsarenegligible.Theonlyconsequenceistohaveapositivetestin“thisframe”orthe“nextframe”. I’vealsomadesometests,basedonthethreeversions(1inthearticle,2inthecomments).Thesourcecodeisavailableathttps://github.com/Studiofreya/code-samples/tree/master/physics. Theresultsfromthetestare: AABB1:AABBcenter(000)halfs(0.50.50.5) AABB2:AABBcenter(000)halfs(0.50.50.5) Postresult1 Anonresult1 CJMresult1 AABB1:AABBcenter(000)halfs(0.50.50.5) AABB2:AABBcenter(100)halfs(0.50.50.5) Postresult1 Anonresult1 CJMresult1 AABB1:AABBcenter(000)halfs(0.50.50.5) AABB2:AABBcenter(1.500)halfs(0.50.50.5) Postresult0 Anonresult1 CJMresult0 AABB1:AABBcenter(000)halfs(0.50.50.5) AABB2:AABBcenter(1500)halfs(0.50.50.5) Postresult0 Anonresult1 CJMresult0 AABB1:AABBcenter(100)halfs(0.50.50.5) AABB2:AABBcenter(100)halfs(0.50.50.5) Postresult1 Anonresult1 CJMresult1 AABB1:AABBcenter(100)halfs(0.50.50.5) AABB2:AABBcenter(1.500)halfs(0.50.50.5) Postresult1 Anonresult1 CJMresult1 AABB1:AABBcenter(100)halfs(0.50.50.5) AABB2:AABBcenter(1500)halfs(0.50.50.5) Postresult0 Anonresult1 CJMresult0 AABB1:AABBcenter(1.500)halfs(0.50.50.5) AABB2:AABBcenter(1.500)halfs(0.50.50.5) Postresult1 Anonresult1 CJMresult1 AABB1:AABBcenter(1.500)halfs(0.50.50.5) AABB2:AABBcenter(1500)halfs(0.50.50.5) Postresult0 Anonresult1 CJMresult0 AABB1:AABBcenter(000)halfs(0.50.50.5) AABB2:AABBcenter(01.50)halfs(0.50.50.5) Postresult0 Anonresult1 CJMresult0 AABB1:AABBcenter(000)halfs(0.50.50.5) AABB2:AABBcenter(02.50)halfs(0.50.50.5) Postresult0 Anonresult1 CJMresult0 AABB1:AABBcenter(000)halfs(0.50.50.5) AABB2:AABBcenter(03.50)halfs(0.50.50.5) Postresult0 Anonresult1 CJMresult0 AABB1:AABBcenter(000)halfs(0.50.50.5) AABB2:AABBcenter(151515)halfs(0.50.50.5) Postresult0 Anonresult0 CJMresult0 ThepostandCJhaveidenticalresults.DonotuseAnonstest. Bonus HereisaSIMD-optimiziedtest,removingtheconditionalbranches. booltestAABBAABB_SIMD(constAABB&a,constAABB&b) { //SIMDoptimizedAABB-AABBtest //Optimizedbyremovingconditionalbranches boolx=Abs(a.c[0]-b.c[0])<=(a.r[0]+b.r[0]); booly=Abs(a.c[1]-b.c[1])<=(a.r[1]+b.r[1]); boolz=Abs(a.c[2]-b.c[2])<=(a.r[2]+b.r[2]); returnx&&y&&z; } Resources: SimpleAABBvsAABBcollisiondetectionwaslastmodified:November28th,2019byKent Relatedposts:  SpherevsAABBcollisiondetectiontest Basicprimitives SimpleSphere-SphereCollisionDetectionandCollisionResponse Distancefrompointtoplaneimplementation AdvancedSphere-SphereContinuousCollisionDetection(CCD) Kent ProfessionalSoftwareDeveloper,doingmostlyC++.ConnectwithKentonTwitter. Comments BlazeX January7,2011LeaveaReply Whatisthe“floatt;”for?Youneverusethisvar. kent January7,2011LeaveaReply Itcanbesafelyremoved. It’sprobablysomeleftoversfromtryingtodocontinuouscollisiondetection(CCD). geekygenius May17,2012LeaveaReply Isiscommontooptimizethisbychangingaroundtheorderoftheaxis’sbeingchecked?Like,checkZYXinsteadofXYZifitmakesmoresenseinaparticularplatform? kent May17,2012LeaveaReply IfyouknowthereisabiggerchanceofoverlaponZ,thenyoucancheckZfirst. ButI’dsaythereisabiggerbenefitoftestingintheorderdataisstructured,becauseofcodereadabilityandCPUpipelining. Anonymous January28,2013LeaveaReply Shouldbe: if(Abs(a.c[0]–b.c[0])>(a.r[0]+b.r[0]){ if(Abs(a.c[1]–b.c[1])>(a.r[1]+b.r[1]){ if(Abs(a.c[2]–b.c[2])>(a.r[2]+b.r[2]){ returnfalse; } } } otherwiseitwillreturnfalsewhenevertheobjectisalignedonanyoftheaxis,sotheonlytimeitwillreturntrueiswhentheobjectaisdiagonallyoffsetfromobjectb.Herewearejustcheckingtomakesurethatitistouchingonalloftheaxis. CJ March17,2014LeaveaReply THISALGORITHMWILLNOTWORK. It’sdisappointingthatmanywillbemisleadbythis“solution,”sinceGoogleputsthisverynearthetopofAABBoverlap-detectionsearches. ThemostobviouserrorispartiallycorrectedbyAnonymous,inthatonlyadiagonally-offsetAABBonall3axeswillbeconsideredamiss.However,hissuggestionisincomplete,asyoumustcheckallaxesINDEPENDENTLY.Amoreaccurateanswerwouldbethefollowing: boolxOverlap=true; boolyOverlap=true; boolzOverlap=true; boolanyOverlap=false; if(Abs(a.c[0]–b.c[0])>(a.r[0]+b.r[0]))xOverlap=false; if(Abs(a.c[1]–b.c[1])>(a.r[1]+b.r[1]))yOverlap=false; if(Abs(a.c[2]–b.c[2])>(a.r[2]+b.r[2]))zOverlap=false; anyOverlap=xOverlap&&yOverlap&&zOverlap; returnanyOverlap; TheaboveANDstogethertheresultsofthe3axes’overlaptests,andwillonlyreturn“true”ifALLTHREEtestsfail,indicatingthatoverlapscannotberuledoutonanyaxes.Justtoclarify,inorderforanoverlaptooccur,theAABBofAmustbebreachedbyB,andthisscenariorequiresoverlappingALLTHREEaxes,otherwiseitwouldhavemissedinsomedimension. However,westilldonothaveacompletesolution,thankstothelovely“gotchas”offloatingpointarithmetic.Aworkaroundwouldbetouseintegersforourcoordinates,butthiswouldplaceamorestringentupper-limitoncoordinatesthanfloatsordoubles,andalsocomplicatephysicscalculations.So,stickingwithfloatingpointnumbersforourcoordinatesystemrequiresustoaccountfortheirfundamentalimprecision.ItisextremelyunlikelythatanytwofloatscanbesubtractedtoequalEXACTLY0.Althoughyoumayhaveinitializedthembothto1.4,theyarenotrepresentedasexactly1.4internally,they’reprobablysomethinglike1.4000000023and1.4000000017.Subtractingthesenumberswillobviouslyyieldanonzeroresult.Therefore,toaccountforthis,youmustdefinemarginsoferror.YouthenconsiderAABBstobeoverlappingiftheirboundsarewithinthismarginoferrorofeachotheronagivenaxis. Ihavetogodoimportantthingsnow,soI’llleavethefinal,completesolutiontothenextpoorsap. kent March19,2014LeaveaReply HiCJ, Thankyoufortakingyourtimetorespond! I’llreviewthispostandupdateit. Kent CJ March19,2014LeaveaReply Awesome! Ithoughtmypostwasdoomedtoobscurity,sincetheOPwasover4yearsold.Thanksman! kent July4,2014LeaveaReply HiCJ, Ittooksometime,butI’veupdatedthepostwithmoreinformationanddiscussionaboutthetests. ben August12,2015LeaveaReply Hey, I’mtryingtounderstandhowthisworksandwasjustwonderingwhatthehalf-widthis. Thanksisadvance. kent August13,2015LeaveaReply HiBen, Thehalf-widthisjusthalfthelengthofeachsidestoredinaPoint. Thinkofitasfromacenterpointinthebox,havingthehalf-widthsasaPoint,it’sthelengthtoeitherofthesides. Sogomn August17,2015LeaveaReply Thisdoesn’tworkwhentheAABBisrotated,doesit? kent August25,2015LeaveaReply Hi,AABBisanacronymforAxisAlignedBoundingBox. Thatmeanstheboxisfixedtotheaxes,thusnorotation. Marc June5,2017LeaveaReply Pleasenotethatthistestdoesnotworktoknowifaboxisinsideanotherbox. LeaveaReplyCancelreplyCommentYoumayusetheseHTMLtagsandattributes:Name* Email* Website Studiofreya WhatWeDo Support    Copyright@2012-2019