Performance comparisons of bonding box-based contact detection algorithms and a new improvement technique based on parallelization

Abstract

Purpose

The purpose of this paper is to find a convenient contact detection algorithm in order to apply in distinct element simulation.

Design/methodology/approach

Taking the most computation effort, the performance of the contact detection algorithm highly affects the running time. The algorithms investigated in this study consist of Incremental Sort-and-Update (ISU) and Double-Ended Spatial Sorting (DESS). These algorithms are based on bounding boxes, which makes the algorithm independent of blocks shapes. ISU and DESS algorithms contain sorting and updating phases. To compare the algorithms, they were implemented in identical examples of rock engineering problems with varying parameters.

Findings

The results show that the ISU algorithm gives lower running time and shows better performance when blocks are unevenly distributed in both axes. The conventional ISU merges the sorting and updating phases in its naïve implementation. In this paper, a new computational technique is proposed based on parallelization in order to effectively improve the ISU algorithm and decrease the running time of numerical analysis in large-scale rock mass projects.

Originality/value

In this approach, the sorting and updating phases are separated by minor changes in the algorithm. This tends to a minimal overhead of running time and a little extra memory usage and then the parallelization of phases can be applied. On the other hand, the time consumed by the updating phase of ISU algorithm is about 30 percent of the total time, which makes the parallelization justifiable. Here, according to the results for the large-scale problems, this improved technique can increase the performance of the ISU algorithm up to 20 percent.

Citation

Yazdani, M., Paseh, H. and Sharifzadeh, M. (2016), "Performance comparisons of bonding box-based contact detection algorithms and a new improvement technique based on parallelization", Engineering Computations, Vol. 33 No. 1, pp. 7-27. https://doi.org/10.1108/EC-05-2014-0102