论文部分内容阅读
摘要:对曲面工件的超声自动检测中的碰撞干涉检测技术及其在超声自动检测中的应用进行了综述。
关键词:曲面工件；超声自动检测；碰撞干涉
1碰撞干涉检测
碰撞干涉检测问题是确定不同的物体在空间是否占有相同区域的问题。该问题可描述如下:“给定N 个物体s1 ， s2 ，… ， sn ，它们在空间中的位置是由定义在时间域[t 0 ， t 1 ] 上的函数f 1 ，f 2 ，… ， f n 来确定的，判定在这个时间域内相同时刻是否存在任何一对物体占有公共空间”。该问题的描述说明了这样的意义，物体占有的空间决定于时间，由此又引出静态干涉和动态干涉检测的定义。
静态干涉检测: 物体在空间中的位置是可移动的，但不随时间变化，位置的变化是由其它参数定义的，判别是否有任何一对物体占有公共空间。空间布局和装配干涉检测等即属于此类问题。
动态干涉检测: 动态干涉检测与时间相关，即碰撞检测。物体在空间中的位置是随时间变化的，它可分为二种情况: ( 1) 运动空间中只有一个物体是运动的。例如一个机器人在车间里运动，机器人是运动的，车间里的其它障碍物是静止的；( 2) 一对物体都必须是运动的，例如车间里两个运动的机器人。无论是静态干涉检测还是动态干涉检测，目的都是要求避免物体间的碰撞。
2碰撞干涉检测技术
2.1二维平面碰撞检测
Tetsuya，Toshiaki和Mario等人提出了一种称为空间占有的方法，即物体在目标空间移动，当试图占有相同的球体时来检测它们的碰撞。这种算法基于这样一条原理没有任何物体和其它物体占有同一个球体，也不需要特殊的计算来检测碰撞。并且，在它们的方法中，每个物体连同它们所占有的球体在三维空间中都被赋予一个名字，因而其它物体知道它们和哪个物体发生碰撞。
chin和wang研究了两个多边形的相交和最小距离问题。利用可视边链和凸的顶点相对于其内部点的单调性，提出了判别凸一边形和一个简单非凸m-边形的相交问题的最优算法，并且研究了当两个多边形相交时一个多边形是否被另一个多边形完全包含的问题，其时间复杂度都为o(m+n)。
汪嘉业利用单调折线研究了在一个多边形的凸包和另一个多边形不相交的条件下，确定两个多边形是否碰撞，并在碰撞时确定全部碰撞部位的问题，提出了时间复杂度为o(m+n)的最优算法，并且其算法还可推广到确定包含有圆弧边的多边形之间的最初碰撞部位。
李辉利用最大最小坐标的顶点子集的方法研究了一个凸多边形沿一给定方向移动时是否与另一凸多边形发生碰撞，并且利用斜支撑线的方法来研究一个凸多边形相对于另一个凸多边形的可移动区域问题，提出了时间复杂度为o(log(n+m))和o(m+n)的算法，在常数意义下，它们都是最优的。
2.2三维空间碰撞检测
三维空间碰撞检侧干涉有两大类静态干涉和动态碰撞检测。动态碰撞检测就是沿特定轨迹移动的物体的干涉检测。动态碰撞检测算法又可分为两大类①判断移动的物体之间是否发生碰撞亦即可碰撞问题②检测到碰撞的存在并采取措施进行规避，也就是碰撞规避问题。根据所用实体表示模型的不同，静态干涉检测算法大致可分成两类。一类算法主要基于B-rep模型，提高算法效率的关键是如何减少被测元素的数量。在这方面Ganter利用空间分割技术作出了新的尝试。另一类算法是以层次模型为基础的，如八叉树干涉检验算法和层次Sphere检验算法等。由于层次模型中相邻两层节点的检测过程之间缺乏直接联系，即一个层次上的干涉检验结果并没有反映出下一个层次节点的状态信息，因此无法对检验过程进行优化，以减少不必要的运算。
动态碰撞检测先后利用到两类技术。第一类技术是基于给定轨迹反复利用静态干涉检测被称为“单步检测”的方法，即当物体移动过程中将轨迹划分为很多时间步，在每一个时间步都进行静态干涉检测，来判定运动的物体之间是否发生碰撞。Maruyama介绍了多面体之间的静态干涉检测的第一种一般方法，提出了一种递归空间分割算法和一种一般的面对面相交算法然而，提出了第一种可用的单步检测系统，。计算几何领域对许多其它相交测试技术进行了规范化和分类。其中有许多技术是二维相交技术的延伸和扩展。第二类技术是基于产生称之为“扫描实体”的物体。这些物体代表了物体在给定轨迹上移动过程中所占有的体积空间。如果环境中的物体在它们各自的轨迹上行进时会发生碰撞，那么它们各自的扫描体将会发生静态干涉。因而，扫描体可用简单的静态干涉检查来对动态碰撞进行测试，这些扫描体的产生是运动学和实体模型的结合。由于实体模型具有多种表示方式，因此，多种形式的扫描体被提出。
虽然扫描体可用于许多有趣的工程问题，但在现在的计算机图形硬件条件下，单步检测方法更适合于实时计算机图形显示。并且扫描体方法也没有单步检测方法所具有的决定碰撞时间的灵活性。而且用扫描体来进行碰撞检测需要利用一个独立的步骤来产生扫描实体。和发展了单步检测方法，提出了一种空间分割技术的方法，这种空间分割技术将包含物体的空间划分为一个个子空间，将所有的测试限制在两个物体的重叠局部区域来进行。并且在重登区域内的所有的子空间都按照它们的最小、最大值来排序。然而在空间分割技术中，子空间的个数将影响到检侧结果的正确性和算法的效率。
Hahn采用层次包围盒技术来加速多面体场景的碰撞检测。Moore则提出了两个有效的碰撞检测算法，其一是用来处理三角剖分过的物体表面。由于任一表面均可表示成一系列三角面片，因而该碰撞检测算法具有普遍性该算法的缺点是当景物为一复杂的雕塑曲面时，三角剖分可能产生大量的三角片，这会大大影响算法的效率。而另一算法则用来处理多面体环境的碰撞检测。Moore和Wilhelems根据Cyrus-Beck裁剪算法提出了一种凸多面体碰撞检测算法，即通过检测多面体顶点是否相互包含来判定它们是否发生碰撞。对于具有n个凸多面体、每个多面体有m个顶点的问题，此算法的时间复杂度为o(n2m2)；对于凹多面体则分解为多个凸多面体来处理Ganter和Isarankura提出了一种空间分割的方法，即将给定物体所占有的空间划分成一系列子空间，将碰撞测试限定在两物体的重叠子空间中进行，并且在重叠子空间里的元素都按最大、最小来排序，从而进一步减少了测试时间。Alonso，Serrano和Flaquer采用定义碰撞影响矩阵及体元的数据结构等一些优化策略来加快碰撞检测，它们的算法分四步来检测两个物体的干涉①检测碰撞影响矩阵②计算每对容器之间的干涉③计算体元之间的干涉④计算面与面之间的干涉。算法的基本思想是每一步都比它的下一步快，因而，假如在某一步发现两个物体不会碰撞，就不必进行下面的测试，从而可节省计算时间。
3碰撞干涉在超声自动检测中的应用
和数控加工、产品装配一样，超声自动检测过程中可能存在碰撞干涉，如探头和工件的碰撞、工件夹具和探头的碰撞等。在实际检测过程中如果发生了碰撞，不仅可能造成工件的报废、探头和设备的损坏，严重时还可能威胁到操作者的人身安全。因此有必要在实际检测之前对扫描路径进行校验，找出发生碰撞干涉的运动点位，重新进行路径规划，避免碰撞带来的损失。
超声检测的曲面工件一般具有复杂的外形，碰撞干涉检测时运算量很大，同时对检测的精度和效率都有较高的要求。尽管现有碰撞干涉检测的方法很多，但针对超声自动检测过程中碰撞干涉检测的性能有限，如包围盒算法计算简单，容易实现快速碰撞检测，但该方法的精确性不高；空间分解法将整个虚拟空间划分成相等体积的小单元格，然后对占据同一单元格或相邻单元格的几何对象进行相交测试，精确性高但运算复杂。
参考文献：
[1]张旭辉，马宏伟.超声无损检测技术的现状和发展趋势，机械制造，2002，40（7）：24-26
[2]罗雄彪，陈铁群.超声无损检测的发展趋势，无损检测，2005，27（3）：148-152
[3]吴思源.曲面工件超声自动检测中若干关键技术研究，杭州浙江大学博士论文，2006
作者简介： 和娟（1984-），女，中级工程师。
关键词:曲面工件；超声自动检测；碰撞干涉
1碰撞干涉检测
碰撞干涉检测问题是确定不同的物体在空间是否占有相同区域的问题。该问题可描述如下:“给定N 个物体s1 ， s2 ，… ， sn ，它们在空间中的位置是由定义在时间域[t 0 ， t 1 ] 上的函数f 1 ，f 2 ，… ， f n 来确定的，判定在这个时间域内相同时刻是否存在任何一对物体占有公共空间”。该问题的描述说明了这样的意义，物体占有的空间决定于时间，由此又引出静态干涉和动态干涉检测的定义。
静态干涉检测: 物体在空间中的位置是可移动的，但不随时间变化，位置的变化是由其它参数定义的，判别是否有任何一对物体占有公共空间。空间布局和装配干涉检测等即属于此类问题。
动态干涉检测: 动态干涉检测与时间相关，即碰撞检测。物体在空间中的位置是随时间变化的，它可分为二种情况: ( 1) 运动空间中只有一个物体是运动的。例如一个机器人在车间里运动，机器人是运动的，车间里的其它障碍物是静止的；( 2) 一对物体都必须是运动的，例如车间里两个运动的机器人。无论是静态干涉检测还是动态干涉检测，目的都是要求避免物体间的碰撞。
2碰撞干涉检测技术
2.1二维平面碰撞检测
Tetsuya，Toshiaki和Mario等人提出了一种称为空间占有的方法，即物体在目标空间移动，当试图占有相同的球体时来检测它们的碰撞。这种算法基于这样一条原理没有任何物体和其它物体占有同一个球体，也不需要特殊的计算来检测碰撞。并且，在它们的方法中，每个物体连同它们所占有的球体在三维空间中都被赋予一个名字，因而其它物体知道它们和哪个物体发生碰撞。
chin和wang研究了两个多边形的相交和最小距离问题。利用可视边链和凸的顶点相对于其内部点的单调性，提出了判别凸一边形和一个简单非凸m-边形的相交问题的最优算法，并且研究了当两个多边形相交时一个多边形是否被另一个多边形完全包含的问题，其时间复杂度都为o(m+n)。
汪嘉业利用单调折线研究了在一个多边形的凸包和另一个多边形不相交的条件下，确定两个多边形是否碰撞，并在碰撞时确定全部碰撞部位的问题，提出了时间复杂度为o(m+n)的最优算法，并且其算法还可推广到确定包含有圆弧边的多边形之间的最初碰撞部位。
李辉利用最大最小坐标的顶点子集的方法研究了一个凸多边形沿一给定方向移动时是否与另一凸多边形发生碰撞，并且利用斜支撑线的方法来研究一个凸多边形相对于另一个凸多边形的可移动区域问题，提出了时间复杂度为o(log(n+m))和o(m+n)的算法，在常数意义下，它们都是最优的。
2.2三维空间碰撞检测
三维空间碰撞检侧干涉有两大类静态干涉和动态碰撞检测。动态碰撞检测就是沿特定轨迹移动的物体的干涉检测。动态碰撞检测算法又可分为两大类①判断移动的物体之间是否发生碰撞亦即可碰撞问题②检测到碰撞的存在并采取措施进行规避，也就是碰撞规避问题。根据所用实体表示模型的不同，静态干涉检测算法大致可分成两类。一类算法主要基于B-rep模型，提高算法效率的关键是如何减少被测元素的数量。在这方面Ganter利用空间分割技术作出了新的尝试。另一类算法是以层次模型为基础的，如八叉树干涉检验算法和层次Sphere检验算法等。由于层次模型中相邻两层节点的检测过程之间缺乏直接联系，即一个层次上的干涉检验结果并没有反映出下一个层次节点的状态信息，因此无法对检验过程进行优化，以减少不必要的运算。
动态碰撞检测先后利用到两类技术。第一类技术是基于给定轨迹反复利用静态干涉检测被称为“单步检测”的方法，即当物体移动过程中将轨迹划分为很多时间步，在每一个时间步都进行静态干涉检测，来判定运动的物体之间是否发生碰撞。Maruyama介绍了多面体之间的静态干涉检测的第一种一般方法，提出了一种递归空间分割算法和一种一般的面对面相交算法然而，提出了第一种可用的单步检测系统，。计算几何领域对许多其它相交测试技术进行了规范化和分类。其中有许多技术是二维相交技术的延伸和扩展。第二类技术是基于产生称之为“扫描实体”的物体。这些物体代表了物体在给定轨迹上移动过程中所占有的体积空间。如果环境中的物体在它们各自的轨迹上行进时会发生碰撞，那么它们各自的扫描体将会发生静态干涉。因而，扫描体可用简单的静态干涉检查来对动态碰撞进行测试，这些扫描体的产生是运动学和实体模型的结合。由于实体模型具有多种表示方式，因此，多种形式的扫描体被提出。
虽然扫描体可用于许多有趣的工程问题，但在现在的计算机图形硬件条件下，单步检测方法更适合于实时计算机图形显示。并且扫描体方法也没有单步检测方法所具有的决定碰撞时间的灵活性。而且用扫描体来进行碰撞检测需要利用一个独立的步骤来产生扫描实体。和发展了单步检测方法，提出了一种空间分割技术的方法，这种空间分割技术将包含物体的空间划分为一个个子空间，将所有的测试限制在两个物体的重叠局部区域来进行。并且在重登区域内的所有的子空间都按照它们的最小、最大值来排序。然而在空间分割技术中，子空间的个数将影响到检侧结果的正确性和算法的效率。
Hahn采用层次包围盒技术来加速多面体场景的碰撞检测。Moore则提出了两个有效的碰撞检测算法，其一是用来处理三角剖分过的物体表面。由于任一表面均可表示成一系列三角面片，因而该碰撞检测算法具有普遍性该算法的缺点是当景物为一复杂的雕塑曲面时，三角剖分可能产生大量的三角片，这会大大影响算法的效率。而另一算法则用来处理多面体环境的碰撞检测。Moore和Wilhelems根据Cyrus-Beck裁剪算法提出了一种凸多面体碰撞检测算法，即通过检测多面体顶点是否相互包含来判定它们是否发生碰撞。对于具有n个凸多面体、每个多面体有m个顶点的问题，此算法的时间复杂度为o(n2m2)；对于凹多面体则分解为多个凸多面体来处理Ganter和Isarankura提出了一种空间分割的方法，即将给定物体所占有的空间划分成一系列子空间，将碰撞测试限定在两物体的重叠子空间中进行，并且在重叠子空间里的元素都按最大、最小来排序，从而进一步减少了测试时间。Alonso，Serrano和Flaquer采用定义碰撞影响矩阵及体元的数据结构等一些优化策略来加快碰撞检测，它们的算法分四步来检测两个物体的干涉①检测碰撞影响矩阵②计算每对容器之间的干涉③计算体元之间的干涉④计算面与面之间的干涉。算法的基本思想是每一步都比它的下一步快，因而，假如在某一步发现两个物体不会碰撞，就不必进行下面的测试，从而可节省计算时间。
3碰撞干涉在超声自动检测中的应用
和数控加工、产品装配一样，超声自动检测过程中可能存在碰撞干涉，如探头和工件的碰撞、工件夹具和探头的碰撞等。在实际检测过程中如果发生了碰撞，不仅可能造成工件的报废、探头和设备的损坏，严重时还可能威胁到操作者的人身安全。因此有必要在实际检测之前对扫描路径进行校验，找出发生碰撞干涉的运动点位，重新进行路径规划，避免碰撞带来的损失。
超声检测的曲面工件一般具有复杂的外形，碰撞干涉检测时运算量很大，同时对检测的精度和效率都有较高的要求。尽管现有碰撞干涉检测的方法很多，但针对超声自动检测过程中碰撞干涉检测的性能有限，如包围盒算法计算简单，容易实现快速碰撞检测，但该方法的精确性不高；空间分解法将整个虚拟空间划分成相等体积的小单元格，然后对占据同一单元格或相邻单元格的几何对象进行相交测试，精确性高但运算复杂。
参考文献：
[1]张旭辉，马宏伟.超声无损检测技术的现状和发展趋势，机械制造，2002，40（7）：24-26
[2]罗雄彪，陈铁群.超声无损检测的发展趋势，无损检测，2005，27（3）：148-152
[3]吴思源.曲面工件超声自动检测中若干关键技术研究，杭州浙江大学博士论文，2006
作者简介： 和娟（1984-），女，中级工程师。