【作者】 王天柱；

【导师】 李文辉；

【作者基本信息】 吉林大学 ， 计算机应用技术， 2006， 博士

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

【Abstract】 Collision Detection (CD), also called Interference Detection or Contact Detection, is a fundamental operation used in a variety of areas such as computer graphics, computer animation, robotics, computational geometry, visualization and more. Efficient and exact collision detection is very important to improve reality and enhance immersion for virtual environment, because most often collision detection is performed in real-time environments that require an interaction with users. Frequently, the models that are used consist of very large geometric primitives that consume a lot of time to process, which often becomes the neck of bottle in the whole application. So how to improve the efficiency and accuracy is the main task to all researchers in this area.The collision detection problem has been studied extensively in the literature and numerous collision detection methods have been extensively developed in this area. These approaches can be divided into two main classes of algorithms. The first one is feature-based which uses temporal and spatial coherence to maintain the close features. One example is to tile a grid of voxels and assign objects to the voxels that contain them. The second and most widely class uses hierarchical bounding volumes trees (BVHs). The idea is that levels of bounding volumes cover the objects. At the top level, the bounding volume bounds the entire model, and at the bottom one, it bounds primitives. In between, it bounds subsets of primitive. One of the design choices with BV trees is the type of BV. In the past, a wealth of BV types has been explored, such as spheres, AABBs, OBBs, DOPs, and Convex Hulls.The known collision detection algorithms usually have been demonstrated to work更多还原