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