基于量子蚁群的快速碰撞检测算法研究

发布时间：2022-02-05 00:20

　　针对在复杂三维场景中传统的碰撞检测算法存在的检测速率慢等问题,提出了一种基于量子蚁群的快速碰撞检测算法。算法首先基于AABB层次包围盒技术剔除不相交的模型部分,再应用随机碰撞检测算法的思想将三维空间中的碰撞问题转化为二维空间上的待检测物体特征对距离的优化问题,结合了量子计算和蚁群算法的寻优策略,引入变异算子和一种新的自动旋转角策略,设计了一种新的量子蚁群算法来解决碰撞检测问题。实验证明,在待检测模型多边形数量较多的情况下,可以提高碰撞检测检测速率。 

【文章来源】：计算机仿真. 2019,36(12)北大核心

【文章页数】：6 页

【部分图文】：

三角形相交测试结果显示

把本文算法与单纯基于层次包围盒(HBV)的碰撞检测算法进行检测时间比较,比较两种算法在达到不同检测结果时所需时间,算法采样特征对数量为2304,实验结果如图3所示。根据结果显示,若完全检测,HBV在达到100%检测率时,时间消耗为33ms;QACO算法检测率达到90%时,需要的时间为18.1ms。即在损失了10%的检测率的情况下,QACO的算法时间效率比传统的HBV算法提高了45%。

把本文算法、基于蚁群算法(ACO)的随机碰撞检测算法、单纯基于粒子群(PSO)的随机碰撞检测算法进行碰撞检测率比较,算法采样特征对数量为2304,实验结果如图4所示。根据结果显示,在检测初期,几种算法的检测率基本相同。随着检测时间的增加,本文算法的检测率明显高于其它算法。QACO在16ms可以达到80%的检测率,PSO所需时间则为18ms,与PSO算法相比,本文算法效率提高了11%;检测率达到90%时QACO与PSO和ACO的差距达到了3ms,算法效率提高了13%。在相同碰撞检测率的要求下,QACO具有更快的检测效率。

【参考文献】：
期刊论文
[1]基于八叉树的柔性体切割仿真中并行化的碰撞算法[J]. 贾世宇,张维忠,于晓康,潘振宽.  计算机辅助设计与图形学学报. 2017(12)
[2]融合智能算法的变形体碰撞检测算法研究[J]. 靳雁霞,任超,李照,程思岳,王贺,韩慧妍.  计算机工程与应用. 2017(19)
[3]基于量子蚁群算法的图像分割[J]. 李积英,党建武.  系统仿真学报. 2014(04)
[4]基于多智能体粒子群的快速碰撞检测算法研究[J]. 付跃文,梁加红,李猛,刘全平.  系统仿真学报. 2013(08)
[5]基于粒子群面向可变形物体的随机碰撞检测算法[J]. 李文辉,王天柱,王祎,秦忠.  系统仿真学报. 2006(08)



本文编号：3614215