Page 95 - The Combined Finite-Discrete Element Method

78 CONTACT DETECTION

where x and y denote the current coordinates of the centres of the bounding circles.
Each check involves two float point multiplications. Thus, the total number of float point
multiplications necessary to detect all the contacts is given as

2
N − N 2
n N = ∝ N (3.10)
2
The implementation of this algorithm takes a few minutes of a programmer’s time.
However, CPU times for solving large-scale combined finite-discrete element problems
involving even thousands of bodies are large. Consequently, systems comprising millions
of discrete elements are not feasible on present day computers due to the fact that contact
detection is performed millions of times, and the CPU times required can be estimated
from the total number of float-point operation performed, being given by

2
2
F ∝ 1,000,000N = 1,000,000·1,000,000 = 10 18 (3.11)
Such CPU demanding jobs for large enough systems would probably run for centuries
on the most expensive machines. Although this algorithm is very often implemented in
the finite element analysis of contact problems, it is never a part of any serious combined
finite-discrete element code.

3.2.2 Square bounding object

It is assumed that all discrete elements are squares of constant edge a, chosen in such
a way that no point of any discrete element is outside the bounding square. Thus,
the edge of the bounding square is defined by the largest discrete element present,
(Figure 3.5).
A loop over all bounding squares is performed, and each bounding square is checked
against all others for intersection:

a

a
a

a
a

a

Figure 3.5 Identical bounding squares for 2D discrete elements.