 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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 -
> O(n²).
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
precalculations, you would have a step testing all pairs (O(n²)) for
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Daniel Jungmann wrote:
>
> Using a hash function that maps 3D boxes (cells) to a 1D hash table index.
> http://graphics.ethz.ch/~brunoh/download/CollisionDetectionHashing_VMV03.pdf
The technique presented in the paper is subject to the same restrictions
as the grid technique Nicolas suggested. They are able to test
collisions between tetrahedrons because they restrict it to true
penetrating collisions. It's like 'drawing' the tetrahedrons/their
bounding boxes into a 3d grid and checking if some grid cell is occupied.
For the mechsim patch i need to detect if a mass is closer to a triangle
than its radius (which can be different for each mass). This would not
be possible with that method.
Introducing a new topology element (a mass with zero radius) would allow
such techniques. Feel invited to implement something like this in for
the mechsim patch - it would surely be interesting to test how it performs.
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:
> Introducing a new topology element (a mass with zero radius) would allow
> such techniques. Feel invited to implement something like this in for
> the mechsim patch - it would surely be interesting to test how it
> performs.
I will do my very best :-)
Daniel
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> this will only be useful if you have
> a high number of particles that fill a bounded area
Right -- in fact I was talking about treatment of many particles.
> 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.
Not necessarily. With smarter algorithm you could subdivide
space and update the pairwise list only in places where particles move
faster. The list build still represent O(N) simple operations anyway.
> And as you already said your space division grid will only work if you
> have only point masses with all the same radius.
No, just pick the larger object first to decide what grid spacing
to use. Of course this still make sense when all objects are about the
same size (ie _not_ one or two orders of magnitude difference in their
largest dimension).
> The original topic of
> this discussion was mass-triangle collisions with varying radii.
Yes, sorry, for some reason I assumed that the main problem was
coming from a high number of particles to deal with, while I realize
now that the topic deals with the inner function of the collision
detection. Still, it might be nice to be able to speed up the many-
particles problem :-)
- NC
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Daniel Jungmann wrote:
> Hi,
>
> I have now written a patch for faster collision detection. I just made some
> quick checks and it seems working but might be still a lot of bugs. Fee
> free to report them all.
>
> The zipfile contains the changed source files (mechsim.cpp and mechsim.h)
> and a diff file. You don't need both of them.
Attachments should go to p.binaries.programming, please don't post
binaries in the non-binary groups.
I will have a look at this ASAP.
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Daniel Jungmann wrote:
> Hi,
>
> I have now written a patch for faster collision detection. I just made some
> quick checks and it seems working but might be still a lot of bugs. Fee
> free to report them all.
>
> The zipfile contains the changed source files (mechsim.cpp and mechsim.h)
> and a diff file. You don't need both of them.
I did not yet have time to test it but from a quick look at the source
it seems it might lead to slower calculations in cases of:
- relatively few masses
- situations where grouping works very well (like single masses
colliding with grid structures).
It would be useful to have some numbers actually comparing speed in such
situations. Also you replaced the exisiting collision method with the
new technique - it would probably have been better to introduce it as an
alternative method so you can compare them more easily.
Christoph
--
POV-Ray tutorials, include files, Sim-POV,
HCR-Edit and more: http://www.tu-bs.de/~y0013390/
Last updated 21 Mar. 2004 _____./\/^>_*_<^\/\.______
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Christoph Hormann wrote:
> I did not yet have time to test it but from a quick look at the source
> it seems it might lead to slower calculations in cases of:
>
> - relatively few masses
> - situations where grouping works very well (like single masses
> colliding with grid structures).
>
> It would be useful to have some numbers actually comparing speed in such
> situations. Also you replaced the exisiting collision method with the
> new technique - it would probably have been better to introduce it as an
> alternative method so you can compare them more easily.
>
> Christoph
>
Ok, I change it.
Daniel
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Christoph Hormann wrote:
> Daniel Jungmann wrote:
>> Hi,
>>
>> I have nowenableen a patch for faster collision detection. I just made
>> some quick checks and it seems working but might be still a lot of bugs.
>> Fee free to report them all.
>>
>> The zipfile contains the changed source files (mechsim.cpp and mechsim.h)
>> and a diff file. You don't need both of them.
>
> I did not yet have time to test it but from a quick look at the source
> it seems it might lead to slower calculations in cases of:
>
> - relatively few masses
> - situations where grouping works very well (like single masses
> colliding with grid structures).
>
> It would be useful to have some numbers actually comparing speed in such
> situations. Also you replaced the exisiting collision method with the
> new technique - it would probably have been better to introduce it as an
> alternative method so you can compare them more easily.
>
> Christoph
>
Hi,
I have now rewritten the patch for faster collision detection. Now you can
enable and disable them. I made a new switch "bounding" inside mechsim.
MECHSIM:
mechsim { [MECHSIM_ITEMS...] }
MECHSIM_ITEM:
method INTEGER | gravity VECTOR | time_step FLOAT |
step_count INTEGER | time FLOAT | start_time FLOAT |
end_time FLOAT | bounding INTEGER
..
Bounding 0 means no bounding, just like before. Bounding 1 enables bounding
boxes for faces. Bounding 2 enables bounding boxes for faces and hash
bounding. I just made some quick checks and it seems working but there
might be still a lot of bugs. Fee free to report them all. The patch (diff
and changed files) is posted at povray.binaries.programming "MegaPov
collision detection patch 2".
Daniel
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
