机器人虚拟仿真及控制技术研究

计算机工程与设计ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇ　ａｎｄＤｅｓｉｇｎ　２０１０，３１（２０）４４５５　·仿真技术·　机器人虚拟仿真及控制技术研究　陈　伟　，　陈一民　，　汪　地　，　陈　明　（１．上海大学计算机工程与科学学院，上海２０００７２；２．上海大学机械与自动化学院，上海２０００７２）　摘要：为了实现对实体机器人逼真的模拟和准确的反馈，设计了一套具有一定通用性的机器人虚拟仿真系统，并在系统　中对虚拟物体采用分类策略成功地将ＡＡＢＢ与ｓｗＩＦＴ＋＋算法相结合，兼顾了仿真系统对碰撞检测算法的实时性与准确性的　要求，有效地解决了效率与正确性之间的矛盾　在算法预处理阶段对非凸物体采用表面凸分解的方法，使碰撞检测算法具　有处理非凸物体的能力。实验结果表明，该系统同样适用于服务型机器人，具有一定的通用性，碰撞检测算法比单独使用　ｓｗＩＦＴ＋＋算法具有更快速的优点。　关键词：机器人仿真；ＡＡＢＢ；ＳＷＩＦＴ＋＋；表面凸分解；碰撞检测　中图法分类号：ＴＰ３９１．４１　文献标识码：Ａ　文章编号：１０００—７０２４（２ｏｌｏ）２０．４４５５—０４　Ｒｅｓｅａｒｃｈ　ｏｎ　ｖｉｒｔｕａｌ　ｓｉｍｕｌａｔｉｏｎ　ａｎｄ　ｃｏｎｔｒｏｌ　ｏｆ　ｒｏｂｏｔ　ＣＨＥＮ　Ｗｅｉ　，ＣＨＥＮ　Ｙｉ—ｍｉｎ　，ＷＡＮＧ　Ｄｉ　，ＣＨＥＮ　Ｍｉｎｇ　（１．Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ｓｃｉｅｎｃｅ，Ｓｈａｎｇｈａｉ　Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ　２０００７２，Ｃｈｉｎａ；　２．Ｓｃｈｏｏｌ　ｏｆＭｅｃｈａｔｒｏｎｉｃｓ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｕｔｏｍａｔｉｏｎ，Ｓｈａｎｇｈａｉ　Ｕｎｉｖｅｒｓｉｙ，Ｓｈａｎｇｈａｉｔ　２０００７２，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｉｎ　ｏｒｄｅｒ　ｔｏ　ｒｅａｌｉｚｅ　ｔｈｅ　ｖｉｖｉｄ　ｓｉｍｕｌａｔｉｏｎ　ａｎｄ　ｔｈｅ　ａｃｃｕｒａｔｅ　ｆｅｅｄｂａｃｋ　ｏｆ　ｔｈｅ　ｅｎｔｉｔｙ　ｒｏｂｏｔ，ａ　ｓｅｔ　ｏｆ　ｒｏｂｏｔ　ｓｉｍｕｌａｔｉｏｎ　ｓｙｓｔｅｍ　ｉｓ　ｄｅｓｉｇｎｅｄ，ｗｈｉｃｈ　ｉｓ　ｏｆ　ｇｅｎｅｒａｌｉｔｙ．Ｉｔ　ｕｓｅｓ　ｃｌａｓｓｉｉｆｃａｔｉｏｎ　ｓｔｒａｔｅｇｙ　ｆｏｒ　ｖｉｒｔｕａｌ　ｏｂｊｅｃｔｓ　ｔｏ　ｃｏｍｂｉｎｅ　ｔｈｅ　ＡＡＢＢ　ａｌｇｏｒｉｔｈｍ　ｗｉｔｈ　ｔｈｅ　ｓｗＩＦＴ＋＋　ａｌｇｏｒｉｔｈｍ．Ｔｈｅｒｅｆｏｒｅ，ｉｔ　ｍｅｅｔｓ　ｔｈｅ　ｒｅｑｕｉｒｅｍｅｎｔｓ　ｏｆ　ｒｅａｌ—ｔｉｍｅ　ａｎｄ　ａｃｃｕｒａｔｅ　ｔｏｗａｒｄ　ｃｏｌｌｉｓｉｏｎ　ｄｅｔｅｃｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｉｎ　ｔｈｅ　ｓｉｍｕｌａｔｉｏｎ　ｓｙｓｔｅｍ　ａｎｄ　ｓｏｌｖｅｓ　ｔｈｅ　ｐａｒａｄｏｘ　ｂｅｔｗｅｅｎ　ｅｆｉｃｉｆｅｎｃｙ　ａｎｄ　ａｃｃｕｒａｃｙ．Ｉｎ　ｔｈｅ　ｓｔａｇｅ　ｏｆａｌｇｏｒｉｔｈｍ　ｐｒｅｔｒｅａｔｍｅｎｔ，ｔｈｅ　ｓｕｒｆａｃｅ　ｃｏｎｖｅｘ　ｄｅｃｏｍｐｏｓｉｔｉｏｎ　ｍｅｔｈｏｄ　ｉｓ　ｔａｋｅｎ　ＳＯ　ｔｈａｔ　ｔｈｅ　ｃｏｌｌｉｓｉｏｎ　ｄｅｔｅｃｔｉｏｎ　ａｌｇｏｒｉｈｍ　ｔｉｓ　ａｂｌｅ　ｔｏ　ｄｅａｌ　ｗｉｔｈ　ｔｈｅ　ｎｏｎ—ｃｏｎｖｅｘ　ｏｂｊｅｃｔｓ．Ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｓｙｓｔｅｍ　ｃａｎ　ｂｅ　ａｐｐｌｉｅｄ　ｉｎ　ｓｅｒｖｉｃｅ　ｒｏｂｏｔ　ａｎｄ　ｉｔ　ｉｓ　ｏｆ　ｇｅｎｅｒａｌｉｙ．Ｔｈｅ　ｃｏｌｔｌｉｓｉｏｎ　ｄｅｔｅｃｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｍｏｒｅ　ｅｆｉｃｉｆｅｎｔ　ｔｈａｎ　ｔｈｏｓｅ　ｗｈｉｃｈ　ｏｎｌｙ　ｕｓｅ　ＳＷＩＦＴ＋＋　ａｌｇｏｒｉｔｈｍ．　Ｋｅｙ　ｗｏｒｄｓ：ｒｏｂｏｔ　ｓｉｍｕｌａｔｉｏｎ；ＡＡＢＢ；ＳＷＩＦＴ＋＋；ｓｕｒｆａｃｅ　ｃｏｎｖｅｘ　ｄｅｃｏｍｐｏｓｉｔｉｏｎ；ｃｏｌｌｉｓｉｏｎ　ｄｅｔｅｃｔｉｏｎ　０引　言　传统的机器人研发面临着不能有效验证设计的合理性、　无法避免设计失误给机器人研发工作带来的影响，将虚拟技　术与仿真技术相结合的虚拟仿真技术能够给机器人的研发工　作提供可视化效果。虚拟仿真技术具有成本低、效率高和灵　使用ＶＣ＋＋与ＯｐｅｎＧＬ相结合的技术研究了虚拟仿真技术在　机器人仿真中的应用　。唐安慧等主要探索构建三维仿真平　台的总体框架，并对平台所涉及的各项关键技术进行了研究“　。　赵小川等通过使用Ｗｅｂｏｔｓ完成了仿真六足机器人的仿真造　型，并通过仿真实验验证了仿生六足机器人机构的合理性和　运动的灵活性　。文献［６】提出了一种使用模糊逻辑的足球机　活性好等特点，应用范围很广，相关研究较多，如上海大学对　Ｎ自由度机器人进行了数学建模和仿真研究，借助Ｍａｔｌａｂ和　Ｓｉｍｕｌｉｎｋ的计算和绘图能力实现了Ｎ自由度机器人的运动仿　真“　。哈尔滨工程大学提出了通过虚拟样机进行远程控制的　康复机器人系统方案，通过在Ｍａｔｌａｂ环境下实现虚拟仿真，达　到可视化效果　。文献［１—２］都是基于Ｍａｔｌａｂ开发平台的，其可　扩展性和通用性不是很好，且其显示效果不佳。张晨旭通过　器人传球策略的实现，通过使用虚拟仿真技术实现了对所设　计的系统的评估。其中文献ｎ一２】都是基于Ｍａｔｌａｂ开发平台的，　其可扩展性和通用性不是很好，且其显示效果不佳。文献【３—６］　未对适合机器人仿真的碰撞检测问题作深入研究，而碰撞检　测是虚拟现实系统中的研究难点。其主要的任务是判断物体　模型之间、模型与场景之间是否发生了碰撞，以及给出碰撞位　置、穿刺深度等信息。效果逼真、快速检测是这类算法的目　收稿日期：２００９—１２—０７；修订日期：２０１０－０３—１０。　基金项目：国家８６３高技术研究发展计划基金项目（２００７ＡＡ０１Ｚ３１９）；国家科技支撑计划课题基金项目（２ｏ０６ＢＡＫｌ３ＢｌＯ）：上海重点学科建设基　金项目０５０１０３）。　作者简介：陈伟（】９８５－－），男，江西南昌人，硕士研究生，研究方向为多媒体技术　陈一民（１９６１～），男，上海人，博士，教授，博士生导　师，研究方向为计算机控制、增强现实技术、网络与多媒体技术；　汪地（１９６８－－），男，浙江宁波人，博士，研究方向为机器人、网络与多媒体　技术；　陈明（１９７８一），男，江苏泰州人，博士研究生，研究方向为多媒体技术。Ｅ．ｍａｉｌ：￣ｃｈｅｎ２４＠ｙａｈｏｏ．ｃｎ　４４５６　２０１０，３　１（２０）　计算机工程与设计Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ｄｅｓｉｇｎ　标。朱元峰等提出了基于球状包围盒结构和有向包围盒的复　合层次包围盒的碰撞检测算法，其算法能较为有效地应用于　复杂场景的实时碰撞检测　。唐勇等利用帧与帧之间具有很　强关联性的特点，对基于轴向包围盒的碰撞检测算法进行了　优化，并使用基于压缩存储的方法改善了ＡＡＢＢ包围盒紧密　性差、占用大量存储空间的问题　。文献［９］研究了一种新的分　层结构并且能快速组织结构的实时碰撞检测算法，并在基于　超二次虚拟物体建模的虚拟环境中实现了触觉交互。文献　［１０】通过使用连通域剔除的方法实现了与可变形模型连续的　碰撞检测交互。碰撞检测也是研究的热点，本文根据机器人　仿真中对碰撞检测实时性与准确性的要求，在ＡＡＢＢ与　ｓｗＩＦＴ＋＋两类算法预处理及两者结合方面做了深入的研究工　作，较好地解决了机器人碰撞检测效率与正确性之间的矛盾，　另外，我们提出的算法具有处理非凸物体的能力。　１机器人仿真系统　机器人仿真系统包括机器人建模、虚拟场景的显示与交　互、机器人控制以及碰撞检测等。其中机器人建模又可以分　为几何建模和运动学建模两部分。　１．１机器人几何建模　几何建模是指用来描述对象内部固有的几何性质的抽象　模型，所表示的内容包括对象的三维造型（多边形、三角形和顶　点）与外观（纹理、表面反射系数、颜色等），主要有这样几类方法：　（１）利用计算机底层函数，编写大量代码从基本几何形体　开始逐步构建机器人外形；　（２）使用ＶＲＭＬ这种工业标准的虚拟现实描述语言，描述　虚拟机器人，构建虚拟场景：　（３）利用软件自带的简单三维几何模型组合成复杂的机器　人外形；　（４）利用专业建模软件如ＵＧ、Ｓｏｌｉｄｗｏｒｋｓ、３ｄｓｍａｘ对机器人　进行建模，并导出系统所需要的文件格式。通过比较发现最　后一种方法具有可视性、造型精确、易掌握等优点，有利于实　现仿真系统的通用性。　本文使用ｓｏｌｉｄｗｏｒｋｓ对机器人的每个部分进行单独的建　模，再统一装配，如图１所示。这个过程包括：测量实际机器　人的各个参数（包括本身的尺寸，各个关节的关节角等），建立　虚拟机器人与实际机器人之间的一个映射关系，最后将模型　统一输出为ＶＲＭＬ格式。　１．２机器人运动学建模　机器人的运动学分析是对杆件、传感器等机器人的各个　部件和作业环境内的对象等设置坐标系并分析这些坐标系之　间的位置和姿态的关系。杆件坐标系的选择有多种方法，但　最常用是Ｄｅｎａｖｉｔ－Ｈａｒｔｅｎｂｅｒｇ方法（简称Ｄ—Ｈ法）。假设用公式　（１）确定坐标系ｉ在坐标系ｉ－１中的位置和姿态　；　：？　～，，　）　（ｚ　，　）　ａ　，ａＪ　（１）　则可以递推完成各个连杆坐标系的变换，得到　２　＝　誓　１＝　【　　…　』　图１主要部件装配　使用公式（２），对每个连杆按照Ｄ．Ｈ法来进行建模，便可　以得到从底座到末端执行器间任意连杆的变换式。　由于我们使用ｓｏｌｉｄｗｏｒｋｓ进行建模、装配，ＯｐｅｎＩｎｖｅｎｔｏｒ对　机器人进行虚拟仿真，各个部件导入Ｏｐｅｎ　Ｉｎｖｅｎｔｏｒ之后具有　装配关系即已经有相对原点的位置和姿态，根据本文机器人　特点，参考公式（２）。我们使用的建模方法如图２所示。　图２部分关节坐标系　对各个关节求出相对于原点坐标系的变换矩阵，得到公　式（３）　Ｐａｒｔ－ｇ一１：ＴＩ＝Ｒｏｔ（Ｚ，０１）　Ｐａｒｔ－ｇ一２：Ｔｚ＝Ｔ。：　Ｒｏｔ（Ｖ，　）　Ｔ　Ｐａｒｔ—ｇ一３：Ｔ３＝Ｔ２　ＴＲｏｔ（Ｙ，　）　Ｔ　Ｐａｒｔ．ｇ一４：Ｌ＝Ｉ＂３　Ｒｏｔ（Ｙ，　）　（３）　Ｐａｒｔ—ｇ．５：Ｔ　＝Ｔ　ＯＴＲｏｔ（Ｙ，　）　Ｔ　Ｐａｒｔ．ｇ一６：Ｔ６：Ｔ５：　Ｒｏｔ（Ｙ，　ｌ６）３　式中：　卜坐标系Ｂ在坐标系Ａ中的表示。　部分丝杆及螺母变换矩阵　Ｐａｒｔ—ｓ－１：Ｔ　＝Ｔｌ；ＴＲｏｔ（Ｖ，　）　Ｐａｔｒ－ｍ一１：１ｌｍｌ＝Ｔ２：　Ｒｏｔ（Ｙ，　Ｉ）：Ｔ　式中：∞＝ｆ（　），崩＝ｇ（　），ｆ（ｘ），ｇ（ｘ）均为关于ｘ的非线性函数。　１．３虚拟场景的显示与人机交互的实现　虚拟场景的显示与人机交互主要利用专业的具有图形显　示功能仿真软件ＯｐｅｎＩｎｖｅｎｔｏｒ来实现。使用专业的仿真工具　可以缩短研发的时间，提高效率，能够得到准确、逼真的仿真　画面　ＯｐｅｎＩｎｖｅｎｔｏｒ具有很强的图形显示能力，并且是平台无　关的，可以方便的移植到不同操作系统的硬件平台上。本文　结合机器人的几何建模和运动学建模，以ＶＲＭＬ作为模型数　据载体，以ＯｐｅｎＩｎｖｅｎｔｏｒ作为仿真平台，对虚拟机器人模型构　建的场景图主要如图３所示。　在场景图中以树的形式组织各类节点，其中最上层的为　根节点，负责输出场景以及作为遍历的起点。根节点以下主　要为两类节点，分别是模型节点和变换节点。模型节点作为　存储模型部件数据的载体，使用ｓｏｌｉｄｗｏｒｋｓ装配好并导出的各　陈伟，陈一民，汪地，等：机器人虚拟仿真及控制技术研究　２０１０，３　ｌ（２０）４４５７　图３虚拟机器人主要场景　模型数据分别存储在各模型节点中。变换节点存储对相应模　面。如果两多面体上最近的特征对与两曲面上最近的点集一　型部件进行操作的变换矩阵，在虚拟场景的初始化显示中这　致，点集所在曲面的法线具有共线的特性，可以用变量表示，　里存储的是使用运动学建模得到的各个模型文件的变换矩阵。　其中Ｆ　，Ｆ　，Ｇ　，Ｇｖ为对应的偏导数，如式（４）所示　按照从上至下，从坐至右的原则对树状图进行遍历，读取变换　Ｆ－－　，ｔ，Ｕ，ｖ，　－）＝（Ｆ（ｓ，ｔ）－Ｇ（ｕ，ｖ））　］　节点和模型节点，并通过向Ｏｐｅｎ　Ｉｎｖｅｎｔｏｒ场景图中添加响应　Ｆ。２　，ｔ，“，ｖ，。ｃ１）：Ⅱ。（Ｇ　（　，ｖ）ｘＧ　（“，ｖ））【　事件实时更新场景图各节点的变换矩阵实现对虚拟机器人的　Ｆ２　（　，ｔ，“，ｖ，嘞）：（　，ｔ）￣Ｆｔ（ｓ，ｆ））　Ｉ　（４）　显示与控制。以图３中ｐａｒｔ—ｇ．２、ｐａｒｔ—ｍ．１、ｐａｒｔ．ｍ一２为例，这３个　ｚ　，ｔ，“，ｖ，６ｃｚ）＝　２（Ｇ　（　，ｖ）×Ｇ　（“，ｖ））　Ｊ　模型属于机器人的某一个部件，具有相同的运动特性，又由于　可得最近的点满足等式（５），解为具有４个未知数的等式，　他们具有相对运动，因而在组织场景图结构时需要为其分配　其中·为点积。　统一的父节点和变换节点，还需要为ｐａｒｔ—ｍ一１和ｐａｒｔ－ｍ．２分别　，ｔ，　，ｖ）＝（　，，）一Ｇ（ｕ，　）·　（“，ｖ）＝０　１　分配一个变换节点。　（　，ｔ，“，ｖ）＝Ｃ　，ｆ）一Ｇ（　，ｖ））·　（“，ｖ）＝０　ｌ　（５）　２仿真系统中的碰撞检测　ｎ３（ｓ，ｔ，Ｕ，　＝（只　，ｆ）一Ｇ　，ｖ））‘　，ｔ）：０　Ｉ　１－１，　，ｔ，　，　＝（　，ｆ）一Ｇ（　，ｖ））·　，ｆ）＝０　Ｊ　ＡＡＢＢ有一个最显著的特点便是ＡＡＢＢ间的相交测试非　代数曲面最近特征对使用公式（６）求解，其中，假设两代数　常的简单快速，符合机器人仿真系统中对碰撞检测的实时性　曲面分别为：　＝０，　∥　＝Ｏ。　要求，但是ＡＡＢＢ包围盒的紧密性较差，可能会导致大量冗余　ｆ（ｘ．　，＇ｚ。）：０　的包围相交测试，并且ＡＡＢＢ包围盒的碰撞检测算法的精度　ｇ　ｚ　，ｚ２）：０　不高，所以单独的ＡＡＢＢ算法不能满足机器人仿真系统的要　求。ＳｗＩＦＴ＋＋算法是Ｅｈｍａｎｎ等通过使用凸包包围盒对以Ｌｉｎ．　Ｃａｎｎｙ…　算法为基础的ＳＷＩＦＴ算法进行扩展而提出的，ＳＷＩＦＴ　具有高鲁棒性、精度高等特点，另一方面ｓｗＩＦＴ＋＋解决了　ＳＷＩＦＴ不能处理非凸体的问题。因此本文按照两物体是否运　＝啦　动、是否同一底座这一分类策略将不同的虚拟物体进行分类　］　以选择合适的碰撞算法，充分发挥两类算法的优点，解决仿真　在得到最近特征对后将多面体相交情况分为切线相交及　系统对碰撞检测的实时性和准确性的要求，并且在预处理阶　边界相交，对于参数曲面的切线相交的情况由方程（７）有无根　段对物体进行表面凸分解使算法具有对非凸物体处理的能力。　来确定。　２．１算法分析　Ｆ（ｓ，力＝６（ｕ，　１　ｓＷＩＦＴ＋＋采用Ｌｉｎ—Ｃａｎｎｙ算法的计算最近特征对的方法　（　，ｆ）×　，ｆ））·　（“，ｖ）＝０｝　（７）　检测曲面物体的碰撞，其中假设：Ｆ（ｕ，ｖ）＝　，ｆ），ｒ（ｓ，，），Ｚ（ｓ，ｆ），　，ｆ）×　，ｆ））·　（“，ｖ）＝０，　Ｗ（ｓ，力）和Ｇ（ｕ，ｖ）：（　“，ｖ），ｙ（“，　，２（ｕ，ｖ），　“，ｖ））表示两个参数曲　代数曲面的切线相交　４４５８　２０１０，３１（２０）　计算机工程与设计Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ｄｅｓｉｇｎ　２．３相交测试　２－３．１　测试预处理　相关的分类原则是两物体是否运动、两物体是否同一底　座。按照这一原则进行分类是因为我们在对机器人的仿真系　统进行碰撞检测实验时发现两个具有同一底座且运动的物体　对于边界相交，假设做为相交参考的曲面为贝齐尔曲面，　之间的碰撞比较频繁，对精度的要求也比较高，这一类的碰撞　定义　，ｔ）Ｅ［ｏ，１］ｘ［ｏ，１】，则只需要计算下面的方程（９）。　Ｆ（ｓ，ｆ）＝Ｇ（ｕ，ｖ）　其它可能的边界相交可用类似的方法解决。　（９）　检测可以选用ＳｗＩＦＴ＋＋算法；两个具有不同底座且运动或者　是一个运动一个固定的物体之间经常处于没有碰到的状态，　对这一类问题选用＿ＡＡＢＢ和ｓｗＩＦＴ＋＋相结合的方法可以提高　碰撞检测的速度并兼顾检测的精度。　２．３．２测试步骤　２．２算法实现　算法实现分为算法预处理和相交检测两部分。算法预处　理阶段进行的工作如下：　（１）对仿真系统中的虚拟物体以及机器人各个部件进行表　对二叉树的遍历我们采用广度优先的策略，详细的步骤　如下：①从两物体二叉树的根节点开始遍历，将根节点设为当　前节点。②以ＡＡＢＢ算法判定两当前节点对应的凸块的ＡＡＢＢ　面凸分解，并对得到的凸片集合中的每个凸片构建凸块；　（２）对凸块集合构建层次二叉树；　（３）对每个凸块构建ＡＡＢＢ包围盒。　２．２．１表面凸分解　基于表面的凸分解实际上是把非凸物体的表面分解成一　个个的凸面片的集合，如用ｓ表示物体的表面，Ｓｉ表示凸面片，　则基于表面的凸分解可用公式０ｏ）表示　＝包围盒是否相交，如果不相交就递归返回直到为根节点，则递　归结束。如果相交就调用ＳｗＩＦＴ＋＋算法作进一步的判定，若　不相交则递归返回直到根节点，若相交则返回检测结果。　ＡＡＢＢ碰撞检测需要取得ＡＡＢＢ包围盒的Ｘ、Ｙ、ｚ的最大值和　最小值，在进行检测时需要分别比较这６个值，并对比较结果　进行分类，只有在３个坐标轴上均符合图４情况的才认为　ＡＡＢＢ相交。　ＵＳ，，Ｓｉｎ母＝　Ｊ　（１０）　式中：ｆ　。　我们采用了Ｅｈｍａｎｎ“　提出的一种针对用多面体表示物体　的凸表面分解的方法。这种方法要求分解后的结果要满足一　定的约束条件，可用公式（１１）表示　Ｓｆ＇Ｖ（ｓ３＝盛　式中：／　，卜　的凸块。　（１１）　Ａｒａｉｎ　Ｂ　ａｉｎ　ｒＡ　ｍａｘ　Ｂｍａｘ　ｒ　Ａｍｉｎ　Ｂｒａｉｎ　Ｂｒａｉｎ　Ｂ　ｍｉｎ　Ａ　ａｉｎ　ｒＡｍｉｎ　Ｂｍａｘ　Ｂｍａｘ　Ａｍａｘ　Ａｍａｘ　Ａｍａｘ　Ｂｍａｘ　图４　ＡＡＢＢ相交判定　该算法的分解步骤如下：　３实验结果　实验是在ＣＰＵ２．５３ＧＨｚ，２ＧＢ内存ＰＣ机上进行的。测试　的场景是一个六自由度小型工业机器人的虚拟仿真及控制。　（１）在待分解面中选择一多边形面片作为种子面构成当前　连通凸面片；　（２）以种子面为起点，通过深度优先或广度优先算法递归　搜索物体待分解面的对偶图，重复直到待分解面中的每一个　多边形都进行了处理；　在测试碰撞检测时，为增加场景的复杂度，本文在场景中再添　加了一个可操作的５自由度虚拟机器人，并且与单独使用　ｓｗＩＦＴ＋＋算法时作了比较，如图５所示。　（３）对所有的凸片求凸包得到与其相应的凸块。　２．２＿２构建层次二叉树和ＡＡＢＢ包围盒　表面凸分解是将产生的无序凸块组织成二叉树的形式而　在空间排列上有序。有自顶向下和自底向上两种方法。两方　法最根本的区别是看把一个集合划分成若干个不相交的子集　还是把若干个集合归并为一个父集。相对而言，自顶向下的　方法在碰撞检测中使用得较多，技术更成熟一些，也比自底向　上的方法更为健壮更易实现，故本文采用这一方法构造层次　二叉树。具体步骤如下：　（１）对得到的所有凸块集合求其凸包，创建根节点；　（２）将凸块集合划分为不相交的两组子集，并求其凸包，分　别创建节点；　图５小型工业机器人仿真场景　在对模型进行预处理阶段，部分模型生成的包围盒如图６　所示。本文对碰撞检测采用对一定面片数的平均碰撞检测时　间来测量检测的效果，采用多次测试取平均值的办法对相同的　面片数测量１０次，去掉最大值最小值，再取平均值作为该面片　（３）将新得到的两个节点做为根节点的子节点；　（４）类似地分别对两个子节点中的凸块集合进行划分，求　数的碰撞检测时间。随着面片数的增加，本文算法和单独使用　ＳｗＩＦＴ＿Ｈ算法的平均碰撞检测时间的变化如图７所示。　（下转第４４９６页）　凸包，构建更低一级的子节点；　（５）重复第４步，直到节点中的凸块集合只剩一个凸块为止。　４４９６　２０１０，３１（２０）　计算机工程与设计Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ｄｅｓｉｇｎ　（上接第４４５８页）　与单独使用ＳＷＩＦＴ＋＋算法的系统比较，本系统所需平均碰撞　检测时间更少。此仿真系统同样适用于服务型机器人。　参考文献　［１】　宋增来，陈振华．Ｎ自由度机器人仿真的实现［Ｊ］计算机工程与　图６一个模型部件的包围盒　设计，２００６，２７（２４）：４８１３．４８１６．　［２】　张立勋，张今瑜，王志超．基于Ｍａｔｌａｂ的下肢康复机器人虚拟现　实仿真研究［Ｊ］．机电工程，２００８，２５（３）：７．９．　［３】　张晨旭．基于ＯｐｅｎＧＬ的机器人仿真技术研究［Ｊ］．机械管理开　嚣２０　发，２００９，２４（３）：１７０　１７１．　［４】　唐安慧，张尚弘．三维虚拟仿真研究框架［Ｊ】．信息技术，２００８，３２　ｏ　（１２）：７７．８１．　２００Ｕ　４０００　６０００　８０００　ｉ００００　面片数　［５】　赵小川，罗庆生，韩宝玲．基于Ｗｅｂｏｔｓ仿真软件的仿生六足机　——本文算法　～单独ｓｗＩＦＴ＋＋算法　器人机构设计与步态规划［Ｊ］．系统仿真学报，２００９，２１（１１）：　３２４１—３２４５，３２６７．　图７平均碰撞检测时间的变化情况　［６】　Ｅｓｍａｅｉｌ　Ａａｔａｓｈｐａｚ－Ｇａｒｇａｒｉ，Ｂａｂａｋ　Ｎ　Ａｒａａｂｉ，Ｃａｒｏ　Ｌｕｃａｓ．Ｏｐｔｉ—　在通用性实验中，本文成功的将这套仿真系统应用于服　ｅｒａｌ　ｆｕｚｚｙ　ｐａｓｓｉｎｇ　ｓｔｒａｔｅｇｙ　ｆｏｒ　ｒｏｂｏｔ　ｓｏｃｃｅｒ　ｐｌａｙｅｒｓ［Ｃ］．ＩＥＥＥ　Ｉｎ—　务型机器人的仿真，实验显示系统运行良好，仿真、碰撞检测　ｔｅｍａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｆｕｚｚｙ　Ｓｙｓｔｅｍｓ，２００８：１５７６·１５８１．　块均正常工作。证明本文所述仿真系统具有一定的通用性。　［７】　朱元峰，孟军，谢光华，马文娟．基于复合层次包围盒的实时碰撞　服务型机器人的运行界面如图８所示。　检测研究［Ｊ】．系统仿真学报，２００８，２０（２）：３７２—３７７．　［８］　唐勇，冯立颖，吕梦雅．基于轴向包围盒碰撞检测算法的改进【Ｊ］．　系统仿真学报，２００９，２１（１）：１５７．１６０．　【９】　Ｋｏｎｓｔａｎｔｉｎｏｓ　Ｍｏｕｓｔａｋａｓ，Ｄｉｍｉｔｒｉｏｓ　Ｔｚｏｖａｒａｓ，Ｍｉｃｈａｅｌ　Ｇｅｒａｓｓｉ—　ｍｏｓ　Ｓｔｒｉｎｔｚｉｓ．ＳＱ—Ｍａｐ：Ｅｆｉｆｃｉｅｎｔ　ｌａｙｅｒｅｄ　ｃｏｌｌｉｓｉｏｎ　ｄｅｔｅｃｔｉｏｎ　ａｎｄ　ｈａｐｔｉｃ　ｒｅｎｄｅｒｉｎｇ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｖｉｓｕａｌｉｚａｔｉｏｎ　ａｎｄ　Ｃｏｍｐｕｔｅｒ　Ｇｒａｐｈｉｃｓ，２００７，１３（１）：８０—９３．　［１０】ＭｉＩＩ　Ｔａｎｇ，Ｓｅａｎ　Ｃｕｒｔｉｓ，Ｓｕｎｇ—Ｅｕｉ　Ｙｏｏｎ，ｅｔ　ａ１．ＩＣＣＤ：Ｉｎｔｅｒａｃｔｉｖｅ　ｃｏｎｔｉｎｕｏｕｓ　ｃｏｌｌｉｓｉｏｎ　ｄｅｔｅｃｔｉｏｎ　ｂｅｔｗｅｅｎ　ｄｅｆｏｒｍａｂｌｅ　ｍｏｄｅｌｓ　ｕｓｉｎｇ　图８服务型机器人仿真场景　ｃｏｎｎｅｃｉｔｖｉｔｙ－ｂａｓｅｄ　ｃｕｌｌｉｎ［Ｊ］．ＩＥＥＥ　Ｔｒｎａｓａｃｔｉｏｎｓ　ｏｎ　Ｖｉｓｕａｌｉｚａｔｉｏｎ　ａｎｄ　Ｃｏｍｐｕｔｅｒ　Ｇｒａｐｈｉｃｓ，２００９，１　５（４）：５４４—５５７．　４结束语　【１　１】Ｓｕｄ　Ａ，Ｇｏｖｉｎｄａｒａｊｕ　Ｎ，Ｇａｙｌｅ　Ｒ，ｅｔ　ａ１．Ｉｎｔｅｒａｃｔｉｖｅ　３Ｄ　ｄｉｓｔａｎｃｅ　ｉｆｅｌｄ　本文提出了采用Ｓｏｌｉｄｗｏｒｋｓ进行几何建模，Ｏｐｅｎ　Ｉｎｖｅｎｔｏｒ　ｃｏｍｐｕｔａｔｉｏｎ　ｕｓｉｎｇ　ｌｉｎｅａｒ　ｆａｃｔｏｒｉｚａｔｉｏｎ【Ｃ】．Ｐｒｏｃ　ＡＣＭ　Ｓｙｍｐｏ·　进行虚拟显示与交互，对虚拟物体采用分类策略成功地将　ｓｉｕｍ　ｏｎ　Ｉｎｔｅｒａｃｔｉｖｅ３Ｄ　Ｇｒａｐｈｉｃｓ　ａｎｄ　Ｇａｍｅｓ，２００６：１１７—１２４．　ＡＡＢＢ与ｓｗＩＦＴ＋＋算法相结合，设计了一套拥有结合ＡＡＢＢ　【１２］Ｔｅｓｃｈｎｅｒ　Ｍ，Ｋｉｍｍｅｒｌｅ　Ｓ，Ｈｅｉｄｅｌｂｅｒｇｅｒ　Ｂ，ｅｔ　ａ１．Ｃｏｌｌｉｓｉｏｎ　ｄｅｔｅｃ－　与ＳＷＩＦＴ＋＋的复合碰撞检测方法的虚拟机器人仿真系统，通　ｔｉｏｎ　ｆｏｒ　ｄｅｆｏｒｍａｂｌｅ　ｏｂｊｅｃｔｓ［Ｊ］．Ｃｏｍｐｕｔｅｒ　Ｇｒａｐｈｉｃｓ　Ｆｏｒｕｍ，　过实验验证了机器人几何建模、运动学建模的正确性。另外，　２００５．１９（１）：６１－８１．