Moving a static and rehashing

[slembcke]

Both of those code snippets do pretty much the same thing, but there are some subtle differences between. Before 5.3, the second simply would have been a (very) slightly less efficient way of doing the first. After 5.3, the second method has some strong advantages for static objects. The explanation gets a bit technical though.

...

I started typing up a very long and technical explanation of why the second is slightly better in 5.3 but then realized that it would simply be easier to change a few lines so that cpSpaceHashRehashObject() had the advantages of the second. I also wrote a cpSpaceRehashShape() function. Check in trunk.

Basically with the first code snippet, the spatial hash would continue to return false positives at the old position of the shape until a full rehash was performed. The second snippet creates a new handle for the shape in the spatial hash which as of 5.3 gets automatically cleaned up as queries are made even without a full rehash. This was added to make the static -> active transition more efficient when sleeping bodies were woken up.

[dieterweb]

Great, thank you.

[dieterweb]

When calling cpSpaceRehash very often while the simulation is not running (no spaceStep called) will drop the performance very quickly. I have to start the simulation to get it back to normal.

[slembcke]

cpSpaceRehashStatic() or cpSpaceRehashShape()?

[dieterweb]

cpSpaceRehashShape

and I use this for static and active shapes.

[slembcke]

So you are moving objects, rehashing them using cpSpaceRehashObject() and then performing queries? I could foresee problems with this. The query functions probably don't strip out dead hash handles, so you would end up with more every time you rehashed an object. Incremental updates to spatial indexes always requires a bunch of special purpose code. :-\

In the case where you rehash an object that moves very little, you will probably be putting an extra handle in all the hash cells that it already occupies. Each time you do so, the hash will get slower when querying that location and use more memory. The normal collision routines strip these unused handles out each time they are encountered, but I don't think it was done for the point/segment query functions. I'll look into this.

At the moment, the best workaround would be full rehash every few times instead of doing an individual rehash.

[dieterweb]

What do I have to do to do a full rehash of active shapes?

[slembcke]

There isn't an API function to do it because I didn't figure anybody would ever want to do it. It would look pretty much identical to cpSpaceRehashStatic() however. (which is a 2 line function)

I have a full day allocated to work on Chipmunk today. It's on my to do list to look at this today. I'll see if I can come up with a more efficient solution for you.

[slembcke]

So point and bounding box queries were cleaning up the extra shape handles, but segment queries were not. Was this your issue?

I refactored the cleanup code so that it could be shared with the segment query functions and I optimized it slightly. The logo smash demo now runs 2.6% faster. \o/

This should fix your performance issue as well.

[dieterweb]

Hi,

I do not make any segment queries when the simulation is paused.

I now made a custom spaceStepPaused function which is called when a dynamic object changes it properties while the sim is paused. When a static one changes I call cpSpaceRehashStatics. I do not have performance problems anymore.

Code: Select all

void
cpSpaceStepPaused(cpSpace *space)
{	
	space->locked = cpTrue;
	
	// Empty the arbiter list.
	space->arbiters->num = 0;
		
	// Pre-cache BBoxes and shape data.
	cpSpaceHashEach(space->activeShapes, (cpSpaceHashIterator)updateBBCache, NULL);
	
	// Collide!
	cpSpaceHashQueryRehash(space->activeShapes, (cpSpaceHashQueryFunc)queryFunc, space);
		
	// Clear out old cached arbiters and dispatch untouch functions
	cpHashSetFilter(space->contactSet, (cpHashSetFilterFunc)contactSetFilter, space);	
	
	space->locked = cpFalse;
	
	// Increment the stamp.
	space->stamp++;
}