# Impact Fracture and Fragmentation of Glass via the 3D Combined Finite-Discrete Element Method +
## 2 Overview of the Combined Finite-Discrete Element Method
### Contact Detection  
In the context of FDEM, contact enforcement is usually conducted in two steps, contact detection and contact interaction [20]. The goal of contact detection is to determine the contact relationship between each finite element and its adjacent elements, while contact interaction algorithms calculate the contact forces between the elements in contact. In typical FDEM applications, the simulation system can have thousands to millions of discrete elements with irregular shapes which can freely move and rotate in space until they are in contact with other elements. As a result, random collisions can occur between any free faces of the discrete elements at any moment. In order to correctly resolve contact relationships in such a complex multibody system, contact detection algorithms are required to have good robustness, be highly efficient and require low memory usage.  
Most of the modern contact detection algorithms can be classified either as tree-based or grid-based algorithms [20]. In the tree-based algorithms, the position and size of each contact body (discrete element or finite element) is represented using a special tree structure, while grid-based algorithms build a data structure by mapping each contact body onto identical background grids (bins). Both groups of algorithms usually contain sort and search components: the data structure is first sorted via selected sorting algorithms and the final contact search is then conducted on the sorted data structure. [PERSON] et al. compared the performance of several selected tree-based and grid-based contact algorithms and showed that selected grid-based algorithms can be 100\(\times\) times faster than tree-based algorithms [29].  
The NBS algorithm is a linear contact detection algorithm that was first proposed by [PERSON] for bodies of similar size [30]. Since NBS features linear sort and linear search algorithms, the total detection time is linearly proportional to the number of contact bodies in the system. Moreover, a special linked-list structure is used in NBS which guarantees that memory usage is nearly proportional to the number of contact bodies. Other grid-based algorithms with linear complexity include the MR and CGRID algorithms, of which both were built on top of the NBS algorithm. The memory usage in MR is exactly proportional to the number of contact bodies [31], while computational efficiency and memory usage in CGRID are insensitive to the size of the contact bodies [32].  
For more recent versions of FDEM, a contact detection algorithm called MRCK was developed to improve contact detection performance [22]. In MRCK, the contact targets are sorted using the MR linear sort which takes advantage of the fact that no contact target can move more than the size of a single cell in a single time step. For a given contactor, a process called \"contactor rendering\" is used to detect all the cells that the contactor currently occupies. The rendering is done in conjunction with the sorted list of targets in such a manner that only the cells that have targets mapped to them are rendered. MRCK significantly speeds up the rendering process since a contactor with no contacts is not rendered at all.