颗粒团聚过程准确碰撞检测快速算法  

High-speed algorithm for accurate collision detection during particle aggregation

作　　者：王亚飞 黄群星[1] 王飞[1] 池涌[1] 严建华[1] WANG Ya-fei;HUANG Qun-xing;WANG Fei;CHI Yong;YAN Jian-hua(State Key Laboratory of Clean Energy Utilization, Zhejiang University, Hangzhou 310027, China)

机构地区：[1]浙江大学能源清洁利用国家重点实验室,浙江杭州310027

出　　处：《浙江大学学报（工学版）》2019年第6期1148-1156,共9页Journal of Zhejiang University：Engineering Science

基　　金：国家自然科学基金创新研究群体资助项目(51621005);国家重点研发计划资助项目(2016YFE0202000);浙江省科技计划资助项目(2016C33005)

摘　　要：碰撞检测的传统算法在应对大量颗粒碰撞团聚时往往执行效率低下,为此提出一种基于"包围球-最大检测区域"预处理的两步式准确碰撞检测快速算法.粗略筛选阶段:所有团聚体用更新成本低的包围球替代表示,并将包围球间的碰撞检测转变为求解关于时间的一元二次方程问题,通过并行求解这些方程快速筛选出所有可能发生的碰撞;忽略最大检测区域外的碰撞检测以进一步缩短执行时间.精细确定阶段:采用离散碰撞检测快速确定碰撞发生的具体时间和位置;在该阶段,采样时间间隔是自适应的且逐渐减小.将模拟计算结果与未优化的传统算法结果进行对比后发现,在满足相同碰撞检测准确性的前提下,提出的算法将执行效率提升了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.

关 键 词：颗粒团聚 碰撞检测 包围球 最大检测区域 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]