随着虚拟现实的发展和人们对体验要求的提高,碰撞检测算法实时性与准确性的要求也随之提高。层次包围盒碰撞检测算法将物体分为粒度不同的包围盒进行测试,具有较高的准确性,但是实时性较差。本文优化了传统的层次包围盒碰撞检测算法,并使用GPU并行计算,进一步加快了碰撞检测算法的速度。本文主要研究内容如下:(1)以现有碰撞检测算法为基础,归纳总结了基于空间分解的碰撞检测算法和基于层次包围盒的碰撞检测算法,分析并比较各类碰撞检测算法的优缺点。(2)对构造层次包围盒树算法进行优化。分析哈夫曼法构造层次包围盒树的实现方式,提出使用平衡二叉树法对构造层次包围盒树的优化方案,节省了构造层次包围盒树的耗时。(3)实现优化后的构造层次包围盒树算法的并行化。对优化后的构造层次包围盒算法进行可行性分析,并在CUDA平台上对其进行并行化,进一步节省了构造层次包围盒树的耗时。(4)实现层次包围盒碰撞检测算法的并行化。分析串行碰撞检测算法中双重遍历层次包围盒树的实现方式,针对其存在无效遍历增加算法耗时的缺点,提出并行化的解决方案,并在CUDA平台上对其进行并行化。并行遍历层次包围盒树屏蔽了无效遍历的算法耗时,从而加快了碰撞检测算法的速度。试验验证表明,优化后的层次包围盒碰撞检测算法具有更高的效率,有效的提高了构造层次包围盒树和遍历层次包围盒树的速度。