So I was writing a general particle system capable of spitting out POV-Ray
code (as SDL solutions are too slow for my tastes), and I found MegaPOV
with mechsim.  Needless to say, I've been busy playing with it, and find it
both complete and effective.  Good job on a good patch!

Anyway, I noticed that I'm still not happy with the simulation speed, so I
looked at the code for the patch.  Collisions are checked between masses by
calculating the distance, which requires a sqrt call.  The only way I can
think of to speed that up is to use a box format first, such as this
pseudocode:

if ((abs(dx)<max) and (abs(dy)<max)) and (abs(dz)<max)))
 if (sqrt(dx^2+dy^2+dz^2)<max)
  collision is true
 end
end

But, as this requires three tests which could screw branch prediction up,
before you even get to the sqrt, I'm not sure it would save any time.

Or, you could do one test:

if (abs(dx)+abs(dy)+abs(dz) < max*3)
 if (sqrt...

Other than that, the only way to improve the speed would be to improve
POV-Ray's internal handling of geometry.

So, would such things actually help a lot?  And, because I'm not familiar
with POV-Ray's internals, would my writing a separate system be likely to
work any faster than the mechsim compiled in POV-Ray?

....Chambers, who wants to simulate millions of mass points but is currently
waiting for a trace with only 17000...

Post a reply to this message

Chambers wrote:
...
> Anyway, I noticed that I'm still not happy with the simulation speed, so I
> looked at the code for the patch.  Collisions are checked between masses by
> calculating the distance, which requires a sqrt call.  The only way I can
> think of to speed that up is to use a box format first, such as this
> pseudocode:
> 
> if ((abs(dx)<max) and (abs(dy)<max)) and (abs(dz)<max)))
>  if (sqrt(dx^2+dy^2+dz^2)<max)
>   collision is true
>  end
> end
...

I've never looked at the code you're describing here, but it looks like 
you don't need the sqrt at all. Wherever max gets set, square it and 
store it in maxSquared, then do:

if ((dx^2+dy^2+dz^2)<maxSquared)
  collision is true
end

Post a reply to this message

Chambers wrote:
> So I was writing a general particle system capable of spitting out POV-Ray
> code (as SDL solutions are too slow for my tastes), and I found MegaPOV
> with mechsim.  Needless to say, I've been busy playing with it, and find it
> both complete and effective.  Good job on a good patch!

Thanks.

> Anyway, I noticed that I'm still not happy with the simulation speed, so I
> looked at the code for the patch.  Collisions are checked between masses by
> calculating the distance, which requires a sqrt call.  The only way I can
> think of to speed that up is to use a box format first, such as this
> pseudocode:
> 
> if ((abs(dx)<max) and (abs(dy)<max)) and (abs(dz)<max)))
>  if (sqrt(dx^2+dy^2+dz^2)<max)
>   collision is true
>  end
> end

This would be just a bounding box test that would certainly speed up the 
collisions a bit but would not change anything about the principal 
problem of mass interactions being O(n^2).  You should have a look at 
what Daniel Jungmann wrote recently (a few threads ago) which was mostly 
meant for mass-face-collisions but also works on mass-mass collisions to 
some extent.

And the sqrt() has to be calculated for all collisions that actually 
occur since the force depends on the distance.

Christoph

-- 
POV-Ray tutorials, include files, Sim-POV,
HCR-Edit and more: http://www.tu-bs.de/~y0013390/
Last updated 01 May. 2004 _____./\/^>_*_<^\/\.______

Post a reply to this message

Christoph Hormann <chr### [at] gmxde> wrote:
> This would be just a bounding box test that would certainly speed up the
> collisions a bit but would not change anything about the principal
> problem of mass interactions being O(n^2).

And here's the crux of the problem - I don't know of any way to make the
function simpler or faster, which means I'm just stuck with the speed of it
as it is right now.  I might continue writing my own system, and use sse
for speed, but that would be at the expense of accuracy.

>  You should have a look at
> what Daniel Jungmann wrote recently (a few threads ago) which was mostly
> meant for mass-face-collisions but also works on mass-mass collisions to
> some extent.

I'll take a look at this.

> And the sqrt() has to be calculated for all collisions that actually
> occur since the force depends on the distance.

Of course, and I never meant to imply that you could do without calculating
it for those collisions that do occur.  I was only looking for a way to
cull those which do not.

....Chambers

Post a reply to this message

"Chambers" <bdc### [at] yahoocom> wrote:
> Of course, and I never meant to imply that you could do without calculating
> it for those collisions that do occur.  I was only looking for a way to
> cull those which do not.
>
> ....Chambers

For a static area-filling I've used 'binning' to speed up intersection
checks when adding new items:

Chop one or more of the axes into bins of equal width (of about twice the
expected interaction radius), covering the extent of the items. A simple,
fast function will then tell you which bin any point belongs to. Each bin
uses a variable length array to hold a sorted list of the items in that
bin.

To add a new item check the bins which span item_pos +/-(item_radius +
max_radius) for collisions.

For non-static systems check each item against the items in each bin
spanning item_pos +/-(item_radius + max_radius + |item_vel| + |max_vel|).

Because the items in each bin are in a sorted array you can discard some of
these quickly, too.

My code is on another computer; I'll try to remember to post it later.

Hope this helps a little.

Mike Andrews.

Post a reply to this message