← Back to team overview

yade-dev team mailing list archive

Re: polyhedron collisions

 

Václav S(milauer said:     (by the date of Sun, 25 Jan 2009 08:40:40 +0100)

> Great to hear that. I hope you will also commit a very simple example,
> like 2 of those bumping into each other.

when I get it to work - yes. Something like SDECSpherePlane, but with
random polyhedrons.

> AFAIK the common solution is to cut the shape into parts that are
> convex, since convex shapes are mathematically easier to handle.

I'm not doing that. In fact it also won't work correctly if two
polyhedrons have multiple surfaces of contact.... But I don't care
about it now.

I used a quite stupid approach of simplifying polyhedron into a list
of parallelepipeds made out of each surface-triangle (and a
tetrahedron, for more precise collision detection). This allows for
quick collision checking - just one dot product and few cross products.
See the comments that I have just committed, if you want...


> There are sophisticated algorithms for detecting triangular surface
> collisions (see httpo://gts.sf.net for some references). For such
> complicated shapes, 

I'm not going this way, it's too complex for me, to understand. And
probably slower too. OTOH my solution is not volume-perfect in
mathematical sense.


> though, what folks in Glasgow do (and what I tried
> with tetraheda) is to treat the intersection as volume, i.e. compute
> volume and direction in which this volume is the thinnest (that is the
> direction of repulsive force); I used exact code for that (which is -
> who knows - maybe incorrect: extra/tetra), Bicanic &co in Glasgow get
> the direction from some averages over normals of planar elements
> involved in the collision.

First I'll try a plane directed directly between centers of both
polyhedrons in contact. If it gives stupid results, then I'll try
least-squares fitting a plane into a cloud of 3D points, using
algorithm directly copied from wildmagic library (LGPL).


> > And is much slower than spheres, so you can forget about simulations
> > with 5000 polyhedrons, anyway.
> >   
> I bet you can forget simulations with 500 polyhedra as well ;-) Do you
> have some benchmarks on that, BTW?

doesn't work yet. So no benchmarks :)

-- 
Janek Kozicki                                                         |



References