Contact Search Theory
DEM simulations often involve a large number of grains where, at any given time, each grain is in contact with a very small number of grains and wall elements. Therefore, an efficient contact search algorithm is required to determine the contact pairs. The Granular Flow Interface uses the no binary search (NBS) algorithm for detecting grain–grain contact pairs and the tree-based search algorithms for determining grain–wall contacts. The two algorithms are briefly described below. More details can be found in Ref. 1.
Grain–Grain Contact Search
The NBS algorithm consists of two steps: broad search and fine search. The broad search first organizes the grains into the grid cells based on their position. The fine search step then checks for potential contacts by surveying the grains in the adjacent cells.
Broad Search
The broad search begins by constructing a uniform rectangular grid across the entire geometry. The length of the grid cell in each direction is constrained to be larger than the maximum contact search radius. The contact search radius for each grain is equal to or greater than the grain radius depending on the Contact search expansion ratio β specified in the Grain Properties feature. Subsequently, if the total number of grid cells in each direction exceeds the Maximum number of cells per direction (specified in the physics interface settings), the grid cell length is adjusted to ensure that these limits are satisfied. Once the grid is constructed, each grain is indexed into a grid cell based on its position.
Fine Search
Once all the grains have been assigned a cell index, the fine search step goes through each grain and checks for contact with every grain in its own cell and the neighboring cells. Note that the choice of the minimum length of the grid cell ensures that this step can be restricted to just the adjacent cells.
To avoid double counting the grain contacts, the fine search is restricted to a subset of neighboring cells. In 2D, if the own cell has the index (0, 0), then the neighboring cells that are searched for are indexed as
Similarly in 3D, if the own cell has the index (0, 0, 0), then the neighboring cells that are searched for are indexed as
Once a contact pair has been identified, the contact information is updated for both grains in the pair.
When a Periodic Condition feature is active in and the target cells are the are near the boundaries of the geometry, the neighboring cell list is modified to ensure that the contacts are detected with the periodic images of the grains from across the periodic boundaries.
When releasing grains, it is often necessary to ensure that the grain being considered for release has an acceptable overlap with preexisting grains. In such situations, every single neighboring cell is scanned (along with the own cell) for potential contacts.
Grain–Wall Contact Search
Tree based algorithms are used to detect grain–wall contacts. The wall elements are initially used to build a quadtree in 2D, or an octree in 3D, which are hierarchical data structures. The root node represents the entire space that is recursively divided into four quadrants in 2D or eight octants in 3D. Each wall element is inserted into the appropriate nodes based on their spatial location.
Once the tree is constructed, the search for a grain–wall contact consists of two stages. In the first stage, the tree is traversed beginning at the root node to identify the nodes of the tree associated with the spatial locations in the vicinity of the grain position. This step restricts the list of potential wall elements that need to be searched for contact. The second stage then searches for contact between the grain and each of the previously identified wall elements.