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

Fast Collision Detection Algorithm Based on Quantum Ant Colony

作　　者：杜群 甄成刚 郝悍勇[2] DU Qun;ZHEN Cheng-gang;HAO Han-yong(College of Control Science and Engineering,North China Electric Power University,Baoding Hebei 071003,China;State Grid Corporation of China,Beijing 100031,China)

机构地区：[1]华北电力大学控制科学与工程学院,河北保定071003 [2]国家电网公司,北京100031

出　　处：《计算机仿真》2019年第12期209-213,262,共6页Computer Simulation

基　　金：中央高校基本科研业务费专项资金资助(2018 MS078)

摘　　要：针对在复杂三维场景中传统的碰撞检测算法存在的检测速率慢等问题,提出了一种基于量子蚁群的快速碰撞检测算法。算法首先基于AABB层次包围盒技术剔除不相交的模型部分,再应用随机碰撞检测算法的思想将三维空间中的碰撞问题转化为二维空间上的待检测物体特征对距离的优化问题,结合了量子计算和蚁群算法的寻优策略,引入变异算子和一种新的自动旋转角策略,设计了一种新的量子蚁群算法来解决碰撞检测问题。实验证明,在待检测模型多边形数量较多的情况下,可以提高碰撞检测检测速率。Aiming at the problem of slow detection rate of traditional collision detection algorithms in complex 3 D scenes,a fast collision detection algorithm based on quantum ant colony is proposed.We firstly removed the disjoint model parts based on the AABB hierarchical bounding box technique,and then applied the idea of random collision detection algorithm to transform the collision problem in three-dimensional space into the optimization problem of the feature distance of the object to be detected in two-dimensional space.Quantum computation and ant colony algorithm optimization strategy were combined,mutation operator and a new automatic rotation angle strategy were introduced,and a new quantum ant colony algorithm was designed to solve the collision detection problem.Experiments show that the collision detection rate can be improved in the case where the number of polygons to be detected is large.

关 键 词：虚拟现实 碰撞检测 层次包围盒 量子蚁群算法 

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