Well, the basic alogrithm is to find the closest neighboring particle, and
if it is within a certain distance, generate a force towards this nearest
neighbor. The slow O(N^2) part is finding the nearest particle.

What if you chopped up the space into cubes, and only looked for a nearest
neighbor in the same cube? I assume that somewhere deep down in your
simulation is a 1-dimensional array representing the particles.

Suppose you divided the space into 10x10x10 cubes, and had a 4-dimensional
array Neighbors[10][10][10][N_PARTICLES]. When the physics loop starts, the
array is cleared. When each particle position is updated, calculate which
cube it belongs in, say <4,5,6> and write that into Neighbors[4][5][6]. Now
when it comes time to calculate, for each particle only check for its
nearest neighbor in the same neighbor cube. This could reduce time to
O(1000*(N/1000)^2).


"JRG" <jrg### [at] hotmailcom> wrote in message
news:3bcdbc8c@news.povray.org...
> Do you know a *fast* way to do that in POV SDL? As I said elsewhere, it
> would be really a simple implementation, but it would be *extremely* slow
to
> compute with so many particles. I could consider to implement non
persistent
> (sp?) particles to reduce the number of particles per frame though... any
> help?
>
> --
> Jonathan.
> "Chris Jeppesen" <chr### [at] digiquillcom> ha scritto nel messaggio
> news:3bcdb821$1@news.povray.org...
> > After staring at this animation for literally seconds, I finally
realized
> > what was missing: surface tension. there must be some way for a partile
to
> > know if it is connected to another one and if so, is attracted to it.
This
> > would prevent the tiny droplets from escaping like they do now.
> >
> > "JRG" <jrg### [at] hotmailcom> wrote in message
> > news:3bcc6b2a@news.povray.org...
> > > See same thread in p.b-i.
> > > I know I can get better compression with divx, but the quality was
> > *really*
> > > poor. Is there anyone who can drive me through all those encoding
> options?
> > > TIA.
> > >
> > > --
> > > Jonathan.
> > >
> > >
> > >
> > >
> >
> >
>
>

Post a reply to this message

Hmmm, it sounds clever. This algorithm might be use for reciprocal repulsion
as well.
I'll give it a try and post the results.
Thank you,

--
Jonathan.
"Chris Jeppesen" <chr### [at] digiquillcom> ha scritto nel messaggio
news:3bcdc15c$1@news.povray.org...
> Well, the basic alogrithm is to find the closest neighboring particle, and
> if it is within a certain distance, generate a force towards this nearest
> neighbor. The slow O(N^2) part is finding the nearest particle.
>
> What if you chopped up the space into cubes, and only looked for a nearest
> neighbor in the same cube? I assume that somewhere deep down in your
> simulation is a 1-dimensional array representing the particles.
>
> Suppose you divided the space into 10x10x10 cubes, and had a 4-dimensional
> array Neighbors[10][10][10][N_PARTICLES]. When the physics loop starts,
the
> array is cleared. When each particle position is updated, calculate which
> cube it belongs in, say <4,5,6> and write that into Neighbors[4][5][6].
Now
> when it comes time to calculate, for each particle only check for its
> nearest neighbor in the same neighbor cube. This could reduce time to
> O(1000*(N/1000)^2).
>
>
> "JRG" <jrg### [at] hotmailcom> wrote in message
> news:3bcdbc8c@news.povray.org...
> > Do you know a *fast* way to do that in POV SDL? As I said elsewhere, it
> > would be really a simple implementation, but it would be *extremely*
slow
> to
> > compute with so many particles. I could consider to implement non
> persistent
> > (sp?) particles to reduce the number of particles per frame though...
any
> > help?
> >
> > --
> > Jonathan.
> > "Chris Jeppesen" <chr### [at] digiquillcom> ha scritto nel messaggio
> > news:3bcdb821$1@news.povray.org...
> > > After staring at this animation for literally seconds, I finally
> realized
> > > what was missing: surface tension. there must be some way for a
partile
> to
> > > know if it is connected to another one and if so, is attracted to it.
> This
> > > would prevent the tiny droplets from escaping like they do now.
> > >
> > > "JRG" <jrg### [at] hotmailcom> wrote in message
> > > news:3bcc6b2a@news.povray.org...
> > > > See same thread in p.b-i.
> > > > I know I can get better compression with divx, but the quality was
> > > *really*
> > > > poor. Is there anyone who can drive me through all those encoding
> > options?
> > > > TIA.
> > > >
> > > > --
> > > > Jonathan.
> > > >
> > > >
> > > >
> > > >
> > >
> > >
> >
> >
>
>

Post a reply to this message

Actually you should check the 26 cubes immediately surrounding the cube in
question as well, otherwise particles at the very edge of one cube wouldn't
be influenced by particles at the very edge of the next cube

-tgq


"Chris Jeppesen" <chr### [at] digiquillcom> wrote in message
news:3bcdc15c$1@news.povray.org...
> Well, the basic alogrithm is to find the closest neighboring particle, and
> if it is within a certain distance, generate a force towards this nearest
> neighbor. The slow O(N^2) part is finding the nearest particle.
>
> What if you chopped up the space into cubes, and only looked for a nearest
> neighbor in the same cube? I assume that somewhere deep down in your
> simulation is a 1-dimensional array representing the particles.
>
> Suppose you divided the space into 10x10x10 cubes, and had a 4-dimensional
> array Neighbors[10][10][10][N_PARTICLES]. When the physics loop starts,
the
> array is cleared. When each particle position is updated, calculate which
> cube it belongs in, say <4,5,6> and write that into Neighbors[4][5][6].
Now
> when it comes time to calculate, for each particle only check for its
> nearest neighbor in the same neighbor cube. This could reduce time to
> O(1000*(N/1000)^2).
>

Post a reply to this message

26?

--
Jonathan.
"Trevor Quayle" <Tin### [at] hotmailcom> ha scritto nel messaggio
news:3bcdc957$1@news.povray.org...
> Actually you should check the 26 cubes immediately surrounding the cube in
> question as well, otherwise particles at the very edge of one cube
wouldn't
> be influenced by particles at the very edge of the next cube
>
> -tgq
>
>
> "Chris Jeppesen" <chr### [at] digiquillcom> wrote in message
> news:3bcdc15c$1@news.povray.org...
> > Well, the basic alogrithm is to find the closest neighboring particle,
and
> > if it is within a certain distance, generate a force towards this
nearest
> > neighbor. The slow O(N^2) part is finding the nearest particle.
> >
> > What if you chopped up the space into cubes, and only looked for a
nearest
> > neighbor in the same cube? I assume that somewhere deep down in your
> > simulation is a 1-dimensional array representing the particles.
> >
> > Suppose you divided the space into 10x10x10 cubes, and had a
4-dimensional
> > array Neighbors[10][10][10][N_PARTICLES]. When the physics loop starts,
> the
> > array is cleared. When each particle position is updated, calculate
which
> > cube it belongs in, say <4,5,6> and write that into Neighbors[4][5][6].
> Now
> > when it comes time to calculate, for each particle only check for its
> > nearest neighbor in the same neighbor cube. This could reduce time to
> > O(1000*(N/1000)^2).
> >
>
>
>

Post a reply to this message

3^3 -1 (cubes that share faces, edges and corners)

-tgq


"JRG" <jrg### [at] hotmailcom> wrote in message
news:3bcdcbde@news.povray.org...
> 26?
>
> --
> Jonathan.
> "Trevor Quayle" <Tin### [at] hotmailcom> ha scritto nel messaggio
> news:3bcdc957$1@news.povray.org...
> > Actually you should check the 26 cubes immediately surrounding the cube
in
> > question as well, otherwise particles at the very edge of one cube
> wouldn't
> > be influenced by particles at the very edge of the next cube
> >
> > -tgq
> >
> >
> > "Chris Jeppesen" <chr### [at] digiquillcom> wrote in message
> > news:3bcdc15c$1@news.povray.org...
> > > Well, the basic alogrithm is to find the closest neighboring particle,
> and
> > > if it is within a certain distance, generate a force towards this
> nearest
> > > neighbor. The slow O(N^2) part is finding the nearest particle.
> > >
> > > What if you chopped up the space into cubes, and only looked for a
> nearest
> > > neighbor in the same cube? I assume that somewhere deep down in your
> > > simulation is a 1-dimensional array representing the particles.
> > >
> > > Suppose you divided the space into 10x10x10 cubes, and had a
> 4-dimensional
> > > array Neighbors[10][10][10][N_PARTICLES]. When the physics loop
starts,
> > the
> > > array is cleared. When each particle position is updated, calculate
> which
> > > cube it belongs in, say <4,5,6> and write that into
Neighbors[4][5][6].
> > Now
> > > when it comes time to calculate, for each particle only check for its
> > > nearest neighbor in the same neighbor cube. This could reduce time to
> > > O(1000*(N/1000)^2).
> > >
> >
> >
> >
>
>

Post a reply to this message

Right. But I think this would slow things down...

--
Jonathan.
"Trevor Quayle" <Tin### [at] hotmailcom> ha scritto nel messaggio
news:3bcdcd96$1@news.povray.org...
> 3^3 -1 (cubes that share faces, edges and corners)
>
> -tgq
>
>
> "JRG" <jrg### [at] hotmailcom> wrote in message
> news:3bcdcbde@news.povray.org...
> > 26?
> >
> > --
> > Jonathan.
> > "Trevor Quayle" <Tin### [at] hotmailcom> ha scritto nel messaggio
> > news:3bcdc957$1@news.povray.org...
> > > Actually you should check the 26 cubes immediately surrounding the
cube
> in
> > > question as well, otherwise particles at the very edge of one cube
> > wouldn't
> > > be influenced by particles at the very edge of the next cube
> > >
> > > -tgq
> > >
> > >
> > > "Chris Jeppesen" <chr### [at] digiquillcom> wrote in message
> > > news:3bcdc15c$1@news.povray.org...
> > > > Well, the basic alogrithm is to find the closest neighboring
particle,
> > and
> > > > if it is within a certain distance, generate a force towards this
> > nearest
> > > > neighbor. The slow O(N^2) part is finding the nearest particle.
> > > >
> > > > What if you chopped up the space into cubes, and only looked for a
> > nearest
> > > > neighbor in the same cube? I assume that somewhere deep down in your
> > > > simulation is a 1-dimensional array representing the particles.
> > > >
> > > > Suppose you divided the space into 10x10x10 cubes, and had a
> > 4-dimensional
> > > > array Neighbors[10][10][10][N_PARTICLES]. When the physics loop
> starts,
> > > the
> > > > array is cleared. When each particle position is updated, calculate
> > which
> > > > cube it belongs in, say <4,5,6> and write that into
> Neighbors[4][5][6].
> > > Now
> > > > when it comes time to calculate, for each particle only check for
its
> > > > nearest neighbor in the same neighbor cube. This could reduce time
to
> > > > O(1000*(N/1000)^2).
> > > >
> > >
> > >
> > >
> >
> >
>
>

Post a reply to this message

Yes, but it would also prevent the particles from forming into cubes which
fall apart from each other.  You would get cohesion within each spatial
cube, but not between each cube.

-tgq


"JRG" <jrg### [at] hotmailcom> wrote in message
news:3bcdce4f$1@news.povray.org...
> Right. But I think this would slow things down...
>
> --
> Jonathan.
> "Trevor Quayle" <Tin### [at] hotmailcom> ha scritto nel messaggio
> news:3bcdcd96$1@news.povray.org...
> > 3^3 -1 (cubes that share faces, edges and corners)
> >
> > -tgq
> >
> >
> > "JRG" <jrg### [at] hotmailcom> wrote in message
> > news:3bcdcbde@news.povray.org...
> > > 26?
> > >
> > > --
> > > Jonathan.
> > > "Trevor Quayle" <Tin### [at] hotmailcom> ha scritto nel messaggio
> > > news:3bcdc957$1@news.povray.org...
> > > > Actually you should check the 26 cubes immediately surrounding the
> cube
> > in
> > > > question as well, otherwise particles at the very edge of one cube
> > > wouldn't
> > > > be influenced by particles at the very edge of the next cube
> > > >
> > > > -tgq
> > > >
> > > >
> > > > "Chris Jeppesen" <chr### [at] digiquillcom> wrote in message
> > > > news:3bcdc15c$1@news.povray.org...
> > > > > Well, the basic alogrithm is to find the closest neighboring
> particle,
> > > and
> > > > > if it is within a certain distance, generate a force towards this
> > > nearest
> > > > > neighbor. The slow O(N^2) part is finding the nearest particle.
> > > > >
> > > > > What if you chopped up the space into cubes, and only looked for a
> > > nearest
> > > > > neighbor in the same cube? I assume that somewhere deep down in
your
> > > > > simulation is a 1-dimensional array representing the particles.
> > > > >
> > > > > Suppose you divided the space into 10x10x10 cubes, and had a
> > > 4-dimensional
> > > > > array Neighbors[10][10][10][N_PARTICLES]. When the physics loop
> > starts,
> > > > the
> > > > > array is cleared. When each particle position is updated,
calculate
> > > which
> > > > > cube it belongs in, say <4,5,6> and write that into
> > Neighbors[4][5][6].
> > > > Now
> > > > > when it comes time to calculate, for each particle only check for
> its
> > > > > nearest neighbor in the same neighbor cube. This could reduce time
> to
> > > > > O(1000*(N/1000)^2).
> > > > >
> > > >
> > > >
> > > >
> > >
> > >
> >
> >
>
>

Post a reply to this message

I recently decided to do my own (unfinished) particle system (when it's done,
I might call it... the wheel :), so that I can do this sort of effect. I have
found that a block map is tolerably fast even when checking the contents of 27
cells.
    Getting the effect of cubes ignoring one another can occur if you only check
one cell, but this behaviour is dependent on the relative magnitudes of the
particle-particle interactions, and their velocities.
    I hope your system is entertaining you JRG, I know mine is.

MJL

Trevor Quayle wrote:

> Yes, but it would also prevent the particles from forming into cubes which
> fall apart from each other.  You would get cohesion within each spatial
> cube, but not between each cube.
>
> -tgq
>
> "JRG" <jrg### [at] hotmailcom> wrote in message
> news:3bcdce4f$1@news.povray.org...
> > Right. But I think this would slow things down...

Post a reply to this message

"JRG" <jrg### [at] hotmailcom> wrote in message news:3bcdbc8c@news.povray.org...
> Do you know a *fast* way to do that in POV SDL? As I said elsewhere, it
> would be really a simple implementation, but it would be *extremely* slow to
> compute with so many particles. I could consider to implement non persistent
> (sp?) particles to reduce the number of particles per frame though... any
> help?
>

I would just place a huge squashed blob just beneath the surface with a small
strength value. But that wouldn't be perfect...

- Nekar


---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.282 / Virus Database: 150 - Release Date: 2001/09/25

Post a reply to this message

Looks very nice, ammazing what one can do with pov. I agree with the earlier
comments that the particle should interact with the surface as well. I'm sure
you will find a solution that is fast enough.

One thing I would like to mention however is that everyone (You, Rune and Mark
James Lewin apperently) are all writing particle systems. Wouldn't it be an
idea to combine al these efforts?

Just my two cents....


Thomas

ps. Yes I know it is very rewarding writing your own.

JRG wrote:

> See same thread in p.b-i.
> I know I can get better compression with divx, but the quality was *really*
> poor. Is there anyone who can drive me through all those encoding options?
> TIA.
>

Post a reply to this message