Page 96 - The Combined Finite-Discrete Element Method

DIRECT CHECKING CONTACT DETECTION ALGORITHM 79

Loop over discrete elements (i=1; i<N;i++)
{ Loop over remaining discrete elements (j=i+1; j<N;j++)
{ contact check
}
}
Contact check is a simple operation, given as follows:
a a

x i + < x j − for x i ≤ x j (3.12)
2 2
a a
x j + < x i − for x i >x j
2 2
a a

y i + < y j − for y i ≤ y j
2 2
a a

y j + < y i − for y i >y j
2 2
where x and y denote the current coordinates of the centres of the bounding squares.
Contact check involves no float point multiplication, and is therefore usually a cheaper
operation than in the case of the bounding box being a circle. However, the total number
of operations is still given as
n N ∝ N 2 (3.13)

Again, the implementation of this algorithm takes minutes of a programmer’s time. How-
ever, CPU times for solving problems involving as little as a few thousand discrete
elements are extremely large.

3.2.3 Complex bounding box

It is possible to introduce a more complex bounding box than a square or circle, for
instance, a rectangle of constant edges a and b chosen in such a way that no point of any
discrete element is outside the bounding rectangle (Figure 3.6). Contact check is again a
simple operation as follows:
a a

x i + < x j − for x i ≤ x j (3.14)
2 2
a a

x j + < x i − for x i >x j
2 2
b b

y i + < y j − for y i ≤ y j
2 2
b b

y j + < y i − for y i >y j
2 2
It is in principle possible to select any shape of the bounding box. In addition, different
shapes and sizes of the bounding boxes for each discrete element could be selected. These
improvements could in some cases result in CPU times being reduced by 10%, 20% or
even 500%. However, the major problem would still remain–irrespective of the bounding