Iterate over objects ina bounding box?
-
- Posts: 13
- Joined: Tue Jul 08, 2008 6:06 am
Iterate over objects ina bounding box?
Hello all-
Suppose I have a large number of objects in a world.
If I have a small axis-aligned bounding box (AABB), is there a quick (efficient) way to iterate over all objects within (or potentially within) that AABB?
I'm hoping that the internal space partitioning that Bullet uses means that iterating over all objects within an AABB is faster than iterating over all the objects in the world. That is, something like log(N) performance.
Or is my best bet to iterate over all objects and see if they intersect the AABB?
-Thomas
Suppose I have a large number of objects in a world.
If I have a small axis-aligned bounding box (AABB), is there a quick (efficient) way to iterate over all objects within (or potentially within) that AABB?
I'm hoping that the internal space partitioning that Bullet uses means that iterating over all objects within an AABB is faster than iterating over all the objects in the world. That is, something like log(N) performance.
Or is my best bet to iterate over all objects and see if they intersect the AABB?
-Thomas
-
- Posts: 10
- Joined: Wed Jul 29, 2009 4:04 am
- Location: Seoul, Korea
Re: Iterate over objects ina bounding box?
Hi,
It seems that there's no direct AABB checking API (Correct me if I'm wrong). So I'm using btGhostObject to iterate over all objects within ghost's shape at every simulation step. For AABB only, you can remove iteration code related to narrowphase and manifold iteration.
With a ghost object you can iterate something like this:
This is similar to wiki page describing btGhostObject, except that broadphase with AABB takes place only, which means other than the broadphase pair caching (the thing you point as 'internal space partitioning'), there's no additional calculations.
Note that a ghost object should be added to world prior, but simulationStep() may need not be called. (pair caching is occurred during addCollisionObject())
In other word, one time checking possible like:
I had about 2000 objects (static, dynamic) and 20~30 ghosts. In my case, it was a lot faster using this than checking every object in world.
(One thing to care about is that I had to carefully adjust collision group and filter to speed up even further.)
Thanks
It seems that there's no direct AABB checking API (Correct me if I'm wrong). So I'm using btGhostObject to iterate over all objects within ghost's shape at every simulation step. For AABB only, you can remove iteration code related to narrowphase and manifold iteration.
With a ghost object you can iterate something like this:
Code: Select all
void OverlapAABB(btPairCachingGhostObject* ghost, std::vector<btCollisionObject*>& results)
{
btBroadphasePairArray& pairs = ghost->getOverlappingPairCache()->getOverlappingPairArray();
for (int i=0; i<pairs.size(); ++i)
{
const btBroadphasePair& pair = pairs[i];
btBroadphaseProxy* proxy = pair.m_pProxy0->m_ClientObject != ghost ? pair.m_pProxy0 : pair.m_pProxy1;
btCollisionObject* obj = (btCollisionObject*)proxy->m_clientObject;
// Now you have one object. Do something here
results.push_back(obj); // <-- this is just an example.
}
}
Note that a ghost object should be added to world prior, but simulationStep() may need not be called. (pair caching is occurred during addCollisionObject())
In other word, one time checking possible like:
Code: Select all
world->addCollisionObject(ghost);
OverlapAABB(ghost, results);
world->removeCollisionObject(ghost);
(One thing to care about is that I had to carefully adjust collision group and filter to speed up even further.)
Thanks
-
- Posts: 456
- Joined: Tue Dec 25, 2007 1:06 pm
Re: Iterate over objects ina bounding box?
Thank you very much for your clean explanation (I'm trying to know more about btGhostObjects).
I got just one more question. Currently I'm using a simpler code, like this:
This code works for the base btGhostObject class too.
So, the difference between my code and yours (that needs a btPairCachingGhostObject) is that in mine the objects intersect the ghost with their AABB and in yours with their "real" shape ? Is this correct ?
Thank you in advance.
P.S. Adding and removing ghost objects "in place" seems very useful. Thank you for telling us.
I got just one more question. Currently I'm using a simpler code, like this:
btAlignedObjectArray<btCollisionObject*>& overlappingObjects = m_ghostObject->getOverlappingPairs();
const int numObjects=overlappingObjects.size();
for(int i=0;i<numObjects;i++)
{
btCollisionObject* colObj=overlappingObjects;
/// Do something with colObj
}
This code works for the base btGhostObject class too.
So, the difference between my code and yours (that needs a btPairCachingGhostObject) is that in mine the objects intersect the ghost with their AABB and in yours with their "real" shape ? Is this correct ?
Thank you in advance.
P.S. Adding and removing ghost objects "in place" seems very useful. Thank you for telling us.
-
- Posts: 10
- Joined: Wed Jul 29, 2009 4:04 am
- Location: Seoul, Korea
Re: Iterate over objects ina bounding box?
Hi Flix,
There's no gain with btPairCachingGhostObject over btGhostObject on this topic (AABB only intersection). So your code is much simpler and suits better. Thank you for your concise example!
As you note, the difference is that btPairCachingGhostObject is useful when you need to know if 'real' shapes are actually colliding (not just overlapping AABB) and need to get manifold (contact) points. As far as I know, a plain btGhostObject doesn't support this feature effectively.
ADDED: My code above also does not perform actual narrowphase calculation ('real' shape collision). narrowphase is occured only when following code has been called:
the 'ghost->getOverlappingPairCache()' is the thing plain btGhostObject is missing for narrowphase. Without this call, btPairCachingGhostObject is a little bit expensive but just same with btGhostObject.
I hope this answer to your question.
Thanks
There's no gain with btPairCachingGhostObject over btGhostObject on this topic (AABB only intersection). So your code is much simpler and suits better. Thank you for your concise example!
As you note, the difference is that btPairCachingGhostObject is useful when you need to know if 'real' shapes are actually colliding (not just overlapping AABB) and need to get manifold (contact) points. As far as I know, a plain btGhostObject doesn't support this feature effectively.
ADDED: My code above also does not perform actual narrowphase calculation ('real' shape collision). narrowphase is occured only when following code has been called:
Code: Select all
world->getDispatcher()->dispatchAllCollisionPairs(ghost->getOverlappingPairCache(), world->getDispatchInfo(), world->getDispatcher());
I hope this answer to your question.
Thanks
-
- Posts: 456
- Joined: Tue Dec 25, 2007 1:06 pm
Re: Iterate over objects ina bounding box?
Ellon wrote:
So there's no gain in using btPairCachingGhostObjects without the line:
to get narrowphase calculations.
Thank you for your clarifications.
Yes, it's all much clearer to me now.I hope this answer to your question.
So there's no gain in using btPairCachingGhostObjects without the line:
Code: Select all
world->getDispatcher()->dispatchAllCollisionPairs(ghost->getOverlappingPairCache(), world->getDispatchInfo(), world->getDispatcher());
Thank you for your clarifications.
-
- Posts: 13
- Joined: Tue Jul 08, 2008 6:06 am
Re: Iterate over objects ina bounding box?
Thanks to both of you for the answers!
Using ghost objects is a very elegant solution, I'll do that.
Using ghost objects is a very elegant solution, I'll do that.
-
- Posts: 13
- Joined: Tue Jul 08, 2008 6:06 am
Re: Iterate over objects ina bounding box?
Well, I finally got a chance to implement this (find all objects in an AABB bounding box using ghost objects) and it's not working as I expected.
I created ghost objects for my AABB. In my case, these are long-lived AABB's, so I created them at the beginning and check them every simulation step.
As far as I can tell, the call:
returns the list of objects that overlap with the surface of the AABB only!
So for instance, objects contained entirely within the AABB won't be returned.
My code is very simple:
Is there a chance I've done something wrong? Is there another way to find all objects entirely contained by the AABB, and not just intersecting the surface?
I created ghost objects for my AABB. In my case, these are long-lived AABB's, so I created them at the beginning and check them every simulation step.
As far as I can tell, the call:
Code: Select all
ghostObject->getOverlappingObjects()
So for instance, objects contained entirely within the AABB won't be returned.
My code is very simple:
Code: Select all
int numObjects = ghost->getNumOverlappingObjects();
for (int i = 0; i < numObjects; ++i) {
btCollisionObject * cobj = ghost->getOverlappingObject(i);
}
-
- Site Admin
- Posts: 4221
- Joined: Sun Jun 26, 2005 6:43 pm
- Location: California, USA
Re: Iterate over objects ina bounding box?
ghostObject->getOverlappingObjects() returns ALL overlapping AABB's, including the fully embedded ones (there is no such thing as a surface AABB check in Bullet)As far as I can tell, the call:returns the list of objects that overlap with the surface of the AABB only!Code: Select all
ghostObject->getOverlappingObjects()
So for instance, objects contained entirely within the AABB won't be returned.
Please double-check the Bullet/CharacterDemo, it shows how to setup the btGhostObject.
Can you reproduce a failing case by modifying any of the existing Bullet demos?
Thanks,
Erwin
-
- Posts: 13
- Joined: Tue Jul 08, 2008 6:06 am
Re: Iterate over objects ina bounding box?
Yes! I was definitely doing something wrong. As you may have guessed, I had the wrong boundaries set up.Is there a chance I've done something wrong?
Now it is *almost* working. I've hit a strange bug: if I add the AABB ghost objects at the beginning of time, I see weird effects during the simulation. That is, having the ghost objects in the world seems to impact the simulation (?), and in particular, some collisions seem to be missed. But if I add and remove the AABB objects only when I perform AABB containment testing, the simulation works fine.
Any ideas on that? For now I'll just go with adding and removing the ghost objects as necessary. And that works perfectly.
Thanks again for the suggestions.
-
- Posts: 456
- Joined: Tue Dec 25, 2007 1:06 pm
Re: Iterate over objects ina bounding box?
tomva wrote:
Here is how I created it:
P.S. If you want to see my full code, I've posted a modified Basic Demo here:
http://www.bulletphysics.com/Bullet/php ... f=9&t=3896
Well, I've implemented a (huge!) ghost object for frustum culling (with narrowphase collision detection) and I didn't suffer from any of these problems (the only problem so far is that raytests return the ghost objects if filters are the default ones, and so I can't use normal picking or default raycast vehicles).That is, having the ghost objects in the world seems to impact the simulation (?), and in particular, some collisions seem to be missed.
Here is how I created it:
Hope it helps.
btDynamicsWorld* btWorld = getDynamicsWorld();
if (!m_ghostPairCallback) {
m_ghostPairCallback = new btGhostPairCallback();//btOverlappingPairCallback* m_ghostPairCallback can be actually global
btWorld->getBroadphase()->getOverlappingPairCache()->setInternalGhostPairCallback(m_ghostPairCallback);
}
m_ghostObject = new btPairCachingGhostObject(); //or new btGhostObject() if you don't need narrow phase contact detection
m_ghostObject->setCollisionShape(shape);//Well shape must be a valid shape
m_ghostObject->setCollisionFlags(btCollisionObject::CF_NO_CONTACT_RESPONSE);// otherwise objects can't get inside it
btWorld->addCollisionObject(m_ghostObject,btBroadphaseProxy::SensorTrigger,btBroadphaseProxy::AllFilter & ~btBroadphaseProxy::SensorTrigger); // Every raycast must have the mask: btBroadphaseProxy::AllFilter & ~btBroadphaseProxy::SensorTrigger to exclude it
P.S. If you want to see my full code, I've posted a modified Basic Demo here:
http://www.bulletphysics.com/Bullet/php ... f=9&t=3896
-
- Posts: 13
- Joined: Tue Jul 08, 2008 6:06 am
Re: Iterate over objects ina bounding box?
Hmmm.... That is probably what's happening! That is, my ghost bounding box is somehow not allowing anything in it. So what I see is that my object (which starts out inside one of these boxes) is quickly ejected and goes into free fall.
I tried your code
but that didn't seem to help at all. But I'll play with that a bit more in case I've missed something.
I tried your code
Code: Select all
m_ghostObject->setCollisionFlags(btCollisionObject::CF_NO_CONTACT_RESPONSE);
-
- Posts: 456
- Joined: Tue Dec 25, 2007 1:06 pm
Re: Iterate over objects ina bounding box?
I've tested this code and it works for me (I just put it somewhere in the main loop):
With the debug drawer I can see that objects can stay inside of it peacefully.
Hope you can solve the problem.
Code: Select all
#define DEBUG_AABB_GHOST_OBJECT
#ifdef DEBUG_AABB_GHOST_OBJECT
{
static btGhostObject* m_AABBghostObject = NULL;
btDynamicsWorld* btWorld = getDynamicsWorld();
if (!m_AABBghostObject && btWorld) {
if (!m_ghostPairCallback) {
m_ghostPairCallback = new btGhostPairCallback(); // I store it to ensure that the next line is executed only once: you can simply set btGhostPairCallback* m_ghostPairCallback = NULL; globally.
btWorld->getBroadphase()->getOverlappingPairCache()->setInternalGhostPairCallback(m_ghostPairCallback);
}
m_AABBghostObject = new btGhostObject();
const btScalar dim(40.0);
m_AABBghostObject->setCollisionShape(new btBoxShape(btVector3(0.5*dim,0.5*dim,0.5*dim)));
m_AABBghostObject->setCollisionFlags(btCollisionObject::CF_NO_CONTACT_RESPONSE);
btWorld->addCollisionObject(m_AABBghostObject,btBroadphaseProxy::DefaultFilter,btBroadphaseProxy::AllFilter);
m_AABBghostObject->setWorldTransform(btTransform(btQuaternion::getIdentity(),btVector3(0.,dim*0.5,0.)));
printf("AABB Ghost Object: created.\n\n");
}
if (m_AABBghostObject) {
static int numObjects = 0;
int newNumber = m_AABBghostObject->getNumOverlappingObjects();
if (newNumber!=numObjects) {
numObjects = newNumber;
printf("AABB Ghost Object Has Inside %i Objects.\n",numObjects);
}
}
}
#endif //DEBUG_AABB_GHOST_OBJECT
Hope you can solve the problem.
-
- Posts: 11
- Joined: Mon Nov 02, 2009 11:55 am
Re: Iterate over objects ina bounding box?
m_ghostPairCallback = new btGhostPairCallback();//btOverlappingPairCallback* m_ghostPairCallback can be actually global
btWorld->getBroadphase()->getOverlappingPairCache()->setInternalGhostPairCallback(m_ghostPairCallback);
What is this for?
btWorld->getBroadphase()->getOverlappingPairCache()->setInternalGhostPairCallback(m_ghostPairCallback);
What is this for?
-
- Posts: 237
- Joined: Tue Jun 29, 2010 10:27 pm
Re: Iterate over objects ina bounding box?
bumpRademanc wrote:m_ghostPairCallback = new btGhostPairCallback();//btOverlappingPairCallback* m_ghostPairCallback can be actually global
btWorld->getBroadphase()->getOverlappingPairCache()->setInternalGhostPairCallback(m_ghostPairCallback);
What is this for?
-
- Posts: 456
- Joined: Tue Dec 25, 2007 1:06 pm
Re: Iterate over objects ina bounding box?
I wrote this code quite a while ago...
As far as I remember the line:
is needed once at initialization to enable ghost objects in the Bullet engine.
But I don't know if things are changed in the last versions... simply comment it out and see if it works!
As far as I remember the line:
Code: Select all
btWorld->getBroadphase()->getOverlappingPairCache()->setInternalGhostPairCallback(new btGhostPairCallback());
But I don't know if things are changed in the last versions... simply comment it out and see if it works!