how to improve performance for particle systems

flowen

dear creatives,

I'm building a particle system, based on Daniel Shiffman's code from nature of code. Drawing triangle vertices when distance is within the defined range. Quite fast I get massive fps drops, which i sort of expected as it's 3 loops within each other.

I've been briefly told about binned particle system, for which I could only find some old thread containing dead links. https://forum.libcinder.org/topic/kyle-mcdonald-s-binned-particle-system

I wonder if there are other known techniques like this and if you know some resources or perhaps even a tutorial ;)

Thx in advance

Chrisir

show your code

why 3 loops? shouldn't it be 2?

and remember to compare each pair only once, not twice

flowen

I just don't understand how to format code on this forum..

for (int i = particleList.size()-1; i >= 0; i--) {
   //display particles
    Particle p = particleList.get(i);
    p.update();
    p.display();`
       for (int j = particleList.size()-2; j >= 0; j--) {
          Particle p2 = particleList.get(j);
          if ( dist(p.pos.x, p.pos.y, p2.pos.x, p2.pos.y) < maxDistance ) {

            for (int k = particleList.size()-3; k >= 0; k--) {
              Particle p3 = particleList.get(k);

              if ( dist(p3.pos.x, p3.pos.y, p2.pos.x, p2.pos.y) < maxDistance ) {
             //draw particles

koogs

edit post, highlight code, hit ctrl-o.

Chrisir

for (int i = particleList.size()-1; i >= 0; i--) {

  //display particles

  Particle p = particleList.get(i);
  p.update();
  p.display(); 

  for (int j = particleList.size()-2; j >= 0; j--) {

    Particle p2 = particleList.get(j);

    if ( dist(p.pos.x, p.pos.y, p2.pos.x, p2.pos.y) < maxDistance ) {

      for (int k = particleList.size()-3; k >= 0; k--) {
        Particle p3 = particleList.get(k);

        if ( dist(p3.pos.x, p3.pos.y, p2.pos.x, p2.pos.y) < maxDistance ) {
          //draw particles

koogs

please explain your for loops.

why iterating backwards?

why -1, -2, -3?

i think your outer loop should iterate over everything

the middle loop should iterate over everything after the current outer loop index

the inner loop should iterate over everything after the current middle loop index.

it's a 3d case of this

  0 1 2 3
0 . A B C
1 A . D E
2 B D . F
3 C E F .

there's no point in checking (0,1) AND (1,0), as that is the same check. similarly (0, 0), (1, 1) etc is invalid (checking against itself)

Chrisir

line 9 :

for (int j = particleList.size()-2;

better :

for (int j = i-1;

because then you start behind the current i (this is my remark: remember to compare each pair only once, not twice)

koogs

you should move all the points in a separate loop, before checking for neighbours. you're checking for closeness BEFORE moving, they might not be close after moving.

how big is particle list? you are currently doing n^3 checks

flowen

Hm I thought initially it would be cheaper to only loop when its within maxdistance. But of course: when many particles are close, a lot of loops will be triggered. So

@koogs : I had the backwards loop because I wanted to remove particles at different events, but using .remove() changes the index and that could potentially skip certain particles. Except for going backwards, right?

Currently if I have 70-80+ particles, i get framedrops when most of them are within maxDistance. So too many loops as you said.

I get your approach! makes sense, I thought I was doing it but clearly not :) I'm going to try and post the code

@Chrisir : How could I check with only 2 loops? I need to check distances for at least 3 particles to get triangles right?

jeremydouglass

@flowen -- if you are looking at binned particle system optimization, you'll find related discussions under Processing forum thread about collision detection -- in particular, about "spatial partitioning".

I seem to remember that someone on the forum has a large particle system spatial partitioning demo sketch with a full GUI interface, and that it came up in the last few months... I just can't find it right now. Anyone?

koogs

80 * 80 * 80 = 510,000

int count = 0;
int SIZE = 80;

for (int x = 1 ; x < SIZE ; x++) { // skip 0
  for (int y = x + 1 ; y < SIZE ; y++) { // skip all x values
    for (int z = y + 1 ; z < SIZE ; z++) { // skip all y values
      count++;
    }
  }
}
println(count);

gives ~80k comparisons, about 6% of 500k. (actually, that sounds too good to be true, i am doubting myself now)

yes, iterate backwards if you are removing particles. but moving / deletion should both be part of the update loop before the distance comparison / triangle drawing loop otherwise you're linking to items that you may later move or delete.

flowen

@jeremydouglass : Thanks for your reply! Lots of interesting information.. now time to learn what it all means :)

@koogs : i've tried exactly that, but I cannot spot any performance improvements, let me post the exact code (there's of course a lot more going on, OSC, MIDI, etc but only posted whats concerned with the loops and particles). Wouldn't be surprised if I did something stupid:)

void setup() {
  background(0);

  particleList = new ArrayList<Particle>();
  attractorList = new ArrayList<Attractor>();

  addParticles(particlesLength);

  for (int i = 0; i < 5; i++) {
    float wOffset = width/3,
          hOffset = height/3,
          x = random(wOffset, width-wOffset),
          y = random(hOffset, height-hOffset);
    attractorList.add(new Attractor(x, y));
  }
}

void draw() {

  //display attractors
  for (int i = attractorList.size()-1; i >= 0; i--) {
    Attractor a = attractorList.get(i);
    a.display();
  }

  for (int i = 1; i < particleList.size(); i++) {
    Particle p = particleList.get(i);
    p.update();
    p.display();

    if (attractParticles) {
      for (int j = attractorList.size()-1; j >= 0; j--) {
        // get attraction and apply on all particles
        Attractor a = attractorList.get(j);
        PVector attraction = a.calculateForce(p);
        p.applyForce(attraction);
      } 
    }

    // check if particles are within maxDistance and draw vertices
    for (int j = i+1; j < particleList.size(); j++) {
      if (j > 0) {
        Particle p2 = particleList.get(j);

        if ( dist(p.pos.x, p.pos.y, p2.pos.x, p2.pos.y) < maxDistance ) {
          for (int k = j+1; k < particleList.size(); k++) {
            Particle p3 = particleList.get(k);

            if ( dist(p3.pos.x, p3.pos.y, p2.pos.x, p2.pos.y) < maxDistance ) {
              float whiteFlash = map(kickFollower, .4, .75, 0, 255);

                    stroke(255, whiteFlash);
                    fill(255, whiteFlash);
                    beginShape(TRIANGLES);
                    vertex(p.pos.x, p.pos.y);
                    vertex(p2.pos.x, p2.pos.y);
                    vertex(p3.pos.x, p3.pos.y);
                    endShape();
                    break;
            }
          }
        }
      }
    }
  }
}

}

jeremydouglass

@flowen re: me saying:

"I seem to remember that someone on the forum has a large particle system spatial partitioning demo"

...found it, link and description of getting it working in this thread:

• https://forum.processing.org/two/discussion/18326/what-is-the-best-way-to-show-many-images-together

Edit: oh, looks like you actually found it already!

koogs

Couple of obvious things looking at your code (but not running it)

You don't need line 42, j is never 0

Try squaring the distances, removing the sqrt.

Use triangle rather than a separate shape for every one. Or move the beginShape outside the outermost loop.

You are still updating and linking particles in the same loop. Do all the updating before the linking.

A runnable example would be better.