非均匀颗粒快速线性接触检测算法

A fast linear contact detection algorithm for discrete particles of arbitrary sizes

提出一种适用于非均匀离散颗粒体系的接触检测算法,时间复杂度为O(n),对内存的占用较小,对于大规模、分布密集、大粒径比的颗粒体系具有较高的效率。在NBS (no binary search)接触检测算法的基础上进行改进,提高了对于非均匀颗粒体系的适用性。采用对颗粒进行分组,对检测过程分步的策略提高了邻居检索精度;通过设置基于包围盒的初判环节减少了接触判断次数,解决了颗粒尺寸非均匀造成的效率下降问题。颗粒分组方式简单,易于调整,对于各种不同级配的颗粒体系具有广泛的适用性。通过算例验证了算法的性能,在非均匀颗粒体系中相对于NBS算法具有明显的优势。

A new contact detection algorithm is proposed for the system of greatly differing particle sizes. The time complexity is linear with the particle number and the memory consumption is low. The algorithm has significant advantages to tackle the problems which have a large number of particles with arbitrary sizes and high density. Improved based on the NBS(no binary search)algorithm, the algorithm is more applicable to the polydisperse system with a multistep strategy than the NBS algorithm. With the particles divided into several groups and the detection progress divided into different steps, the particles in the same group can be considered as uniform and the size of grid can be set separately for different steps. As a result, the accuracy of the neighbour searching is increased. The number of the geometry resolution is decreased by setting the primary checking of the bounding boxes when the number of potential contact particles is more than 4. The number of groups is determined by a parameter previously chosen and is easily adjusted with different size gradations, so the algorithm has applicability to a wide range of particle systems. The properties of the algorithm are tested in several examples with different size gradation and the results show clear advantages over NBS algorithm.