how to enumerate all contact pairs ?

[dim1r]

Hello!

What is the best way to enumerate all contacting pairs?

My final goal is to find all connected groups (contact clusters). Is there standard solution or i should enumerate all N*(N-1) body pairs and check if they intersect ?

Thanks in advice
Dima

[bone]

I believe what you are looking for is called 'broadphase collision detection', and yes you can typically do better than the O(n^2) algorithm that you suggest, although that is always the worst case. You can probably just search for broadphase on this site to get more info. I believe Bullet uses some form of SAP (sweep-and-prune) algorithm which is somewhat standard.

[Bublik]

if you need to find all pairs of potentially colliding objects, you can use btOverlappingPairCache (btHashedOverlappingPairCache).
i don't know how to determine contact clusters (simulation islands), maybe, you should try iterating over each btPersistentManifold and insert unique pairs into a hash table.

[dim1r]

if you need to find all pairs of potentially colliding objects, you can use btOverlappingPairCache (btHashedOverlappingPairCache).
i don't know how to determine contact clusters (simulation islands), maybe, you should try iterating over each btPersistentManifold and insert unique pairs into a hash table.

I need to find exactly colliding pairs. Potentially colliding pair list is not good for me.

btw - How precise box-box pair detection ? If two boxes intersect at only one dot - will they have intersection or not?

[Bublik]

To find colliding pairs (within some tolerance), you should retrieve btOverlappingPairCache from btCollisionWorld,
iterate over each btBroadphasePair and examine all contact manifolds. If it's not empty then you have a collision.
it seems that Bullet's box-box detector doesn't check for 'vertex-vertex' cases.

[dim1r]

To find colliding pairs (within some tolerance), you should retrieve btOverlappingPairCache from btCollisionWorld,
iterate over each btBroadphasePair and examine all contact manifolds. If it's not empty then you have a collision.
it seems that Bullet's box-box detector doesn't check for 'vertex-vertex' cases.

Thank you for answer !!! You answer clarifies much for me.

I actually need staic scene with 10^5 .. 10^6 boxes of the same size and random orientation for scientific calculation.

I tested BasicDemo with 3*10^5 boxes.
I changed BasicDemo.cpp lines to
#define ARRAY_SIZE_X 100
#define ARRAY_SIZE_Y 100
#define ARRAY_SIZE_Z 30

Scene building took about 20 minutes . Is it possible to speed up this process ?


I suppose that pair finding will take too much time.

Thanks, Dima

[dim1r]

I have modified BasicDemo as shown at the picture. Certainly there are some colliding pairs.

2010-11-27_174232.png

But two examples below do not find collisions. What is wrong?

Code: Select all

m_dynamicsWorld->performDiscreteCollisionDetection();

	int numManifolds = m_dynamicsWorld->getDispatcher()->getNumManifolds();
	printf("numManifolds %d\n",numManifolds);  <--------== 0
	for (int i=0;i<numManifolds;i++)
	{
		btPersistentManifold* contactManifold =  m_dynamicsWorld->getDispatcher()->getManifoldByIndexInternal(i);
		btCollisionObject* obA = static_cast<btCollisionObject*>(contactManifold->getBody0());
		btCollisionObject* obB = static_cast<btCollisionObject*>(contactManifold->getBody1());
	
		int numContacts = contactManifold->getNumContacts();
		for (int j=0;j<numContacts;j++)
		{
			btManifoldPoint& pt = contactManifold->getContactPoint(j);
			if (pt.getDistance()<0.f)
			{
				const btVector3& ptA = pt.getPositionWorldOnA();
				const btVector3& ptB = pt.getPositionWorldOnB();
				const btVector3& normalOnB = pt.m_normalWorldOnB;
			}
		}
	}

Code: Select all

	btBroadphaseInterface *bi=m_dynamicsWorld->getBroadphase();
	btOverlappingPairCache *opc=bi->getOverlappingPairCache();
	btBroadphasePairArray parr = opc->getOverlappingPairArray();
	int i = parr.size();  <---------== 0
	printf("parr size %d\n",i);

[Bublik]

Hi !

It seems that you shouldn't check for "(pt.getDistance()<0.f)".

See:
http://www.bulletphysics.org/Bullet/php ... f=9&t=1523
"Each contact manifold provides the number of vertices that are valid."

But i've never done that so take my advice with a grain of salt.

[Johan Gidlund]

If you have a static scene of only boxes common algorithms will probably not be very efficient.
Most of them use frame coherency in some way.

Why I would do in your case would be to use the bounding sphere of all boxes (because it's trivial to find) and insert them into some kind of tree. From this tree you can identify potentially colliding boxes and you can then process this list and do simple box-box collision.

If you can run it on a GPU or some other massive parallell device you might be better of just brute forcing the sphere tests. This becuase trees often introduce lots of branching and cache misses.

[dim1r]

If you have a static scene of only boxes common algorithms will probably not be very efficient.
Most of them use frame coherency in some way.

Yes scene is static.

Why I would do in your case would be to use the bounding sphere of all boxes (because it's trivial to find) and insert them into some kind of tree. From this tree you can identify potentially colliding boxes and you can then process this list and do simple box-box collision.

So you propose to make own code to find contact pairs.

If you can run it on a GPU or some other massive parallell device you might be better of just brute forcing the sphere tests. This becuase trees often introduce lots of branching and cache misses.

Yes, trees introduce some overhead.
Actually Sweep-And-Prune solves problem without additional structures in most cases.

[Johan Gidlund]

So you propose to make own code to find contact pairs.

In this case yes because it's very simple. Checking if two spheres intersect is trivial and checking for two oriented boxes is not hard either. I think there is box-box intersection code in bullet that you could use.

Yes, trees introduce some overhead.
Actually Sweep-And-Prune solves problem without additional structures in most cases.

Well SAP is a bounding structure in itself.
Creating the axis lists from scratch as in your case is equal to doing an insertion sort of all the end points of the axis projection fot the bounding boxes though.
The reason for SAP:s popularity is that it is really cheap to update between frames since your typical simulation has realtively little motion so you will only need to swap a few elements in your axis vectors.