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

《虚拟环境中物体碰撞检测算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、华中科技大学博士学位论文虚拟环境中物体碰撞检测算法研究姓名：金汉均申请学位级别：博士专业：系统分析与集成指导教师：李朝晖20061111华中科技大学博士学位论文摘要虚拟环境中物体间的碰撞检测是虚拟现实技术、计算机动画技术、机器人技术等领域中一个极富挑战性的问题，其基本任务是确定虚拟空间中两个或多个物体彼此之间是否发生接触或穿透。尽管针对碰撞检测问题国内外已有了大量的、有价值的、实用的研究成果。但随着虚拟现实等新领域的涌现以及人们对虚拟环境真实性要求和用户交互实时性要求的不断提高，如何有效地提高碰撞检测的速度以

2、保持虚拟环境真实性的问题也日益突出，它也一直是科技工作者研究的热点问题。本文在对各类碰撞检测算法作出全面了解、深入分析的基础上，针对碰撞检测技术目前存在的问题，分别从三个方面，设计、实现并验证了一组新的碰撞检测算法。提出了一种检测两静态凸多面体间碰撞方法。该方法利用凸多面体上的任意一点的值可以由凸多面体有限顶点的值表示的特点，将检测两凸多面体间是否发生碰撞问题转化为求目标函数为两凸多面体间最短距离的非线性规划问题，通过计算最短距离值来判断某时刻两凸多面体是否发生了碰撞。此方法不但可以判断两凸多面体间碰撞，而且

3、还可以计算穿透距离，实例证明所提的方法是有效的。将基本遗传算法应用于求解这类问题。在对约束条件处理后，通过设置各种遗传算子，利用基本遗传算法求解，并且与用传统方法计算的结果进行了比较。实例证明遗传算法计算速度快，计算精度高，说明了遗传算法求解此类问题的有效性和快速性。改进了AABB包围盒层次树的存贮结构。用优化的AABB包围盒层次树来检测变形物体间碰撞。该方法利用包围盒中基本几何体间交互检测方法，将树中的包围盒存贮结构进行了优化，去掉叶结点的存储信息，从算法的空间复杂度上进行了优化，模拟效果证明该方法的快速性

4、。大部分碰撞检测的算法，都试图减少三角形与三角形之间交互检测数目。本文提出的物体三角形与三角形之间交互检测是从两方面进行了优化。结合DirectX的特点，通过判断一点到三角形平面距离以及是否从三角形内穿过来判断两三角形接触情况，从而简化了三角形面片间交互判断步骤加快了检测速度，模拟效果证明该方法的有效性；通过判断两三角形交线上重叠区域来判断物体三角形与三角形相交的情况，用I华中科技大学博士学位论文JAVA语言与VRML语言的结合来描述简化的区域交互判断方法，非常适应于网络环境下物体间碰撞检测。关键词：虚拟现实

5、；碰撞检测；距离函数；遗传算法；层次包围盒；三角形交互；算法优化II华中科技大学博士学位论文AbstractItisachallengetodetectcollisionindomainsofvirtualreality,animation,robotic,etc.Ithasbecomethebasicissuethatwhetheracontactorpenetrationhashappenedinvirtualenvironmentornot.Manyarticleshavegivenamountofva

6、luableandpracticablestudyontheproblem.Butwhilemanynoveldomainscomeforthandtherequirementsfortherealityofsceneandreal-timeofinteractivebecomemoreandmorecritical,itisimportanttoimprovetheperformanceofcollisiondetectiontoensuretherealityofvirtualenvironment.Af

7、tergivingacomprehensiveunderstandingandintensiveanalysisforallkindsofalgorithms,thepaperpresents,implementsandexperimentsagroupofnovelcollisiondetectionalgorithmsinthreeperspectives,aimingathandlingproblemsoftheexistingcollisiondetectionalgorithms.Analgorit

8、hmthatdetectscollisionbetweentwostaticconvexpolyhedraispresented.Themethodmakesuseoftheprinciplethatthevalueofanarbitrarypointintheconvexpolyhedralcanbepresentedbythevaluesofitsvertexes.Theproblemofdet