碰撞检测用于确定两个或多个物体彼此之间是否发生接触或穿透,是计算机图形学、虚拟现实、计算机游戏以及CAD/CAM等领域一个非常重要的问题。经过研究人员多年的探索,出现了许多在一定程度上比较成熟的碰撞检测算法。但是,随着应用中三维模型的越来越复杂,以及人们对交互实时性和场景真实性要求的提高,给碰撞检测算法的效率也提出了更高的要求。同时,图形处理器通用计算技术的快速发展,为实时碰撞检测问题的解决提供了一种全新的方法。在对已有碰撞检测算法深入分析的基础上,本文结合GPU通用计算平台CUDA,从如下三个方面对碰撞检测算法进行设计和改进:首先,从GPU的通用计算角度出发,提出一种基于GPU通用计算的碰撞检测算法。算法进行一物体所有三角形和另一物体所有三角形之间的相交测试,以判断两物体之间是否发生碰撞;通过CUDA平台,将相交测试计算映射到GPU多线程,以利用GPU强大的并行计算能力,完成并行化的碰撞检测计算。其次,在上述算法的基础上,引入层次树改进算法性能,得到一种基于GPGPU的实时碰撞检测算法。对于两物体间的碰撞检测,算法首先遍历一个物体的层次包围盒树,进行包围盒与另一物体的三角形之间的相交测试,快速剔除两物体中明显不相交的三角形,将相交计算复杂度从O(N2)降至O(N);然后进行两物体潜在相交三角形之间的相交测试,获得碰撞检测结果。所有相交测试计算均由GPU多线程并行执行。算法利用了“CPU+GPU异构运算”的思想,将不同的任务在CPU和GPU之间进行合理的分配,获得较优的算法性能。最后,根据CUDA编程的优化原则,对算法的GPU内存访问方式和线程并行度进行优化。在内存存取方面,有效利用CUDA的共享内存机制,将数据的全局内存读取次数从每线程一次降低至每块一次;在线程并行度方面,结合计算量和GPU的计算能力对网格和块的维度进行合理配置。实验结果表明,基于GPGPU的实时碰撞检测算法,能适应任意形状物体间的碰撞检测,具有较好的实时性。本文的研究成果,对物体间的实时碰撞检测具有一定的理论和实际意义,同时也对GPU通用计算的发展起到了推动作用。