Iterate over objects ina bounding box?

[tomva]

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

[Ellon]

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:

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.
  }
}

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:

Code: Select all

world->addCollisionObject(ghost);
OverlapAABB(ghost, results);
world->removeCollisionObject(ghost);

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

[Flix]

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:

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.

[Ellon]

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:

Code: Select all

world->getDispatcher()->dispatchAllCollisionPairs(ghost->getOverlappingPairCache(), world->getDispatchInfo(), world->getDispatcher());

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

[Flix]

Ellon wrote:

I hope this answer to your question.

Yes, it's all much clearer to me now.
So there's no gain in using btPairCachingGhostObjects without the line:

Code: Select all

world->getDispatcher()->dispatchAllCollisionPairs(ghost->getOverlappingPairCache(), world->getDispatchInfo(), world->getDispatcher());

to get narrowphase calculations.

Thank you for your clarifications.

[tomva]

Thanks to both of you for the answers!

Using ghost objects is a very elegant solution, I'll do that.

[tomva]

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:

Code: Select all

ghostObject->getOverlappingObjects()

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:

Code: Select all

int numObjects = ghost->getNumOverlappingObjects();
for (int i = 0; i < numObjects; ++i) {
    btCollisionObject * cobj = ghost->getOverlappingObject(i);
}

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?

[Erwin Coumans]

As far as I can tell, the call:

Code: Select all

ghostObject->getOverlappingObjects()

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.

ghostObject->getOverlappingObjects() returns ALL overlapping AABB's, including the fully embedded ones (there is no such thing as a surface AABB check in Bullet)
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

[tomva]

Is there a chance I've done something wrong?

Yes! I was definitely doing something wrong. As you may have guessed, I had the wrong boundaries set up.

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.

[Flix]

tomva wrote:

That is, having the ghost objects in the world seems to impact the simulation (?), and in particular, some collisions seem to be missed.

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).

Here is how I created it:

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

Hope it helps.

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

[tomva]

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

Code: Select all

m_ghostObject->setCollisionFlags(btCollisionObject::CF_NO_CONTACT_RESPONSE);

but that didn't seem to help at all. But I'll play with that a bit more in case I've missed something.

[Flix]

I've tested this code and it works for me (I just put it somewhere in the main loop):

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

With the debug drawer I can see that objects can stay inside of it peacefully.

Hope you can solve the problem.

[Rademanc]

m_ghostPairCallback = new btGhostPairCallback();//btOverlappingPairCallback* m_ghostPairCallback can be actually global
btWorld->getBroadphase()->getOverlappingPairCache()->setInternalGhostPairCallback(m_ghostPairCallback);

What is this for?

[dphil]

m_ghostPairCallback = new btGhostPairCallback();//btOverlappingPairCallback* m_ghostPairCallback can be actually global
btWorld->getBroadphase()->getOverlappingPairCache()->setInternalGhostPairCallback(m_ghostPairCallback);

What is this for?

bump

[Flix]

I wrote this code quite a while ago...

As far as I remember the line:

Code: Select all

btWorld->getBroadphase()->getOverlappingPairCache()->setInternalGhostPairCallback(new btGhostPairCallback());

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!