Computer Engineering and Applications ›› 2012, Vol. 48 ›› Issue (6): 143-145.

• 图形、图像、模式识别 • Previous Articles     Next Articles

New collision detection algorithm based on hybrid hierarchical bounding box

JIANG Xiaolu1,2, LIU Yuan2   

  1. 1.College of Internet of things, Jiangnan University, Wuxi, Jiangsu 214122, China
    2.College of Digital Media, Jiangnan University, Wuxi, Jiangsu 214122, China
  • Received:1900-01-01 Revised:1900-01-01 Online:2012-02-21 Published:2012-02-21

一种新的基于混合层次包围盒的碰撞检测算法

姜晓路1,2,刘 渊2   

  1. 1.江南大学 物联网工程学院,江苏 无锡 214122
    2.江南大学 数字媒体学院,江苏 无锡 214122

Abstract: To achieve fast and accurate collision detection among objects, a new collision detection algorithm based on hybrid hierarchical bounding box is presented. The algorithm builds hybrid hierarchical bounding box by simple calculation of Sphere and good tightness of K-DOPs bounding box, using Sphere bounding box in the upper layer to get rid of nonintersecting objects and using K-DOPs bounding box in the bottom layer to achieve a more precise intersection test. Therefore, it improves the real-time collision detcetion. The experimental results show that the proposed algorithm is effective and feasible, and the real-time and robustness performance is better than traditional collision detection algorithms.

Key words: hybrid hierarchical bounding box, collision detection, Sphere, K-DOPs

摘要: 为了实现物体间快速精确的碰撞检测,提出了一种新的基于混合层次包围盒的碰撞检测算法,充分利用了包围球计算简单和K-DOPs包围盒紧密性好的优点,来构建物体的混合层次包围盒结构。在包围盒树的上层采用Sphere包围盒,能快速排除不相交的物体,下层采用K-DOPs包围盒,进行更加精确的相交测试,提高了碰撞检测实时性。实验结果表明,该算法是有效可行的,具有较强的实时性及鲁棒性,性能优于传统碰撞检测算法。

关键词: 混合层次包围盒, 碰撞检测, 包围球, 离散方向多面体包围盒