融合R-Sphere包围球的变形体碰撞检测算法  

Deformation collision detection algorithm fusing R-Sphere bounding volume

作　　者：靳雁霞[1] 秦志鹏[1] 李照[1] 

机构地区：[1]中北大学计算机与控制工程学院,山西太原030051

出　　处：《计算机工程与设计》2017年第1期92-96,共5页Computer Engineering and Design

基　　金：国家自然科学基金项目(61379080);山西省自然科学基金项目(2013011017-7)

摘　　要：针对变形体碰撞检测算法中实时性较差的问题,提出一种R-Sphere包围球与粒子群优化算法融合的混合碰撞检测算法。将有公共顶点的三角片构造成R-Sphere包围球,利用R-Sphere包围球的旋转不变性和球心固定的特性对包围球更新过程进行优化;利用层次包围球(BVH)树快速剔除不相交的包围体,在确认发生碰撞的包围球中融合粒子群算法,将复杂的三维空间距离检测问题转换为二维离散空间内的寻优问题,快速找到发生碰撞的包围球对。实验结果表明,混合算法有效提高了碰撞检测的实时性。To improve the timeliness of deformation collision detection algorithm, a hybrid collision detection algorithm of R-Sphere bounding volume combined with particle swarm optimization was proposed. Triangles with public vertex were used to construct R-Sphere bounding volume, and the rotation invariance and fixed center of R-Sphere bounding volume were used to optimize the bounding volume update process. The bounding volume hierarchies （BVH） were used to remove disjoint bounding volume quickly, particle swarm optimization （PSO） algorithm was introduced in the collision bounding volume, and the complex three-dimensional space problem was turned into a two-dimensional discrete space optimization problem, which found the pairs of collision bounding volume quickly. The experiments verify that the hybrid algorithm improves the timeliness of collision detection effectively.

关 键 词：R-Sphere包围球 层次包围盒 粒子群优化算法 碰撞检测 二维离散空间 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]