发布时间：2014-09-25 14:43所属分类：电子手艺论文浏览：1次插手珍藏
摘 要： 碰撞检测在图形学、仿真、动画和虚拟现实等手艺中获得普遍的研究，这些研究具有十分主要的意义。文章对二维空间中多边形等面模子间订交，以及三维空间中多面体等体模子间的角度对碰撞检测手艺的研究和成长作了较为全面的阐述，并对几种常用的碰
摘 要： 碰撞检测在图形学、仿真、动画和虚拟现实等手艺中获得普遍的研究，这些研究具有十分主要的意义。文章对二维空间中多边形等面模子间订交，以及三维空间中多面体等体模子间的角度对碰撞检测手艺的研究和成长作了较为全面的阐述，并对几种常用的碰撞检测算法进行了阐发和比力，最初对碰撞检测算法的成长标的目的提出了几点。
环节词：电子手艺论文颁发,虚拟现实,碰撞检测,条理包抄盒,
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]提出在绘制凸体的同时，保留视窗口中每个象素上物体的最大和最小深度序列，并将它们按大小挨次陈列，然后检测物体在某一象素上的最大深度值能否与其最小深度值相邻来判别订交环境。虽然图形硬件能够支撑物体最大/最小深度的计较，但该方式并不适用，由于它要求大量的内存来保留深度序列，并且从图形硬件中读取深度值本身就很是费时。
Gress等[10]操纵GPU的可编程性，将碰撞检测计较映照到GPU的极点处置器和片段处置器中，通过实施绘制完成碰撞检测计较，再通过遮挡查询获得碰撞检测成果。该算法既了碰撞检测的精确性，同时也充实操纵了GPU强大的并行计较能力。
Govindaraju等[11]操纵图形硬件进行初步检测阶段，敏捷剔除大规模场景中较着不发生碰撞的物体;然后操纵几何布局下的快速订交检测算法获得切确的碰撞检测成果。该算法在处置虚拟场景中多物体间初期碰撞检测方面能取得不错的结果。
Heidelberger等[12]操纵面向体暗示的方式，提出了一种可以或许处置可变形物体的碰撞检测算法。该算法起首将两物体的订交区域按条理深度分化为条理深度图(layered depth image);然后通过图形硬件绘制过程来判断两物体在条理深度图的每个像素上能否有订交区间具有，从而确定物体能否发生碰撞。此算法不适合大规模物体间的碰撞检测。
2.2 基于物体空间的碰撞检测算法
三维空间中碰撞检测问题与二维空间碰撞检测问题比拟要复杂得多，目前，基于三维空间的碰撞检测算法次要分为三类：距离法、空间分化法(或空间剖分法)、条理包抄盒法。
2.2.1 距离法
距离法是通过寻找和两个多面体之间的比来点来计较它们之间的距离。当距离小于等于零时，发生碰撞;不然没有发生碰撞。当物体的活动速度不快，相邻帧间活动物体的位移变化很小时，能够操纵帧间的持续性来增量式的计较物体间的距离。
最早呈现的算法是Lin-Canny算法[13]，它畴前次获得的比来特征对起头，沿多面体的概况挪动，直到找到新的比来特征。明显，这种算法依赖于相邻两次比来特征的距离，即模子的相关性。若是相关性越高，那么算法的效率越高;相反相关性越低，算法效率就越低。
Enhanced GJK算法[14]是在GJK算法上改良而成。GJK算法是一个计较两凸多面体间的最短距离的算法，与Lin-Canny算法分歧的是，GJK不是间接对两凸多面体进行搜刮和，而是在他们的明氏距离多面体参数空间中搜刮施行，它具性时间复杂度;Enhanced GJK算法将原GJK算法的时间复杂度改良为近乎常量级，达到与Lin-Canny算法的划一程度。Enhanced GJK采用了“登山法”迭代算法求解，使时间复杂度大大降低，根基呈线性，大大削减了运算时间。
2.2.2 空间剖分法
空间剖分法是将整个虚拟空间划分成相等体积的小单位格，只对占领统一单位格或相邻单位格的几何对象进行订交测试。合用于物体在空间中平均分布的稀少。
Ganter和Isarankura成长了单步检测方式，提出了一种空间朋分手艺的方式[15]，这种空间朋分手艺将包含物体的空间划分为一个个子空间，将所有的测试在两个物体的堆叠局部区域来进行，而且在堆叠区域内的所有的子空间都按照最小、最大值来排序，从而进一步削减测试的时间。
Fuch和Kedem提出二叉空间朋分BSP(Binary Space Partition)即空间任何一个平面，都能够将它地点的空间朋分为两个互不订交的子空间，空间中其他平面均可划归在某一子空间中。同样，某一子空间中任一平面能够将该空间分为别的两个互不订交的子空间。如斯递归朋分，将每次朋分平面插手二叉树节点，即可构成一棵描述场景条理布局的BSP树。BSP树碰撞检测算法是在虚拟场景中的两个对象间找出朋分平面以判断两个对象能否订交。若两个对象间具有朋分平面，则没有发生碰撞;否者，发生了碰撞。
2.2.3 条理包抄盒法
条理包抄盒算法是操纵体积略大而几何特征简单的包抄盒来近似地描述相对复杂的虚拟对象，进而通过机关树状条理布局能够越来越迫近对象的几何模子，直到几乎完全获得对象的几何特征，从而只需对包抄盒堆叠的部门进行进一步的订交测试。与一个物体相对应的条理布局的节点是空间上包抄该物体一部门几何对象的几何近似体(包抄盒)：条理布局的根节点包抄了整个物体，每个父节点包抄的几何对象是它的所有子节点包抄的几何对象之和，节点从上到下逐步迫近它包抄的几何对象。操纵条理包抄盒方式进行碰撞检测时，起首测试几何对象的包抄盒能否订交，若是包抄盒不订交，则被包抄的对象就不订交;只要包抄盒订交时，才对其所包裹的几何对象做进一步订交测试。
目前，比力典型的包抄盒类型有包抄球(Sphere)、轴向包抄盒AABB(Axis-Aligned Bounding Box)、标的目的包抄盒OBB(Oriented Bounding Box)以及离散有向多面体k-DOPs(Discrete Orientation Polytopes)等。 包抄球(Sphere)[16]是简单性好慎密性差的一类包抄盒，一个给定对象的包抄球被定义为包含该对象的最小的。计较给定对象的包抄球，起首需别离计较对象的根基几何元素调集中所有元素的极点的x、y、z坐标均值以确定包抄球的球心c，再由球心与三个最大值坐标所确定的点与点之间的距离计较半径r。包抄球确定的区域为：R={(x，y，z)T(x-cx)2+(y-cy)2+(z-cz)2轴向包抄盒AABB(axis-aligned bounding box)[17]是最早的一类包抄盒，在碰撞检测的研究汗青中利用得最广，一个物体的AABB被定义为包含该对象且边平行于坐标轴的最小正六面体。对于给定的对象，它的AABB仅需六个标量描述，即构成物体根基几何元素的极点的x坐标、y坐标以及z坐标的最大值和最小值。AABB间的堆叠测试比力简单，两个AABB堆叠当且仅当它们在三个坐标轴上的投影区间均堆叠，则它们是订交的。
OBB包抄盒条理(Oriented Bounding Box)是慎密型好、订交测试复杂的一类包抄盒[18]。一个给定对象的OBB被定义为包含该对象且相对于坐标轴标的目的肆意的最小的正六面体。OBB最大特点是它的标的目的的肆意性，这使得它能够按照被包抄对象的外形特点尽可能慎密地包抄对象，但同时也使得它的订交测试变得复杂。OBB间的订交测试基于分手轴理论，若两个OBB在一条轴线上(不必然是坐标轴)上的投影不堆叠，则这条轴称为分手轴，若一对OBB间具有一条分手轴，则能够鉴定这两个OBB不订交，不然它们是订交的。
离散有向多面体k-DOPs(Discrete Orientation Polytopes)[19]是由纽约州立大学的James T、Klosowski等人提出的。一个对象的k-DOPs被定义为包含该对象且它的所有面的法向量都来自一个固定标的目的(k个向量)的调集的凸包，此中的标的目的向量为共线且标的目的相反的向量对。一个几何对象的k-DOPs能够通过计较对象的极点与固定标的目的集D中的各个标的目的的最大点积获得。D中有k/2对标的目的相反的向量对，k-DOPs在每对向量上的最大延长确定了它在该对向量上的投影区间，一个k-DOPs包抄盒完全可由描述它在这些向量对上的k/2个投影区间所确定。因而，k-DOPs包抄盒间的订交测试能够通过投影区间的堆叠测试来完成，只需两个k-DOPs包抄盒在D中某一个标的目的对上的投影区间不堆叠，就能够鉴定它们是不订交的;不然认为它们是订交的。
2.2.4 基于物体空间的碰撞检测算法的阐发比力
目前，在物体空间的碰撞检测的算法中，距离法依赖于相邻两次比来特征的距离，即模子的相关性。若是相关性越高，那么算法的效率越高;相反，相关性越低，算法效率就越低。这就使得算法具有了不不变性，其健壮性也遭到影响。空间剖分法因为只适合于物体在空间平均分布的稀少，简单地从大量物体中解除不订交的物体。但对于一般的，很难选择一个最优的剖分尺寸，若选择不妥，会导致空间花费大，计较效率降低，因而空间剖分法有必然的局限性，是一种较罕用到的方式。与上述两种算法比拟，条理包抄盒法是碰撞检测算法中一种被普遍利用的方式，在对物体进行碰撞检测时，起首辈行包抄盒间的订交测试，因为包抄盒间的求交过程比物体间求交过程简单，所以能够尽早地解除大量不订交的物体，节流碰撞检测的时间，提高碰撞检测的效率。对研究人员来说，这种方式无疑是一种较好的选择。可是，这种方式也有它的错误谬误，当被检测的对象的变得越来越复杂时，建立包抄盒树会占用大量存储空间的同时，也会添加参与订交测试包抄盒的数量，因而会花费大量存储空间和订交测试的时间。
3 竣事语
在虚拟中，碰撞问题不断是典范而环节的问题之一，因此获得良多专家学者的关心和研究，他们提出了各类各样的方式来提高检测算法的效率和鲁棒性。作者认为在当前研究中能够从以下几个方面入手。
⑴ 条理包抄盒法是一种被研究人员普遍利用的算法，操纵该方式对物体间进行订交测试时，在大多环境下城市当即发生无碰撞结论。因而节流包抄盒间订交测试的次数和订交测试的时间是提高检测效率的无效路子，所以研究者能够采用夹杂的包抄盒方式，即外层采用慎密性差、订交测试简单的包抄盒，如包抄球，而里层采用慎密性好、订交测试复杂的包抄盒，如OBB，在处理及时碰撞检测问题时不失为一个无效的方式。
⑵ 基于图像的碰撞检测算法属于较新的一类算法。但已经因为遭到图形硬件成长的，研究进展相对比力迟缓。跟着图形硬件的成长才得以从头进入研究者的视野，国外有一批研究者正在进行该方面的研究，包含了碰撞检测范畴，国内在这方面的研究尚属起步阶段，较少。CPU与GPU间的负载均衡问题有待进一步研究，以提高算法效率。该类算法因为其本身的劣势，出格是跟着图形硬件的飞速成长，具有广漠的研究前景和研究价值。
⑶ 操纵多核CPU并行计较的功能来提高碰撞检测的效率。跟着计较机硬件的不竭成长，双核，四核，以至少核CPU应运而生，通过把多核CPU并行计较，以及数据分块思惟使用到碰撞检测算法之中，以静态和动态使命分派策略相连系的方式来提高算法的并行度，从而达到提高碰撞检测速度的目标。其焦点问题是若何找出更好的动态使命分派策略以完全实现CPU间负载平衡，这是此后一个研究标的目的。
总之，碰撞检测手艺仍有很多方面需要进一步切磋和研究，包罗软体模子、复杂模子之间的碰撞、框架与框架之间的空间分歧性，以及接触和之间的区分等问题。因而，需要研究者不竭细心研究，拓宽思，设想出更高效的算法，才能满足虚拟场景中大量复杂物体之间碰撞检测及时性的要求。
参考文献： [1] 何雪薇，龚光红.虚拟人活动的动力学实现方式研究[C]. 2003全国
系统仿真年会论文集.西安：中国系统仿真学，2003：614-619
[2] 强，洪嘉振，杨辉.碰撞检测问题研究综述[J].软件学报，1999.10
(5)：545-551
[3] F.Chin， C.A.Wang. Optimal Algorithms for the Intersection and
the Minimum Distance Problems between Planar Polygons. IEEE Transactions on Computers，1993.C-32(12)：1203-1207
[4] 曲.确定肆意简单多边形平移时碰撞部位的扫描算法[J].计较机
学报，2000.23(7)：692-1698
[5] 覃中平，张焕国.确定凸多边形平移时最后碰撞部位的最优算法[J].
计较机学报，1992.15(3)：171-177
[6] 汪嘉业.平面上简单多边形平移时确定碰撞部位的最优算法[J].计较
机学报，1992.15(8)：582-588
[7] 申静波，唐国维，李井辉.基于夹边边对的凸多边形间快速订交检测
算法[J].计较机工程与科学，2007.29(12)：93-94
[8] N.K. Govindaraju， M.C. Lin， D. Manocha. Fast and reliable
collision culling using graphics hardware[J].IEEE Transactions on Visuallization and Computer Graphics，2006.12(2)：143-154
[9] M. Shinya， M. Forgue. Interference Detection through Rasteriza-
tion. Journal of Visua-lization and Computer Animation，1997.2(8)：131-134
[10] A. Gress， G. Zachmann. Object-space interference detection on
programmable graphics hardware[C]. SIAM Conference on Geometric Design and Computing Washington. DC： Nashboro Press，2006：13-17
[11] GOVINDARAJU N K， LINM C， MANOCHA D.Quick-
CULLIDE： st inter-and intra-object collision culling using graphics hardware[C] //Proc of IEEE Virtual Reality，2005：59-66
[12] HEIDELBERGER B， TESCHNER M， GROSS M.Volumetric
collision detection for derformable objects， TR395[R].Zurich， Switzerland： Computer Science Department ETH，2003.
[13] M. C. Lin， J. F. Canny. A Fast Algorithm for Incremental
Distance Calculation. In Proceedings of the IEEE International Conference on Robotics and Automation， Sacramento， CA，1991：1008-1014
转载请注明来自：http://www.lunwencheng.com/lunwen/dzi/5523.html
