融合GASA的Snake模型碰撞检测算法
|
摘要
针对现有碰撞检测算法难以解决变形体碰撞的实时性和逼真性问题,提出一种基于可变形物体的碰撞检测算法。利用Snake模型对FDH包围盒进行更新,由于传统Snake模型存在弱边缘易溢出的问题,结合模拟退火算法(GASA)的遗传思想对其进行优化。实验结果表明,优化后的碰撞检测算法可快速准确得到碰撞物体的最佳轮廓曲线,弥补了遗传算法和模拟退火算存在的过早收敛和低收敛速度的问题,加快了包围盒的更新速度,提高了碰撞检测效率和逼真程度。
In view that the existing collision detection algorithm can not solve the real-time and realistic problem of deformation object collision,a collision detection algorithm based on deformable objects was proposed.Snake model was used to update the FDH bounding box.Because the traditional Snake model has the problem of weak edge spillover,simulated annealing(GASA)genetic ideas were combined to optimize the Snake model.Experimental results show that the optimized collision detection algorithm can quickly and accurately get the best contour of the object,which makes up for the defect of genetic algorithm and simulated annealing algorithm including premature convergence and low convergence speed,accelerating the speed of updating the bounding box,while improving the efficiency of collision detection rate and the degree of realism.
In view that the existing collision detection algorithm can not solve the real-time and realistic problem of deformation object collision,a collision detection algorithm based on deformable objects was proposed.Snake model was used to update the FDH bounding box.Because the traditional Snake model has the problem of weak edge spillover,simulated annealing(GASA)genetic ideas were combined to optimize the Snake model.Experimental results show that the optimized collision detection algorithm can quickly and accurately get the best contour of the object,which makes up for the defect of genetic algorithm and simulated annealing algorithm including premature convergence and low convergence speed,accelerating the speed of updating the bounding box,while improving the efficiency of collision detection rate and the degree of realism.
引文
[1]HUANG Xin,YANG Wenzhen,WU Xinli.Virtual fabric haptic rendering with double haptic interactive points[J].Journal of System Simulation,2014,26(9):1997-2008(in Chinese).[黄欣,杨文珍,吴新丽.双触点虚拟织物触觉交互[J].系统仿真学报,2014,26(9):1997-2008.]
[2]FU Yuewen,LIANG Jiahong,LI Meng.Research on fast collision detection using multi-agent particle swarm optimization[J].Journal of System Simulation,2013,25(8):1876-1880(in Chinese).[付跃文,梁加红,李猛.基于多智能体粒子群的快速碰撞检测算法研究[J].系统仿真学报,2013,25(8):1876-1880.]
[3]Du Peng,Tang Min,Tong Ruofeng.Fast continuous collision culling with deforming noncollinear filters[J].Computer Animation&Virtual Worlds,2012,23(3-4):375-383.
[4]Chang JW,Wang W,Kim MS.Efficient collision detection using a dual OBB-sphere bounding volume hierarchy[J].Computer-Aided Design,2009,42(1):50-57.
[5]ZHANG Zhi,ZOU Shengtao.Collision detection algorithm between convex polyhedrons based on projection of edges[J].Journal of Computer-Aided Design&Computer Graphics,2015,27(8):1407-1415(in Chinese).[张智,邹盛涛.凸多面体碰撞检测的棱线投影分离算法[J].计算机辅助设计与图形学学报,2015,27(8):1407-1415.]
[6]LI Yanbo,YIN Guisheng,ZHANG Jing.Research on collision detection methods based on Snake[J].Application Research of Computers,2009,26(3):855-857(in Chinese).[李艳波,印桂生,张菁.基于Snake模型的碰撞检测算法研究[J].计算机应用研究,2009,26(3):855-857.]
[7]LIN Yunqi.Collision detection algorithm for deformable objects[J].Journal of Jilin University(Information Science Edition),2012,30(3):321-326(in Chinese).[李蕴奇.基于可变形物体的碰撞检测算法[J].吉林大学学报(信息科学版),2012,30(3):321-326.]
[8]XU Pengfei,MIAO Qiguang,LI Weisheng,et al.Adaptive simulated annealing algorithm and TaBu search algorithm based on the function complexity[J].Acta Electronica Sinica,2012,40(6):1218-1222(in Chinese).[许鹏飞,苗启广,李伟生,等.基于函数复杂度的自适应模拟退火和禁忌搜索新算法[J].电子学报,2012,40(6):1218-1222.]
[9]FANG Rui,ZHU Biying,LI Fanchen.Genetic algorithm parameter tuning based on simulated annealing[J].Journal of Computer Applications,2014,34(S1):114-116(in Chinese).[方睿,朱碧颖,粟藩臣.基于模拟退火思想的遗传算法参数选择[J].计算机应用,2014,34(S1):114-116.]
[10]MA Yongjie,YUN Wenxia.Research progress of genetic algorithm[J].Application Research of Computer,2012,29(4):1201-1206(in Chinese).[马永杰,云文霞.遗传算法研究进展[J].计算机应用研究,2012,29(4):1201-1206.]
[11]CHEN Lichao,NIU Yumei,PAN Lihu,et al.Research advances of Snake model[J].Application Research of Computer,2014,31(7):1931-1936(in Chinese).[陈立潮,牛玉梅,潘理虎,等.Snake模型的研究进展[J].计算机应用研究,2014,31(7):1931-1936.]
[2]FU Yuewen,LIANG Jiahong,LI Meng.Research on fast collision detection using multi-agent particle swarm optimization[J].Journal of System Simulation,2013,25(8):1876-1880(in Chinese).[付跃文,梁加红,李猛.基于多智能体粒子群的快速碰撞检测算法研究[J].系统仿真学报,2013,25(8):1876-1880.]
[3]Du Peng,Tang Min,Tong Ruofeng.Fast continuous collision culling with deforming noncollinear filters[J].Computer Animation&Virtual Worlds,2012,23(3-4):375-383.
[4]Chang JW,Wang W,Kim MS.Efficient collision detection using a dual OBB-sphere bounding volume hierarchy[J].Computer-Aided Design,2009,42(1):50-57.
[5]ZHANG Zhi,ZOU Shengtao.Collision detection algorithm between convex polyhedrons based on projection of edges[J].Journal of Computer-Aided Design&Computer Graphics,2015,27(8):1407-1415(in Chinese).[张智,邹盛涛.凸多面体碰撞检测的棱线投影分离算法[J].计算机辅助设计与图形学学报,2015,27(8):1407-1415.]
[6]LI Yanbo,YIN Guisheng,ZHANG Jing.Research on collision detection methods based on Snake[J].Application Research of Computers,2009,26(3):855-857(in Chinese).[李艳波,印桂生,张菁.基于Snake模型的碰撞检测算法研究[J].计算机应用研究,2009,26(3):855-857.]
[7]LIN Yunqi.Collision detection algorithm for deformable objects[J].Journal of Jilin University(Information Science Edition),2012,30(3):321-326(in Chinese).[李蕴奇.基于可变形物体的碰撞检测算法[J].吉林大学学报(信息科学版),2012,30(3):321-326.]
[8]XU Pengfei,MIAO Qiguang,LI Weisheng,et al.Adaptive simulated annealing algorithm and TaBu search algorithm based on the function complexity[J].Acta Electronica Sinica,2012,40(6):1218-1222(in Chinese).[许鹏飞,苗启广,李伟生,等.基于函数复杂度的自适应模拟退火和禁忌搜索新算法[J].电子学报,2012,40(6):1218-1222.]
[9]FANG Rui,ZHU Biying,LI Fanchen.Genetic algorithm parameter tuning based on simulated annealing[J].Journal of Computer Applications,2014,34(S1):114-116(in Chinese).[方睿,朱碧颖,粟藩臣.基于模拟退火思想的遗传算法参数选择[J].计算机应用,2014,34(S1):114-116.]
[10]MA Yongjie,YUN Wenxia.Research progress of genetic algorithm[J].Application Research of Computer,2012,29(4):1201-1206(in Chinese).[马永杰,云文霞.遗传算法研究进展[J].计算机应用研究,2012,29(4):1201-1206.]
[11]CHEN Lichao,NIU Yumei,PAN Lihu,et al.Research advances of Snake model[J].Application Research of Computer,2014,31(7):1931-1936(in Chinese).[陈立潮,牛玉梅,潘理虎,等.Snake模型的研究进展[J].计算机应用研究,2014,31(7):1931-1936.]