[ODE] Strategies for efficient collisions in a large world with few moving bodies

[Shamyl Zakariya]

Thank you for the replies!

With some futzing, I came upon a solution which both works, and  
brings CPU time in the dCollide functions down to about 2.5%, which  
is as far as I'm concerned excellent. I'm going to describe what I  
did, and I hope somebody here can explain to me why it works... as  
opposed to before.

First, I added a new space specifically for the ground trimesh. I'm  
not certain how ODE's quadtree works, but the quadtree visibility  
determination system I wrote for my game allows an object to be in  
only one node at a time ( so objects are only drawn once ), therefore  
nodes will expand to fit their contents. Now, it's possible ODE's  
implementation allows objects to be in multiple nodes simultaneously  
( makes sense in this context ), but I figured I might give a stab  
anyway at taking the ground trimesh out and putting it in its own  
space. Second, I made only the static space a quadtree space, the  
ground and actor spaces are hash spaces. I didn't change my  
nearCallback, but I'll show it below.

So my setup looks like:

	_staticSpace = dQuadTreeSpaceCreate( 0, vec3( 0,0,0 ), vec3 
( _worldSize, _worldSize, _worldSize ), 5 );
	_actorSpace = dHashSpaceCreate( 0 );
	_groundSpace = dHashSpaceCreate( 0 );

Next, in my World::step() method I call dCollide2 twice

	dSpaceCollide2( (dGeomID) _staticSpace, (dGeomID) _actorSpace, this,  
&nearCallback );
	dSpaceCollide2( (dGeomID) _groundSpace, (dGeomID) _actorSpace, this,  
&nearCallback );
	dSpaceCollide( _actorSpace, this, &nearCallback);

	dWorldStep( _world, deltaT );			
	dJointGroupEmpty( _contactGroup );

Now, here's my nearCallback:

void nearCallback (void *data, dGeomID g1, dGeomID g2)
{
	const int maxContacts = 6;
	World *world = (World *) data;
	
	/*
		back out if either doesn't allow collisions with the other
	*/

	Entity *e1 = Entity::entityForGeom( g1 );
	Entity *e2 = Entity::entityForGeom( g2 );

	if ( e1 && e2 )
	{
		if ( !e1->allowCollisionWith( e2 ) || !e2->allowCollisionWith 
( e1 )) return;
	}
	
	dBodyID b1 = dGeomGetBody( g1 );
	dBodyID b2 = dGeomGetBody( g2 );

	/*
		Exit if they have corresponding bodies.
		This, conveniently, discards collisions between statics, since  
their bodies == NULL.
	*/
	if ( b1 == b2 )
	{
		return;
	}

	/*
		exit without doing anything if the two bodies are connected by a joint
		or Connection. Connection implementations may need more complex  
checking than
		just the default joint checking, since some (Servo) use  
intermediate "pinion"
		bodies.
	*/
	
	#warning Removed Connection::connectedBy() from nearCallback
	
	if (
			b1 && b2 &&
			(dAreConnectedExcluding( b1, b2, dJointTypeContact ))
	   )
	{
		return;
	}		
	
	/*
		Determine mu values for b1 and b2
		Note that the geoms for the ground mesh and walls have no bodies, so
		we special case it to use sim->getGroundMu()
	*/

	float defaultMu = world->_defaultMu;
	float g1Mu = e1 ? e1->mu() : defaultMu;
	float g2Mu = e2 ? e2->mu() : defaultMu;
	float combinedMu = 0;

	/*
		This is my preposterous way to determine combined friction for two  
objects:
		product divided by average. Seems "good enough". Allows for a  
sticky object
		to slip if against a frictionless one. Seems reasonable to me :/
	*/
	if ( g1Mu < EPSILON && g2Mu < EPSILON )
	{
		combinedMu = 0;
	}
	else
	{
		combinedMu = ( g1Mu * g2Mu ) / ( (g1Mu + g2Mu) * 0.5f );
	}


	dContact contact[maxContacts];
	for (int i = 0; i < maxContacts; i++)
	{
		contact[i].surface.mode = dContactSoftCFM | dContactSoftERP;
		contact[i].surface.mu = combinedMu;
		contact[i].surface.soft_cfm = 0.0001f;
		contact[i].surface.soft_erp = 0.2f;
	}
	

	if ( int numc = dCollide( g1, g2, maxContacts, &contact[0].geom,  
sizeof(dContact)) )
	{
		for ( int i = 0; i < numc; i++ )
		{
			dJointID c = dJointCreateContact( world->_world, world- 
 >_contactGroup, &(contact[i]) );
			dJointAttach( c, b1, b2 );
						
			if ( e1 )
			{
				e1->collision( e2, contact[i].geom.pos, contact[i].geom.normal,  
contact[i].geom.depth );
			}
			
			if ( e2 )
			{
				e2->collision( e1, contact[i].geom.pos, contact[i].geom.normal,  
contact[i].geom.depth );
			}						
		}
	}
}


shamyl zakariya
     "obviously, you're not a golfer"
         -- the Dude

On Jan 17, 2006, at 8:47 PM, Chris Ledwith wrote:

> No collisions? Very strange. Can we see what your near callback  
> function looks like?
>
> By the way, once you do get collision with quadtree spaces working,  
> make sure that it is oriented correctly, that is, you may need to  
> modify the AXIS0, AXIS1, and UP #defines at the top of  
> collision_quadtreespace.cpp.
>
> -C
>