变形物体碰撞检测技术研究

碰撞检测及其相关问题有着悠久的研究历史,在计算机图形学、计算几何、机器人学、CAD/CAM等研究领域具有十分重要的作用。近年来随着虚拟现实、分布交互仿真等技术的兴起,人们对交互的实时性、场景的真实性的要求越来越高,变形物体的实时碰撞检测成为了研究的热点。本文在对各类碰撞检测算法作出全面了解和透彻分析的基础上,从以下几个方面对变形物体的碰撞检测问题进行研究,提出新的检测碰撞的思想和方法,从而使碰撞检测技术有进一步的发展。 (1)从提高碰撞检测的实时性和通用性方面入手,将人工智能中经典的粒子群优化算法引入到碰撞检测领域,提出了应用粒子群优化算法的通用随机碰撞检测算法。该算法在继承一般碰撞检测算法优点的同时,突破了它们的局限性,不但能够在保证效率的前提下处理无拓扑物体的碰撞检测问题而且也可以处理任意物体表示模型之间的碰撞检测,具有较强的通用性;此外检测精度和速度可以人为的调整以满足不同应用的需求,增加了碰撞检测系统的灵活性。 (2)结合层次包围体树结构和随机碰撞检测算法的优点提出了一种大型复杂变形物体的快速碰撞检测方法。该算法利用层次包围体树快速剔除物体上不相交的区域,只在碰撞了的节点内进行智能搜索,既避免了单纯采用粒子群优化方法目标空间过大造成的搜索速度慢的缺点,又减少单纯使用层次包围体树的方法所消耗的大量存储空间和更新速度慢等问题。 (3)在分析研究虚拟装配领域的实际问题的基础上,针对虚拟装配系统中的变形物体的特点,提出了一种基于组件的碰撞检测技术。其中重点研究了基于物体OBB包围盒的组件层次包围体树的构建和更新问题,提出了快速的组件OBB包围盒的生成算法、求两OBB包围盒凸壳的快速算法和N个物体构成组件层次体树的建构与更新的方法。实验证明组件模型具有构建层次分明、运动更新简便、能完成自我碰撞检测等诸多优点。