 |
Author |
Topic: particle magnet (help) (Read 10072 times) |
|
Charles Hinshaw
 
|
particle magnet (help)
« on: Apr 21st, 2004, 7:10pm » |
|
Hello to everybody in Processing land.
I have a question -- it is more of a conceptual nature as to how you would go about doing something.
I want to make an object (of which there could be a random number of on the screen) that draws particles (say - again, a random number (albiet much larger than the number of magnets), randomly strewn about) towards it, until it is "full" somewhere between 50-75 pixels.
As I am not a programmer (I'm one of the "artists" that processing has sucked in) I was wondering how to think like a programmer on this problem.
Any insight would be great.
Thanks.
|
Charles Hinshaw
PHAERSE
http://www.phaerse.com
|
|
|
miked
|
Re: particle magnet (help)
« Reply #1 on: Apr 21st, 2004, 8:57pm » |
|
Hi Charles,
This sounds like a physics problem to me (unfortunately, everything sounds like a physics problem to me these days)!
What you're describing could be modeled as a simulation of charged particles interacting. For example, your "magnets" are objects with a large positive charge, and your "particles" are objects with a small negative charge. The positively charged particle generates an electric field that attracts the negatively charged ones, in a process described by Coulomb's Law.
Here is an example of what I'm talking about. Unfortunately, it's not done in Processing, but in Director (Shockwave), mainly because I already had the code lying around and haven't ported it to Processing yet. Click on the red sphere in the middle and press "+" ("=") to increase it's charge, and "-" to decrease it's charge. Note how the negatively charged particles (the blue spheres) are attracted to it. You have to be careful not to increase the charge too quickly or things will go wild. 
http://web.mit.edu/mdanzig/www/attractiontest.htm
There's some other stuff going on here that I won't get in to right now (ie. a "Pauli Force" that keeps the particles from collapsing in on each other, and the fact that the negatively charged particles are interacting with each other as well, which you may not want), but I offer it as a conceptual example.
There are any number of ways you could modify something like this to suit your needs. You mentioned that you wanted them to "fill up", which actually happens automatically in this physical simulation. A large positive charge will pull in smaller negative charges until their "total" charge (ie. the charge of the positive particle and all the negative particles combined) cancels itself out and reaches zero. If you study physics or chemistry, this is basically what "shielding" is all about. A nucleus with some positive charge captures an electron, which effectively reduces the charge of the nucleus slightly. Hence, other electrons out in space are slightly less attracted to that nucleus until, eventually, the net charge on it is zero, at which point it is no longer an ion (ie. doesn't attract electrons anymore). But I digress...
If you're interested I can give you a bit more information.
(also, shameless plug for TEAL at MIT... this example is based on some of the work I've done for the TEAL project for freshman physics at MIT: http://web.mit.edu/8.02t/www/802TEAL3D . Electromagnetism visualized! yay! )
Hope this helps,
-mike
|
|
|
|
|
Charles Hinshaw
|
Re: particle magnet (help)
« Reply #2 on: Apr 21st, 2004, 11:01pm » |
|
Mike -
That is actually very similar to what I am going for.
What I am building is a tool for creating animations from two black and white images. The pixel values from the first map is used to launch particles -- a white pixel, for example, will give birth to 0 particles, while a black one will give birth to 100 particles. The particles then cloud up, each a 1x1x1 pixel cube with an alpha value of 1/100, and go about their business, but, to make the animation, eventually, they need to go through the reverse process with the final image, which, after looking at your shockwave example, might be best to do by taking the pixel values for that image and using them to determine the ammount of positive charge that an invisible particle in that x,y location has -- the charge could then, over time, be ramped up to that point, until all of the final particles are in their new locations -- my concept of "filling up" a location meant that if the location has a darkness value of 70, and each particle is 1/100th of an alpha, it needs to end up with 70 particles in it.
So, that said, and assuming that your attraction concept is the best way to solve this, how does one implement coulomb's law?
Charles
|
Charles Hinshaw
PHAERSE
http://www.phaerse.com
|
|
|
arielm
|
Re: particle magnet (help)
« Reply #3 on: Apr 21st, 2004, 11:10pm » |
|
wow, thanks mike for pointing us to this TEAL project, really an awesome one!
|
Ariel Malka | www.chronotext.org
|
|
|
miked
|
Re: particle magnet (help)
« Reply #4 on: Apr 22nd, 2004, 12:18am » |
|
Hi Charles,
After reading your description of what you want to do, I'm not sure treating it as a charged particle simulation is necessarily the most efficient way to go about that sort of thing. It sounds like you want to do some kind of "morphing" transition between two images, in which case you may want to consider using some sort of convolution algorithm. There's a lot of info about convolution on these boards, everyone here seems to love it . I'm pretty sure I saw an example here where a "cloud" of particles solidified in to another form, but I can't seem to find it right now.
That being said, if you want to go the route of particle dynamics simulation, the algorithm is pretty simple. First off, the electric force is functionally identical to the gravitational force, so if you've ever done any gravitational orbit stuff, it's pretty much the same. Basically, an electrically charged point-object (ie. a point charge, which has no dimension) generates an electric field given by:
E = [some constants]* ( q / r^2 )
where "q" is the charge of the object generating the field, and "r" is the distance from that object where you're measuring the field.
Next, generally speaking, the electric force felt by a charged object sitting in an electric field is given by:
F = q * E
where "q" is the charge of the object sitting in the field, and "E" is the value of the field at that point.
So, to figure out how all of your particles are going to move, you just need to calculate the force on each particle (the second equation). To find that force, you need to know the total electric field at the position of each particle. The total field at that point will be given by the sum of the individual fields generated by each of the other particles (first equation).
In a simple two particle case, with two charges q1 and q2, the force on each particle is given by:
force on q1 = q1 * ([constants] q2 / r^2)
where "r" points FROM q2 TO q1.
force on q2 = q2 * ([constants] q1 / r^2)
where "r" points FROM q1 TO q2.
Doing this for a many-particle system is simply the extension of this process, except that to calculate the force on particle N, you need to iterate over N-1 (a particle does not feel a force from itself) particles, calculating the above equations for each one.
Ok, so now that you have the force on each particle, you can calculate it's motion via Newton's Law:
F = m * a
Where "m" is mass, and "a" is acceleration.
To calculate the motion of a particle, you really want its acceleration. Well, you already have the force calculate above, so you just divide out the particle's mass to get its acceleration.
Now you can use any number of integration techniques to get velocity and position from acceleration. The simplest integration algorithms are Euler or Verlet. Euler is really simple:
velocity = acceleration * timestep
position = velocity * timestep
Keep in mind, these are all going to be vector quantities.
That's about it. So, at every step of the simulation you do four things:
1) calculate the force on each particle
2) get the acceleration on each particle from the force
3) advance the velocity of the particle by the acceleration
4) advance the position of the particle by the velocity (strictly speaking, this step should actually happen first)
I'm not much of a physics teacher, so I hope that made sense. If not I can probably dig up some references, or some code samples.
If you get this far, keep in mind that you have to do something about particles that get really close to one another. Note that according to Coulomb's Law (the first equation up there), if "r", the distance between two particles, gets really small, the quantity q / r^2 is going to blow up to infinity, which means particles will feel a huge force, and end up shooting off in to the stratosphere. To prevent this, you may want to force particles to stop moving once they get in to the same pixel as your magnet. There are other tricks too... I used a "Pauli Force" in my example, but I won't bother going in to that now.
Anyways, I'm sure this is a mess, but hopefully you can decode it. I would suggest doing a simple example of two particles interacting. That's like six lines of code... if you get that running happily, just think about extending it to N particles. It's just a question of iterating over big arrays of particles!
Hope this helps,
-mike
|
|
|
|
|
miked
|
Re: particle magnet (help)
« Reply #5 on: Apr 22nd, 2004, 12:36am » |
|
hi arielm,
Thanks for the kind words! The goal of TEAL (Technology Enabled Active Learning) is to reform the way physics is taught to freshman at MIT (and everywhere, really), by dispensing with the typical huge lecture/recitation format, and moving to a smaller group/collaborative format using technology as much as possible in the classroom. Part of this is developing animations and simulations of the phenomena that they study in class (this is the part I work on). In the case of electromagnetism, for example, students don't have a clue what an electric field looks like, because you can't see them in real life. So we try and develop simulations and such that visualize those sorts of things.
I just found out about Processing, and it turns out to be a great platform for simulation development. Here's one I've been working on for electromagnetic radiation (disclaimer: work in progess, may break!):
http://web.mit.edu/mdanzig/www/p5waves_2d_hi.html
and a test of a 3d version I put together using your Arcball code (disclaimer: very early work in progress, obviously doesn't work exactly right! it starts off in a bad position, click and drag to rotate):
http://web.mit.edu/mdanzig/www/p5waves_3dtest.html
Anyways, just wanted to share. (sorry to threadjack, Charles!)
Take care,
-mike
|
|
|
|
|
arielm
|
Re: particle magnet (help)
« Reply #6 on: Apr 22nd, 2004, 8:09am » |
|
mike, saw the 2d waves already + the 3d version looks cool + looking forward to see more of them (end of hijack)
|
Ariel Malka | www.chronotext.org
|
|
|
flight404
|
Re: particle magnet (help)
« Reply #7 on: Apr 25th, 2004, 9:12pm » |
|
Wonderful description Mike. I was able to get a multiple particle version working. Any chance you could describe alternate ways to deal with the q/r^2 craziness? I did a poke around on google for Pauli Force but quickly found myself in over my head. I ended up putting a constrain cap on E but the overall effect is a little less than desireable.
I also thought about checking to see if the particle is within a certain radius and if that occurs, kill the adjust-velocity method until it leaves that radius. But this seemed like overkill.
Any suggestions?
|
|
|
|
|
miked
|
Re: particle magnet (help)
« Reply #8 on: Apr 26th, 2004, 6:19pm » |
|
hi flight404,
There are two main ways I've dealt with that issue. One is implementing a collision detection scheme to handle particle interactions when they get close to each other (ie. are touching), the other is the Pauli Force solution. Since collision detection is a whole other can of worms, and requires an "extra layer" to the program, I prefer the simple Pauli Force solution:
Without going in to too much back story, the Pauli Force is a Newtonian interpretation of the quantum mechanical Pauli Exclusion Principle, which basically states that two particles (fermions in this case) can't be in the same place at the same time (or, in other words, occupy the same energy states). While this is conceptually interesting, it really has nothing to do with the implementation... I just wanted to motivate it a bit!
Anyways, in terms of our simulation, it's an additional force that ALWAYS (regardless of charge) pushes the particles away from each other. The trick is that we only want it to operate over very short distances, so it only comes in to play when the particles are very close to one another. As it turns out (they've measured this experimentally, apparently), the functional form of this force is 1/r^12. So, if you think about it (or graph it), 1/r^12 is huge when "r" is small, but falls off very quickly so that when "r" is larger, 1/r^12 quickly approaches zero.
All you have to do, then, is add this "Pauli Force" in addition to the electrostatic force you have already calculated. So, the total force will look like:
F = [constants] q1*q2 / r^2 + [constants] abs(q1)*abs(q2) / r^12
The first term is the electrostatic term... at longer distances, that one will dominate. The second term is the Pauli term, and it will dominate at shorter distances. For the Pauli term, you want to use the absolute value of the charges of the particles, so that it is always a repulsive force, regardless of the sign of the charges that are interacting. The [constants] should be adjusted to suit your liking. Note that the constants in the Pauli term generally describe the effective "Pauli Radius", which is the distance at which the the Pauli Force starts to dominate. In effect, what you'll see is that two oppositely charged particles will be attracted to on another, but once they get close ("close" being determined by your constants), the will "bounce off" or repel one another.
Obviously, you calculate the Pauli Force in exactly the same way as the electrostatic force. It simply adds in to the total force on a particle. This is the method that my example above uses, although to get the particles to "settle down" once they're touching each other, you'll also need to add a damping term to the force. Generally, damping is always proportional to velocity and acts in the direction opposite of the velocity, so you might add a third force term that looks like -[0.1] * velocity, which would damp the velocity by 10 percent at each step.
Also note that whenever you deal with "sharp" functions like this in a stepped simulation, you need to make sure you use a small enough time step so that things don't get out of hand. Integration schemes like Runge-Kutta do this automatically, but Euler certainly doesn't. The issue being that with large time steps you run in to a situation where at step N, your two particles are far enough away from one another that the Pauli force between them is negligable, but at step N+1, they've moved closer by such a large amount that they suddenly find themselves deep inside the potential well of the Pauli term, causing them to fly apart very quickly. You need to take care that they "ease in" to this state, rather than having a huge change in force from one step to the next. The simplest way to do this with the Euler method is to make your time step smaller. The other thing you can do is put a speed limit on your particles, so that they can't move far enough in one step to cause this kind of thing to happen.
If you play with my example above, you'll probably see what I mean if you crank the charge up very quickly on the positive particle. The others fly in really fast, then get blown away when once they collide. This is the issue I'm talking about. Unfortunately, with Euler there's not much you can do about it. You need a more powerful (and expensive) integration algorithm like Runge-Kutta to really deal with it correctly.
Anyways, hope that helps! If that was too scatter-brained, let me know and I'll try to present it more clearly.
Cheers,
-mike
|
|
|
|
|
arielm
|
Re: particle magnet (help)
« Reply #9 on: Apr 26th, 2004, 6:55pm » |
|
miked,
(things get more and more interesting out there!)
just a general interest question: for the kind of issues you're describing, is it possible to use Verlet instead of RK for integrating, since it's more adapted to common mortals?
|
Ariel Malka | www.chronotext.org
|
|
|
miked
|
Re: particle magnet (help)
« Reply #10 on: Apr 26th, 2004, 8:05pm » |
|
You can absolutely use the Verlet algorithm, as it's certainly more stable and accurate than the Euler method. But again, it won't be as stable and accurate as a fourth order Runge-Kutta implementation, for example.
The truth is, for almost anything else, the Euler method stinks. If you consider what it's doing, it has a couple of bad features. For one, it approximates the slope of the function over the step interval simply by using the slope at the beginning of the step. Second (and related), it doesn't consider the curvature of the function across the interval. What you really want is an algorithm that more thoroughly analyzes the function on the interval that you're stepping across. If you look at higher order Runge-Kutta methods (we use fourth order a lot for some of the stuff we do), what it does is break each step in to a number of "sub-steps", and does some fancy averaging (you'll have to talk to a mathematician if you want more details ) to come up with a more approprate value by which to advance the solution. Verlet, if I recall correctly, approaches this by doing something like examining the previous step and the next step to come up with a value for the current step.
But when I say "what you really want is...", I'm speaking theoretically. Theoretically, more accuracy is better, but in practice you may not need anything more complex than the Euler method. If you don't need significant precision, it will do the trick. Unlike Runge-Kutta, it's very simple to implement. Hell, I've been looking at Runge-Kutta for years now, and I still get confused dealing with it! Also, obviously, it's faster, since it takes less calculations to complete a step.
So, in other words, there's no one integration scheme that's going to be the best 100% of the time. Mainly it's a trade off between speed an accuracy. If Euler isn't cutting it, certainly use Verlet. If Verlet isn't cutting it, have a go at Runge-Kutta... Whatever suits your needs.
Although I have come across integration algorithm snobbery on occasion. "You used the EULER method for this? My god..." So you'll never go wrong with Verlet, as it's a little bit fancier!
Cheers,
-mike
|
|
|
|
|
flight404
|
Re: particle magnet (help)
« Reply #11 on: Apr 26th, 2004, 8:24pm » |
|
Well, i haven't gotten around to implementing a Pauli Force yet, and frankly, I think my code is full of errors. For example, I believe my particles respond to a opposites repluse and likes attract behavior set. I cannot be certain at this point (although an earlier test made me believe this was the case).
But I am quite satisfied with the result of this particular applet.
http://www.flight404.com/p5/attraction/
360 particles are created around a small central gravitational field. Each particle is given a charge from -constant to +constant. And then they are left to do what they do. Instantly clumps start to form and form long fuzzy cables.
But be forewarned if you want to play with the source... I think my math is wrong (not that that is a bad thing)
r
|
|
|
|
|
arielm
|
Re: particle magnet (help)
« Reply #12 on: Apr 27th, 2004, 11:20am » |
|
on Apr 26th, 2004, 8:05pm, miked wrote:| Although I have come across integration algorithm snobbery on occasion. "You used the EULER method for this My god..." So you'll never go wrong with Verlet, as it's a little bit fancier! |
|
yeah, i know exactly what you mean! a 4th order RK has a kind of aura, a bit like quaternions
|
Ariel Malka | www.chronotext.org
|
|
|
flight404
|
Re: particle magnet (help)
« Reply #13 on: May 2nd, 2004, 8:03am » |
|
I think I finally got the Pauli force working. Took a bit of head scratching and I suspect I am going about it the long way.
http://www.flight404.com/p5/magnets
This version uses 360 positively charged particles and a gravitational force. I was surprised to see this algorithm produce images similar to Phi experiments i have seen here and there. Very sunflowery. I made a couple of videos using over a 1000 particles. Here is one of the nicer ones, me thinks.
http://www.flight404.com/p5/video/magnets03cSmall.mov (15 megs)
Fun stuff.
|
|
|
|
|
justo
|
Re: particle magnet (help)
« Reply #14 on: May 2nd, 2004, 9:21am » |
|
i implemented a 4th order RK solver a while back and came upon this phenomenal, phenomenal resource...it was a talk given by some pixar folks at siggraph 2001 to demystify a lot of the math needed for games today. with no real source code given (though sometimes some pseudo code), its great when youre trying to really understand this stuff...and then, voila, rk4 isnt so magical
the different integration techniques can be found in this paper:
http://www.pixar.com/companyinfo/research/pbm2001/notesb.pdf
and the overall course notes can be found here:
http://www.pixar.com/companyinfo/research/pbm2001/index.html
for a method that is guarunteed to always converge on a solution see the implicit methods...i havent really waded through that one yet, though. it is definitely overkill for all but the most accurate simulations.
also, keep in mind that with software rendering platforms like processing, fillrate is definitely the biggest bottleneck...so dont be afraid to toss a lot of math at the problem...it'll often have little effect on the framerate and give you some great looking results (your real enemy is that siren song, smooth() ).
|
|
|
|
|
|
