【作者】 王龙涛；

【导师】 赵伟；

【作者基本信息】 吉林农业大学 ， 计算机应用技术， 2013， 硕士

【摘要】 碰撞检测的主要任务是研究虚拟场景中多个物体之间是否发生接触或穿透并及时作出相关相应。在目前计算机研究领域例如图形学、计算机仿真、机器人路径规划等方面占有举足轻重的位置。尽管迄今为止,碰撞检测技术得到一定程度的发展,但随着虚拟场景的规模越来越大,复杂性越来越高,碰撞检测技术往往成为制约虚拟现实发展的一个瓶颈。因而,设计出快速、精确、实时的碰撞检测算法并为未来大规模复杂虚拟场景服务成为亟待解决的问题。伴随着云计算技术快速发展,云计算给研究者们带来了巨大的机遇和挑战。本文在对各类碰撞检测技术做出透彻分析的基础上,引入云计算中的Hyper-V与Dynamic Data Center技术,设计实现并验证了两种新的碰撞检测算法,对加速碰撞检测过程,提高碰撞响应过程等相关技术的的发展做了有益的探究。本文首先提出了一种云环境下基于投影反馈与表面提取的碰撞检测算法。该算法总共分成两部分,预处理与精确检测过程。该算法在预处理阶段首先利用投影反馈的方法进行空间剖分,然后在剖分后的空间内对物体模型表面单元格通过表面提取的方式抽象出来,减少了虚拟空间中物体参与精确碰撞检测的元素数量。最后利用OBB包围盒紧密型高的特点进一步细化参与精确碰撞检测的物体面片元素,使碰撞检测算法的精确度得到更好的提升而更加精确。并且,在物体精确碰撞检测阶段引入云计算的处理方式,是算法的执行速度得到几何层次提升。其次本文将碰撞检测技术与粒子群优化算法相结合,通过对物体特征的采样提取,将物体间的碰撞检测问题由三维空间转移到二维离散搜索空间中去。由于输入的可以是不具有拓扑信息的任意物体模型,因而增加了算法适应性。除此之外,也不需要建立复杂的数据结构,因而在很大程度上减少了存储空间,提高了检测效率。最后运用云计算技术执行其中的大量计算,进一步提高了碰撞检测算法的效率。更多还原

【Abstract】 Collision detection is the key issues of the research area, such as computer graphics, computer simulation, robot path planning and computer animation. Its main task is to determine whether two or more objects happened contact, collision or penetrate phenomenon in virtual scene and returns the corresponding information. Although collision detection technology has of developed for a certain degree, with the scale of the virtual scene is more and more big and complexity, collision detection technology is often becomes a bottleneck that restricts the development of virtual reality. Therefore, designed a rapid, accurate, real-time, general collision detection algorithms become urgently problem that needs to be solved.With the rapid development of cloud computing technology, the cloud computing is taking great opportunities and challenges to the researchers. Based on thorough analysis of all kinds of collision detection technology, we design and verify two new collision detection algorithm by introducing the hyper-v cloud computing and dynamic data center technology to accelerate the collision detection which made a beneficial exploratory study on the development of collision response process.A fast algorithm of collision detection based on projection feedback and surface extraction was proposed. In the pre-processing stage of this algorithm, we make the triangles elements which take part in the precise collision detection reduce greatly by dividing the space with the method of projection feedback and extracting the surface cell of the collision body with the method of surface extraction. In the precise collision detection stage, we subdivide the extracted surface cells by using the OBB bounding box in order to make the collision detection more precise. Finally, the calculation speed of the precise collision detection is accelerated by using the parallel computing.Secondly, we put forward a collision detection algorithm based on particle swarm under the cloud environment in this paper. The collision detection algorithm combined with particle swarm optimization (PSO) algorithm, by sampling the collision detection problem in3-d object space transformation into two-dimensional discrete search space. Due to the input object model may without topological information, thus increase the adaptability of the algorithm. Besides, the algorithm doesn’t need to build complex data structures which largely reduce the storage space and improve the detection efficiency. Finally, we use cloud computing technology to deal the part of the large amount of calculation, which further improve the efficiency of collision detection.更多还原