![](/i/fill.gif) |
![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
John VanSickle <evi### [at] hotmail com> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Invisible <voi### [at] dev null> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
>> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |