非均匀颗粒快速线性接触检测算法
|
摘要
提出一种适用于非均匀离散颗粒体系的接触检测算法,时间复杂度为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.
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.
引文
[1]CUNDALL P A.A computer model for simulating progressive,large scale movements in blocky rock systems[C]//International Symposium on Rock Mechanics.Nancy:[s.n.],1971.
[2]CUNDALL P A,STRACK O D L.A discrete numerical model for granular assemblies[J].Geotechnique,1979,29(1):47-65.
[3]WILLIAMS J R,O'CONNOR R.Discrete element simulation and the contact problem[J].Archives of Computational Methods in Engineering,1999,6(4):279-304.
[4]苏凤环,姚令侃,陈春光.三维离散单元法数值模拟中查找邻居元的一种新算法[J].计算机应用,2004,24(1):149-151.SU Feng-huan,YAO Ling-kan,CHEN Chun-guang.Anew algorithm for determining neighborhood in three-dimensional DEM simulation[J].Computer Applications,2004,24(1):149-151.
[5]周先齐,徐卫亚,钮新强,等.离散单元法研究进展及应用综述[J].岩土力学,2007,28(增刊1):408-416.ZHOU Xian-qi,XU Wei-ya,NIU Xin-qiang,et al.Areview of distinct element method researching progress and application[J].Rock and Soil Mechanics,2007,28(Suppl.1):408-416.
[6]MUNJIZA A,ANDREWS K R F.NBS contact detection algorithm for bodies of similar size[J].International Journal for Numerical Methods in Engineering,1998,43(1):131-149.
[7]黄绵松,安雪晖.颗粒离散元的HACell检索算法用于SCC模拟[J].清华大学学报(自然科学版),2010,50(9):1357-1360.HUANG Mian-song,AN Xue-hui.HACell detection algorithm of particle discrete element for use in simulations of self-compacting concrete[J].Journal of Tsinghua University(Science and Technology),2010,50(9):1357-1360.
[8]刘勋楠,赵兰浩,毛佳,等.三维距离势离散单元法[J].岩土力学,2018,39(7):2639-2650.LIU Xun-nan,ZHAO Lan-hao,MAO Jia,et al.Discrete element method using three dimensional distance potential[J].Rock and Soil Mechanics,2018 39(7):2639-2650.
[9]MIRTICH B.Efficient algorithms for two phase collision detection[R].[S.l.]:Mitsubishi Electric Research Laboratory,1997.
[10]ERICSON C.Real-time collision detection[M].[S.l.]:CRC Press,2004.
[11]游灵聪.分布式多层次粒子碰撞检测算法[D].广州:华南理工大学,2015.YOU Ling-cong.Distributed multi-layer particle contact detection algorithms[D].Guangzhou:South China University of Technology,2015.
[12]HAN K,FENG Y T,OWEN D R J.Performance comparisons of tree-based and cell-based contact detection algorithms[J].Engineering Computations,2007,24(2):165-181.
[13]MUNJIZA A.The combined finite-discrete element method[M].[S.l.]:John Wiley&Sons,2004.
[14]BONET J,PERAIRE J.An alternating digital tree(ADT)algorithm for 3D geometric searching and intersection problems[J].International Journal for Numerical Methods in Engineering,1991,31(1):1-17.
[15]FENG Y T,OWEN D R J.An augmented spatial digital tree algorithm for contact detection in computational mechanics[J].International Journal for Numerical Methods in Engineering,2002,55(2):159-176.
[16]PERKINS E,WILLIAMS J R.A fast contact detection algorithm insensitive to particle sizes[J].Engineering Computations,2001,18(1/2):48-62.
[17]HOCKNEY R W,EASTWOOD J W.Computer simulation using particles[M].[S.l.]:Taylor&Francis,Inc.,1981.
[18]IWAI T,HONG C W,GREIL P.Fast particle pair detection algorithms for particle simulations[J].International Journal of Modern Physics C,1999,10(5):823-837.
[19]MIO H,SHIMOSAKA A,SHIRAKAWA Y,et al.Cell optimization for fast contact detection in the discrete element method algorithm[J].Advanced Powder Technology,2007,18(4):441-453.
[20]OGARKO V,LUDING S.A fast multilevel algorithm for contact detection of arbitrarily polydisperse particles[J].Computer Physics Communications,2012,183(4):931-936.
[21]PETERS J F,KALA R,MAIER R S.A hierarchical search algorithm for discrete element method of greatly differing particle sizes[J].Engineering Computations,2009,26(6):621-634.
[22]WILLIAMS J R,PERKINS E,COOK B.A contact algorithm for partitioning N arbitrary sized particles[J].Engineering Computations,2004,21(2/3/4):235-248.
[23]HE K,DONG S,ZHOU Z.Multigrid contact detection method[J].Physical Review E,2007,75(3):036710.
[24]KRIJGSMAN D,OGARKO V,LUDING S.Optimal parameters for a hierarchical grid data structure for contact detection in arbitrarily polydisperse particle systems[J].Computational Particle Mechanics,2014,1(3):357-372.
[25]薛亚东,刘忠强,吴坚.崩积混合体直剪试验与PFC2D数值模拟分析[J].岩土力学,2014,35(增刊2):587-592.XUE Ya-dong,LIU Zhong-qiang,WU Jian.Direct shear tests and PFC2D numerical simulation of colluvial mixture[J].Rock and Soil Mechanics,2014,35(Suppl.2):587-592.
[2]CUNDALL P A,STRACK O D L.A discrete numerical model for granular assemblies[J].Geotechnique,1979,29(1):47-65.
[3]WILLIAMS J R,O'CONNOR R.Discrete element simulation and the contact problem[J].Archives of Computational Methods in Engineering,1999,6(4):279-304.
[4]苏凤环,姚令侃,陈春光.三维离散单元法数值模拟中查找邻居元的一种新算法[J].计算机应用,2004,24(1):149-151.SU Feng-huan,YAO Ling-kan,CHEN Chun-guang.Anew algorithm for determining neighborhood in three-dimensional DEM simulation[J].Computer Applications,2004,24(1):149-151.
[5]周先齐,徐卫亚,钮新强,等.离散单元法研究进展及应用综述[J].岩土力学,2007,28(增刊1):408-416.ZHOU Xian-qi,XU Wei-ya,NIU Xin-qiang,et al.Areview of distinct element method researching progress and application[J].Rock and Soil Mechanics,2007,28(Suppl.1):408-416.
[6]MUNJIZA A,ANDREWS K R F.NBS contact detection algorithm for bodies of similar size[J].International Journal for Numerical Methods in Engineering,1998,43(1):131-149.
[7]黄绵松,安雪晖.颗粒离散元的HACell检索算法用于SCC模拟[J].清华大学学报(自然科学版),2010,50(9):1357-1360.HUANG Mian-song,AN Xue-hui.HACell detection algorithm of particle discrete element for use in simulations of self-compacting concrete[J].Journal of Tsinghua University(Science and Technology),2010,50(9):1357-1360.
[8]刘勋楠,赵兰浩,毛佳,等.三维距离势离散单元法[J].岩土力学,2018,39(7):2639-2650.LIU Xun-nan,ZHAO Lan-hao,MAO Jia,et al.Discrete element method using three dimensional distance potential[J].Rock and Soil Mechanics,2018 39(7):2639-2650.
[9]MIRTICH B.Efficient algorithms for two phase collision detection[R].[S.l.]:Mitsubishi Electric Research Laboratory,1997.
[10]ERICSON C.Real-time collision detection[M].[S.l.]:CRC Press,2004.
[11]游灵聪.分布式多层次粒子碰撞检测算法[D].广州:华南理工大学,2015.YOU Ling-cong.Distributed multi-layer particle contact detection algorithms[D].Guangzhou:South China University of Technology,2015.
[12]HAN K,FENG Y T,OWEN D R J.Performance comparisons of tree-based and cell-based contact detection algorithms[J].Engineering Computations,2007,24(2):165-181.
[13]MUNJIZA A.The combined finite-discrete element method[M].[S.l.]:John Wiley&Sons,2004.
[14]BONET J,PERAIRE J.An alternating digital tree(ADT)algorithm for 3D geometric searching and intersection problems[J].International Journal for Numerical Methods in Engineering,1991,31(1):1-17.
[15]FENG Y T,OWEN D R J.An augmented spatial digital tree algorithm for contact detection in computational mechanics[J].International Journal for Numerical Methods in Engineering,2002,55(2):159-176.
[16]PERKINS E,WILLIAMS J R.A fast contact detection algorithm insensitive to particle sizes[J].Engineering Computations,2001,18(1/2):48-62.
[17]HOCKNEY R W,EASTWOOD J W.Computer simulation using particles[M].[S.l.]:Taylor&Francis,Inc.,1981.
[18]IWAI T,HONG C W,GREIL P.Fast particle pair detection algorithms for particle simulations[J].International Journal of Modern Physics C,1999,10(5):823-837.
[19]MIO H,SHIMOSAKA A,SHIRAKAWA Y,et al.Cell optimization for fast contact detection in the discrete element method algorithm[J].Advanced Powder Technology,2007,18(4):441-453.
[20]OGARKO V,LUDING S.A fast multilevel algorithm for contact detection of arbitrarily polydisperse particles[J].Computer Physics Communications,2012,183(4):931-936.
[21]PETERS J F,KALA R,MAIER R S.A hierarchical search algorithm for discrete element method of greatly differing particle sizes[J].Engineering Computations,2009,26(6):621-634.
[22]WILLIAMS J R,PERKINS E,COOK B.A contact algorithm for partitioning N arbitrary sized particles[J].Engineering Computations,2004,21(2/3/4):235-248.
[23]HE K,DONG S,ZHOU Z.Multigrid contact detection method[J].Physical Review E,2007,75(3):036710.
[24]KRIJGSMAN D,OGARKO V,LUDING S.Optimal parameters for a hierarchical grid data structure for contact detection in arbitrarily polydisperse particle systems[J].Computational Particle Mechanics,2014,1(3):357-372.
[25]薛亚东,刘忠强,吴坚.崩积混合体直剪试验与PFC2D数值模拟分析[J].岩土力学,2014,35(增刊2):587-592.XUE Ya-dong,LIU Zhong-qiang,WU Jian.Direct shear tests and PFC2D numerical simulation of colluvial mixture[J].Rock and Soil Mechanics,2014,35(Suppl.2):587-592.