Hi, 
 
collision detection in MegaPov is a cool feature, but it is verry slow,
especialy mass-face collision. MegaPov spend most of it's time in the
function func_triangle (file mechsim.cpp). A bounding system coud speed up
the mass-face and mass-mass collision.
What do you think of this idea?

Post a reply to this message

Daniel Jungmann wrote:
> Hi, 
>  
> collision detection in MegaPov is a cool feature, but it is verry slow,
> especialy mass-face collision. MegaPov spend most of it's time in the
> function func_triangle (file mechsim.cpp). A bounding system coud speed up
> the mass-face and mass-mass collision.
> What do you think of this idea?

Do you think recalculating a bounding tree after every simulation step 
will be faster in the end?

It would be possible to speed up the triangle function a bit since we 
don't actually need its value if it exceeds the mass radius of course.

To speed up collision calculations the mechsim patch has the possibility 
to group masses and only enable collisions between masses of different 
groups.

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

> Do you think recalculating a bounding tree after every simulation step
> will be faster in the end?

        I don't know how collision detection is performed in MegaPOV for now: does
it account for all particles at once ?  (i.e. O(N^2) time complexity ?)

        From my experience in biomolecular simulations, there is in principle no
need to recalculate the interaction list (or bounding tree) at every step
of the simulation.  Simple heuristics can be used to recalculate it when
the particule moves away by more than a certain distance from the position
at which the bounding tree was calculated.  Of course the efficiency then
depends on the velocity of the fastest particle at a given time step, but
typically the tree could be updated only every 5-10 steps.  Speed up is
considerable with respect to O(N^2) anyway (especially for short "cutoff"
distance when calculating the interaction list).

        - NC

Post a reply to this message

Nicolas Calimet wrote:
>>Do you think recalculating a bounding tree after every simulation step
>>will be faster in the end?
> 
> 
>         I don't know how collision detection is performed in MegaPOV fo
r now: does
> it account for all particles at once ?  (i.e. O(N^2) time complexity ?)


That depends on your settings, if you do full collision detection you of 

course need to check every topology feature against every other one - O(n


>         From my experience in biomolecular simulations, there is in pri
nciple no
> need to recalculate the interaction list (or bounding tree) at every st
ep
> of the simulation.  [...]

I am not sure what you mean by 'interaction list' but this is not like a 

molecular simulation 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 idea of 
using techniques known from bounding (i.e. min/max metric to determine 
the possibility of a collision) is surely not bad but this will not 
change the order of complexity.

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

> 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

> but I'm good enough in maths to tell whether it's the case  :-(

        ... "I'm _NOT_ good enough" is what I meant  :-( :-( :-(

        - NC

Post a reply to this message

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

Christoph Hormann wrote:

> Do you think recalculating a bounding tree after every simulation step
> will be faster in the end?
> 
> It would be possible to speed up the triangle function a bit since we
> don't actually need its value if it exceeds the mass radius of course.
> 
> To speed up collision calculations the mechsim patch has the possibility
> to group masses and only enable collisions between masses of different
> groups.
> 
> Christoph
> 

Yes, I think bounding would speed up the hole thing. Building a bounding box
or sphere tree is too slow, but using a hash function is fast enough.

Daniel

Post a reply to this message

Daniel Jungmann wrote:
> 
> Yes, I think bounding would speed up the hole thing. Building a bounding box
> or sphere tree is too slow, but using a hash function is fast enough.

I am not sure what you are trying to suggest here.  If you have a 
technique in mind you think that would speed up the collision tests 
please make a more elaborate description.

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

Christoph Hormann wrote:

> Daniel Jungmann wrote:
>> 
>> Yes, I think bounding would speed up the hole thing. Building a bounding
>> box or sphere tree is too slow, but using a hash function is fast enough.
> 
> I am not sure what you are trying to suggest here.  If you have a
> technique in mind you think that would speed up the collision tests
> please make a more elaborate description.
> 
> Christoph
> 

Using a hash function that maps 3D boxes (cells) to a 1D hash table index.
http://graphics.ethz.ch/~brunoh/download/CollisionDetectionHashing_VMV03.pdf

Post a reply to this message