The Broadphase

Post Reply
User avatar
KKlouzal
Posts: 65
Joined: Thu Mar 06, 2014 5:56 am
Location: USA - Arizona

The Broadphase

Post by KKlouzal »

I'm looking for some more detailed information about the btDbvtBroadphase.

It is to my understanding that the broadphases purpose is to group individual objects into small lists based on how likely they are to collide. Could someone give a more detailed explanation about this?

If my assumption of the broadphase creating multiple smaller lists is correct the following questions arise:

Will every object in the simulation eventually get put in a list during broadphase, in other words are no objects left out?
Is it possible to retrieve these lists and if so is each list assigned an AABB in world-space-coordinates?
Basroil
Posts: 463
Joined: Fri Nov 30, 2012 4:50 am

Re: The Broadphase

Post by Basroil »

I could be wrong, but from my cursory reading of the code the broadphase selects overlapping pairs of objects based on a tree search and adds those "hits" to a list of overlapping pairs.

Rather than a greyscale "how likely they are to collide", it is more of a black or white "might already be colliding".

In DBVT, everything that can collide should be included in the tree by the time it's formed. Unfortunately, it's pretty hard to read the code (very recursive structure and I don't have that much paper on me), but the general method in bounded volume trees (from blender documentation, bullet could always be different) is to group smaller volumes into larger volumes and and search up and across the tree for what you want (data nodes that are overlapping). So there aren't really any lists you query, but all the AABB data should be there for every object. Finding the object you want (in terms of general spatial location) should be as easy as any binary search tree (but data is only on leaves rather than the branches along the way)
User avatar
KKlouzal
Posts: 65
Joined: Thu Mar 06, 2014 5:56 am
Location: USA - Arizona

Re: The Broadphase

Post by KKlouzal »

Thank you, I appreciate your help Basroli.

What I've been able to gather is eventually all objects that can collide will end up in the tree, hopefully this means that no objects in the simulation are left out of the tree, unless of course maybe idle objects. It also sounds like it is possible to search the tree based on world coordinates which is very good.

Essentially what I need to do is get 'clusters' of objects that are likely to collide, for example if we have two piles of cubes separated by some arbitrary distance I would be able to query the tree to get these two 'clusters' of objects and process them.

Even if the tree only includes objects whose AABB are already overlapping this might still be workable for my needs.

I've been looking at the API and can't make hide-nor-hair of the btDbvtBroadphase page. http://bulletphysics.org/Bullet/BulletF ... phase.html

Does anyone know if this is possible using the tree created during broadphase or using any other aspect of bullet that might gather this type of information?
xexuxjy
Posts: 225
Joined: Wed Jan 07, 2009 11:43 am
Location: London

Re: The Broadphase

Post by xexuxjy »

The btDbvtBroadphase (and all the other broadphases) just allow you do do simple queries do find out which objects are in a given area based on their aabb, they also provide a mechanism of generating possible overlapping pairs for the dispatcher.
From what I remember , you might be better looking at the SimulationIslandManager as I think that groups together all potentially touching objects , so if A touches B and B touches C you should see that relationship in there even if the aabb's for A and C don't overlap.
User avatar
KKlouzal
Posts: 65
Joined: Thu Mar 06, 2014 5:56 am
Location: USA - Arizona

Re: The Broadphase

Post by KKlouzal »

Thank you xexuxjy. My original thought was to look into Simulation Island's and see if that mechanism could give me the data I'm looking for however I read in a few very old topics that they are only used for objects that have gone into their sleep state.

More information about Simulation Island's and/or the Broad Phase from any experienced user would be greatly appreciated.

Thank you everyone for your time.
Basroil
Posts: 463
Joined: Fri Nov 30, 2012 4:50 am

Re: The Broadphase

Post by Basroil »

KKlouzal wrote: Essentially what I need to do is get 'clusters' of objects that are likely to collide, for example if we have two piles of cubes separated by some arbitrary distance I would be able to query the tree to get these two 'clusters' of objects and process them.
.
.
.
.
More information about Simulation Island's and/or the Broad Phase from any experienced user would be greatly appreciated.
From the island manager code, islands are basically joined from the bottom up, much like traversing the broadphase tree backwards and finding chained objects. It'll get you the clusters as long as the minimum island size it set to 1 (only objects in broadphase range will be in the group). I highly suggest taking a look at btSimulationIslandsManager, it has great commenting and might just be what you were looking for.
Post Reply