颗粒团聚过程准确碰撞检测快速算法
|
摘要
碰撞检测的传统算法在应对大量颗粒碰撞团聚时往往执行效率低下,为此提出一种基于"包围球-最大检测区域"预处理的两步式准确碰撞检测快速算法.粗略筛选阶段:所有团聚体用更新成本低的包围球替代表示,并将包围球间的碰撞检测转变为求解关于时间的一元二次方程问题,通过并行求解这些方程快速筛选出所有可能发生的碰撞;忽略最大检测区域外的碰撞检测以进一步缩短执行时间.精细确定阶段:采用离散碰撞检测快速确定碰撞发生的具体时间和位置;在该阶段,采样时间间隔是自适应的且逐渐减小.将模拟计算结果与未优化的传统算法结果进行对比后发现,在满足相同碰撞检测准确性的前提下,提出的算法将执行效率提升了10～30倍,表明此算法更加适用于大量颗粒团聚过程中的碰撞检测.
The traditional algorithms of collision detection often have poor execution efficiency in dealing with the aggregation following collision of a large number of particles. Therefore, a two-step, fast and accurate algorithm of collision detection was proposed based on the pretreatment of bounding sphere and maximum detection region. In the broad phase, all aggregates were represented by bounding spheres with low update cost. The detection of collisions between bounding spheres was converted into solving the problem of quadratic equations regarding time,and all possible collisions were detected fast by solving these equations parallelly. The detection of collisions outside the maximum detection region was ignored to further reduce execution time. In the narrow phase, the specific time and position of collisions were rapidly determined by discrete collision detection, where sampling time intervals were self-adaptive and decreasing. Simulation results were compared with those by non-optimized traditional algorithms, and it was found that, on the premise of meeting the same accuracy of collision detection the algorithm proposed here could increase the execution efficiency 10 to 30 times, indicating that this algorithm is more applicable to collision detection during the aggregation process of a large number of particles.
The traditional algorithms of collision detection often have poor execution efficiency in dealing with the aggregation following collision of a large number of particles. Therefore, a two-step, fast and accurate algorithm of collision detection was proposed based on the pretreatment of bounding sphere and maximum detection region. In the broad phase, all aggregates were represented by bounding spheres with low update cost. The detection of collisions between bounding spheres was converted into solving the problem of quadratic equations regarding time,and all possible collisions were detected fast by solving these equations parallelly. The detection of collisions outside the maximum detection region was ignored to further reduce execution time. In the narrow phase, the specific time and position of collisions were rapidly determined by discrete collision detection, where sampling time intervals were self-adaptive and decreasing. Simulation results were compared with those by non-optimized traditional algorithms, and it was found that, on the premise of meeting the same accuracy of collision detection the algorithm proposed here could increase the execution efficiency 10 to 30 times, indicating that this algorithm is more applicable to collision detection during the aggregation process of a large number of particles.
引文
[1]KUSAKA Y,FUKASAWA T,ADACHIA Y.Cluster-cluster aggregation simulation in a concentrated suspension[J].Journal of Colloid and Interface Science,2011,363:34-41.
[2]WANG Y F,HUANG Q X,WANG F,et al.Brownian dynamics simulation of soot primary particle aggregation in laminar ethylene diffusion flames[J].Physica A,2019,514:936-947.
[3]张忠辉,丑武胜.可变形物体间的精确碰撞检测方法研究[J].计算机工程与应用,2009,45(1):176-178.ZHANG Zhong-hui,CHOU Wu-sheng.Research on precise collision detection between deformable objects[J].Computer Engineering and Applications,2009,45(1):176-178.
[4]于瑞云,赵金龙,余龙,等.结合轴对齐包围盒和空间划分的碰撞检测算法[J].中国图像图形学报,2018,23(12):1925-1937.YU Rui-yun,ZHAO Jin-long,YU Long,et al.Collision detection algorithm based on AABBbounding box and space division[J].Journal of Image and Graphics,2018,23(12):1925-1937.
[5]孙劲光,吴素红.基于空间分割与椭球包围盒的碰撞检测算法[J].计算机工程与应用,2016,52(4):217-222.SUN Jin-guang,WU Su-hong.Collision detection algorithm based on ellipsoid bounding box and spatial decomposition[J].Computer Engineering and Applications,2016,52(4):217-222.
[6]李炎,卢晓军,贺汉根.USSCD:一个基于均匀空间分割的快速碰撞检测算法[J].中国图像图形学报,2003,8(12):1444-1449.LI Yan,LU Xiao-jun,HE Han-gen.USSCD:a fast collision detection algorithm based on uniform spatial subdivision[J].Journal of Image and Graphics,2003,8(12):1444-1449.
[7]范昭炜,万华根,高曙明.基于图像的快速碰撞检测算法[J].计算机辅助设计与图形学报,2002,14(9):805-810.FAN Zhao-wei,WAN Hua-gen,GAO Shu-ming.Afast collision detection algorithm in image space[J].Journal of Computer-Aided Design and Computer Graphics,2002,14(9):805-810.
[8]邹益胜,丁国富,周晓莉,等.一种基于图像空间的碰撞检测算法[J].系统仿真学报,2011,23(5):944-949.ZOU Yi-sheng,DING Guo-fu,ZHOU Xiao-li,et al.Collision detection algorithm based on image space[J].Journal of System Simulation,2011,23(5):944-949.
[9]FOSS D R,BRADY J F.Brownian dynamics simulation of hard-sphere colloidal dispersions[J].Journal of Rheology,2002,44(3):629-651.
[10]BANCHIO A J,BERGENHOLTZ J,NAGELE G.Rheology and dynamics of colloidal dispersions[J].Physical Review Letters,1999,82:1792-1795.
[11]CHEN J C,KIM A S.Brownian dynamics,molecular dynamics,and Monte Carlo modeling of colloidal systems[J].Advances in Colloid and Interface Science,2004,112:159-173.
[12]WATANABE M,TANAKA D.Brownian dynamics simulation of the aggregation of submicron particles in static gas[J].Computers and Chemical Engineering,2013,54:151-158.
[13]DOPERTCHOUK O.Simple bounding-sphere collision detection[EB/OL].[2019-02-18].https://www.gamedev.net/articles/programming/mat h-and-physics/simple-bounding-sphere-collisiondetection-r1234.
[14]ANDERSON L.Realistic billiards simulation with variable time-step[EB/OL].[2019-02-18].https://www.cs.rpi.edu/~cutler/classes/advancedgrap hics/S09/final_projects/anderson.pdf.
[15]黄伟益.基于GPU并行加速碰撞检测算法的研究[D].重庆:重庆大学,2015:11-29.HUANG Wei-yi.Research on collision detection algorithm based on GPU parallel speed up[D].Chongqing:Chongqing University,2015:11-29.
[16]水泳.虚拟现实中连续碰撞检测算法研究[D].合肥:中国科学技术大学,2013:2-17.SHUI Yong.Research on continuous collision detection algorithm in virtual reality[D].Hefei:University of science and technology of China,2013:2-17.
[17]DONER N,LIU F S.Impact of morphology on the radiative properties of fractal soot aggregates[J].Journal of Quantitative Spectroscopy and Radiative Transfer,2017,187:10-19.
[18]BOURG D M,BYWALEC B.Physics for game developers[M].2nd ed.Sebastopol:O’REILLY,2013.
[19]WANG Y F,HUANG Q X,WANG F,et al.Afeasible and accurate method for calculating the radiative properties of soot particle ensembles in flames[J].Journal of Quantitative Spectroscopy and Radiative Transfer,2019,224:222-232.
[2]WANG Y F,HUANG Q X,WANG F,et al.Brownian dynamics simulation of soot primary particle aggregation in laminar ethylene diffusion flames[J].Physica A,2019,514:936-947.
[3]张忠辉,丑武胜.可变形物体间的精确碰撞检测方法研究[J].计算机工程与应用,2009,45(1):176-178.ZHANG Zhong-hui,CHOU Wu-sheng.Research on precise collision detection between deformable objects[J].Computer Engineering and Applications,2009,45(1):176-178.
[4]于瑞云,赵金龙,余龙,等.结合轴对齐包围盒和空间划分的碰撞检测算法[J].中国图像图形学报,2018,23(12):1925-1937.YU Rui-yun,ZHAO Jin-long,YU Long,et al.Collision detection algorithm based on AABBbounding box and space division[J].Journal of Image and Graphics,2018,23(12):1925-1937.
[5]孙劲光,吴素红.基于空间分割与椭球包围盒的碰撞检测算法[J].计算机工程与应用,2016,52(4):217-222.SUN Jin-guang,WU Su-hong.Collision detection algorithm based on ellipsoid bounding box and spatial decomposition[J].Computer Engineering and Applications,2016,52(4):217-222.
[6]李炎,卢晓军,贺汉根.USSCD:一个基于均匀空间分割的快速碰撞检测算法[J].中国图像图形学报,2003,8(12):1444-1449.LI Yan,LU Xiao-jun,HE Han-gen.USSCD:a fast collision detection algorithm based on uniform spatial subdivision[J].Journal of Image and Graphics,2003,8(12):1444-1449.
[7]范昭炜,万华根,高曙明.基于图像的快速碰撞检测算法[J].计算机辅助设计与图形学报,2002,14(9):805-810.FAN Zhao-wei,WAN Hua-gen,GAO Shu-ming.Afast collision detection algorithm in image space[J].Journal of Computer-Aided Design and Computer Graphics,2002,14(9):805-810.
[8]邹益胜,丁国富,周晓莉,等.一种基于图像空间的碰撞检测算法[J].系统仿真学报,2011,23(5):944-949.ZOU Yi-sheng,DING Guo-fu,ZHOU Xiao-li,et al.Collision detection algorithm based on image space[J].Journal of System Simulation,2011,23(5):944-949.
[9]FOSS D R,BRADY J F.Brownian dynamics simulation of hard-sphere colloidal dispersions[J].Journal of Rheology,2002,44(3):629-651.
[10]BANCHIO A J,BERGENHOLTZ J,NAGELE G.Rheology and dynamics of colloidal dispersions[J].Physical Review Letters,1999,82:1792-1795.
[11]CHEN J C,KIM A S.Brownian dynamics,molecular dynamics,and Monte Carlo modeling of colloidal systems[J].Advances in Colloid and Interface Science,2004,112:159-173.
[12]WATANABE M,TANAKA D.Brownian dynamics simulation of the aggregation of submicron particles in static gas[J].Computers and Chemical Engineering,2013,54:151-158.
[13]DOPERTCHOUK O.Simple bounding-sphere collision detection[EB/OL].[2019-02-18].https://www.gamedev.net/articles/programming/mat h-and-physics/simple-bounding-sphere-collisiondetection-r1234.
[14]ANDERSON L.Realistic billiards simulation with variable time-step[EB/OL].[2019-02-18].https://www.cs.rpi.edu/~cutler/classes/advancedgrap hics/S09/final_projects/anderson.pdf.
[15]黄伟益.基于GPU并行加速碰撞检测算法的研究[D].重庆:重庆大学,2015:11-29.HUANG Wei-yi.Research on collision detection algorithm based on GPU parallel speed up[D].Chongqing:Chongqing University,2015:11-29.
[16]水泳.虚拟现实中连续碰撞检测算法研究[D].合肥:中国科学技术大学,2013:2-17.SHUI Yong.Research on continuous collision detection algorithm in virtual reality[D].Hefei:University of science and technology of China,2013:2-17.
[17]DONER N,LIU F S.Impact of morphology on the radiative properties of fractal soot aggregates[J].Journal of Quantitative Spectroscopy and Radiative Transfer,2017,187:10-19.
[18]BOURG D M,BYWALEC B.Physics for game developers[M].2nd ed.Sebastopol:O’REILLY,2013.
[19]WANG Y F,HUANG Q X,WANG F,et al.Afeasible and accurate method for calculating the radiative properties of soot particle ensembles in flames[J].Journal of Quantitative Spectroscopy and Radiative Transfer,2019,224:222-232.