变形体的碰撞检测算法研究

【作者】 李建波；

【导师】 潘振宽；

【作者基本信息】 青岛大学 ， 计算机软件与理论， 2005， 硕士

【摘要】 一个快速并且健壮的碰撞检测检测算法在很多领域比如虚拟现实、计算机游戏、计算机辅助设计都扮演着重要角色。近几年来,随着虚拟现实技术和分布式仿真技术的兴起,碰撞检测问题成为一个研究的热点。 相对于刚体对象,变形对象表现在当它移动时组成变形体对象的顶点之间的相对位置发生变化。对于刚体对象,大部分碰撞检测算法所依赖的数据结构都可以在预处理阶段处理完毕。但对于变形体对象,适用于刚体对象的碰撞检测算法将不能直接应用。因为顶点之间的相对位移发生变化,因此用于碰撞检测算法的数据结构必须实时的重新构建或者更新。 对于变形体的碰撞检测算法,本文从两个方面对传统的算法进行改进。第一种方法是处理可变形体对象时更新而不是重新构建数据结构,因为重新构建整个数据结构的时间耗费在一个实时的仿真环境中是不能接受的。同时通过压缩方法对传统AABB层次包围盒进行了改进,通过从空间的角度来对传统的层次AABB包围盒进行优化,从而节省了大量的存储空间,提高了变形体的碰撞检测效率。第二种方法提出了一种基于包围盒方法与空间分解方法相结合的碰撞检测算法,与其他碰撞检测算法相比较,本算法不仅具有能够节省空间,而且时间复杂度也比较低。除此之外,本算法不仅能够找出发生碰撞的基本几何元素对,而且还能够精确地找出碰撞点。更多还原

【Abstract】 A rapid and robust collision detection algorithm plays an important role in many fields such as virtual reality, computer game and computer aid design. In recent years, collision detection has been a hot topic with the boom of virtual reality and distributed simulation technology.Compared with rigid object, the deformable object has the distinctive feature that the relative position of vertices comprising the object changes when the object moves. For rigid object, the data structures that most collision detection algorithms depend on end in the pre-processing phase. But for deformable object, the collision detection algorithm fit for rigid object can’t apply to the deformable object. Because the relative displacement of vertices changes, the data structure applied to collision detection must be rebuilt or refit in real time.This paper has tried to make improvements from two aspects for the collision detection algorithm of deformable objects. First, improvement is made to the traditional AABB hierarchical bounding boxes by the compressive AABB bounding box, trying to optimize the traditional hierarchical bounding boxes from a space perspective. The direct result is that it can save a large amount of space and enhance the efficiency of collision detection dramatically. The second method proposes a new collision detection algorithm that combines bounding volume boxes method and space subdivision method. It can solve the collision detection problems between deformable objects. Compared with other collision detection algorithm, the algorithm this paper proposes not only has the advantage that it can save the storage space but also its time complexity is comparatively low. Besides, it can find not only the colliding elementary geometry element pairs but also the precise colliding points.更多还原