[精品]碰撞检测技术研究综述.doc

《[精品]碰撞检测技术研究综述.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、碰撞检测技术研究综述碰撞检测技术研究综述摘要：碰撞检测在图形学、仿真、动画和虚拟现实等技术中得到广泛的研究，这些研究具有十分重要的意义。文章对二维空间屮多边形等面模型间相交，以及三维空间中多面体等体模型间干涉的角度对碰撞检测技术的研究和发展作了较为全面的论述，并对几种常用的碰撞检测算法进行了分析和比较，最后对碰撞检测算法的发展方向提出了几点建议。关键词：虚拟现实；碰撞检测；层次包围盒；干涉中图分类号：TP391文献标志码：A文章编号：1006-8228(2014)08-07-04AsurveyoncollisiondetectiontechnologyFengI’

2、iying(TnformationTechnologyOfficeofYanShanUniversity,Qinhuangdao,Hebei066004,China)Abstract：Thecol1isiondetectionproblemamongobjectsiswidelystudiedingraphics,simulation,animationandvirtualrealitytechnologies.Acomprehensiveintroductionofstudyanddevelopmentoftheproblemisgivenfromtheaspe

3、ctsoftheintersectionbetweenfacemodelsin2D,suchaspolygon,andtheinterferencebetweenbodymodelsin3D,suchaspolyhedron.Somecollisiondetectionalgorithmsarebrieflyanalyzedandcompared・Somesuggestionsofdevelopmentofcollisiondetectionalgorithmsareproposed・Keywords：virtualreality；collisiondetecti

4、on；boundingvolumehierarchies；interference0引言数字化、信息化是当今国内外高科技发展的潮流和趋势，随着计算机软硬件技术的快速发展，尤其是图形处理器以及与之相关的三维游戏，虚拟仿真等技术的兴起，碰撞检测技术再次成为计算机仿真领域研究的热点之一。在虚拟仿真系统中，如果物体间发生碰撞，系统必须实时而准确地检测到这些碰撞并作出相应的碰撞响应[1],否则物体间就会产生穿透现象，影响虚拟场景的真实性。以前在自动装配规划以及路径规划等领域中,为了检测场景中的物体之间或零件之间是否发生碰撞，产生了许多碰撞检测算法，而后有关专家在碰撞检测的理

5、论和应用方面做了i系列的实验，并得到了许多有重要价值的研究结果。近二三十年来，国内外研究人员在碰撞检测领域中做了大量有意义的工作，经过细致的研究和实验验证之后，得到了许多实用的碰撞检测算法，对虚拟现实技术的快速发展起到了积极的推动作用。本文将从二维平面和三维空间两个方面对碰撞检测技术进行较为详尽的论述。1二维空间碰撞检测问题二维空间中的碰撞检测儿乎是所有碰撞检测算法不可回避的问题，它是指三角形、多边形等面模型之间的求交问题,是三维空间中精确碰撞检测的必经阶段［2］。近儿十年来，许多专家学者对平面碰撞问题进行了深入的研究，并取得一些满意的结果，提出了许多优秀的算法。

6、Chin和Wang两人研究了两个多边形的相交和最小距离问题。利用可视边链和凸的顶点相对于其内部点的单调性，提出了判别凸n边形和一个简单非凸m边形的相交问题的最优算法［3］,并且研究了当两个多边形相交时，一个多边形是否被另一个多边形完全包含的问题，其时间复杂度都为0(m+n)o曲吉林釆用平面扫描算法，解决了平面内任意简单多边形平移吋碰撞部位的判定问题［4］。平而内任意两个互不相交的简单多边形，若其屮一个多边形沿某一方向平移吋与另一个多边形碰撞，釆用平面扫描法,通过提取多边形的单调链，给出了求其碰撞部位的算法。与现有的算法相比，降低了吋间复杂性。覃中平、张焕国研究了平

7、面内两个互不相交的凸多边形，若其中一个凸多边形沿某一方向与另一个凸多边形相碰撞，釆用折半搜索技术来确定凸多边形相碰撞吋两者最初相碰撞的顶点和边［5］,并且提出了时间复杂度为0(logm+logn)的优秀算法。汪嘉业利用单调折线研究了在一个多边形的凸包和另一个多边形不相交的条件下，确定两个多边形是否碰撞，并在碰撞时确定全部碰撞部位的问题［6］,提出了时间复杂度为0(m+n)的最优算法，并且其算法还可推广到确定包含有圆弧边的多边形之间的最初碰撞部位。申静波，唐国维等人提出了基于夹边边对的空间平面凸多边形快速相交检测算法［7］,并将算法的应用对象从三角形扩展到任意空间平

8、面凸多边形