Computer Engineering and Applications ›› 2014, Vol. 50 ›› Issue (9): 170-175.

Previous Articles     Next Articles

Fast collision detection algorithm for deformable objects

TAN Ruipu1, ZHAO Wei2   

  1. 1.School of Electronic Information Science, Fujian Jiangxia University, Fuzhou 350108, China
    2.Department of Information Technology, Jilin Agricultural University, Changchun 130118, China
  • Online:2014-05-01 Published:2014-05-14


谭睿璞1,赵  伟2   

  1. 1.福建江夏学院 电子信息科学学院,福州 350108
    2.吉林农业大学 信息技术系,长春 130118

Abstract: In order to achieve a real-time collision detection between deformable objects and rigid body in the virtual environment, a fast parallel collision detection algorithm based on hybrid bounding box hierarchy is proposed. Taking into account the different characteristics of the bounding box in the detection speed and accuracy, this algorithm builds a sphere-AABB hybrid bounding box hierarchy tree for deformable object, and establishes a sphere-OBB hybrid bounding box hierarchy tree for rigid body; in addition, every hybrid bounding box hierarchy tree is divided into upper layer, middle layer and lower layer, and each layer uses a different bounding box; when traversing the trees, this algorithm uses sphere-sphere test in the upper layer, sphere-OBB test in the middle layer and AABB-OBB test in the lower layer to detect collision. This paper uses multi-threading technology to achieve parallel collision detection algorithm on multi-core devices. Experimental results show that this algorithm has obvious advantages compared with the classic AABB algorithm in the aspect of efficiency, and can meet the requirement of collision detection between deformable objects and rigid body.

Key words: collision detection, deformable objects, rigid body, hybrid bounding volume hierarchy, multiple thread

摘要: 为实现虚拟环境中可变形物体与刚体间实时的碰撞检测,提出了一种快速的基于混合包围盒层次结构的并行碰撞检测算法。算法充分利用包围盒在检测速度和精度上的不同侧重,对可变形物体建立Sphere和AABB混合包围盒层次树,对刚体建立Sphere和OBB混合包围盒层次树;每个物体的混合包围盒层次树又分成上层、中层和下层,每层使用不同的包围盒;在碰撞检测遍历时,上层使用Sphere和Sphere相交检测快速排除不相交物体,在中层使用Sphere和OBB的相交检测进一步排除物体相交的可能性,在下层使用AABB和OBB的相交检测较精确地确定物体是否相交;采用多线程技术,在多核设备上实现并行碰撞检测算法。实验结果表明,与经典的AABB算法相比较,该算法在效率方面具有明显优势,能够满足可变形物体与刚体的碰撞检测要求。

关键词: 碰撞检测, 可变形物体, 刚体, 混合包围盒层次, 多线程