yade-dev team mailing list archive

[Fernando Alonso-Marroquin <fernando@xxxxxxxxxxxxxxxxx>]

Hi Vaclav

Thank you very much for your interesting questions
> Hi Fernando,
>
> thanks for your code. After a quick look, I have some questions; feel 
> free to let me know that I didn't read the code right.
>
> 1. For poly-poly intersection, you check all edges in poly1 against 
> all edges in poly2 (Interacton.cpp:95). That scales badly (i.e. 
> O(n^2)) and will be unusable for more complicated polyhedra; I think 
> that GTS or similar libraries have somehow optimized this (using 
> spatial search trees, I think, but I am not familiar with that).
Actually it scales even more badly as you think. We calculate non only 
edge-edge interactions, but also vertex-face interactions. Besides, we 
still do not have a neighbor
search algorithm, so the complexity scales as 0(n^2 N^2), where N is the 
number of
particles.  First I want to get rid from the N^2 term, by using the 
neighbor detection
(cut and prune..) algorithm in YADE. The algorithm is usable for 
arbitrary shaped particles,
although it has not optimized yet. We have used a Verlet algorithm to 
reduce the
complexity to 0(N), but so far it has been implemented only in 2D

Please find the detail of the algorithm is the paper:

http://physics.uq.edu.au/people/fernando/papers/spheropolygons.pdf

> 2. The repulsive force of both polyhedra depends on penetration of 
> their bounding spheres, do I read it right? 
> (dist=normOf(distance_Edge3d_Edge3d(...)); delta=R1+R2-dist; 
> if(delta>0){ f=n*(Kn*delta) }). I am wondering how that could give 
> correct results, especially for complex shapes like the jumping cow 
> you sent.
The idea is to allow multiple contacts between each pair of interacting 
bodies.  The
contact interactions are given by well defined equations, that you can 
found in this paper.

http://physics.uq.edu.au/people/fernando/papers/spheropolygons2.pdf.

The last equation, at the end of the paper, is the interaction law for 
3D simulations
> 3. Concerning integration into yade, how do we detect collisions? As 
> we use aabb's, for irregular shapes the aabb will contain many other 
> bodies that will not be in contact; but at every step, their contact 
> will have to be checked for distance. Would it be possible to break 
> (for instance) the polyhedron into many faces, compute collisions with 
> single faces (like we do with Facets now) and then interaction the 
> polyhedra as whole or something similar? (BTW we really should use 
> grid-based collision detection, esys does that and they take no more 
> than around 10% at the collision detection even for very large 
> simulations).
BTW: what does means "aabb"? esys refers to esys_Particle?

As far as I know YADE detect collision by enclosing particles in a box 
and checking
whether the boxes overlap. for complex shapes I dont think there is a 
large difference
between this and grid-based (link cell) collision-detection. As you say, 
the most important
is to break the particle into features, and then perform neighbor 
identification  between
their features (in my case the features are vertices ,edges and faces). 
This is something I did in 2D and that  i have to do in 3D in order to 
speed up the simulations. But for the moment the contact detection of 
YADE is enough for me
> To summarize, for anything except Polyhedron-polyhedron, one's 
> probably better off using facets that we have already; if dynamic 
> behavior is needed, clumped facets with some mass-bearing sphere in 
> the middle will do. I thought you would have some sophisticated 
> algorithms for poly-poly interactions, but it doesn't seem to be the 
> case.
You are right, SPOLY3D is not intended to be sophisticated, but it is a 
simple algorithm
to handle collision with arbitrary shaped particles. My interest is to 
merge SPOLY3D with the contact detection algorithm and graphical 
interface of YADE.  I really think YADE is one of the best option, and i 
hope I will became one of the YADE's supporters for the future.
> I did run the examples, but didn't see them as I don't have povray 
> installed here, sorry.
povray is in ubuntu repository, you can install it with synaptic manager.
> Cheers, Vaclav
Cheers

Fernando