一种快速的可变形物体的碰撞检测算法

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

Fast collision detection algorithm for deformable objects

In order to achieve a real-time collision detection between deformable objects and rigid body in the virtual envi-ronment, 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. Experi-mental 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.