面向遥操作机器人的混合层次包围盒碰撞检测

刘文聪,李作清,李世其

(华中科技大学机械科学与工程学院,湖北武汉430074)

0 引言

基于虚拟现实的遥操作机器人系统[1],通过建立机器人及其工作环境的虚拟交互模型,实时地将视觉、力觉、触觉等信息反馈给本地操作者,使操作者产生身临其境的感觉,从而有效地控制机器人完成复杂的作业任务,不仅提高了遥操作安全性,节约成本,消除时延对操作者的影响[2],还提高了系统运行的稳定性和透明性,极大地改善了遥操作机器人的作业效率和精细程度,广泛应用于空间服务、深海探测、核环境、远程医疗等领域。

碰撞检测是计算机动画、系统仿真、计算机图形学、机器人学、CAD/CAM等研究领域的经典问题,吸引了众多学者参与研究,出现了很多成熟的算法。碰撞检测算法按空间域角度可分为基于实体空间的碰撞检测方法和基于图像空间的碰撞检测方法,其中基于实体空间的算法又包括空间剖分法、层次包围盒法、基于单纯形的GJK及其改进算法、基于距离场的算法和基于智能优化技术算法等[3]。空间划分法通常适用于环境稀疏分布均匀的场景,层次包围体技术是最为常用的碰撞检测方法,适合于复杂物体间的快速碰撞检测,典型的包围盒包括包围球sphere、轴对齐包围盒AABB、方向包围盒OBB,每种包围盒都有自己的优缺点,适用于不同几何特征的物体[4]。

随着并行机的高速发展及多核处理器的普及,并行技术广泛应用于碰撞检测中。Tang[5]、Thomaszewski[6]、薛广涛[7]、赵伟[8]、杜鹏[9]等人采用并行处理技术来加速测试计算,对提高算法效率取得很好的效果。

结合不同包围盒的优点及并行处理快速计算的特点,本文采用混合层次包围体技术和多线程并行技术来提高检测质量和效率,并实时将干涉的图元渲染出来,给操作者以直观的感受。

1 遥操作机器人系统框架

基于虚拟现实的遥操作机器人系统主要包括主端、从端和网络通信三个部分:主端为操作端,主要负责操作者与虚拟场景及外设的交互操作,及控制指令的发送和反馈信息的接收;从端是机器人所在的远端,接收主端的指令完成相关任务,并把传感器和视觉等信息发送给主端,供操作者参考和交互;网络通信部分主要负责主从端之间的信息交互。基于虚拟现实的遥操作机器人系统框架如图1所示。

图1 基于虚拟现实的遥操作机器人系统框架

在基于虚拟现实的遥操作机器人系统中,碰撞检测是机器人路径规划、机器人完成抓取和安装等任务计算虚拟力及判断预测仿真结果的可取性等方面的依据。同时,检测速度至少要达到300 FPS,以维持触觉交互的稳定性,要达到1 000 FPS才能获得较好的效果[10]。快速精确的碰撞检测成为保证遥操作安全性、增强虚拟环境的真实感和用户的沉浸感的重要因素。

2 基于混合层次包围的碰撞检测

2.1 构建混合层次包围盒

包围盒的核心思想是优先使用代价低廉的测试类型,尽量使测试提早退出。包围球由于其较少的内存占有量、不受旋转变换的影响、快速的测试及相对较差的紧密性而被广泛应用在首次的粗略剔除判断中,而且在频繁运动且又具有关联关系的仿真场景中优于空间剖分法。AABB是应用最为广泛的包围体之一,能够实现快速的相交测试。为了弥补包围球和AABB紧密性较差的缺点,最后采用适合不断运动的杆状结构的OBB包围盒进行剔除测试。因此,采用包围球、AABB和OBB树构成物体的混合层次包围盒。

在预处理阶段,采用自顶向下的方式建立包含包围球、AABB、OBB树的混合层次包围盒,每个物体的混合层次包围盒结构如图2所示。

图2 混合层次包围盒结构图

a)构建AABB包围盒

AABB是包含几何对象且各边平行于坐标轴的最小六面体,可以用各坐标轴上的最小值和最大值来表示。首先遍历模型所有顶点,并向各个坐标轴投影获取沿各个坐标轴的最大值和最小值,依此来构成包围盒的最大值点和最小值点。

b)构建包围球

一个物体的包围球包含球心坐标和半径两个几何元素,可以通过物体的AABB来获取一个逼近的包围球:AABB的中心作为球心,AABB的最大值点和最小值点的距离的一半作为半径。

c)构建OBB层次包围盒

一个对象的OBB是包含对象且相对于坐标轴方向任意的最小的长方体,关键在找出最佳方向。采用Gottschalk在文献[11]中提出的计算三角形面片的方向包围盒的方法,并用自顶向下递归的方式构建树型结构。

在包含n个三角形的模型中,第k个三角形的顶点为(pk,qk,rk),面积为 ak,质心为 mk,模型三角面片的总面积和加权质心的均值分别为aH和mH,Cij为3×3协方差矩阵C元素:

协方差矩阵C是对称矩阵,其三个特征向量是相互正交的,把三个特征向量单位化后作为OBB局部坐标的三个轴向,把所有顶点向这三个轴投影,可以获得OBB的大小和中心坐标。

获得了模型OBB层次包围盒最上层的OBB后,用垂直父OBB最长轴且过所有顶点的均值点的平面分割父盒体,根据图元在分割面的位置,将图元划分到相应的子集中,如果图元跨越分割面,则将其归于质心坐标所处的子集中。如果最长轴上无法生成两个非半空子集,按照长度序列方式尝试其他轴,若全部轴都失效,那么该盒体是不能分割的。依此递归分割,直到不能分割为止。

2.2 运动物体的快速相交测试

在执行任务的过程中,机器人及其他部分物体的位姿和位置不断发生变化,因此需要进行混合层次包围盒的更新。在模型平移运动时,混合层次包围盒中各包围盒只需要加上平移向量即可,不需要重新构建。由于包围球和OBB是不受特定方向限制的非对齐包围体,而AABB是依赖于其既定的方向的对齐包围体,所以模型在旋转运动时:包围球没有方向性不需要重新构建;OBB的方向会发生相应的旋转变化,但只需要在基底上乘以旋转矩阵即可,同样不需要构建;至于AABB,鉴于其他测试方法的计算代价较大,这里还是按照上节方法重新构建。

在相交测试过程中按同步规则进行层次结构的下降,即依次按照 Sphere－Sphere,AABB－ AABB,OBBTree－OBBTree,三角形图元的顺序进行测试,若前者没有干涉就返回未干涉结果,提前完成两个物体之间的测试:球体之间的测试最为简便,只需比较两个球心之间的距离与两球体半径和的大小,为了避免计算成本较高的平方根操作,用距离的平方值进行相关运算;通过判断两个AABB在三个世界坐标轴上是否都存在交集,才能确定两盒体是否相交;OBBTree之间的测试采取深度优先的层次结构遍历策略[11]用分离轴理论进行OBB间的相交测试;三角形图元间的相交测试采用Held在文献[12]提出的穿越算法。

随着多核处理器的出现,计算机的计算性能得到较高提升,现代CPU支持单指令多数据流(single instruction multiple data,SIMD)的处理方式。为了加快多物体场景中的模型和混合包围盒树型结构遍历过程,本文将需要处理的不同层次的干涉测试进行任务划分:混合包围盒构建、检测序列遍历和包围球测试属于同一线程;而AABB测试、OBB Tree测试、面片测试与干涉面片的绘制分别用不同的线程来并行处理。如果上层干涉,就将干涉的物体对加入到下层测试线程中。

2.3 算法流程

正如上文所述,包围球和OBB层次包围盒只需要构建一次,而AABB需要在检测时进行不断构建,因此在整个场景只在进行首次测试时构建混合层次包围盒,否则只更新AABB。当需要检测的模型对序列遍历结束时完成一次整体的检测流程。如果序列没有遍历结束,首先进行最外层的包围球检测,若球检测未干涉,返回为未干涉结果,若干涉,就把待检测的模型对添加到AABB检测线程处理的检测序列中。依此类推,若上层未干涉就返回检测结果,上层检测干涉就将待检测的元素添加到下层检测线程处理序列中。如果三角形检测干涉的话,就将干涉的三角形对绘制出来,并返回干涉结果。整体算法流程如图3所示。

图3 碰撞检测流程图

3 仿真实验

利用VC＋＋6.0作为开发工具,使用面向对象和交互式的三维图形开发软件包Open Inventor5.0建立仿真界面,计算机系统配置为:操作系统Windows XP 32位;处理器Intel Core i5 CPU 750 2.67 GHz 4核;显卡NVIDIA Ge-Force GT 220 1GB;内存 4 GB。

遥操作机器人虚拟现实仿真平台如图4所示,六自由度机器人用末端工具将物体1移动到位置1处,并将物体2移动到物体1原来所在的位置2处。采用CAD软件Pro/E建立几何模型,并将弦高和角度值都设置为0.5,将CAD几何模型转换成包含几何信息的IV格式数据文件,仿真环境共包含10个模型对象,22 112个三角面片,模型IV文件大小为6.7 MB。

图4 实验仿真平台(未检测)

由于机器人自身的装配特性,在实验中并不检测相邻连杆间的干涉情况,除此之外,要遍历场景中的所有物体对进行检测,并将相互干涉的三角面片对实时绘制出来。发生干涉时的场景图5所示,存在干涉的三角形用细红线绘制。检测时间信息统计如表1所示,其中时间是完成一次完整场景遍历进行干涉检测所需要时间。

由表1可知,采用的多线程并行方法比串行计算效率提高13%~20%左右,而且当场景中存在的干涉三角面片对数小于1 000时,帧速率能达到30 FPS以上。

图5 发生干涉时的场景

表1 仿真实验干涉信息统计

4 结语

为了提高基于虚拟现实的遥操作机器人系统中碰撞检测的实时性和准确性,提出基于混合层次包围盒和多线程的快速测试方法:采用包围球、轴对齐包围盒和方向包围盒树构建模型的混合层次包围盒,快速逐步排除不相交的物体或物体的一部分,并用三角形间的测试进行精确检测;同时,在场景的遍历、层次结构的下降及绘制干涉三角形对中采用多线程技术加速计算过程。实验结果表明该算法在保证检测实时性方面有较好的表现。

[1]宋爱国.力觉临场感遥操作机器人技术研究进展[J].机械制造与自动化,2012(01).

[2]Woo Y.K.,Toshihlko G.,Kawabe H.Model－Based Space Robot Teleoperation of ETS-VII Manipulator[J].IEEE Trans.on Rob.and Auto.,Vol20(3),2004:602-612.

[3]熊玉梅.虚拟环境中物体碰撞检测技术的研究[D].上海:上海大学,2011.

[4]邹益胜,丁国富,许明恒,等.实时碰撞检测算法综述[J].计算机应用研究,2008(01).

[5]Min Tang, DineshManochab,Ruofeng Tong.MCCD:Multi-core collision detection between deformable models using front-based decomposition[J].Graphical Models,2010(03).

[6]Bernhard Thomaszewski,WolfgangBlochinger.Physically based simulation of cloth on distributed memory architectures[J].Parallel Computing,2007(06).

[7]薛广涛,李超,尤晋元.基于凸多面体剖分的并行碰撞检测算法[J].上海交通大学学报,2004(08).

[8]赵伟,何艳爽.一种快速的基于并行的碰撞检测算法[J].吉林大学学报(工学版),2008(01).

[9]杜鹏,唐敏,童若锋.多核加速的并行碰撞检测[J].计算机辅助设计与图形学学报,2011(05).

[10]金汉均.虚拟环境中物体碰撞检测算法研究[D].武汉:华中科技大学,2006.

[11]Stefan Gottschalk.Collision Queries Using Oriented Bounding Boxes[D].Department of Computer Science,University of North Carolina, Chapel Hill, 2000.

[12]Martin Held.ERIT-A Collection of Efficient and Reliable Intersection Tests[J].Journal of Graphics Tools, Volume 2, Issue 4, 1997.