Volume 14, Issue 3 (2014)                   MCEJ 2014, 14(3): 43-60 | Back to browse issues page

XML Persian Abstract Print

Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:

Paseh H, Yazdani M, Sharifzadeh M. Evaluation and Improvement of Contact Detection Algorithms for Using in DEM in Rock Mechanics. MCEJ. 2014; 14 (3) :43-60
URL: http://mcej.modares.ac.ir/article-16-10641-en.html
1- Ph.D. student
Abstract:   (4524 Views)
Discrete Element Method (DEM) is a numerical method for computing the motion and effect of a large number of small particles. It is a very common method to solve rock mechanics problems, since it can solve problems containing particles in contact with complicated geometries efficiently. Contact detection is the most time consuming (so the most significant) part of DEM-based problem solving methods. In this article, authors, with the goal of implementing a numerical hydro-mechanical software to analyze and solve DEM rock mechanics problems (DA2), studied and investigated algorithms able to solve contact detection problem. The most algorithms designed to find contacts (contact detection algorithms), lie in two classes: 1) algorithms based on bounding boxes, and 2) algorithms based on hashing. The bounding box idea helps to simplify the contact detection problem and to prevent dealing with particle shapes by enveloping the whole particle in a shape (generally a rectangle or an ellipse) which is easy to check for finding overlaps. Since overlaps of bounding boxes may not directly result in contacts between particles, further checks are needed. In the former class, there are two well-known published algorithms, both based on sorting bounding boxes’ extents, able to find contacts between generally shaped particles in a fast and efficient way: incremental sorting and updating (ISU) algorithm, and double-ended spatial sorting (DESS) algorithm. Hashing algorithms are generally appropriate for particles with uniform sizes. Since rock mechanics problems mostly contain models constituted of blocks with non-uniform sizes, hashing algorithms are not utilized for solving them. In this article, ISU and DESS algorithms along with direct checking (DC) method are compared for their running time results to find the most appropriate (i.e. the fastest) algorithm to find contacts between rock blocks. For this purpose, algorithms were implemented by DA2 software, then, ran in the same environment and for same commonplace geomechanical problems with varying model parameters, like number of blocks, block size variation, angle of discontinuities and friction angle, and compared for their running time results. Results shows that ISU algorithm compared to DESS algorithm gives better/lower running time (ISU is at least twice as fast as DESS), i.e. more performance, and shows less sensitivity to model parameters. Also, ISU algorithm consumes less memory and it is simpler to implement. In the end, for further improvement of performance of ISU algorithm, delayed updating and parallelization solutions are offered. Delayed updating is a common way to optimize algorithms containing two phases of processing and updating. In order to apply delayed updating and parallelization to ISU algorithm, a solution is presented to separate sorting and updating phases of the algorithm. Then, parallelization is applied. Results show that using these techniques, can increase the performance of ISU algorithm by 20%.
Full-Text [PDF 1476 kb]   (1951 Downloads)    
Article Type: Original Manuscript | Subject: -------
Received: 2013/10/8 | Accepted: 2014/05/1 | Published: 2015/01/21

Add your comments about this article : Your username or Email:

Rights and permissions
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.