Page 127 - The Combined Finite-Discrete Element Method

110 CONTACT DETECTION

(i x ,i y ) with one or more discrete elements assigned to it, i.e. a ‘new’ x ix,iy list. Discrete
elements mapped to each such cell are checked for contact against all discrete elements
mapped to neighbouring cells, as shown in Figure 3.45. For instance, for the list y 7 from
Figure 3.41, the loop over all discrete elements from the list will include discrete elements
10, 7, 4 and 1, resulting in ‘new’ lists x 3,7 ,x 4,7 and x 5,7 being found. Thus, all discrete
elements from lists x 3,7 ,x 4,7 and x 5,7 are checked for contact against discrete elements
from lists of discrete elements mapped to neighbouring cells.
It is worth noting that no loop over cells is performed for any operation described so
far, which leads to the conclusion that the total CPU time needed to perform detection of
contact described is independent of either the total number of cells in the x-direction n x ,
or the total number of cells in the y-direction n y .

Implementation. The implementation of the NBS algorithm in the form of pseudo-code
can be summarised as follows:
1. Loop over all discrete elements(k=0;k≤N;k++)
{ calculate integerised y coordinates of its centre
place the discrete element
onto a list for the corresponding row of cells (y-list)
}
consider all y-lists to be “new” lists
2. Loop over discrete elements(k=0;k≤N;)
{ calculate integerised y coordinates of its centre
if discrete element belongs to a new y-list
{ mark the y-list as an old list and call it central y-list
{ 3. loop over all discrete elements from central y-list
{ integerise x coordinate of the discrete element and place
it onto the corresponding x-list
}
4. loop over all discrete elements from neighbouring (y-)-list
{ integerise x coordinate of the discrete element and place
discrete element onto the corresponding x-list
}
5. loop over all discrete elements from the central y-list
{ if the discrete element belongs to a new list (x,y) list
{ mark the list (x,y) as old and call it central (x,y)-list
check for contact between discrete elements from
the central list (x,y) and lists
(x,y),(x-1,y),(x-1,y-1),(x,y-1), (x+1,y-1)
}
}
}
6. loop over all discrete element from the central y-list
{ remove the corresponding x-list
i.e. set the head of the list to zero
}
7. loop over all discrete element from list (y-1)
{ remove the corresponding x-list,