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();
}
