实时碰撞检测是机器人、动画仿真、虚拟现实等领域中一个非常关键的问题,其基本任务是确定两个或多个物体彼此之间是否发生接触或穿透。尽管针对碰撞检测已有了大量有价值的研究成果,但随着诸如虚拟现实等新兴领域的涌现及随之而来的人们对交互实时性、场景真实性要求的不断提高,碰撞检测技术所面临的问题也日益突出,其中最核心的问题是如何有效地提高碰撞检测的速度。层次包围体法是解决碰撞检测问题固有时间复杂性的一种有效的方法,它是用体积略大而几何特性简单的包围体来近似地描述复杂的几何对象。通过构造树状层次结构来逼近对象的几何模型,在对包围体层次树进行遍历的过程中,通过包围体间的快速相交测试来及早地排除明显不可能相交的基本几何元素对,而只对包围体重叠的部分元素进行进一步的相交测试,以提高碰撞检测的速度。本文提出了一种基于迭代的Lloyd分簇方法的变分逼近构建层次包围体方法,为解决构建层次包围体问题提供了一种新的方法,我们的方法所构建的层次包围树以包围体的外部体积为代价函数,利用逼近的思想来解决实现空间面片的划分问题,通过多次迭代,产生的包围体更加逼近原物体,有效提高了碰撞检测中的检测效率。