Nicolas Calimet wrote:
  >
>>I am not sure what you mean by 'interaction list'
> 
> 
>         This list stores all possible pairs of particles that are seper
ated
> by less than a threshold distance.  Building such a list is basically i
n
> O(N) operations -- devide the space into cubes and assign each particle

> to a given cube, then for each cube check the particles in the 26 neigh
-
> bours and the current cube.  The later collision detection remains in
> O(N'^2) but with N' << N.  Overall you should get something like O(N lo
g N)
> but I'm good enough in maths to tell whether it's the case  :-(

I think i understand your point but this will only be useful if you have 

a high number of particles that fill a bounded area and do not change 
their distribution in space very fast.  If this is not the case you will 

spent most of your time doing the list building.

The technique i outlined in my last post would not require any 

possible collision (which would just be a number of coordinate 
comparisons) and the rest would be the same O(N'^2) as in your method.

And as you already said your space division grid will only work if you 
have only point masses with all the same radius.  The original topic of 
this discussion was mass-triangle collisions with varying radii.

Christoph.

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

Post a reply to this message