全光电子技术论文发表碰撞检测技术研究综述
发布时间：2014-12-01
您当前的：中国月期刊网>>计较机论文>>电子手艺论文
电子手艺论文颁发碰撞检测手艺研究综述摘 要： 碰撞检测在图形学、仿真、动画和虚拟现实等手艺中获得普遍的研究，这些研究具有十分主要的意义。文章对二维空间中多边形等面模子间订交，以及三维空间中多面体等体模子间的角度对碰撞检测手艺的研究和成长作了较为全面的阐述，并对几种常用的碰
摘 要： 碰撞检测在图形学、仿真、动画和虚拟现实等手艺中获得普遍的研究，这些研究具有十分主要的意义。文章对二维空间中多边形等面模子间订交，以及三维空间中多面体等体模子间的角度对碰撞检测手艺的研究和成长作了较为全面的阐述，并对几种常用的碰撞检测算法进行了阐发和比力，最初对碰撞检测算法的成长标的目的提出了几点。
环节词： 电子手艺论文颁发,虚拟现实,碰撞检测,条理包抄盒,
A survey on collision detection technology
Feng Liying
(Information Technology Office of YanShan University， Qinhuangdao， Hebei 066004， China)
Abstract： The collision detection problem among objects is widely studied in graphics， simulation， animation and virtual reality technologies. A comprehensive introduction of study and development of the problem is given from the aspects of the intersection between ce models in 2D， such as polygon， and the interference between body models in 3D， such as polyhedron. Some collision detection algorithms are briefly analyzed and compared. Some suggestions of development of collision detection algorithms are proposed.
Key words： virtual reality; collision detection; bounding volume hierarchies; interference
0 引言
数字化、消息化是当今国表里高科技成长的潮水和趋向，跟着计较机软硬件手艺的快速成长，特别是图形处置器以及与之相关的三维游戏，虚拟仿真等手艺的兴起，碰撞检测手艺再次成为计较机仿真范畴研究的热点之一。在虚拟仿真系统中，若是物体间发生碰撞，系统必需及时而精确地检测到这些碰撞并作出响应的碰撞响应[1]，不然物体间就会发生穿透现象，影响虚拟场景的实在性。以前在主动拆卸规划以及径规划等范畴中，为了检测场景中的物体之间或零件之间能否发生碰撞，发生了很多碰撞检测算法，尔后相关专家在碰撞检测的理论和使用方面做了一系列的尝试，并获得了很多有主要价值的研究成果。
近二三十年来，国表里研究人员在碰撞检测范畴中做了大量成心义的工作，颠末详尽的研究和尝试验证之后，获得了很多适用的碰撞检测算法，对虚拟现实手艺的快速成长起到了积极的鞭策感化。本文将从二维平面和三维空间两个方面临碰撞检测手艺进行较为详尽的阐述。
1 二维空间碰撞检测问题
二维空间中的碰撞检测几乎是所有碰撞检测算法不成回避的问题，它是指三角形、多边形等面模子之间的求交问题，是三维空间中切确碰撞检测的必经阶段[2]。近几十年来，很多专家学者对平面碰撞问题进行了深切的研究，并取得一些对劲的成果，提出了很多优良的算法。
Chin和Wang两人研究了两个多边形的订交和最小距离问题。操纵可视边链和凸的极点相对于其内部点的枯燥性，提出了判别凸n边形和一个简单非凸m边形的订交问题的最优算法[3]，而且研究了当两个多边形订交时，一个多边形能否被另一个多边形完全包含的问题，当时间复杂度都为O(m+n)。
曲采用平面扫描算法，处理了平面内肆意简单多边形平移时碰撞部位的鉴定问题[4]。平面内肆意两个互不订交的简单多边形，若此中一个多边形沿某一标的目的平移时与另一个多边形碰撞，采用平面扫描法，通过提取多边形的枯燥链，给出了求其碰撞部位的算法。与现有的算法比拟，降低了时间复杂性。
覃中平、张焕国研究了平面内两个互不订交的凸多边形，若此中一个凸多边形沿某一标的目的与另一个凸多边形相碰撞，采用折半搜刮手艺来确定凸多边形相碰撞时两者最后相碰撞的极点和边[5]，而且提出了时间复杂度为O(logm+logn)的优良算法。
汪嘉业操纵枯燥折线研究了在一个多边形的凸包和另一个多边形不订交的前提下，确定两个多边形能否碰撞，并在碰撞时确定全数碰撞部位的问题[6]，提出了时间复杂度为O(m+n)的最优算法，而且其算法还可推广到确定包含有圆弧边的多边形之间的最后碰撞部位。
申静波，唐国维等人提出了基于夹边边对的空间平面凸多边形快速订交检测算法[7]，并将算法的使用对象从三角形扩展到肆意空间平面凸多边形，间接进行多边形间求交计较。该算法在确定所要检测的两个凸多边形能否都具有相对于另一凸多边形地点平面的夹边边对的根本上，按照计较成果求取两组边对间对应夹边的符号距离，以此判断两个多边形能否订交。
2 三维空间中碰撞检测问题
从空间域的角度来划分，碰撞检测算法大体可分为两大类：一类是基于图象空间的碰撞检测算法;另一类是基于物体空间的碰撞检测算法。这两类算法的区别在于，前者是操纵物体二维投影的图象加上深度消息来进行订交阐发，后者则是操纵物体三维几何特征进行求交计较。
2.1 基于图像空间的碰撞检测算法 基于图象空间的碰撞检测算法的根基思惟是操纵图形硬件将三维几何对象投影到二维图像平面，同时操纵深度缓存进行深度测试，以判断对象之间能否发生碰撞。可是基于图象空间的碰撞检测算法因为其检测成果的不切确性和依赖硬件支撑而不断成长较慢。近十几年，跟着图形硬件手艺的飞速成长，图形加快卡在机能不竭敏捷提高的同时以至呈现了可编程的功能。在碰撞检测的研究中，人们起头将三维几何物体通过投影绘制到图像平面上，获得一个二维的图像空间，然后阐发该空间中保具有各类缓存的消息，进而检测出物体之间能否发生[8]。这类算法劣势在于能无效操纵图形硬件加快手艺来减轻CPU的计较承担，从而达到提高算法效率的目标。
Shinya和Forgue等[9]提出在绘制凸体的同时，保留视窗口中每个象素上物体的最大和最小深度序列，并将它们按大小挨次陈列，然后检测物体在某一象素上的最大深度值能否与其最小深度值相邻来判别订交环境。虽然图形硬件能够支撑物体最大/最小深度的计较，但该方式并不适用，由于它要求大量的内存来保留深度序列，并且从图形硬件中读取深度值本身就很是费时。
(义务编纂：user
