← Back to team overview

yade-users team mailing list archive

Re: Contact detection


> We didn't compare with other methods, because we have just this one
> currently implemented. Some papers about SAP (see SIGGRAPH papers,
> they are cited in our publications about yade) say that it's really
> fast :) That's why we used it. But WE don't have a comparison with
> others.

We don't have comparisons because no-one cares about performance. Try
running the same large scenario with esys-particle, pfc3d and yade and
you will see the difference.

Grid colliders ARE MUCH FASTER, at least in terms of scalability, and I
repeatedly suggested on the list that it would be a nice project (for
diploma thesis perhaps) to implement it. Once that is right, domain
decomposition is actually quite easy and so on.

The current collider (InsertionSort, which is PersistentSAP, but faster
and cleaner implementation) is O(N^2) for the initial sort and around
O(N log N) for the subsequent steps, depending on the packing motion
also. This really prevents yade from being used on large packings
(>10^5), even with fast machines. 

Esys-particle uses domain subdivision & grid collisions and (they say)
it takes around 10% of total simulation time, regardless of the number
of particles (scales O(N); see e.g. Munjiza NBS algorithm and
http://www3.interscience.wiley.com/journal/112140923/abstract I
mentioned earlier; esys-particle uses something similar).

Chiara hit the most weak (IMO) point of yade, the collision detection:
scales badly and is not parallelized. It is a serious issue that will
have to be dealt with, sooner or later.

Cheers, Vaclav