Collision deteciton question

[xerion]

Hey everyone,

I am pretty new to bullet and for the moment I am only using it to do simple collision detection with the purpose being of object selection.
I have various objects that are drawn in an openGL canvas and all of them are static. For bullet I just use primitive shapes.

On my render function I remove all bullet rigid bodies and add them again in order to reflect the new location and orientation of the equivalent opengl objects.
I am able to do simple ray collision to test which object is selected/clicked. Now I would like to be able to do rubber band selection in order to select multiple objects on screen.

I read that btPairCachingGhostObject is the way to go so I have been trying to implement that but I think I am missing something.
Theoretically I should calculate the near and far edges of my frustrum from the rubber band rectangle and add them to a btConvexHullShape which i will then pass to my btPairCachingGhostObject.
But for now lets just make it simple and just use a btBoxShape and actually a rather large one to be sure.
So after my selection finished via the means of a rubberband I do :

Code: Select all

	btBoxShape* box = new btBoxShape(btVector3(3000,3000,3000))

	btPairCachingGhostObject* frustum = new btPairCachingGhostObject();
	frustum->setCollisionShape(box);
	frustum->setCollisionFlags(frustum->getCollisionFlags()|btCollisionObject::CF_NO_CONTACT_RESPONSE);

	this->dynamicsWorld->addCollisionObject(frustum);
	btBroadphasePairArray& collisionPairs = frustum->getOverlappingPairCache()->getOverlappingPairArray();
	const int	numObjects=collisionPairs.size();

Why is it that always get numObjects = 0;
I checked my dynamicsWorld by debugDrawWorld() and I see that my box shape definitely includes all my objects.

Any help would be much appreciated !

[rtrius]

Has the ghost pair callback been set?

Code: Select all

btDiscreteDynamicsWorld* dynamicsWorld = CreateDiscreteDynamicsWorld(); // Assume the world is now initializing...
ghostPairCallback = new btGhostPairCallback();
dynamicsWorld->getPairCache()->setInternalGhostPairCallback(ghostPairCallback);

From:
http://bulletphysics.org/mediawiki-1.5. ... d_Triggers

[xerion]

Yes indeed I have.
I init all bullet related stuff with my opengl constructor.

Code: Select all

void COpenGLView::initCollissionDetection()
{
	///collision configuration contains default setup for memory, collision setup. Advanced users can create their own configuration.
	this->collisionConfiguration = new btDefaultCollisionConfiguration();

	///use the default collision dispatcher. For parallel processing you can use a different dispatcher (see Extras/BulletMultiThreaded)
	this->dispatcher = new	btCollisionDispatcher(collisionConfiguration);

	///btDbvtBroadphase is a good general purpose broadphase. You can also try out btAxis3Sweep.
	this->overlappingPairCache = new btDbvtBroadphase();

	///the default constraint solver. For parallel processing you can use a different solver (see Extras/BulletMultiThreaded)
	this->solver = new btSequentialImpulseConstraintSolver();

	this->dynamicsWorld = new btDiscreteDynamicsWorld(dispatcher, overlappingPairCache, solver, collisionConfiguration);

	this->dynamicsWorld->setGravity(btVector3(0,-9.81,0));

	this->frustum = nullptr;
	this->ghostPairCallback = new btGhostPairCallback();
	this->dynamicsWorld->getPairCache()->setInternalGhostPairCallback(ghostPairCallback);
}

Does anything look suspicious ?

[xerion]

A bit of answering myself here and also a question.

It seems that I had to change the filter group and mask in order to make it work with static objects.

Code: Select all

this->dynamicsWorld->addCollisionObject(frustum, btBroadphaseProxy::AllFilter,btBroadphaseProxy::StaticFilter);

So the next step is of course to perform the narrow phase detection.
With the addition of the filter group and mask my numObjects is now > 0.

Code: Select all

	this->dynamicsWorld->getDispatcher()->dispatchAllCollisionPairs(frustum->getOverlappingPairCache(), dynamicsWorld->getDispatchInfo(), dynamicsWorld->getDispatcher());
	btBroadphasePairArray& collisionPairs = frustum->getOverlappingPairCache()->getOverlappingPairArray();	//New
	const int numObjects=collisionPairs.size();

	static btManifoldArray	m_manifoldArray;
	int count = 0;

	for(int i=0;i<numObjects;i++)
	{
		const btBroadphasePair& collisionPair = collisionPairs[i];

		m_manifoldArray.resize(0);

		if (collisionPair.m_algorithm) 
			collisionPair.m_algorithm->getAllContactManifolds(m_manifoldArray);
		else
			continue;

		for (int j=0;j<m_manifoldArray.size();j++)	
		{
			btPersistentManifold* manifold = m_manifoldArray[j];

			if (manifold->getNumContacts() > 0) 
			{
				count++;
				break;
			}
		}
	}

So question is :

According to http://bulletphysics.org/Bullet/phpBB3/ ... um+culling, they say that

Code: Select all

this->dynamicsWorld->getDispatcher()->dispatchAllCollisionPairs(frustum->getOverlappingPairCache(), dynamicsWorld->getDispatchInfo(), dynamicsWorld->getDispatcher());

is not needed at one of the posts (even though Flix, the guy that originally wrote the test code, said that he initially needed it). I also see that without that call collisionPair.m_algorithm is NULL.
Its definitely an old post so things could have changed.

So I was wondering if anyone can answer if its something that its indeed needed which is what I see or I am missing something.

[Flix]

According to viewtopic.php?f=9&t=3896&hilit=frustum+culling, they say that
Code:
this->dynamicsWorld->getDispatcher()->dispatchAllCollisionPairs(frustum->getOverlappingPairCache(), dynamicsWorld->getDispatchInfo(), dynamicsWorld->getDispatcher());
is not needed...

Well, I don't remember the details, but if without that call collisionPair.m_algorithm is NULL you definitely need it.

However AFAIR, if you only need collision detection (no physics) you can use a plain btCollisionWorld, without having to step the world (with stepSimulation(...)), and after you move your objects manually, you can refresh the collision pairs (probably with the method dispatchAllCollisionPairs(...) above): that could explain why in certain cases that call is required and in other no (stepSimulation(...) could trigger it, but I'm no 100% sure: that demo is very old and I've never used a plain btCollisionworld myself).

P.S: Now I remember I made a btGhostObjectDemo somewhere (http://www.bulletphysics.org/Bullet/php ... emo#p21693), that is (slightly) more recent than that one. You can check it if you need futher info. In that demo the line:

Code: Select all

m_dynamicsWorld->getDispatcher()->dispatchAllCollisionPairs(m_pairCachingGhostObject->getOverlappingPairCache(), m_dynamicsWorld->getDispatchInfo(), m_dynamicsWorld->getDispatcher());

has been commented out and findPair(...) is used. It should be a bit faster.

[xerion]

However AFAIR, if you only need collision detection (no physics) you can use a plain btCollisionWorld, without having to step the world (with stepSimulation(...)), and after you move your objects manually, you can refresh the collision pairs (probably with the method dispatchAllCollisionPairs(...) above): that could explain why in certain cases that call is required and in other no (stepSimulation(...) could trigger it, but I'm no 100% sure: that demo is very old and I've never used a plain btCollisionworld myself).

I think this explanation is what I wanted. Indeed, I dont need to step the world so I dont do it.
Regarding the findpairs I did try that as well since I saw that approach in the CharacterDemo.cpp provided with bullet.
Again the algorithm was Null since i was not stepping the world I guess.

I just tried to step the world and indeed the algorithm was not NULL anymore so I can use the findpairs method.

Would it be better / faster to not step the world and dispatchAllCollisionPairs or to step the world and findPairs ?
I will do some timing tests but was wondering if one approach is better than the other.

[Flix]

Would it be better / faster to not step the world and dispatchAllCollisionPairs or to step the world and findPairs ?

Well, I guess that you should measure the stepSimulation(...) overhead too (and it depends on your timestep).

Anyway I wouldn't call stepSimulation(...) if I don't need it

Another solution would be to use a contact query between a dummy btCollisionObject (created on the stack and not added to the world) and the objects in the world. Maybe by doing this, you can avoid the creation of contacts between the other bodies (but this is something you have to measure too).

[xerion]

Measuring time of

Code: Select all

this->dynamicsWorld->getDispatcher()->dispatchAllCollisionPairs(frustrumGhostObject->getOverlappingPairCache(), dynamicsWorld->getDispatchInfo(), dynamicsWorld->getDispatcher());

vs

Code: Select all

this->dynamicsWorld->stepSimulation(1.0/60.0);

definitely shows that the first option is about 3-4 faster.

However, what I am seeing is that

Code: Select all

this->dynamicsWorld->addCollisionObject(frustrumGhostObject, btBroadphaseProxy::AllFilter,btBroadphaseProxy::StaticFilter);

is really slow.
Or to be more exact it takes a long time when many objects are in scene (in my case about 4sec). More specifically it seems to be the call collideTV()...

So what I have been trying to sort out is contactTest with my frustrum object without adding it to my world.
Would it be too much to provide a simple example or just point me to the right direction ?
Do I necessarily need a callback ? All I care about is just a boolean really

Edit:

Code: Select all

btCollisionObject obj;
	obj.setCollisionShape(ConvexShape);
	
	ContactSensorCallback callback(obj, selectedObjIds);
	dynamicsWorld->contactTest(&obj, callback);

Passing the frustrum convex for a contact test seems to be much faster. I can fill in my indexes I guess in my callback.

[Flix]

Basically you just add the "other" btCollisionObject in a btAlignedObjectArray<btCollisionObject*> inside your callback, in the addSingleResult(...) method. I don't remember exactly if the return value is used or not (I would return 1, it seems more consistent with the ray callbacks when you need further results).

I didn't know it's so slow to add a ghost object to a btcollisionWorld: maybe you can change the broadphase (although the btDbvtBroadphase should be good in most cases).
Maybe you can try calling:

Code: Select all

m_collisionWorld->setForceUpdateAabbs(false);

, then you can leave the ghost object in the world, change its collision shape at runtime and try to call

Code: Select all

m_collisionWorld->updateSingleAabb(m_ghostObject);

, and clearing the ghost object manifold from pairs too if that is necessary.

[Flix]

I've made a basic implementation of rectangular mouse selection using contactTest.

CollisionWorldSelectionDemo.7z

P.S. There's still a faster way of doing it: by using the btDbvtBroadphase directly (in the same way we usually perform normal physic-based frustum culling). The main problem of that approach is that we need the 6 "frustum selection" planes in world space (you can search the forum for further info on this topic).

[Edit]: Nevermind, AFAIR the btDbvtBroadphase method just reports collisions between the frustum and the aabb of the other bodies: that is good for fast frustum culling but not for rectangular selection.

[xerion]

Hey Flix,

Thanks for that. I actually implemented the contact test myself as I posted earlier which was good as I was able to to do some timings tests.
With about 170k objects (the majority of them being 3D points, as in 169500) it takes about 0.7s to complete.

From what I saw, the two slow things were actually adding the collision objects, spheres in this case for the 3d points and in the end removing them.
The removing of all objects from the world was really slow, to the order of 5-6 seconds if I recall correctly.

You mentioned that there is a faster way to do by using btDbvtBroadphase directly. Does that mean I still have to add them to the world or there is a way so that I can just perform the collision detection?

[Flix]

You mentioned that there is a faster way to do by using btDbvtBroadphase directly. Does that mean I still have to add them to the world or there is a way so that I can just perform the collision detection?

Nope, the objects must always be added to the world. AFAIK only contactPairTest can be used without adding both objects to the world, but I guess that 169500 contactPairTest calls take more than just adding and removing objects.

Are you adding and removing objects for the only purpose of calling contactTest ?
I ask because if you just want to test if a point in inside a convex shape, you should not add any object: there should be some 'isInside' method somewhere in the btPolyhedralConvexShape class, but I've never tested it. Or you can just use the static methods in btGeometryUtils.h

Code: Select all

static bool isInside(const btAlignedObjectArray<btVector3>& vertices, const btVector3& planeNormal, btScalar	margin);		
static bool	isPointInsidePlanes(const btAlignedObjectArray<btVector3>& planeEquations, const btVector3& point, btScalar	margin);

I don't remember much about them, but you should probably use the convex planes or points in world space and the btVector3 fourth component is used for the plane equations too.

[xerion]

Are you adding and removing objects for the only purpose of calling contactTest ?

Pretty much yes.
Will have to look into that a bit more. With a quick look I saw that most isInside functions are not implemented expect for the one in the btGeometryUtils and the btBox2dShape.

ContactPairTest might also be possible as I could use my frustrum object and iteratively call all the rest of my objects.

[Flix]

ContactPairTest might also be possible as I could use my frustrum object and iteratively call all the rest of my objects.

Ok, but I would use the btGeometryUtil methods instead to test if points are inside or outside the frustum (frustum points in global space can be calculated by transforming the local frustum points by the camera transform; then to get the plane equations from the global points you can use another method inside btGeometryUtils; at this point you can call a single static method to test if each point is inside or not, and I guess it could be faster than contactPairTest).