I don't think that 3*3 = 9 is an arbitrary number any more than 3*3*3 = 27 is... As long as the sphere's radius is less than or equal to the cell size.

As stated, late at night. ;) I thought he meant a 3 x 3 grid (which is pretty coarse and not very helpful), but he probably meant the same thing that I said.

No, you only need to check for collision in the 4 neighbouring cells with a higher number. That is the neighbour to the right and the three neighbours below (assuming cell 0 is top left corner and last cell is bottom right corner).

If you need to find objects whose center is within a radius R around the center of each object, the best grid size is a 2R by 2R square: every disc straddles up to 4 cells, so if you assign objects to the cell containing the upper left corner of the 2R by 2R AABB of their region of interest you only need to check the objects in the same cell and the three adjacent cells to the right, to the bottom and diagonally to the bottom right.

First try with grid i got 4 times more (1k to 4k) birds without fps drop, but I'm sure it can be faster. Any idea how to optimize it?
[source]Grid::Grid( Flock* flock, float cellsize ) {
min = flock->min - flock->max / 2;
max = flock->max * 1.5f;

this->cellsize = cellsize;
ccx = (int)((max.x - min.x) / cellsize) + 1;
ccy = (int)((max.y - min.y) / cellsize) + 1;

cells = vector< vector< vector< Bird* > > >(ccy);
for( int i = 0; i < ccy; i++ ){
cells = vector< vector< Bird* > >(ccx);
for( int j = 0; j < ccx; j++ ){
cells[j] = vector< Bird* >();
}
}

for( auto b : flock->birds ){
int cx = (int)((b->pos.x - min.x) / cellsize);
int cy = (int)((b->pos.y - min.y) / cellsize);
b->cx = cx; b->cy = cy;
cells[cy][cx].push_back( b );
}
}

Grid::~Grid() {}

vector< Bird* > Grid::getNeighbors( float x, float y, float r ){
int cx = (x - min.x) / cellsize;
int cy = (y - min.y) / cellsize;

vector< Bird* > ret;
int m = ceil( r / cellsize );
for( int i = cy-m; i <= cy+m; i++ ){
for( int j = cx-m; j <= cx+m; j++ ){
if( j < 0 || i < 0 || j >= ccx || i >= ccy )
continue;
ret.insert( ret.end(), cells[j].begin(), cells[j].end());
}
}

return ret;
}

void Grid::update( Bird* bird ){
int cx = (bird->pos.x - min.x) / cellsize;
int cy = (bird->pos.y - min.y) / cellsize;

if( bird->cx != cx || bird->cy != cy ){
auto cell = &cells[bird->cy][bird->cx];
cell->erase( remove( cell->begin(), cell->end(), bird ) );
cells[cy][cx].push_back( bird );

bird->cx = cx; bird->cy = cy;
}
}
[/source]

If you need to find objects whose center is within a radius R around the center of each object, the best grid size is a 2R by 2R square: every disc straddles up to 4 cells, so if you assign objects to the cell containing the upper left corner of the 2R by 2R AABB of their region of interest you only need to check the objects in the same cell and the three adjacent cells to the right, to the bottom and diagonally to the bottom right.

Neat trick, will implement this in my sph simulations.


Edit: Are you sure about this? After doing some pen-and-paper experiments it was easy to construct a scenario where a particle collision is not detected. If sphere A's top left AABB corner is in cell(x, y) and Sphere B's AABB top left corner is in cell(x-1, y+1) then a collision can never be detected.

cheers,
Mike

[quote name='LorenzoGatti' timestamp='1341593992' post='4956375']
If you need to find objects whose center is within a radius R around the center of each object, the best grid size is a 2R by 2R square: every disc straddles up to 4 cells, so if you assign objects to the cell containing the upper left corner of the 2R by 2R AABB of their region of interest you only need to check the objects in the same cell and the three adjacent cells to the right, to the bottom and diagonally to the bottom right.

Neat trick, will implement this in my sph simulations.


Edit: Are you sure about this? After doing some pen-and-paper experiments it was easy to construct a scenario where a particle collision is not detected. If sphere A's top left AABB corner is in cell(x, y) and Sphere B's AABB top left corner is in cell(x-1, y+1) then a collision can never be detected.

cheers,
Mike
[/quote]

I *really* recommend Ericson's "Real-Time Collision Detection", seriously: the chapter on grids covers several different aspects of implementation, including different ways to approach querying and storing objects in cells (including the 4- vs 9-way search), different ways to approach updating the cell occupancy, etc., it's great.

Seriously... I thought I knew something about different ways to use grids, then I read the chapter on grids, and I realized how little I knew

Okay, I'll see if I can pick up a copy somewhere.