Jump to content

  • Log In with Google      Sign In   
  • Create Account


Space partitioning for flocking


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
15 replies to this topic

#1 ardmax1   Members   -  Reputation: 127

Like
0Likes
Like

Posted 04 July 2012 - 03:43 PM

Hi,
I'm looking for space partitioning structure which will be good for moving points and will enable fast fixed radius near neighbors search.

Sponsor:

#2 RubyNL   Members   -  Reputation: 154

Like
1Likes
Like

Posted 04 July 2012 - 03:48 PM

Well, you could use binary space partitions or quadtree's, which are probably easier for 2d things, or even octrees which are easier to use with 3d things.
Or, you can just use a grid, when each cell in the grid has a pointer to the objects in it, the objects only have to check for collisions with objects that are in the same cell.

#3 raigan   Members   -  Reputation: 655

Like
1Likes
Like

Posted 04 July 2012 - 05:47 PM

A simple grid is what I would try first, they're the easiest thing to implement and often very effective (especially for uniform size/fixed radius).

See Ericson's Real-Time Collision Detection for a terrific chapter on various ways to implement and use grids.

#4 jefferytitan   Crossbones+   -  Reputation: 1983

Like
0Likes
Like

Posted 04 July 2012 - 05:57 PM

I'd go for grid. Simple, plus no re-partitioning as the points move.

#5 LorenzoGatti   Crossbones+   -  Reputation: 2629

Like
0Likes
Like

Posted 05 July 2012 - 02:36 AM

I second the grid, since presumably your objects are all the same size and you can tune the size of the grid cells.
Produci, consuma, crepa

#6 ardmax1   Members   -  Reputation: 127

Like
0Likes
Like

Posted 05 July 2012 - 05:47 AM

But with grid I would need to search 9 cells right? And what if I would need different radius in future? Anyway I'll test the grid thing. I should also mention that this its in 2d and I'm just using points if that helps in some case.

#7 jefferytitan   Crossbones+   -  Reputation: 1983

Like
0Likes
Like

Posted 05 July 2012 - 06:09 AM

9 is pretty arbitrary. Whatever size grid works well. The key is that the grid is only for reducing the candidates for comparison, not doing the actual comparison. Say you have a flock of 64 objects. If you use a grid of size 8 by 8, on average there will be 1 object per cell (obviously for flocking some cells would have more). Based on this average you would need to do distance checks for the objects in a cell with the contents of that cell and the directly neighbouring cells too. So around 8 distance comparisons per cell. Which may seem like a lot, but still miles better than comparing every object to every other object.

Excuse my late-night mathematics skills if there are errors. ;)

#8 samoth   Crossbones+   -  Reputation: 4661

Like
1Likes
Like

Posted 05 July 2012 - 06:15 AM

Alternatively, skip the partitioning and instead only do a fixed number of distance checks at all. There's research that real flockers (i.e. birds, fish) do that same thing too. Not sursprising if you think about it, a fish brain isn't so terribly huge.

Looking at half a dozen randomly selected (not necessarily nearest) neighbours pretty accurately simulates real flocking.

#9 taby   Members   -  Reputation: 335

Like
0Likes
Like

Posted 05 July 2012 - 01:59 PM

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.

#10 h4tt3n   Members   -  Reputation: 1001

Like
0Likes
Like

Posted 05 July 2012 - 02:49 PM

But with grid I would need to search 9 cells right? And what if I would need different radius in future? Anyway I'll test the grid thing. I should also mention that this its in 2d and I'm just using points if that helps in some case.


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).

#11 jefferytitan   Crossbones+   -  Reputation: 1983

Like
0Likes
Like

Posted 05 July 2012 - 04:22 PM

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.

#12 LorenzoGatti   Crossbones+   -  Reputation: 2629

Like
0Likes
Like

Posted 06 July 2012 - 10:59 AM

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.
Produci, consuma, crepa

#13 ardmax1   Members   -  Reputation: 127

Like
0Likes
Like

Posted 06 July 2012 - 11:30 AM

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?
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[i] = vector< vector< Bird* > >(ccx);
		for( int j = 0; j < ccx; j++ ){
			cells[i][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[i][j].begin(), cells[i][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;
	}
}


#14 h4tt3n   Members   -  Reputation: 1001

Like
0Likes
Like

Posted 06 July 2012 - 12:28 PM

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

Edited by h4tt3n, 06 July 2012 - 12:56 PM.


#15 raigan   Members   -  Reputation: 655

Like
1Likes
Like

Posted 08 July 2012 - 05:53 PM


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


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 Posted Image

Edited by raigan, 08 July 2012 - 05:54 PM.


#16 h4tt3n   Members   -  Reputation: 1001

Like
0Likes
Like

Posted 09 July 2012 - 05:36 AM

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




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS