【作者】 金汉均；

【导师】 李朝晖；

【作者基本信息】 华中科技大学 ， 系统分析与集成， 2006， 博士

【摘要】 虚拟环境中物体间的碰撞检测是虚拟现实技术、计算机动画技术、机器人技术等领域中一个极富挑战性的问题,其基本任务是确定虚拟空间中两个或多个物体彼此之间是否发生接触或穿透。尽管针对碰撞检测问题国内外已有了大量的、有价值的、实用的研究成果。但随着虚拟现实等新领域的涌现以及人们对虚拟环境真实性要求和用户交互实时性要求的不断提高,如何有效地提高碰撞检测的速度以保持虚拟环境真实性的问题也日益突出,它也一直是科技工作者研究的热点问题。本文在对各类碰撞检测算法作出全面了解、深入分析的基础上,针对碰撞检测技术目前存在的问题,分别从三个方面,设计、实现并验证了一组新的碰撞检测算法。提出了一种检测两静态凸多面体间碰撞方法。该方法利用凸多面体上的任意一点的值可以由凸多面体有限顶点的值表示的特点,将检测两凸多面体间是否发生碰撞问题转化为求目标函数为两凸多面体间最短距离的非线性规划问题,通过计算最短距离值来判断某时刻两凸多面体是否发生了碰撞。此方法不但可以判断两凸多面体间碰撞,而且还可以计算穿透距离,实例证明所提的方法是有效的。将基本遗传算法应用于求解这类问题。在对约束条件处理后,通过设置各种遗传算子,利用基本遗传算法求解,并且与用传统方法计算的结果进行了比较。实例证明遗传算法计算速度快,计算精度高,说明了遗传算法求解此类问题的有效性和快速性。改进了AABB包围盒层次树的存贮结构。用优化的AABB包围盒层次树来检测变形物体间碰撞。该方法利用包围盒中基本几何体间交互检测方法,将树中的包围盒存贮结构进行了优化,去掉叶结点的存储信息,从算法的空间复杂度上进行了优化,模拟效果证明该方法的快速性。大部分碰撞检测的算法,都试图减少三角形与三角形之间交互检测数目。本文提出的物体三角形与三角形之间交互检测是从两方面进行了优化。结合DirectX的特点,通过判断一点到三角形平面距离以及是否从三角形内穿过来判断两三角形接触情况,从而简化了三角形面片间交互判断步骤加快了检测速度,模拟效果证明该方法的有效性;通过判断两三角形交线上重叠区域来判断物体三角形与三角形相交的情况,用JAVA语言与VRML语言的结合来描述简化的区域交互判断方法,非常适应于网络环境下物体间碰撞检测。更多还原

【Abstract】 It is a challenge to detect collision in domains of virtual reality, animation, robotic, etc. It has become the basic issue that whether a contact or penetration has happened in virtual environment or not. Many articles have given a mount of valuable and practicable study on the problem. But while many novel domains come forth and the requirements for the reality of scene and real-time of interactive become more and more critical, it is important to improve the performance of collision detection to ensure the reality of virtual environment.After giving a comprehensive understanding and intensive analysis for all kinds of algorithms, the paper presents, implements and experiments a group of novel collision detection algorithms in three perspectives, aiming at handling problems of the existing collision detection algorithms.An algorithm that detects collision between two static convex polyhedra is presented. The method makes use of the principle that the value of an arbitrary point in the convex polyhedral can be presented by the values of its vertexes. The problem of detecting collision between two convex polyhedral is converted into a constraint nonlinear programming problem that aims at computing the minimum distance between two convex polyhedra. According to the value of minimum distance, the algorithm can determine whether two convex polyhedra have collided or not. Another, the approach is able to obtain the penetrate distance besides detection collision. The efficiency of the algorithm is illustrated by concrete instances. Basic genetic algorithm is used to solve the problem. The method deals with constraint conditions and initializes variant genetic operators firstly; then, genetic algorithm is applied to the distance model and compared with the result of traditional method. The results have shown that genetic algorithm has a lower execution time but a higher precision. Also, the results indicate that it is feasible and efficient to apply genetic algorithm to such kind of distance model.The storage structure of AABBs hierarchies is improved. The optimized AABBs hierarchies is used to detect collision between deformable objects. The algorithm makes use of the interactive detection between the basic geometry bodies in bounding box and optimizes the storage structure of bounding volume by removing leaf node storage information in the perspective of space complexity. Instances have illustrated the efficiency of the method.Most collision detection algorithms try to decrease the number of the intersection triangles. The algorithm presented in this paper simplifies intersection detection between two triangles from two aspects. By combining the characteristic of DirectX, algorithm makes use of the distance between a point and a triangle. According to whether the distance goes through a triangle or not, the algorithm decreases the steps of intersection collision between triangles .The excusive speed is accelerated and instances are used to illustrate the feasibility and efficiency. The concrete situation of interaction is obtained by judging the overlapping regional which is on the line of two triangles intersection. The language of JAVA and VRML are used to describe the algorithm that is well suitable for collision detection in the network environment.更多还原