Page 100 - The Combined Finite-Discrete Element Method

BINARY TREE BASED CONTACT DETECTION ALGORITHM 83

Initially, only the root of the binary tree is necessary. As the discrete elements are
mapped onto the cells, the binary tree is being built node by node until all discrete
elements are ‘loaded’ onto the tree.
Contact detection for each discrete element consists in identifying which cells a par-
ticular discrete element is mapped onto, and thus identifying the smallest cell together
with its neighbouring cells. Contact detection itself is then done in a way similar to the
direct checking approach, except that only discrete elements in the neighbouring cells
are considered.
The algorithm for creating the binary tree can be summarised as follows:

Loop over all discrete elements (i=1; i≤N;i++)
{ Loop over cell levels(j=1; j≤b;j++)
{ check in which of the two cells the centre of the discrete element
is located
if the corresponding node of the binary tree does not exist,
create it
if(j=b) add discrete element i onto the connected list
of discrete elements that are mapped onto the current cell
}
}

It can be seen that the creation of the binary tree involves b loops over cell levels for
each discrete element. Inside each loop, the following operations are performed:

• Step 1: calculation of the boundary between cells. This involves operation of the type
(see Figure 3.10):
x min + x max
x mid = (3.16)
2

Cell level = j−1 Cell level = j

y
x min
x mid

x max

x

Figure 3.10 Calculation of boundary between cells; parent cell (level j − 1) is divided into two
child cells (level j).