OK, so here's a question.

I have a particle system that implements RK4 integration. It works 
great. However... for each step, it involves computing the force acting 
on a particle several times. That's fine if the force is an invariant 
function of the particle's position and/or velocity (and possibly time). 
But what do you do if the forces acting on a particle depend on the 
positions of the other particles? o_O

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

> But what do you do if the forces acting on a particle depend on the 
> positions of the other particles? o_O

The fact that you are even asking that question makes me think you are 
implementing RK4 incorrectly.  The whole point of RK4 is that it gives more 
accurate results when the forces depend on positions of other particles (eg 
springs, collisions etc).

I suspect you are trying to apply the whole RK4 algorithm to one particle, 
then the next, etc.  This is wrong.

You need to store the positions and velocities of all the particles together 
in one "state" object.  Then you apply each step of RK4 on the whole state 
at once.  If you need the positions of other particles when calculating the 
force, then of course you have all the position and velocity information 
available in the state local to the current RK4 step.

Post a reply to this message

> The fact that you are even asking that question makes me think you are 
> implementing RK4 incorrectly.

Well, considering I have no clue why RK4 even works in the first place, 
that's hardly surprising. ;-)

> The whole point of RK4 is that it gives 
> more accurate results when the forces depend on positions of other 
> particles (eg springs, collisions etc).

Really? I was under the impression that RK4 works just like other 
methods, but just gives superior numerical accuracy.

> I suspect you are trying to apply the whole RK4 algorithm to one 
> particle, then the next, etc.  This is wrong.

It works fine if you only *have* one particle. ;-)

Actually, the simulation I'm about to run only consists of one particle. 
But in future I'd like to handle more.

Currently my code is structured the way you indicate. (Heck, you can go 
*read* it if you like... it's in the other NG.) But that doesn't allow 
more complex systems.

> You need to store the positions and velocities of all the particles 
> together in one "state" object.  Then you apply each step of RK4 on the 
> whole state at once.  If you need the positions of other particles when 
> calculating the force, then of course you have all the position and 
> velocity information available in the state local to the current RK4 step.

Right. So just make all functions apply to the entire system at once. I 
think I can do that...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Invisible wrote:
> OK, so here's a question.
> 
> I have a particle system that implements RK4 integration. It works 
> great. However... for each step, it involves computing the force acting 
> on a particle several times. That's fine if the force is an invariant 
> function of the particle's position and/or velocity (and possibly time). 
> But what do you do if the forces acting on a particle depend on the 
> positions of the other particles? o_O

If you have a natural fear of O(N^2) problems, then I have some bad news 
for you.

To accurately calculate the current force on each particle in a system, 
you have to match up every possible pair of particles, all (n^2-n)/2 of 
such pairs, and calculate the force that each of the particles in the 
pair exerts on the other (generally equal and opposite, according to Mr. 
Newton, so there is only one force calculation for each pair).

Try to get n as low as possible.

Regards,
John

Post a reply to this message

John VanSickle wrote:

> If you have a natural fear of O(N^2) problems, then I have some bad news 
> for you.
> 
> Try to get n as low as possible.

I was thinking maybe 8 or so?

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

John VanSickle <evi### [at] hotmailcom> wrote:

> If you have a natural fear of O(N^2) problems, then I have some bad news
> for you.
>
> To accurately calculate the current force on each particle in a system,
> you have to match up every possible pair of particles, all (n^2-n)/2 of
> such pairs, and calculate the force that each of the particles in the
> pair exerts on the other (generally equal and opposite, according to Mr.
> Newton, so there is only one force calculation for each pair).

In all fairness, there are better methods.  Think of dividing all the particles
up into an octree.  A whole group of particles at a distance can be lumped into
one mass.  I guess O(N logN) algorithms like this are as revolutionary as the
FFT.  Of course I'm just regurgitating what's on Wikipedia and haven't actually
done any of this, but it's interesting to think about--and fascinating to watch.
 (See links below)

 - Ricky

http://en.wikipedia.org/wiki/Barnes-Hut_simulation
http://en.wikipedia.org/wiki/Fast_Multipole_Method
http://www.astro.ex.ac.uk/people/mbate/Animations/
http://www.cita.utoronto.ca/~dubinski/nbody/

Post a reply to this message

triple_r <nomail@nomail> wrote:
> In all fairness, there are better methods.  Think of dividing all the particles
> up into an octree.  A whole group of particles at a distance can be lumped into
> one mass.

  But you have to calculate the center of mass of the whole group, and
since each element of the group can change independently of the others,
that would mean you have to re-calculate this center of mass each time
anything changes.

  Also another problem is that groups don't stay the same. If a particle
not belonging to the group enters the "inside" of the group, it cannot
be calculated anymore against that group as if it was just one single
mass located at the center of mass of the group.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:

>   But you have to calculate the center of mass of the whole group, and
> since each element of the group can change independently of the others,
> that would mean you have to re-calculate this center of mass each time
> anything changes.

That's true. I think you're probably still saving yourself work though. 
Compute that center of mass once and use it many times, verses computer 
many object-object interactions many times over.

It depends on what you're simulating of course, but I would think there 
are probably also situations were you can just disregard really distant 
particles.

>   Also another problem is that groups don't stay the same. If a particle
> not belonging to the group enters the "inside" of the group, it cannot
> be calculated anymore against that group as if it was just one single
> mass located at the center of mass of the group.

Isn't this just the "normal" problem of performing space partitioning 
with moving objects?

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> Isn't this just the "normal" problem of performing space partitioning 
> with moving objects?

  Which is a very hard problem. Why do you think scenery is always static
in all games?

-- 
                                                          - Warp

Post a reply to this message

>> Isn't this just the "normal" problem of performing space partitioning 
>> with moving objects?
> 
>   Which is a very hard problem. Why do you think scenery is always static
> in all games?

Oh, OK. I had assumed that this was a "solved" problem, since it occurs 
any time you want to animate multiple moving objects...



I also assumed that scenery is always static in games so that you can 
precompute light maps, occlusion data, and other stuff that makes it 
possible to draw a landscape made up of a trillian polygons without 
slowing everything to a crawl... As you probably know, I don't "do" this 
for a living. ;-)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message