Processing 1.0 - Processing Discourse - Slow collision detection within Particle System

We closed this forum 18 June 2010. It has served us well since 2005 as the ALPHA forum did before it from 2002 to 2005. New discussions are ongoing at the new URL http://forum.processing.org. You'll need to sign up and get a new user account. We're sorry about that inconvenience, but we think it's better in the long run. The content on this forum will remain online.

Index › Programming Questions & Help › Syntax Questions › Slow collision detection within Particle System

‹ Previous Topic | Next Topic ›

Pages: 1

Slow collision detection within Particle System (Read 1514 times)

Bender

Slow collision detection within Particle System
May 5^th, 2010, 12:36am

I made a simple particle detection system to check if particles in a particle system collide.

But it is really processor intensive, when using over 400 particles (simple white dots) it becomes really slow.

This is my detectioncode:
Code:


void detectCollision(PVector b, PVector c, Particle id) {
  dx = c.x - b.x;
  dy = c.y - b.y;
  dist = sqrt(dx*dx + dy * dy);
	
  if (dist < radius) {
    id.stop();
    println("collision detected");
  }
}

It basically calculates the distance between two particles found in an ArrayList by looping through it twice:

Code:


for (int i = 0; i < particle.size(); i++) {
  Particle b = (Particle) particle.get(i);
  b.move();
  b.display();

  for(int j = 0; j < particle.size(); j++) {
    if (i != j) {
    Particle c = (Particle) particle.get(j);
    detectCollision(b.getPosition(), c.getPosition(), c);
    }
  }
}

The code for the particles and the particle system is based on the code of Daniel Shiffman

Are there better ways detect collisions between a lot of particles

TfGuy44

Re: Slow collision detection within Particle System
Reply #1 - May 5^th, 2010, 2:21am

Quote:

for (int i = 0; i < particle.size(); i++) {
Particle b = (Particle) particle.get(i);
b.move();
b.display();
PVector b_pos = b.getPosition;
for(int j = 0; j < particle.size(); j++) {
if (i != j) {
Particle c = (Particle) particle.get(j);
PVector c_pos = c.getPosition();
if( dist( b_pos.x, b_pos.y, c_pos.x, c_pos.y ) < radius ){
c.stop();
println("collision detected");
}
}
}
}

I'm no timing expert, but removing math, a function call, and any duplicate work should (I hope) be faster. Please note: I haven't tried running this myself!

JohnG

Re: Slow collision detection within Particle System
Reply #2 - May 5^th, 2010, 2:41am

Unfortunately that method of doing collision detection gets slow fast, it's O(n^2), that is the length of time it takes to do the calculations in the worst case is related to the square of the number of particles. So for 20 particles it's only 400 calculations at worst.. for 400 it's 160,000 calculations every single frame.

If you want to use a lot of particles that only ever interact when they actually hit (no repulsion at a distance) you'll can make this a lot better, by having some sort of funky storage system that has "boxes" and stores particles in a certain area in the same box, and only checks particles against those in the same box and neighbouring ones, but not any further away than that, which whilst at the worst is just as bad, in the normal case is a lot faster.

Bender

Re: Slow collision detection within Particle System
Reply #3 - May 5^th, 2010, 2:44am

Thanks. Your code works, but it's not really faster. It does seem to help a bit.

I think the main problem is the fact that processing has to calculate for each particle the distances between the other particles. Ergo, if you have 4000 particles, processing needs to calculate something like 4000^2 distances each cycle.

Is this the right way to do it?

edit:
ah I was a bit slow, JohnG is referring to the same

PhiLho

Re: Slow collision detection within Particle System
Reply #4 - May 5^th, 2010, 2:50am

There are better way, as said above. It is known in general as quad trees, IIRC (there is a Wikipedia article on the topic), ie. splitting the plane (or 3D space) with a grid (regular or not) and checking only the particles in a grid cell and around. It can cut down dramatically the check time.
See also the Hash Grid library.

Bender YaBB Newbies Offline Posts: 8	Re: Slow collision detection within Particle System Reply #5 - May 5^th, 2010, 3:01am Thanks, that Hash Grid library looks worth checking out! I guess I'm going to read a fair bit about quad trees too

Smitty

Re: Slow collision detection within Particle System
Reply #6 - May 5^th, 2010, 12:13pm

You can speed up your existing code a bit by removing the sqrt call and just comparing d^2 to r^2:
Code:


void detectCollision(PVector b, PVector c, Particle id) {
  dx = c.x - b.x;
  dy = c.y - b.y;
  distSquared = dx * dx + dy * dy;
	
  if (distSquared < radius*radius) {
    id.stop();
    println("collision detected");
  }
}

If all the particles have the same radius, you can save a little more by e.g., setting radiusSquared = radius*radius and just using that.

It's still an O(n^2) algorithm (with the weaknesses PhiLho and JohnG explain above) but this change will get you a little more breathing room.

koogy

Re: Slow collision detection within Particle System
Reply #7 - May 5^th, 2010, 2:01pm

for (int i = 0; i < particle.size(); i++) {
for(int j = 0; j < particle.size(); j++) {

by nesting loops like this you're comparing everything twice. it's symmetrical, distance from a to b == distance from b to a

for instance when i = 2 and j = 1 and when i = 1 and j = 2 it's the same compare.

using
for (int i = 0 ; i < ...)
for (int j = i + 1 ; j < ...) // start from right of diagonal
reduces it from n^2 to n(n-1)/2, in your case from 160,000 to 79,800

you'll need another loop for your move and display though.

Pages: 1

‹ Previous Topic | Next Topic ›