Yesterday Paul Rouget from Mozilla asked how to uniformly arrange points within a circle. There are a few existing algorithms to do this, but I was interested in seeing if I could use simple physics to create a stable system to distribute the particles evenly.

In the end I don’t think Paul could use them, (although I put him in touch with Mario who came up with slick solutions) but I enjoyed the process and found the results very pleasing!

Click on each thumbnail to see the effects in action. Tip : click to make more particles!

So how did I go about making this system?

I searched the dark recesses of my mind for a recollection of Robert Hodgin explaining the physics for his Magnetosphere : I needed to build a similar system where all particles repel each other.

To start with, I made a simple particle system with position, velocity and drag, explained in these two tutorials here and here if you need a refresher.

I’m using my own Vector object to store position and velocity. Vectors are critical to this type of visual programming, and if you haven’t used them before, it’s worth spending some time getting your head around them. Try this tutorial (based around Processing but still relevant).

Once we have that running we check all the particles against each other. We have an array of particle objects and we iterate through them in a nested loop :

for (i=0; i<particles.length-1; i++){ var p1 = particles[i]; // the first particle for(j=i+1; j<particles.length; j++) { var p2 = particles[j]; // the second particle // compare p1 to p2 here... } } |

If we have 5 particles :

0 1 2 3 4

The first time around the inner loop i will be 0 and j will go from 1 to 4 :

i : 0 0 0 0 j : 1 2 3 4

the second time around :

i : 1 1 1 j : 2 3 4

third time :

i : 2 2 j : 3 4

final time :

i : 3 j : 4

For each comparison we work out the repulsion between the two particles: the closer they are, the more they repel, and we’ll store this value in repelforce vector. First, we set this to the vector between p1 and p2 :

repelforce.copyFrom(p2.position); repelforce.minusEq(p1.position);

then we get the length or magnitude of that vector :

mag = repelforce.magnitude();

We calculate the repel force strength by subtracting the magnitude from 50 : the resulting value increases the closer the particles are.

repelstrength = 50-mag; |

If the force is less than 0, it means that the particles are further than 50 pixels apart, and no force should be applied. Otherwise, we have to work out a repelforce vector to apply to each particle’s velocity.

To do this, we divide the repelforce vector by its magnitude. This process is known as normalisation and it returns a unit vector : a vector with the same angle as before but with a length of 1.

repelforce.divideEq(mag);

The great thing about unit vectors is that you can multiply them by any value to get a vector with a length of that value. So if we multiply it by our repelstrength, we’ll have our repelforce vector :

repelforce.multiplyEq(repelstrength);

Except, we need to multiply that force by a small amount to make it less intense.

repelforce.multiplyEq(repelstrength*0.025);

If we want our particles to repel more use a number higher than 0.025, if you want it to be more subtle go lower. I played around with this value until it seemed to work well.

Of course this division and multiplication can be combined into one call so

repelforce.divideEq(mag); repelforce.multiplyEq(repelstrength*0.025);

can be simplified into :

repelforce.multiplyEq(repelstrength*0.025/mag);

Each particle object has a force vector that we use to add up all the various forces for every frame update. As the force currently works in the direction from p1 to p2 it can be added to p2’s force to push it away from p1 :

p2.force.plusEq(repelforce);

We want p1 to go the opposite direction, so we subtract it from p1’s force:

p1.force.minusEq(repelforce);

All that’s left is a very similar calculation of a force that stops the particles getting too far from the centre and we have a system! :

The great thing about vector maths is that it also works in 3D with no changes at all! So a quick conversion into three.js and we have this :

It seemed a bit chaotic so forced the particles onto the surface of a sphere:

See it in action here.

(Particle image courtesy of Mr.doob’s additive blend three.js particle example)

Wow. It’s taken me all afternoon to explain this, and I’m not entirely sure I’ve done that good a job! Please feel free to ask questions, and if you know this stuff well, perhaps you could point out where I could have explained things better.

awesome stuff. totally makes sense.

Great post! What browser / OS are you using in the video to get that performance?

Thank you! It’s Chrome 8 on OSX MacBook Air.

Great post, thinking in terms of vectors vs coordinates really opened up the possibilities of what you can do with code.

One bit of code I’ve always had trouble with was comparing particles without getting into some nasty semi infinite looping (1*2*3*4*5…). I’ve previously used booleans which slowed down the processor tremendously and left me with unusable code. That simple line of adding i to j in that second for() loop opened/reopened up a ton more possibilities for me.

Thanks Mannytan! Funny how those logical things can trip us up. I’m pretty sure I first saw that nested loop from Keith Peters. I haven’t mentioned him for a while so it’s about time really ðŸ™‚ Seb

To be fair, wasn’t the initial question inquiring for a O( N ) solution? Clearly what we have here is O( N^2 ) even for a constant number of iterations.

Furthermore, “50 – d” seems kind of arbitrary. Did you try using Maxwell’s law of electromagnetic fields? That’d give something along the lines of “1 / d^2” (again, as you do now, you may need a constant to make up for too strong or too weak fields), and I’d expect it to look more natural since … it’s what real world magnets do! ðŸ™‚

Keep up the good work, I love this kind of posts. The fact that you have hands-on visual examples with simple explanations is simply great.

Thanks Dionysis!

Yep I totally ignored Paul’s request ðŸ™‚ Although you could add a grid system to convert this to O(N). 50-d makes for a completely linear response, I was going to try a more “realistic” 1/d^2 (and could improve performance as we could potentially lose the sqrt). To be perfectly honest I was surprised it worked so well and so quickly! I’ll see what happens with the improved attraction formula. Thank you so much for the feedback. Seb

Love it!

Now a couple ideas to make it more atomic..

Don’t let a particle be at the center point (point of attraction).

Let particles have an +1 or -1 “spin” and if they add to zero they can couple, and have a combined repulsion.

The coupling will give you a better distance between energy level shells

Hi Seb, i’d like ask one thing and sorry if i’m being an idiot of ask for this, but everything that you’re showing here is html5 ready? I mean, any library wasn’t added to achieve get this?

Congratulations, your posts always are inspiring.

Thats damn cool seb, hope you show it off at FlashCampBirmingham ðŸ™‚

should have mentioned, getting really good performance here too, 60FPS in Chrome, W7 ðŸ™‚

Pingback: Roundup for February 3rd, 2011 | Stories In Flight

Pingback: links for 2011-02-03 at â‰ˆ Relations

Pingback: JavaScript Magazine Blog for JSMag » Blog Archive » News roundup: the performance of feature detection, Mobile Firefox 4 performance, W3C Touch Events

this is really slick Seb. So much to think about. Thank you very much.

Hi Seb,

Great article! Your idea of using forces matches some technics used to lay out graphs: the Fruchtermann & Reingold algorithm uses the same idea of nodes repelling each other, and also uses an attraction forces to group nodes that stand “close” in the graph. You can see it in actions in Gephi, a great software for graph visualization.

Cheers,

Martin

Seb,

Your particle system is amazing. I have a question though. How can I implement a bounding box instead of a circle? It would be great if you could help me out with that.

Thanks.

Wow, this post is 1 year old now but I’m reading this while experimenting with force based particles. Thanks for this simple, detailed but awesome tutorial! =)

you’re welcome! Really glad it helps Joshua.