Collision check overhead for thousads of static objects

Post Reply
Misterblue
Posts: 14
Joined: Wed Apr 28, 2010 3:09 pm

Collision check overhead for thousads of static objects

Post by Misterblue »

I am using Bullet on a scene that has thousands of static objects. The static objects are buildings and trees and such and they act solid if a dynamic object bumps into them.

My problem is that, even with no dynamic objects, Bullet is taking many milliseconds to process each frame and decide there is nothing to do. It seems that many of the static objects overlap and thus are always collision candidates. I've tried both ISLAND_SLEEPING and DISABLE_SIMULATION and set the collision flags so these static objects should never collide, but they stay in the collision pair cache and are checked over and over.

Other than an "if it hurts, don't do it that way" type of answer (Hey! I'm not the artist. I'm just the physics guy!), what do I need to set so overlapping static objects are taken out of the collision pair cache and are never considered for inter-collision checks? Or what obvious thing am I overlooking?

I've searched around the forum a bit but haven't found the answer. Any suggestions appreciated.

Thanks.

-- mb

Some details: A scene with 70,000 static objects (meshes, zero mass, DISABLE_SIMULATION) takes > 50ms to scan (i7,Win7,64bit). Bullet stats say it spends all of the time in 'calculateSimulationIslands' and 'dispatchAllCollisionPairs' (see below). The count of objects and their activation state are at the bottom.
This is Bullet 2.81 and I'm using btCollsionDispatcher, btDbvtBroadphase, btSequentialImpulseConstraintSolver, and btDiscreteDynamicsWorld.

20121130150846102,[BULLETS UNMANAGED]:----------------------------------
20121130150846102,[BULLETS UNMANAGED]:Profiling: Root (total running time: 54.165 ms) ---
20121130150846102,[BULLETS UNMANAGED]:0 -- stepSimulation (99.99 %) :: 54.161 ms / frame (1 calls)
20121130150846102,[BULLETS UNMANAGED]:Unaccounted: (0.007 %) :: 0.004 ms
20121130150846102,[BULLETS UNMANAGED]:...----------------------------------
20121130150846102,[BULLETS UNMANAGED]:...Profiling: stepSimulation (total running time: 54.161 ms) ---
20121130150846102,[BULLETS UNMANAGED]:...0 -- synchronizeMotionStates (0.00 %) :: 0.000 ms / frame (5 calls)
20121130150846102,[BULLETS UNMANAGED]:...1 -- internalSingleStepSimulation (97.88 %) :: 53.014 ms / frame (5 calls)
20121130150846102,[BULLETS UNMANAGED]:...Unaccounted: (2.118 %) :: 1.147 ms
20121130150846102,[BULLETS UNMANAGED]:......----------------------------------
20121130150846102,[BULLETS UNMANAGED]:......Profiling: internalSingleStepSimulation (total running time: 53.014 ms) ---
20121130150846102,[BULLETS UNMANAGED]:......0 -- updateActivationState (0.00 %) :: 0.000 ms / frame (5 calls)
20121130150846102,[BULLETS UNMANAGED]:......1 -- updateActions (0.00 %) :: 0.000 ms / frame (5 calls)
20121130150846102,[BULLETS UNMANAGED]:......2 -- integrateTransforms (0.00 %) :: 0.000 ms / frame (5 calls)
20121130150846102,[BULLETS UNMANAGED]:......3 -- solveConstraints (0.06 %) :: 0.033 ms / frame (5 calls)
20121130150846102,[BULLETS UNMANAGED]:......4 -- calculateSimulationIslands (61.32 %) :: 32.506 ms / frame (5 calls)
20121130150846102,[BULLETS UNMANAGED]:......5 -- performDiscreteCollisionDetection (38.59 %) :: 20.457 ms / frame (5 calls)
20121130150846102,[BULLETS UNMANAGED]:......6 -- createPredictiveContacts (0.00 %) :: 0.002 ms / frame (5 calls)
20121130150846102,[BULLETS UNMANAGED]:......7 -- predictUnconstraintMotion (0.00 %) :: 0.001 ms / frame (5 calls)
20121130150846102,[BULLETS UNMANAGED]:......Unaccounted: (0.028 %) :: 0.015 ms
20121130150846102,[BULLETS UNMANAGED]:.........----------------------------------
20121130150846102,[BULLETS UNMANAGED]:.........Profiling: solveConstraints (total running time: 0.033 ms) ---
20121130150846102,[BULLETS UNMANAGED]:.........0 -- solveGroup (60.61 %) :: 0.020 ms / frame (5 calls)
20121130150846102,[BULLETS UNMANAGED]:.........1 -- processIslands (6.06 %) :: 0.002 ms / frame (5 calls)
20121130150846102,[BULLETS UNMANAGED]:.........2 -- islandUnionFindAndQuickSort (12.12 %) :: 0.004 ms / frame (5 calls)
20121130150846102,[BULLETS UNMANAGED]:.........Unaccounted: (21.212 %) :: 0.007 ms
20121130150846102,[BULLETS UNMANAGED]:............----------------------------------
20121130150846102,[BULLETS UNMANAGED]:............Profiling: solveGroup (total running time: 0.020 ms) ---
20121130150846102,[BULLETS UNMANAGED]:............0 -- solveGroupCacheFriendlyIterations (15.00 %) :: 0.003 ms / frame (5 calls)
20121130150846102,[BULLETS UNMANAGED]:............1 -- solveGroupCacheFriendlySetup (35.00 %) :: 0.007 ms / frame (5 calls)
20121130150846102,[BULLETS UNMANAGED]:............Unaccounted: (50.000 %) :: 0.010 ms
20121130150846102,[BULLETS UNMANAGED]:.........----------------------------------
20121130150846102,[BULLETS UNMANAGED]:.........Profiling: calculateSimulationIslands (total running time: 32.506 ms) ---
20121130150846102,[BULLETS UNMANAGED]:.........0 -- storeIslandActivationState (23.35 %) :: 7.589 ms / frame (5 calls)
20121130150846102,[BULLETS UNMANAGED]:.........1 -- uniteIslandsFromConstraints (0.00 %) :: 0.001 ms / frame (5 calls)
20121130150846102,[BULLETS UNMANAGED]:.........2 -- uniteIslandsFromPredictiveManifold (0.01 %) :: 0.003 ms / frame (5 calls)
20121130150846102,[BULLETS UNMANAGED]:.........3 -- updateActivationState (76.62 %) :: 24.905 ms / frame (5 calls)
20121130150846102,[BULLETS UNMANAGED]:.........Unaccounted: (0.025 %) :: 0.008 ms
20121130150846103,[BULLETS UNMANAGED]:............----------------------------------
20121130150846103,[BULLETS UNMANAGED]:............Profiling: updateActivationState (total running time: 24.905 ms) ---
20121130150846103,[BULLETS UNMANAGED]:............0 -- findUnions (23.01 %) :: 5.731 ms / frame (5 calls)
20121130150846103,[BULLETS UNMANAGED]:............Unaccounted: (76.989 %) :: 19.174 ms
20121130150846103,[BULLETS UNMANAGED]:.........----------------------------------
20121130150846103,[BULLETS UNMANAGED]:.........Profiling: performDiscreteCollisionDetection (total running time: 20.457 ms) ---
20121130150846103,[BULLETS UNMANAGED]:.........0 -- dispatchAllCollisionPairs (89.55 %) :: 18.320 ms / frame (5 calls)
20121130150846103,[BULLETS UNMANAGED]:.........1 -- calculateOverlappingPairs (0.03 %) :: 0.007 ms / frame (5 calls)
20121130150846103,[BULLETS UNMANAGED]:.........2 -- updateAabbs (10.37 %) :: 2.121 ms / frame (5 calls)
20121130150846103,[BULLETS UNMANAGED]:.........Unaccounted: (0.044 %) :: 0.009 ms
20121130150846103,[BULLETS UNMANAGED]:.........----------------------------------
20121130150846103,[BULLETS UNMANAGED]:.........Profiling: createPredictiveContacts (total running time: 0.002 ms) ---
20121130150846103,[BULLETS UNMANAGED]:.........0 -- release predictive contact manifolds (50.00 %) :: 0.001 ms / frame (5 calls)
20121130150846103,[BULLETS UNMANAGED]:.........Unaccounted: (50.000 %) :: 0.001 ms
20121130150846106,[BULLETS UNMANAGED]: num CollisionObject = 69179
20121130150846106,[BULLETS UNMANAGED]: num RigidBodies = 69179
20121130150846106,[BULLETS UNMANAGED]: num ACTIVE_TAG = 0
20121130150846106,[BULLETS UNMANAGED]: num ISLAND_SLEEPING = 0
20121130150846106,[BULLETS UNMANAGED]: num WANTS_DEACTIVATION = 0
20121130150846106,[BULLETS UNMANAGED]:num DISABLE_DEACTIVATION = 0
20121130150846106,[BULLETS UNMANAGED]: num DISABLE_SIMULATION = 69179
20121130150846106,[BULLETS UNMANAGED]: num overlappingPairs = 69178
20121130150846106,0000000000,Simulate,call, frame=1000, nTaints=0, simTime=63, substeps=5, updates=0, colliders=0
Misterblue
Posts: 14
Joined: Wed Apr 28, 2010 3:09 pm

Re: Collision check overhead for thousads of static objects

Post by Misterblue »

For those who find this topic and have a similar problem here is what I found.

Thousands of possibly colliding objects uses too much CPU. No way around that. Bullet builds a collision cache so the sets of possibly colliding points need not be recomputed from scratch every frame. The contents of that cache is scanned completely each frame to modify and compute collisions, etc. I have seen other script engines that track object changes and only scan the parts of the collision cache that could have changed, but the current Bullet implementation just scans it all.

This is not a problem until you get thousands of, what I'll call 'collisionActive' objects. 'collisionActive' is different than the ACTIVE state (ISLAND_SLEEPING, ACTIVE, DISABLE_SIMULATION, ...) which controls which objects are processed for physics activity (gravity, velocity, ...). Normally, the physically active objects are the ones that create object interactions and, when they interact, the collision contact information is build in the collision cache and only a small number of interesting collisions are being scanned each frame.

There are several ways inactive objects make it into the collision cache. For instance, an active object collides with a DISABLE_SIMULATION static object. The static object and the active, physical object's contact points go into the collision cache for future consideration. Eventually, though, the physical object will move on and the potential collision will go away.

Now, say you're foolish enough to have a scene with thousands of overlapping static objects. They can all be DISABLE_SIMULATION but, if they ever make it into the collision cache, they will be checked for possible collisions every frame and they will never be removed from the collision cache. This is the situation I was in as described in the parent post.

All is not lost! Bullet has a mechanism to control what goes into the collision cache. The btBroadphaseProxy defines m_collisionFilterGroup and m_collisionFilterMask. Yes, this is that stuff you read about on how to control what can collide with what. By default, each of the basic types (dynamic, static, kinematic, ...) have a group and they can collide with anything (filter == AllFilter). And, normally, static objects don't collide with static objects so static-to-static collisions never make it into the collision cache even though the default group/filter would allow that. When a potential collision is about to be added to the collision cache, the two object's groups and filters are compared. If neither object's filter includes the others group bits, the potential collision is not even put into the collision cache. Thus the two object can never collide and the potential collision does not take up any CPU cycles.

So, to fix my problem with too much collision computation, I defined the object collision groups and filters to limit what can go into the collision cache. Among other things, I set the static object filter mask to not include static objects. (The 'group' and 'filter' are bitmasks so I made "staticGroup & staticFilter == 0").

I hope this long missive is helpful for someone, like me, who is newly exploring physics.

-- mb

P.S.: One little gotcha is that the collision group and mask are stored in the btBroadphaseProxy which only exists after the collision object has been added to the dynamic world. So, if you are doing things like taking objects in and out of the dynamic world (to change properties, for instance) these must be restored. Also, setting group and mask when a collision object is not in a dynamic world doesn't do anything.
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: Collision check overhead for thousads of static objects

Post by Erwin Coumans »

Someone pointed me to this posting (Pierre Terdiman)
(The 'group' and 'filter' are bitmasks so I made "staticGroup & staticFilter == 0").
I am trying to reproduce the issue, but things work fine here:
If you add static rigid bodies using btDiscreteDynamicsWorld::addRigidBody, the staticGroup & staticFilter == 0. See the code here:

Code: Select all

void	btDiscreteDynamicsWorld::addRigidBody(btRigidBody* body)
{
	if (!body->isStaticOrKinematicObject() && !(body->getFlags() &BT_DISABLE_WORLD_GRAVITY))
	{
		body->setGravity(m_gravity);
	}

	if (body->getCollisionShape())
	{
		if (!body->isStaticObject())
		{
			m_nonStaticRigidBodies.push_back(body);
		} else
		{
			body->setActivationState(ISLAND_SLEEPING);
		}

		bool isDynamic = !(body->isStaticObject() || body->isKinematicObject());
		short collisionFilterGroup = isDynamic? short(btBroadphaseProxy::DefaultFilter) : short(btBroadphaseProxy::StaticFilter);
		short collisionFilterMask = isDynamic? 	short(btBroadphaseProxy::AllFilter) : 	short(btBroadphaseProxy::AllFilter ^ btBroadphaseProxy::StaticFilter);

		addCollisionObject(body,collisionFilterGroup,collisionFilterMask);
	}
}
Also, you might want to set world->setForceUpdateAllAabbs(false); to avoid expense AABB calculations for static objects.

Are you adding the objects into the world differently?
Thanks!
Erwin
Misterblue
Posts: 14
Joined: Wed Apr 28, 2010 3:09 pm

Re: Collision check overhead for thousads of static objects

Post by Misterblue »

Yes, I was adding my objects to the world differently in that I was setting my own collision filter group and mask. My error was setting the filter group and mask so that static objects could collide with other static objects. If you do that, everything works until you notice all the cpu time being used.

The solution was to define them like the default Bullet code (which you reference) does -- static objects don't collide with static objects.
Post Reply