[Algorithms] Cache-coherent hashing for broad-phase collision detection

[Darren G. <dg...@ke...>]

Hi,

I am looking at ways of improving cache coherence for a typical 
broad-phase collision detection scenario (cpu).  The basic 
implementation utilizes these data structures:

	struct ObjectTracking {
		int ObjectIndex;
		int RefCount;
	};

	typedef set<ObjectTracking> Tile;

	struct TilingLevel {
		vector<Tile> Tiles;
		int Pitch;
		Tile& Map(int x, int y) { return Tiles[y*Pitch+x]; }
	};

	struct TilingHierarchy {
		vector<TilingLevel> TilingLevels;
		Tile& Map(int level, int x, int y)  { return TilingLevels[level].Map(x,y); }
	};


And the hot process involves frequent iteration of:

	for level from 0 to maxlevel
	for y from y0(level) to y1(level)
	for x from x0(level) to x1(level)
		tilingHierarchy.Map(level,x,y).InsertOrRemove();


Performance becomes an issue here when the std::set allocations get 
spread out across process memory.  I will therefore replace 
individual sets with a single shared map to explore implementations 
for coherence:

	(level,x,y,ObjectIndex)->(RefCount).


(level,x,y,ObjectIndex) has simple perfect hash functions since the 
boundary conditions are known at start.  Local memory access roughly 
favours tiling levels > tiling level > tile row > tile according to 
the given code, but I am wary of less obvious yet still important 
observations that may be missed.


Does this sound about right?  Are there any better options I have 
flown right past?

Thank you.



Cheers,
Darren Grant