> That depends on your settings, if you do full collision detection you of
> course need to check every topology feature against every other one -


        Okay so if a full collision detection requires O(N^2) operations,
then it definitely means that there is no "smart" mechanism to "cut away"
all possible cases where collisions cannot happen at that particular
time step.  Such a partitioning scheme can be as simple as a cubic space
division.

> I am not sure what you mean by 'interaction list'

        This list stores all possible pairs of particles that are seperated
by less than a threshold distance.  Building such a list is basically in
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 log N)
but I'm good enough in maths to tell whether it's the case  :-(
        The trick comes from what should be the size of the cube depending
on the particle shape in particular.  In case of only spheres or any simple
shape for the particles, it's very straightforward of course.

> where you have very high number of molecules and
> are only interested in the statistical outcome.  A mass not correctly
> colliding where it should will ruin the whole simulation.

        The simulations I'm talking about do consider much more than
just the mass and shape of the particles (here atoms) to evalulate
their interactions at a given time.  So I don't think there would be
any problem applying similar rules when you are interested in collision
detection.  The only difference is that all particules have the same
shape, so I don't know how to handle situations such as a sphere
colliding a plane or an isosurface (the former could be most likely
treated efficiently, but I suspect the second should require some sort
of tesselated model of the isosurface first).
        Or maybe I don't understand what you mean -- it's often a problem
of mine... you know :-)

        - NC

Post a reply to this message