虚拟环境中物体碰撞检测算法研究

论文摘要

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

论文目录

• 摘要
• Abstract
• 1 概述
• 1.1 虚拟现实技术
• 1.2 构造虚拟环境的要求
• 1.3 虚拟环境中物体碰撞检测的问题
• 1.4 碰撞检测算法分类
• 1.5 国内外研究主要算法
• 1.6 目前碰撞检测亟需解决的问题
• 1.7 本文研究内容及组织
• 2 计算两凸多面体间最短距离的算法
• 2.1 引言
• 2.2 两凸集间距离函数及计算方法
• 2.3 凸多面体表示
• 2.4 碰撞检测算法
• 2.5 实例模拟
• 2.6 本章小结
• 3 计算两凸多面体间最短距离的遗传算法
• 3.1 引言
• 3.2 检测两凸多面体间碰撞的数学模型
• 3.3 遗传算法设计
• 3.4 实例模拟
• 3.5 本章小结
• 4 存储优化的AABB 包围盒层次树碰撞检测算法
• 4.1 引言
• 4.2 构造包围盒层次树的方法
• 4.3 优化的AABB 包围盒层次树存储结构
• 4.4 算法仿真
• 4.5 本章小结
• 5 三角形面片间碰撞检测算法
• 5.1 引言
• 5.2 三角形面片间相交检测算法
• 5.3 优化的三角形面片间相交检测算法
• 5.4 本章小结
• 6 基于VRML 语言碰撞检测算法
• 6.1 引言
• 6.2 VRML 语言中的碰撞检测功能
• 6.3 JAVA 3D 语言中的碰撞检测功能
• 6.4 优化的三角形相交区间检测算法
• 6.5 本章小结
• 7 总结与展望
• 7.1 全文结论
• 7.2 工作展望
• 致谢
• 参考文献
• 附录 攻读博士学位期间发表的学术论文