Page 98 - The Combined Finite-Discrete Element Method

BINARY TREE BASED CONTACT DETECTION ALGORITHM 81

d

s

Figure 3.7 Simplified definition of the contact detection problem in 2D.

3.4 BINARY TREE BASED CONTACT DETECTION ALGORITHM FOR
DISCRETE ELEMENTS OF SIMILAR SIZE

In this section, a simplified contact detection problem is assumed with all discrete elements
being bounded by a circle of constant diameter d. For contact detection purposes, each
discrete element is therefore uniquely identified by the centre of its bounding circle.
Binary tree based search is a space based search, where space is subdivided into hierar-
chical cells. The size of the smallest cell is made large enough so that the largest discrete
element can fit into a cell, i.e. the size of the smallest single cell is equal to the diameter
of the bounding circle d.
For 2D problems, the space is assumed to coincide with the square large enough to
contain all the discrete elements. At level 1 this space is subdivided into two cells of a
rectangular shape. At level 2 each rectangle is further subdivided into two squares. This
process is continued until the smallest cell is reached, as shown in Figure 3.8.
Thus, for instance, the particular discrete element shown in Figure 3.8 is found to
belong to the successive cells as shown. In other words, each discrete element is mapped
onto b cells, where b is the number of successive subdivisions (levels). In the case shown
in Figure 3.8, there are five levels of space subdivision, thus

b = 5 (3.15)

The mapping of discrete elements onto cells is best represented by a binary tree, as
shown in Figure 3.9. At each level, the left-hand cell and lower cell are represented
by the left-hand node, while the upper cell and right-hand cell are represented by the
right-hand node.
A discrete element shown in Figure 3.8 is mapped onto the nodes of the binary tree, as
shown in Figure 3.9. Level one cells are represented by level one nodes, level two cells
by level two nodes, etc.