Page 103 - The Combined Finite-Discrete Element Method

86 CONTACT DETECTION

The total number of operations per discrete element necessary to make a binary tree is
approximately given by

n 1 = (7 additions + 1 division) · b (3.22)

The total number of levels b necessary is a function of the total number of smallest cells.
The lower limit for this number is given by

b = log N (3.23)
2
The upper limit is obviously a function of the distribution of discrete elements in space.
In the cases when discrete elements are sparsely distributed in space this can be very
large. Thus, a lower limit of the total number of operations for building binary tree is
given by
n N = n 1 N = (7 additions + 1 division)b
(3.24)
>(7 additions + 1 division)(N log N)
2
Once the binary tree has been built, contact detection itself can be performed. It is done
in a similar way to how the binary tree has been built. A loop over discrete elements is
performed, and hierarchical cells onto which discrete element is mapped are identified.
Thus, corresponding nodes of the binary tree are followed until the leaf level node corre-
sponding to the smallest cell is reached. Direct check for contact against discrete elements
mapped onto the neighbouring cells is finally performed:

Loop over all discrete elements (i=1; i≤N;i++)
{ Loop over cell levels(j=1; j≤b;j++)
{ check which of the two cells the centre of discrete element is in
if(j=b) collect neighbouring cells at level b and check for contact
against all discrete elements in those cells
}
}
Building a binary tree does not have to be separated from detecting contact. Two
approaches are available:
• The first approach is to completely delete the binary tree after detection is done and
then to rebuild it again. To delete a binary tree, it is enough to set the root to −1,
denoting an empty binary tree, which is an extremely cheap operation in terms of
CPU. In addition, the singly connected lists of discrete elements need to be deleted,
which is done by simply setting all elements of the array E to −1

E[i] =−1; i = 1, 2, 3,...,N (3.25)

meaning the end of lists, i.e. empty lists.
• The second approach is to remember the position of the centre of each discrete element
at the time it was put onto the binary tree. Thus, each discrete element would be
removed from the tree before putting it back onto the tree. This would be done only
if the discrete element has moved significantly. This approach enables rebuilding of