Page 104 - The Combined Finite-Discrete Element Method

DIRECT MAPPING ALGORITHM FOR DISCRETE ELEMENTS OF SIMILAR SIZE 87

the binary tree, and is used, for instance, when most of the discrete elements do not
move. In such a case, it is easier to simply remove those discrete elements that have
moved and place them onto the tree again. The contact check is necessary only for
these discrete elements. This way the contact detection in these particular cases can be
speeded up.

3.5 DIRECT MAPPING ALGORITHM FOR DISCRETE ELEMENTS
OF SIMILAR SIZE

It is not always necessary to use a binary tree to get an efficient spatial based search. Space
subdivision into cells and subsequent mapping of discrete elements onto cells lends itself
well to being used with sorting algorithms. The basic idea is relatively simple. Instead of
dividing the space into a hierarchy of cells, as in the case of the binary tree, the space is
divided into cells all of the same size, as shown in Figure 3.15. The size of individual cells
is chosen so that the largest discrete element contained by the system can be fitted into
a single cell. Thus, the size of the cells is equal to the diameter of the bounding circle,
which for a simplified contact detection problem is the same for all discrete elements
(Figure 3.16).
Contact detection is performed in two steps:

Step 1: Map discrete elements onto cell: discrete elements are mapped onto cells according
to the current position of the centre of the individual discrete element. Thus, each discrete
element is mapped to one and only one cell. This in essence involves only integerisation

10

9
8
•5 •4
7 9• •7
•3 •1 •2
•6
6 •8
5

4
3 d

y 2 d
1
x min
y min 1 2 3 4 5 6 7 8 9 10
x

Figure 3.15 Space divided into identical cells large enough to contain the largest discrete element
comprising the system. Discrete element centres are marked with dots.