《机器鱼2D仿真平台碰撞检测算法.doc》由会员分享，可在线阅读，更多相关《机器鱼2D仿真平台碰撞检测算法.doc（4页珍藏版）》请在三一文库上搜索。
1、2011-12A工0劭化30(12)Ordnance Industry Automation 87 71994-2014 China Academic Journal Electronic Publishing House. All rights reserved, 2011-12A工0劭化71994-2014 China Academic Journal Electronic Publishing House. All rights reserved, 2011-12A工0劭化doi: 10.3969/j.issn.l006.1576 2011.12.023机器鱼2D仿真平台碰撞检测算法任静
2、,谢广明(北京大学工学院,北京100871)摘要：为了实现机器鱼2D仿真平台各个对象间完整的碰技檢测，提出一种基于离做碰技檢测的算法.该算法 以机器鱼2D仿丑平台为基础，结合包围盒树，运用计算机图形羊对平台中各个仿虑对象进行精确建模；并利用图 形学中的分誘轴理论、bronoi Region 念，提出了适合各对象的不同碰技检测算法，快速准确地输出检测结果. 同时采用运动插值技术.减小步长并虢入中间运动模态，实现了模拟连续碰揑检测，进一步提高了碰推检测准确度. 实验结果证明：该方法实现了摸拟连续碰技检测，具有高效、牯淮的特点.关键词：仿真平台；机器鱼；碰技检测；包围盒；分离轴中图分类号：TP306
3、 文献标志码：ACollision Detection on Robot Fish 2D Simulation PlatfonnRen Jing, Xie Guaugming(College of Engineering, Peking University, Beijing 100871. China)Abstract: In order to achieve the all objects collision detection of robot fish 2D simulation platform completed, we propose a collision detection
4、algorithm based on discrete The algorithm taking 2D simulation platform as base, combined with bounding box tree, use computer graphics put up accurately models to every simulation object; and put forwards different collision detection algorithms adapt to objects use separation axis theory, X'or
5、onoi Region concepts in graphics, the output test results quickly and accurately. At the same time using motion interpolation, reducing the step size and type intermediate movement mode to achieve simulation continuous collision detection. ftirther improved collision detection accuracy. Experimental
6、 results show that the method can achieved simulating continuous collision detection, lias high efficiency, precise features.Keywords: simulation platform; robotic fish, collision detection; bounding-volume; separating axis71994-2014 China Academic Journal Electronic Publishing House. All rights res
7、erved, 2011-12A工0劭化收稿 II 期：2011-08-15：修冋日期：2011-09-23V僉项目.国家自備墓金项11 (10972003)：机人损术与系统国家武点实宣开放旅金項目(SKLRS-2009-MST9) 作者简介：仟»(1987).女.山？人.硕L研究生.从事解能控制研究.o引言近年来，随着计算机技术和机器人技术的快速 发展，机器人仿真系统应运而生。仿真系统中最基 础和核心的内容是对彖Z间的碰撞处理，包括碰撷 检测和碰撞响应,前者和計算机技术密切相关,而 后者则主要涉及力学和动力学相关领域。目前对二维场景中的碰撞检测研究非常广泛, 从时间域的角度划分，可分
8、为连续碰撞检测、离散 碰掃检测和静态碰撷检测等；从空间域的角度划分, 可分为计算机图形学法、有限元分割法寧机器 鱼2D仿真平台中对象趋于多元化,且对F机器鱼 这种篡关节驱动的运动模式來说，只依赖某一种碰 掃检测方法无法满足场景模拟隔求。因此，笔昔结 合计算机图形学等理论，提出机器伯2D仿真平台 各个对彖间完整的碰撞检测算法。1机器鱼2D仿真平台简介机器鱼2D 仿真平台 URWPGSim2D(underwater robot water polo game simulation 2D edition)是基 J'- MRDS 的 CCR 和 DSS,采用 C/S 模 式建立起来的，模拟并仿
9、真实体机器伯及水环境， 包括环境信息、驱动形式、运动模态、数据流传输 形式和外形、游动效果等。平台仿真周期为100ms,在每个仿真周期中， 客户端加载用户策略，通过服务器端的公共接II, 传入数据信息，并进行动力学分析、碰撞处理和实 时绘图等。碰撞处理流程如图1。动力学计算结杲a 建模 4型扯检测4更新模型位姿* 亚扯响应卜*绘制对象图1碰撞处理流程2水环境下的对象建模2.1坏境对象如图2,在机器鱼2D仿真平台中,对象包括仿 71994-2014 China Academic Journal Electronic Publishing House. All rights reserved, 第
10、12期任静，等：机器他2D仿真平台碰撞检测算法89真机器他、仿真水球、障碍物、池唯区域等。按照 环境对象的状态属性，分为动态(dynamics)和静态 (statics)2类。静态类包括障碍物、池壁边界;动态 类包括仿其机器鱼、仿真水球。按照环境对彖的形 状，可分为直线(line).圆形(circle).多边形 (polygon)等。结合以上的2种分类，定义各个环境 对彖,方形障碍物(reo)、圆形障碍物(roo)、仿真 水球(ball)、仿真机器鱼(fish),都属于对彖集合 (obj) , Obj=objb obj2, obj3,obj” ( W 1,2,3,，十8)；另外，池壁边界 Bo
11、rder= topline, bottoniline, leftline, rightline, goalblockb goalblock2, goalblock3, goalblock4.每个环境对彖都分属-静 态或动态、直线或関形或筋边形，不同对彖的碰撞 检测方法会自所不同。图2 URWPGSim2D平台环境场景现冇的2D建模方式上耍冇图形学法和冇限元 分割法等。针对水中机器角2D仿真平台实时性要 求较高的特点，综合考虑T-台的运算速度和效率, 笔者主要采用图形学中的包围盒进行建模。常用的 包围盒类型如图3,丄耍有Sphere (包围球)、AABB、 OBB. K-DOP等。平台中恻形对像
12、物体的形状以及 位置均尚定，所以采用报基本的包由球建模。为了 捉丄'. II圜形J象选择包川球或AABB模 型,为了减少计算机的运算处理量和运算复杂度, 同时保证碰掩检测的精度和效率，采用外层模糊， 内层粘确的两层建模模式。各对象模型(仿眞机器他 除外)属性详见表loBETTER BOUND. BETTER CULLINGFASTER TEST. LESS MEMORYSPHltKt AABB OBB 8-DOP CONVEX HULL图3包围盒的类型表1各对象模型属性(不包括仿真机器鱼)对象名称状态属性外层模型内层權型仿翼水球包K)球曲形阵碍畅肾态包国球方彫障碍物背态AABB球门块包
13、围球AABB2.2伯体建模早在1996年Gottschalk就提出了 OBB树在快 速碰撞检测中的应用，在此某础上，纽约州&人学 的Klosowski等人提出了某于K-DOPs的层次包围 盒,提高了包围紧密度.在包阳盒的所仃模型屮， 最省时而且消耗资源最少的模熨是包用球，但其包 鬧紧密性较差。机器鱼是由刚性骡体、2个胸鳍、三关节尾部 和尾鳍组成。仿其机器鱼宙3个关节拟合鱼体波运 动推进，属r多关节连接连续运动的刚体，机器鱼 实体图和仿真图如图4。如果采用单一的包I科盒建 模方式,有可能出现凹多边形的情形,其碰撞检测 IE常复杂。笔者根据仿貞机器鱼多关节的特点，结 介包用球的高效快速优点
14、和k-d树良好的包用紧密 性,采用BV树(bounding volume tree)对多关节的 仿真机器佝建模。既满足了冥务关卩的灵活性，又 优化了仿真平台的运算速度。图4实体机器鱼和仿真机器鱼对比图如图5和图6所示，建立深度为3的无序BV 树。树的叶结点采用K-DOP建模，根结点以及子 结点均采用包閑球模申，在BV树的每个结点处计 算是否发生碰抑，如果发生碰撞，返回true,并继 续更深层的检测。遍历B，树的所仃结点，吃到返 回值为false或所冇结点检测完成后结束。图6仿真机器鱼建模示意图3拟连续碰撞的设计按照时间流的角度来划分碰撞检测，主耍分为 连续碰撞检测(CCD)利离散碰撞检测。对F
15、人龜快 速运动的小型对彖而言，CCD方法以其准确度高、 检测周期短等优点，可以很好地解决碰撞检测中的 难点，但是这种方法运算耗时过长、占用过多资源, 不能很好地适应实时性要求较高的系统，这也是 CCD方法没有得到广泛运用的原因Z。笔者采用离散碰撷检测方法，并利用运动插值 技术，在毎个仿真周期的间隔内插入中间运动模态, 达到模拟连续碰撞检测的效果。机器鱼的状态包括 鱼体中心的位置坐标和身体朝向,由J每个周期机 器龟的尼部都会根据不同的指令呈现不同的状态， 故很难预测伯的姿态，所以这里插值均是以肖前周 期相同模态为基准,进行状态回退,实现同模态下 的模拟连续碰撞检测。4碰撞检测算法4.1检测算法在
16、冇限的水池环境里，n先盂耍考虑如何检测 一个对象是否在此区域中。笔者提出一种简单高效 的算法，即在内存中开辟一个列表空间，用來存储 碰撞模型中的极值坐标,检测所有极值坐标是否均 在水池边界中。在被检测对象都位r水池边界范閑内时，进一 步考虑如何检测多边形之间是否发生碰撞。仿真平 台中对彖建模主耍涉及到K-DOP, AABB和包国球 等，都属于机图形学中的基本模塑.分离轴是 将碰撞问题转换为图形学的关键。如图7,所谓分 离轴理论，即在一个二维平面中，如果2个凸多边 形不相交，则定至少存在一条直线使紂这2个凸 多边形分别位J 这条立线的两侧.则称这条立线为 分离轴。由上述理论可知，寻找被检测物体间
17、是否 存在分离轴是碰撞检测的关键。separating axispolygon为多边，彫;separating axis为分离仙图7分离轴理论结合voronoi region理论和投影法等儿何算法， 给出包田盒模型碰撞检测算法如卜：1) 检测包I时球是否在多边形的voron-oi region 内，如果在此区域中，则跳出算法循坏，并检测 2个对彖的屮心距离；2) 设多边形的边集介N= q,处J" ，从寻找各 边元索的正交向W：M -w,=0.示意图可参照图8：3) 把多边形投影到各个正交向量上，得出各个 多边形的投影线段；4) 如果所有多边形投影线段都相交，则2个多 边形相交；反Z,
18、如果存在一种情况，使得2个多 边形投影线段没仃交集，则存在一条分离轴，根据 分离轴理论，2个多边形在二维平面上不相交，即2 个对彖没有发生碰撞。图8多边形各边正交向呈示意图4.2输出参数碰撞检测的输出参数存储在一个结构体中： public stnict CollisioiiDetectionResultpublic bool Intersect;public xna A>ctor3MinimumTranslationwector;public xnaA>ctor3 NonnalAxis;public xna Arector3 ActionPoint;由在上述碰撞检测算法中，是否发生
19、碰撞的 检测结果滞后于真实情况,输出参数中的最小相交 向 H (minimum translation vector)显示出碰柿发牛 的深度，如图9(a)；法线向(normal axis)在碰撞 响应的处理过程中耳E常重要,它是最小相交向量发生的情况卜的正交向帚，可由法线向帚和与之垂直 的切线向©确定对彖的本地坐标系；在法线向帚:上, 沿着两被检测対彖运动的相反方向移动最小相交向 M.长度，可得碰撞作用点(action point),如图9(b)。上述碰掩检测算法时间复杂度为0(”)，效率较 高,占用资源柑対较少.当作用对象较多时,如4 条机器鱼、9个水球、4个障们物以及各个边界，同
20、 时进行碰撞检测时，检测所用时间非常少，与2个 对象碰撞检测所占用的时间儿乎相同，并不影响f 台的整体运行。tangent axis 为切 圾向篁；normal axis 为法 向 宣：minimum translation vector为曲小柑交向量;action point为戏技作用点 (a)碰技栓测前(b)戍技检测后图9碰撞检测前后被检测对象状态(上接第86页)参考文献：1 岳富占，崔平远.基于改进蚁群算法的星球探测机器人 路径规划技术J.控制与决乾，2006. 21(12): 1437-1440.2 王鹏飞，田冲.用于多机器人路径规划的一种改进蚁群 算法J电脑知识与技术.200&
21、; 4(2): 54-55.3 壮治君，陈妳姆.李波波.机器鱼速度竝制算法研究J.学术探讨，知网空间.2009,(8):http:/www.CQki com cn/Article/CJFDTotal-SYWX20090 8257.htm.4 柴仲明，禹梅.刘舒.基千遗传算法的机器鱼路径规划 J.兵工自动化,2010, 29(11): 92-96.5 吴启迪，汪结.智能蚁群算法及应用M.上海：上海5结束语通过上述的建模方式以及各个对象Z间的碰撞 检测方法，可以很好地适应平台的实时性耍求。并 且在多物体碰撞(超过20个检测对彖)的情况卜，该 算法也可以较为快速精准地完成碰撞检测.参考文献：1 苑吆
22、炜.实时戌挂检测技术研究D.浙江：浙江大学, 2003.2 Enson C. Real-Time Collision DetectionM. USA: Morgan Kaufmann. 20053 S.Gottschalk, M.C.Lm. D Manocha. OBBTree: AHierarchical Stnicture for Rapid Interference Detection Proceedings of ACM international Conference on Computer Graphics and Interac-tive Techniques, 1996: 17
23、1-180.3 Klosowski J T, Held M, Mitchell J S B, et al. Efficient Collision Detection Using Bounding bl-ume Hierarchies of k-DOPsJ. IEEE Transactions on Hrisualization and Computer Graphics, 1998, H4(l): 21-36.4 黄通浪，唐敏，董金祥.H种快速枸确的连续碰技检 测算法HJ.浙江大学学报：工学版.2006. 40(6): 1051-1055.5 Lin M C, Canny J F. A Fa
24、st Algorithm for Incremental Distance Calculation(C. Proceedings of IEEE International Conference on Robotics and Automation, 1991:1008-1014.科技教育出版社,2004: 3-129.6 Dongo. Mamezzo. Colonu AntSystem:optimization by a colony of coorperating agents卩.IEEE Tran saction son SMC, 1996. 26(1): 8-14.7 辜吟吟.基于蚁群
25、算法的移动机器人路径规划方法的 研究D.沈阳：沈阳理工大学,2007.8 Auzinger D. Djumlija G Application of advanced aeclinology packages for improved strip proftie and flatness in hot-strip-imll$J. Iron and steel. 2004. 39(11): 132-133.9 吴丽娟.基千机器人足球比赛的进攻策略的实现J微 计算机应用,2002, 23(6): 351-353.10 中国水中机器人大赛官方网站.URWPGSim2D开发人 员手册Z.北京：北京大学智能控制实验宅，2010. h:tp:/robot pku edu. cn.71994-2014 China Academic Journal Electronic Publishing House. All rights reserved,