Quadtree Particle System

#1

After seeing Zach’s binning-based-particle-system, I was curious to see how quadtrees would handle the same problem.

Here are 12k particles in real time with mouse interaction:


http://www.flickr.com/photos/kylemcdonald/4095854075/


http://www.flickr.com/photos/kylemcdonald/4096670086/

I attached a first revision to this post, or the code can be checked out via SVN:

http://code.google.com/p/kyle/source/browse/trunk/openframeworks/apps/demos/

The quadtree approach comes from the Barnes-Hut-algorithm, which is used for approximating the effects of gravity on systems with tens of millions of particles (generally for astrophysics). It’s based on the idea of treating distant clusters as single objects by recursively computing their centroid and total mass. I implemented Barnes-Hut first:


http://www.flickr.com/photos/kylemcdonald/4096614100/

And used a modified version of the data structure to do fast two dimensional lookup. There is a function in the Tree class that I’m going to reuse, called getNeighbors(). It does an efficient recursive search on the data to return nearby particles.

The main advantage of quadtrees over binning is that they are scale-independent. You could have a huge screen or a small screen, or tons of offscreen particles, and you don’t have to worry about the number of bins because the data structure adapts to the particle distribution.

I thought this would be more helpful as a demo than an addon, but feel free to drag the code around and reuse it. The particle system should be easy to use:

  
  
class ParticleSystem {  
protected:  
  float timeStep;  
  vector<Particle> particles;  
  Tree* tree;  
  
public:  
  ParticleSystem();  
  
  void setTimeStep(float timeStep);  
  
  void add(Particle& p);  
  vector<Particle*> getNeighbors(float x, float y, float radius) const;  
  unsigned size() const;  
  Particle& operator[](unsigned%20i);  
  
  void setupForces();  
  void addRepulsionForce(const Particle& particle, float radius, float scale);  
  void addRepulsionForce(float x, float y, float radius, float scale);  
  void addAttractionForce(const Particle& particle, float radius, float scale);  
  void addAttractionForce(float x, float y, float radius, float scale);  
  void addForce(const Particle& particle, float radius, float scale);  
  void addForce(float x, float y, float radius, float scale);  
  void update();  
  
  void draw();  
};  
  

And the usage pattern is similar to Zach’s:

  
  
void testApp::setup(){  
  for(int i = 0; i < n; i++) {  
    // create particles with initial velocities  
    Particle particle(x, y, xv, yv);  
    particleSystem.add(particle);  
  }  
  particleSystem.setTimeStep(1);  
}  
  
void testApp::update(){  
  particleSystem.setupForces();  
  
  // apply per-particle forces  
  for(int i = 0; i < particleSystem.size(); i++) {  
    Particle& cur = particleSystem[i];  
    // global force on other particles  
    particleSystem.addRepulsionForce(cur, 3, 1);  
    // forces on this particle  
    cur.bounceOffWalls(0, 0, ofGetWidth(), ofGetHeight());  
    cur.addDampingForce();  
  }  
  // single global forces  
  particleSystem.addAttractionForce(ofGetWidth() / 2, ofGetHeight() / 2, 1500, 0.01);  
  particleSystem.addRepulsionForce(mouseX, mouseY, 100, 2);  
  particleSystem.update();  
}  
  
void testApp::draw(){  
  particleSystem.draw();  
}  
  

QuadtreeParticleSystem.zip

2 Likes
Binning based particles system and precise collision numbering
#2

whoa!!!
thanks a lot for sharing :wink:

#3

I couldn’t help myself and had to try my own binning approach too. It should be faster than quadtrees anyway, right? It’s constant time (with respect to the neighborhood) instead of O(n log n) (where n is the number of particles).


http://www.flickr.com/photos/kylemcdonald/4099397347/

Turns out it is faster in this case (limited to on-screen particles, preallocated). The bottleneck comes more at the sqrtf calculation. I substituted that for the fast inverse sqrt trick: http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/ and of course still did the sqlength < sqradius comparison before doing the length itself.

When you set the neighborhood for particle-particle interaction small, this code can handle around 64k particles in realtime :slight_smile:

http://code.google.com/p/kyle/source/browse/#svn/trunk/openframeworks/apps/demos/BinnedParticleSystem

#4

nice stuff!!

we should set a 100K@30fps challenge :slight_smile:

1 Like
#5

Nice work Kyle!

#6

dang thats hot!

#7

I don’t think 100k @ 30 fps would be too hard with the right parameters. If I lower the neighborhood of the particles and up the resolution (which lowers the particles per bin without creating too many more bins) I can already get 100 k @ 20 fps. I think it really comes down to how many neighbors you need to compare forces against.

I also noticed: if you draw the forces as very transparent lines, and make the neighborhood large you get these dandelion type effects on explosions:


http://www.flickr.com/photos/kylemcdonald/4101019202/

#8

Screen capture on vimeo for anyone who’s interested but doesn’t want to compile the source :slight_smile:

http://vimeo.com/7890507

#9

Hey Kyle, This is an awesome example! I’ve been studying your code and I’ve learned a lot about particle system optimizations. I am going to implement my own quadtree system to better understand the technique.

The binning and quadtree optimizations are efficient for finding nearby particles, but what about optimizing a global attraction force, each particle attracted to each other particle? I was reading an article on science direct about particle binning and it also mentioned approximating the forces of distant particles by finding an average location for a group of particles. I think I may apply this concept to the quadtree and see what happens.

#10

Hey Tim, I’m glad you’ve been enjoying/learning with this code :slight_smile:

Almost all the images I posted are about optimizing collision-type effects. But the Barnes-Hut demo is about precisely what you describe: optimizing n^2 particle-particle interactions across the whole scene.

I posted a link above, but it was in passing so you might have missed it. Here it is again: http://www.eecs.berkeley.edu/~demmel/cs267/lecture26/lecture26.html

Tweaking the parameters of the Barnes-Hut demo should yield more classic gravity-like effects. http://code.google.com/p/kyle/source/browse/#svn/trunk/openframeworks/apps/demos/BarnesHut%3Fstate%3Dclosed

Also note that I never added the fast sqrt trick to the Barnes-Hut demo, which should offer a significant speed increase (line 167 of Tree.h).

Hope this helps!

#11

Wow, after reading the Barnes-Hut article, it seems that is is exactly what I just implemented! They beat me to it. I was getting really inaccurate particle-particle interaction, and that is exactly what the article says will happen. I end up getting a pretty cool X patterns in the particles though.

The article also mentions the Fast Multipole Method which I am looking into now.

I think I might use the binning system for a project I’m working on too because the speed increase is so great.

#12

that’s very cool man!

#13

Awesome stuff! I love going through the code for this and being amazed at how elegant it is. though i found a really strange and practically fatal bug (for the program at least). I run the Binning Example (the normal one, not the tree one) and then I went off to do something. I come back a few minutes later and I see this:

http://artem.posterous.com/running-a-binning-example

umm… graphics card failure? I had to forcefully shutdown my laptop.

#14

Wow, that’s absurd. I haven’t seen that before!

There is probably some edge case somewhere that says something like < instead of <= causing it. Let me know if you find it!

Also, I’m glad to hear you say the code is elegant! I try to write things in a way that is readable and efficient… so both other people and myself can understand it :slight_smile:

#15

It is absurd. But it got even worse!

http://artem.posterous.com/another-binning-failure

This time it just completely messed up the system. It could be a memory issue or something like the that since this doesn’t look like an ordinary SEG_FAULT or anything like that. I’ll look around a bit but this is really weird.

I seem to get an error in Particle::draw(). It’s complaining about EXC_BAD_ACCESS. Uninitialized var’s maybe.

#16

i’ve seen things like that before, usually the problem is the graphics card trying to access memory not allocated. normally when the program tries to do that from the cpu you get a seg fault and the program ends but when the gpu is who is trying to do some wrong memory access weird things like this can happen.

look for vertex arrays trying to read more vertexes that the allocated memory or something like that.

#17

Very weird. I don’t know about this one.

Arturo, there are no vertex arrays here (everything is drawn in immediate mode).

I would try commenting out portions of the particle system updating. Or maybe just the drawing? And see if that does anything.

#18

Kyle,

I’m loving your binned particle system. I’ve got it running at 25-30fps with 40k particles on a 2.2ghz C2D.

I’ve added some custom code to the particle update function to make each particle return to its original position automatically *AND* I’m using findNeighbors to add velocities to the particles from a flow field with over 26k points. I think that being able to do 26k checks and still have it running at 25-30fps is pretty amazing. I’ll try and upload a video of this working later.

Thanks for releasing the code- hope to be able to add some useful stuff soon :slight_smile:

Andy

1 Like
#19

Awesome, looking forward to seeing a video.

I think I mentioned in a post above that the Quadtree system doesn’t use the fast sqrt approximation, and that you could speed things up even more with that.

#20

Here you go http://vimeo.com/10419226

Vimeo compression kinda ruined the video quality, but you get the idea. The particles are actually multicoloured and blend together to make the white logo