Page 135 - The Combined Finite-Discrete Element Method

118 CONTACT DETECTION

The Munjiza-NBS contact detection algorithm is slightly less efficient than the sorting
algorithm in terms of RAM requirements. However, this algorithm, while being gentle in
terms of RAM requirements, is superior in terms of CPU requirements.
The binary tree based contact detection algorithms were among the first contact detec-
tion algorithms used in the combined finite-discrete element method. Now, the binary tree
based contact detection algorithms are mostly of historical value for most of the large
scale combined finite-discrete element simulations. These algorithms have been super-
seded by the new generation of algorithms, which are superior in terms of both RAM
and CPU requirements. It is also worth noting that the implementation of the binary tree
based contact detection algorithms is much more complex than that of most of the new
generation of algorithms.

3.10 GENERALISATION OF CONTACT DETECTION ALGORITHMS
TO 3D SPACE

All the contact detection algorithms listed in this chapter have conveniently been explained
using 2D space. In this section, an extension to 3D space is given for each of the
algorithms.

3.10.1 Direct checking contact detection algorithm

Extension of the direct checking contact detection algorithm into 3D space is straight-
forward. The bounding box becomes a 3D object (say sphere), while the check for
contact becomes
2
2
2
(x i − x j ) + (y i − y j ) + (z i − z j ) <d 2 (3.69)
where x, y and z denote the centre coordinates of bounding spheres, while d is the
diameter of the spheres.

3.10.2 Binary tree search

Extension of the binary tree search based contact detection algorithm to 3D space involves
the addition of successive subdivisions of the space in the z-direction, as shown in
Figure 3.54.
The space is first divided into two halves through division in the x-direction (level
1). Subsequent subdivision in the y-direction (level 2) is followed by subdivision in the
z-direction (level 3). This in turn is followed by another subdivision in the x-direction
(level 4), which is followed by subdivision in the y-direction (level 5) and subdivision
in the z-direction (level 6), followed by subdivision in the x-direction (level 7), etc. until
the smallest cell is reached.

3.10.3 Screening contact detection algorithm

Extension of the screening contact detection algorithm into 3D space involves subdivision
of the 3D space into identical cube shaped cells, as shown in Figure 3.55.