基于云计算Map-Reduce模型的快速碰撞检测算法

发布时间：2020-05-07 23:56

【摘要】：针对人机交互系统中碰撞检测实时性、精确性的要求,本文提出了一种基于云计算模型的快速碰撞检测算法。1提出一种新的分裂平面构建OBB平衡包围盒树方法;2引入了标记遍历树概念,对进行碰撞检测的OBB任务树采用堆栈进行深度或广度遍历标记,减少相交检测次数;3采用Map-Reduce云模型对任务树进行划分,划分后子任务采用云模型并行执行,减少了检测时间;4对每个子任务结果进行标识,将标识后的子任务作逻辑运算,通过运算结果判断是否发生了碰撞。对比实验结果表明:与经典的I-COLLIDE、MPI及Pipelining等算法相比,该算法在效率、精确性方面具有明显优势,能够满足复杂虚拟空间人机交互的实时性和精确性的要求。
【图文】：

是云计算的关键技术，工作的基本原理源于程序的函数式，它把要解决的复杂问题分解、简化，即“Ｍａｐ（映射）”和“Ｒｅｄｕｃｅ（化简）”来完成。Ｍａｐ建立了函数与成员的关系，运算结果保存在集合中。而Ｒｅｄｕｃｅ是把Ｍａｐ中处理的结果，通过多线程或多进程并行执行的结果进行分类和归约。无论Ｍａｐ（）和Ｒｅｄｕｃｅ（）是否在同一系统，两者均可以并行执行。将Ｍａｐ－Ｒｅｄｕｃｅ运行在集群上时，可以达到真正的并行，实现任务调度、结点通信等功能。如图１所示。图１Ｍａｐ－Ｒｅｄｕｃｅ执行过程Ｆｉｇ．１ＴｈｅＭａｐ－Ｒｅｄｕｃｅｅｘｅｃｕｔｉｏｎｐｒｏｃｅｓｓ由图１可以看出，Ｍａｐ－Ｒｅｄｕｃｅ工作流程是：从文件块中读取文件，Ｍａｐ将读取的文件分割、执行，将执行结果写入文件，Ｒｅｄｕｃｅ将文件执行结果划分规约，输出文件结果。其中，文件写入是在本地完成的，这主要是为了减少网络传输的压力，同时也减少网络读写文件的时间。另外，Ｍａｐ－Ｒｅｄｕｃｅ还能使大型集群系统在海量数据集上并行执行。如图２所示，，在运行系统的主程序时，系统协调Ｍａｐ－Ｒｅｄｕｃｅ，然后从每个ｒｅｄｕｃｅ操作中收集结果。２．３构建基于ＯＢＢ的平衡包围盒树包围盒间相交测试的精度和速度会直接影响到碰撞检测的精度和速度。由于ＯＢＢ包围盒间图２主系统上的程序运行过程Ｆｉｇ．２Ｔｈｅｍａｉｎｐｒｏｇｒａｍｒｕｎｎｉｎｇｏｎｔｈｅｓｙｓｔｅｍ的相交测试是所有包围盒类型中最精确的相交测试，所以本文采用的检测包围盒选择了ＯＢＢ包围盒，虽然在整体速度上较ＡＡＢＢ包围盒稍慢了一点，但却换

通信等功能。如图１所示。图１Ｍａｐ－Ｒｅｄｕｃｅ执行过程Ｆｉｇ．１ＴｈｅＭａｐ－Ｒｅｄｕｃｅｅｘｅｃｕｔｉｏｎｐｒｏｃｅｓｓ由图１可以看出，Ｍａｐ－Ｒｅｄｕｃｅ工作流程是：从文件块中读取文件，Ｍａｐ将读取的文件分割、执行，将执行结果写入文件，Ｒｅｄｕｃｅ将文件执行结果划分规约，输出文件结果。其中，文件写入是在本地完成的，这主要是为了减少网络传输的压力，同时也减少网络读写文件的时间。另外，Ｍａｐ－Ｒｅｄｕｃｅ还能使大型集群系统在海量数据集上并行执行。如图２所示，在运行系统的主程序时，系统协调Ｍａｐ－Ｒｅｄｕｃｅ，然后从每个ｒｅｄｕｃｅ操作中收集结果。２．３构建基于ＯＢＢ的平衡包围盒树包围盒间相交测试的精度和速度会直接影响到碰撞检测的精度和速度。由于ＯＢＢ包围盒间图２主系统上的程序运行过程Ｆｉｇ．２Ｔｈｅｍａｉｎｐｒｏｇｒａｍｒｕｎｎｉｎｇｏｎｔｈｅｓｙｓｔｅｍ的相交测试是所有包围盒类型中最精确的相交测试，所以本文采用的检测包围盒选择了ＯＢＢ包围盒，虽然在整体速度上较ＡＡＢＢ包围盒稍慢了一点，但却换回了更高的精度，减少了相交检测次数，总的检测效率会更高。鉴于此，本文提出了一种新的构建ＯＢＢ平衡包围盒树的方法。（１）任取空间解集Ｍ＝｛Ｍ１，Ｍ２，…，Ｍｎ｝的任意两个物体Ｍｉ∈Ｍ，Ｍｊ∈Ｍ，分别以Ｍｉ，Ｍｊ为根节点构建其整体ＯＢＢ包围盒树，Ｍｉ，Ｍｊ包含组成物体所有多边形。（２）本文采用文献［１１］分裂平面的方法划分Ｍｉ，Ｍｊ的左右子树。（３）使用最长轴方法确

【相似文献】

相关期刊论文 前10条

1 王浩,张航义;一种适合多机空战仿真的碰撞检测算法及应用[J];系统仿真学报;2004年09期

2 林鸿;常学宏;;计算机碰撞检测算法的研究[J];吉林省经济管理干部学院学报;2008年06期

3 金钺;侯文君;;基于虚拟手简化面法向距离的抓取碰撞检测算法[J];中国机械工程;2008年09期

4 熊玉梅;曾宪文;陈一民;;基于并行的快速碰撞检测算法的研究[J];计算机应用与软件;2008年04期

5 邹承明;汤智勇;;结合二维算法的三维快速碰撞检测算法[J];软件导刊;2009年04期

6 戴高乐;吴贵芳;李艳;;一种快速混合碰撞检测算法研究[J];通信技术;2010年05期

7 梁鹏帅;;碰撞检测算法的探讨[J];黑龙江科技信息;2010年14期

8 齐晓松;胡青泥;刘晶;;基于多视角的动态八叉树碰撞检测算法[J];东华大学学报(自然科学版);2006年05期

9 马登武;叶文;李瑛;吕晓峰;;适用于复杂场景的碰撞检测算法研究[J];计算机仿真;2006年12期

10 韩文君;赵伟;;基于空间数据结构的快速碰撞检测算法[J];长春工业大学学报(自然科学版);2007年04期

相关会议论文 前10条

1 陈二雷;;加速碰撞检测算法的研究[A];2008通信理论与技术新进展——第十三届全国青年通信学术会议论文集（上）[C];2008年

2 邵引平;李瑞鹏;;WTK环境下的碰撞检测算法的应用[A];信号与信息处理技术——第一届信号与信息处理联合学术会议论文集[C];2002年

3 纪传舜;刘卉;;基于质点的快速可变形体自碰撞检测算法[A];中国计算机图形学进展2008--第七届中国计算机图形学大会论文集[C];2008年

4 赵伟;陈承收;李立军;;基于MapReduce云计算模型的碰撞检测算法[A];'2010系统仿真技术及其应用学术会议论文集[C];2010年

5 张安真;孙长嵩;徐俊杰;;一种基于图像的凸多面体碰撞检测算法研究[A];2006北京地区高校研究生学术交流会——通信与信息技术会议论文集（下）[C];2006年

6 金汉军;刘直良;吴天真;;虚拟教学中碰撞检测算法的研究[A];2008通信理论与技术新进展——第十三届全国青年通信学术会议论文集（上）[C];2008年

7 邢一思;刘小平;徐少平;;虚拟焊接仿真系统中碰撞检测算法的改进[A];探索 创新 交流——第五届中国航空学会青年科技论坛文集(第5集)[C];2012年

8 李学庆;孟祥旭;汪嘉业;;基于Minkowski差构造技术的凸体碰撞检测算法[A];第一届全国几何设计与计算学术会议论文集[C];2002年

9 曹力;郑利平;刘晓平;;并行八叉树碰撞检测算法[A];计算机技术与应用进展——全国第17届计算机科学与技术应用（CACIS）学术会议论文集（下册）[C];2006年

10 赵伟;李立军;陈承收;;基于粒子群优化的随机碰撞检测算法研究[A];'2010系统仿真技术及其应用学术会议论文集[C];2010年

相关博士学位论文 前4条

1 赵伟;基于并行的快速碰撞检测算法研究[D];吉林大学;2009年

2 邹益胜;虚拟样机环境下实时碰撞检测算法研究[D];西南交通大学;2009年

3 水泳;虚拟现实中连续碰撞检测算法研究[D];中国科学技术大学;2013年

4 金汉均;虚拟环境中物体碰撞检测算法研究[D];华中科技大学;2006年

相关硕士学位论文 前10条

1 李山;变形物体碰撞检测算法研究[D];吉林农业大学;2012年

2 王龙涛;基于云计算的碰撞检测算法研究[D];吉林农业大学;2013年

3 李立军;基于粒子群蚁群的快速碰撞检测算法研究[D];长春工业大学;2011年

4 游灵聪;分布式多层次粒子碰撞检测算法[D];华南理工大学;2015年

5 张纪锁;虚拟现实中混合碰撞检测算法的应用研究[D];辽宁工程技术大学;2011年

6 程天翔;大规模柔体的连续碰撞检测算法研究[D];天津大学;2014年

7 黎珍;基于空间域的碰撞检测算法的研究[D];湖南师范大学;2013年

8 张锋;移动平台游戏中3D碰撞检测算法的研究与应用[D];上海交通大学;2010年

9 于奎超;柔性织物碰撞检测算法的研究[D];吉林农业大学;2013年

10 李建波;变形体的碰撞检测算法研究[D];青岛大学;2005年

本文编号：2653757