Bounding volume - Wikipedia

In computer graphics and computational geometry, a bounding volume for a set of objects is a closed volume that completely contains the union of the objects ... Boundingvolume FromWikipedia,thefreeencyclopedia Jumptonavigation Jumptosearch Cosedvolumethatcompletelycontainstheunionofasetofobjects A3Dmodelwithitsboundingboxdrawnindashedlines. Forbuildingcodecompliance,seeBounding. Incomputergraphicsandcomputationalgeometry,aboundingvolumeforasetofobjectsisaclosedvolumethatcompletelycontainstheunionoftheobjectsintheset.Boundingvolumesareusedtoimprovetheefficiencyofgeometricaloperationsbyusingsimplevolumestocontainmorecomplexobjects.Normally,simplervolumeshavesimplerwaystotestforoverlap. Aboundingvolumeforasetofobjectsisalsoaboundingvolumeforthesingleobjectconsistingoftheirunion,andtheotherwayaround.Therefore,itispossibletoconfinethedescriptiontothecaseofasingleobject,whichisassumedtobenon-emptyandbounded(finite). Contents 1Uses 2Commontypes 3Basicintersectionchecks 4Seealso 5References 6Externallinks Uses[edit] Boundingvolumesaremostoftenusedtoacceleratecertainkindsoftests. Inraytracing,boundingvolumesareusedinray-intersectiontests,andinmanyrenderingalgorithms,theyareusedforviewingfrustumtests.Iftherayorviewingfrustumdoesnotintersecttheboundingvolume,itcannotintersecttheobjectcontainedwithin,allowingtrivialrejection.Similarlyifthefrustumcontainstheentiretyoftheboundingvolume,thecontentsmaybetriviallyacceptedwithoutfurthertests.Theseintersectiontestsproducealistofobjectsthatmustbe'displayed'(rendered;rasterized). Incollisiondetection,whentwoboundingvolumesdonotintersect,thecontainedobjectscannotcollide. Testingagainstaboundingvolumeistypicallymuchfasterthantestingagainsttheobjectitself,becauseoftheboundingvolume'ssimplergeometry.Thisisbecausean'object'istypicallycomposedofpolygonsordatastructuresthatarereducedtopolygonalapproximations.Ineithercase,itiscomputationallywastefultotesteachpolygonagainsttheviewvolumeiftheobjectisnotvisible.(Onscreenobjectsmustbe'clipped'tothescreen,regardlessofwhethertheirsurfacesareactuallyvisible.) Toobtainboundingvolumesofcomplexobjects,acommonwayistobreaktheobjects/scenedownusingascenegraphormorespecificallyaboundingvolumehierarchy,likee.g.OBBtrees.Thebasicideabehindthisistoorganizeasceneinatree-likestructurewheretherootcomprisesthewholesceneandeachleafcontainsasmallersubpart.[citationneeded] Incomputerstereovision,aboundingvolumereconstructedfromsilhouettesofanobjectisknownasa"visualhull."[1] Commontypes[edit] Thechoiceofthetypeofboundingvolumeforagivenapplicationisdeterminedbyavarietyoffactors:thecomputationalcostofcomputingaboundingvolumeforanobject,thecostofupdatingitinapplicationsinwhichtheobjectscanmoveorchangeshapeorsize,thecostofdeterminingintersections,andthedesiredprecisionoftheintersectiontest.Theprecisionoftheintersectiontestisrelatedtotheamountofspacewithintheboundingvolumenotassociatedwiththeboundedobject,calledvoidspace.Sophisticatedboundingvolumesgenerallyallowforlessvoidspacebutaremorecomputationallyexpensive.Itiscommontouseseveraltypesinconjunction,suchasacheaponeforaquickbutroughtestinconjunctionwithamoreprecisebutalsomoreexpensivetype. Thetypestreatedhereallgiveconvexboundingvolumes.Iftheobjectbeingboundedisknowntobeconvex,thisisnotarestriction.Ifnon-convexboundingvolumesarerequired,anapproachistorepresentthemasaunionofanumberofconvexboundingvolumes.Unfortunately,intersectiontestsbecomequicklymoreexpensiveastheboundingboxesbecomemoresophisticated. Aboundingboxisacuboid,orin2-Darectangle,containingtheobject.Indynamicalsimulation,boundingboxesarepreferredtoothershapesofboundingvolumesuchasboundingspheresorcylindersforobjectsthatareroughlycuboidinshapewhentheintersectiontestneedstobefairlyaccurate.Thebenefitisobvious,forexample,forobjectsthatrestuponother,suchasacarrestingontheground:aboundingspherewouldshowthecaraspossiblyintersectingwiththeground,whichthenwouldneedtoberejectedbyamoreexpensivetestoftheactualmodelofthecar;aboundingboximmediatelyshowsthecarasnotintersectingwiththeground,savingthemoreexpensivetest. Inmanyapplicationstheboundingboxisalignedwiththeaxesoftheco-ordinatesystem,anditisthenknownasanaxis-alignedboundingbox(AABB).TodistinguishthegeneralcasefromanAABB,anarbitraryboundingboxissometimescalledanorientedboundingbox(OBB),oranOOBBwhenanexistingobject'slocalcoordinatesystemisused.AABBsaremuchsimplertotestforintersectionthanOBBs,buthavethedisadvantagethatwhenthemodelisrotatedtheycannotbesimplyrotatedwithit,butneedtoberecomputed. Aboundingcapsuleisasweptsphere(i.e.thevolumethataspheretakesasitmovesalongastraightlinesegment)containingtheobject.Capsulescanberepresentedbytheradiusofthesweptsphereandthesegmentthatthesphereissweptacross).Ithastraitssimilartoacylinder,butiseasiertouse,becausetheintersectiontestissimpler.Acapsuleandanotherobjectintersectifthedistancebetweenthecapsule'sdefiningsegmentandsomefeatureoftheotherobjectissmallerthanthecapsule'sradius.Forexample,twocapsulesintersectifthedistancebetweenthecapsules'segmentsissmallerthanthesumoftheirradii.Thisholdsforarbitrarilyrotatedcapsules,whichiswhythey'remoreappealingthancylindersinpractice. Aboundingcylinderisacylindercontainingtheobject.Inmostapplicationstheaxisofthecylinderisalignedwiththeverticaldirectionofthescene.Cylindersareappropriatefor3-Dobjectsthatcanonlyrotateaboutaverticalaxisbutnotaboutotheraxes,andareotherwiseconstrainedtomovebytranslationonly.Twovertical-axis-alignedcylindersintersectwhen,simultaneously,theirprojectionsontheverticalaxisintersect–whicharetwolinesegments–aswelltheirprojectionsonthehorizontalplane–twocirculardisks.Bothareeasytotest.Invideogames,boundingcylindersareoftenusedasboundingvolumesforpeoplestandingupright. Aboundingellipsoidisanellipsoidcontainingtheobject.Ellipsoidsusuallyprovidetighterfittingthanasphere.Intersectionswithellipsoidsaredonebyscalingtheotherobjectalongtheprincipalaxesoftheellipsoidbyanamountequaltothemultiplicativeinverseoftheradiioftheellipsoid,thusreducingtheproblemtointersectingthescaledobjectwithaunitsphere.Careshouldbetakentoavoidproblemsiftheappliedscalingintroducesskew.Skewcanmaketheusageofellipsoidsimpracticalincertaincases,forexamplecollisionbetweentwoarbitraryellipsoids. Aboundingsphereisaspherecontainingtheobject.In2-Dgraphics,thisisacircle.Boundingspheresarerepresentedbycentreandradius.Theyareveryquicktotestforcollisionwitheachother:twospheresintersectwhenthedistancebetweentheircentresdoesnotexceedthesumoftheirradii.Thismakesboundingspheresappropriateforobjectsthatcanmoveinanynumberofdimensions. Aboundingslabisthevolumethatprojectstoanextentonanaxis,andcanbethoughtofastheslabboundedbetweentwoplanes.Aboundingboxistheintersectionoforthogonallyorientedboundingslabs.Boundingslabshavebeenusedtospeedupraytracing[2] Aboundingtrianglein2-DisquiteusefultospeeduptheclippingorvisibilitytestofaB-Splinecurve.See"CircleandB-Splinesclippingalgorithms"underthesubjectClipping(computergraphics)foranexampleofuse. Aconvexhullisthesmallestconvexvolumecontainingtheobject.Iftheobjectistheunionofafinitesetofpoints,itsconvexhullisapolytope. Adiscreteorientedpolytope(DOP)generalizestheboundingbox.Ak-DOPistheBooleanintersectionofextentsalongkdirections.Thus,ak-DOPistheBooleanintersectionofkboundingslabsandisaconvexpolytopecontainingtheobject(in2-Dapolygon;in3-Dapolyhedron).A2-Drectangleisaspecialcaseofa2-DOP,anda3-Dboxisaspecialcaseofa3-DOP.Ingeneral,theaxesofaDOPdonothavetobeorthogonal,andtherecanbemoreaxesthandimensionsofspace.Forexample,a3-Dboxthatisbeveledonalledgesandcornerscanbeconstructedasa13-DOP.Theactualnumberoffacescanbelessthan2timeskifsomefacesbecomedegenerate,shrunktoanedgeoravertex. AminimumboundingrectangleorMBR–theleastAABBin2-D–isfrequentlyusedinthedescriptionofgeographic(or"geospatial")dataitems,servingasasimplifiedproxyforadataset'sspatialextent(seegeospatialmetadata)forthepurposeofdatasearch(includingspatialqueriesasapplicable)anddisplay.ItisalsoabasiccomponentoftheR-treemethodofspatialindexing. Basicintersectionchecks[edit] Forsometypesofboundingvolume(OBBandconvexpolyhedra),aneffectivecheckisthatoftheseparatingaxistheorem.Theideahereisthat,ifthereexistsanaxisbywhichtheobjectsdonotoverlap,thentheobjectsdonotintersect.Usuallytheaxescheckedarethoseofthebasicaxesforthevolumes(theunitaxesinthecaseofanAABB,orthe3baseaxesfromeachOBBinthecaseofOBBs).Often,thisisfollowedbyalsocheckingthecross-productsofthepreviousaxes(oneaxisfromeachobject). InthecaseofanAABB,thistestsbecomesasimplesetofoverlaptestsintermsoftheunitaxes.ForanAABBdefinedbyM,NagainstonedefinedbyO,Ptheydonotintersectif (Mx > Px)or(Ox > Nx)or(My > Py)or(Oy > Ny)or(Mz > Pz)or(Oz > Nz). AnAABBcanalsobeprojectedalonganaxis,forexample,ifithasedgesoflengthLandiscenteredatC,andisbeingprojectedalongtheaxisN: r = 0.5 L x | N x | + 0.5 L y | N y | + 0.5 L z | N z | {\displaystyler=0.5L_{x}|N_{x}|+0.5L_{y}|N_{y}|+0.5L_{z}|N_{z}|\,} ,and b = C ∗ N {\displaystyleb=C*N\,} or b = C x N x + C y N y + C z N z {\displaystyleb=C_{x}N_{x}+C_{y}N_{y}+C_{z}N_{z}\,} ,and m = b − r , n = b + r {\displaystylem=b-r,n=b+r\,} wheremandnaretheminimumandmaximumextents. AnOBBissimilarinthisrespect,butisslightlymorecomplicated.ForanOBBwithLandCasabove,andwithI,J,andKastheOBB'sbaseaxes,then: r = 0.5 L x | N ∗ I | + 0.5 L y | N ∗ J | + 0.5 L z | N ∗ K | {\displaystyler=0.5L_{x}|N*I|+0.5L_{y}|N*J|+0.5L_{z}|N*K|\,} m = C ∗ N − r  and  n = C ∗ N + r {\displaystylem=C*N-r{\mbox{and}}n=C*N+r\,} Fortherangesm,nando,pitcanbesaidthattheydonotintersectifm > poro > n.Thus,byprojectingtherangesof2OBBsalongtheI,J,andKaxesofeachOBB,andcheckingfornon-intersection,itispossibletodetectnon-intersection.Byadditionallycheckingalongthecrossproductsoftheseaxes(I0×I1,I0×J1,...)onecanbemorecertainthatintersectionisimpossible. Thisconceptofdeterminingnon-intersectionviauseofaxisprojectionalsoextendstoconvexpolyhedra,howeverwiththenormalsofeachpolyhedralfacebeingusedinsteadofthebaseaxes,andwiththeextentsbeingbasedontheminimumandmaximumdotproductsofeachvertexagainsttheaxes.Notethatthisdescriptionassumesthechecksarebeingdoneinworldspace. Theintersectionoftwok-DOP'scanbecomputedverysimilarlytoAABBs:foreachorientation,youjustcheckthetwocorrespondingintervalsofthetwoDOP's.So,justlikeDOP'sbeingageneralizationofAABBs,theintersectiontestisageneralizationoftheAABBoverlaptest.ThecomplexityoftheoverlaptestoftwoDOP'sisinO(k).Thisassumes,however,thatbothDOP'saregivenwithrespecttothesamesetoforientations.Ifoneofthemisrotated,thisisnolongertrue.Inthatcase,onerelativelyeasywaytocheckthetwoDOP's D 1 , D 2 {\displaystyleD^{1},D^{2}} forintersectionistoenclosetherotatedone, D 2 {\displaystyleD^{2}} ,byanother,smallestenclosingDOP D ~ 2 {\displaystyle{\tilde{D}}^{2}} thatisorientedwithrespecttotheorientationsofthefirstDOP D 1 {\displaystyleD^{1}} .Theprocedureforthatisalittlebitmorecomplex,buteventuallyamountstoamatrixvectormultiplicationofcomplexityO(k)aswell.[3] Seealso[edit] Boundingsphere Convexhullalgorithms Minimumboundingbox Minimumboundingrectangle Spatialindex References[edit] ^Erol,Ali,etal."VisualHullConstructionUsingAdaptiveSampling."WACV/MOTION.2005. ^ POV-RayDocumentation[1] ^G.Zachmann:RapidCollisionDetectionbyDynamicallyAlignedDOP-Trees.Proc.ofIEEEVirtualRealityAnnualInternationalSymposium(VRAIS,nowIEEEVR),1998,pp.90-97,DOI10.1109/VRAIS.1998.658428,ISBN 0-8186-8362-7URL:http://cgvr.informatik.uni-bremen.de/papers/vrais98/vrais98.pdf Externallinks[edit] IllustrationofseveralDOPsforthesamemodel,fromepicgames.com Retrievedfrom"https://en.wikipedia.org/w/index.php?title=Bounding_volume&oldid=1079574948" Categories:Geometricalgorithms3DcomputergraphicsHiddencategories:ArticleswithshortdescriptionShortdescriptionisdifferentfromWikidataAllarticleswithunsourcedstatementsArticleswithunsourcedstatementsfromOctober2021 Navigationmenu Personaltools NotloggedinTalkContributionsCreateaccountLogin Namespaces ArticleTalk English Views ReadEditViewhistory More Search Navigation MainpageContentsCurrenteventsRandomarticleAboutWikipediaContactusDonate Contribute HelpLearntoeditCommunityportalRecentchangesUploadfile Tools WhatlinkshereRelatedchangesUploadfileSpecialpagesPermanentlinkPageinformationCitethispageWikidataitem Print/export DownloadasPDFPrintableversion Languages DeutschFrançaisမြန်မာဘာသာPolskiTürkçeУкраїнська中文 Editlinks