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

[Shamyl Zakariya]

I recently stress-tested my engine and found via some profiling that  
it's spending 46.3 percent of CPU time in dSpaceCollide2 ->  
dxHashSpace::collide2 -> collideAABBs.

Obviously, this is pretty disressing. The specifics of the scenario  
are a 20km square world ( using a single trimesh for ground ),  
populated with approx 4000 boulders ( only four boulder models and  
trimesh data instances ) and 4000 trees ( again, only four models and  
four trimesh data instances ).

 From what I've read on this list, I took the approach of making 2  
spaces, a "static" space, for objects which will never move, and an  
"actor" space, which is where my character ( a lozenge ) and other  
moving, bodied and not entities reside. Trees and boulders and the  
ground are all in the static space. Right now, the actor space has  
*nothing* in it except the character lozenge.

In my World::step() method, after doing various bits and pieces to  
update game state, I step ODE as such:

	dSpaceCollide2( (dGeomID) _staticSpace, (dGeomID) _actorSpace, this,  
&nearCallback );
	dSpaceCollide( _actorSpace, this, &nearCallback);
	
	dWorldStep( _world, deltaT );			
	dJointGroupEmpty( _contactGroup );

My understanding is that by using two spaces, this should be pretty  
quick, since I'm not concerned with collisions between individual  
objects in the static space. My understanding is that by doing it  
this way, it'll just determine collisions between the actor space and  
the static space, and collisions between objects in the actor space.  
That said, I'm still getting 46.3% CPU time in the call to  
dSpaceCollide2.

For reference, _staticSpace and _actorSpace are hash spaces. I've  
tried to use quadtree spaces, but for some reason I get *no*  
collisions at all when I do that. Perhaps somebody has a suggestion  
here?

When I use a quadtree space, performance goes up significantly, but I  
get no collisions -- at all. Here's how I set it up to use quadtree  
spaces ( note, again, I get no collisions so I know I'm doing  
something wrong )

	_staticSpace = dQuadTreeSpaceCreate( 0, vec3( 0,0,0 ), vec3( 10000,  
10000, 1000 ), 4 );
	_actorSpace = dQuadTreeSpaceCreate( 0, vec3( 0,0,0 ), vec3( 10000,  
10000, 1000 ), 4 );

Can anybody shed some light on this? And, can anybody give me  
suggestions as to how to speed it up, in general?



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