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.
Ya-fei WANG,Qun-xing HUANG,Fei WANG,Yong CHI,Jian-hua YAN. High-speed algorithm for accurate collision detection during particle aggregation. Journal of ZheJiang University (Engineering Science), 2019, 53(6): 1148-1156.
Fig.1Schematic diagram of bounding sphere of aggregates
Fig.2Illustration of elapsed time and remaining time
Fig.3Structural relation of MCR and MDR
Fig.4Geometrical relation of two bounding spheres colliding with each other
Fig.5Collision detection between particles in intersection of two bounding spheres
序号
预处理
主过程
算法 1
无
DCD (△t自适应且可变)
算法 2
AABB
DCD (△t自适应且可变)
算法 3
BS+MDR
CCD+DCD (△t自适应且可变)
Tab.1Technical comparison of two traditional algorithms with new one
Fig.6Primary soot particle aggregation along centerline of laminar ethylene diffusion flame
Fig.7Typical TEM images of primary soot particle aggregation along flame centerline and corresponding simulation images
Fig.9Experimental determination values and simulation values for fractal properties of soot aggregates
Fig.8Morphological comparison of simulated soot aggregates with real ones captured experimentally
Fig.10Comparison of simulation values for mean primary particle number per simulated soot aggregate with experimental determination values at different flame heights
Fig.11Comparison of average execution time and execution efficiency of collision detection using three algorithms
Fig.12Simulated soot aggregtes using algorithms 1 or 2 when execution times are equal to those of algorithm 3
[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
doi: 10.1016/j.jcis.2011.07.024
[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
doi: 10.1016/j.physa.2018.09.119
[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
doi: 10.3778/j.issn.1002-8331.2009.01.054
[4]
于瑞云, 赵金龙, 余龙, 等 结合轴对齐包围盒和空间划分的碰撞检测算法[J]. 中国图像图形学报, 2018, 23 (12): 1925- 1937 YU Rui-yun, ZHAO Jin-long, YU Long, et al Collision detection algorithm based on AABB bounding 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
doi: 10.3778/j.issn.1002-8331.1405-0105
[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 A fast 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
doi: 10.1103/PhysRevLett.82.1792
[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
doi: 10.1016/j.cis.2004.10.001
[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
doi: 10.1016/j.compchemeng.2013.03.028
[13]
DOPERTCHOUK O. Simple bounding-sphere collision detection [EB/OL]. [2019-02-18]. https://www.gamedev.net/articles/programming/math-and-physics/simple-bounding-sphere-collision-detection-r1234.
[14]
ANDERSON L. Realistic billiards simulation with variable time-step [EB/OL]. [2019-02-18]. https://www.cs.rpi.edu/~cutler/classes/advancedgraphics/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
doi: 10.1016/j.jqsrt.2016.09.005
[18]
BOURG D M, BYWALEC B. Physics for game developers [M]. 2nd ed. Sebastopol: O’REILLY, 2013.
