分布式环境下基于方向包围盒的碰撞检测-论文.pdf

《分布式环境下基于方向包围盒的碰撞检测-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、JournalofComputerApplicationsISSN1001．90812014．O6—3O计算机应用，2014，34(S1)：93—95，99CODENJYIIDUhttp：／／www．joca．an文章编号：1001-9081(2014)S1．0093．03分布式环境下基于方向包围盒的碰撞检测王亮。，沈建京，易卓(信息工程大学理学院，郑州450001)(十通信作者电子邮箱Wireless777@163．corn)摘要：对于碰撞检测占用内存多、计算量大、数据负载高的问题，提出了基于MapReduce模型的方向包围盒(OBB)碰撞检测算法，采用OBB来描述被检对象的几

2、何模型，把复杂模型的碰撞检测抽象成为简单元素的相交测试，并利用云计算关键技术MapReduce模型分布式遍历层次包围盒树进行相交测试，从而提高检测速度。实验表明，在构造的动态场景运行1500步时，该算法比其他算法在帧频和所需时间上最少有着322％和5l％的效率提高。关键词：云计算；虚拟环境；碰撞检测；方向包围盒；MapReduce中图分类号：TP301．6文献标志码：ACollisiondetectionbasedonorientedboundingboxindistributedenvironmentWANGLiang’，SHENJianjing，YIZhuo(Collegeo

3、fSciences，InformationEngineeringUniversity,Zhengzhouttenan450001，China)Abstract：Tosolvetheproblemofnumerousoccupationofmemory，largeamountofcalculationandhighloadofdataincollisiondetection，thispaperpresentedanOrientedBoundingBox(OBB)collisiondetectionalgorithmbasedonMapReducemode1．Thisalgorith

4、mcouldimprovethespeedofcolisiondetectionbyusingOBBstodescribethegeometrymodelofmeasuredobject，SOthecollisiondetectionofcomplexmodelscouldbeabstractedintointersectiontestofsimpleelements，MapReducemodelWasusedaskeytechnologyofcloudcomputingtotraverseOBB—treesindistributionwaytoconducttheinterse

5、ctiontest．Theexperimentshowsthatthisalgorithmhasaminimumof322％and51％eficiencyimprovementthanothersinframerateandtimecostwhentheconstructeddynamicscenerunsI500steps．Keywords：cloudcomputing；virtualenvironment；collisiondetection；OrientedBoundingBox(OBB)；MapReduce碰撞检测，通过包围盒之间的相交测试，快速地排除不相交的0引言基本几

6、何元素对，以减少相交测试的次数。常用的包围盒有碰撞检测是基于现实生活中两个不可穿透的物体不可能球形包围盒(SphereBox，SB)、轴对齐包围盒(Axis—aligned共存于相同的空间区域从而判定两物体或多物体间是否发生BoundingBox，AABB)、方向包围盒(OBB)、固定方向凸包交叉及相交部位的方法J，碰撞检测作为计算机图形学、计(FixedDirectionsHulls，FDH)、离散有向多面体(k-Discrete算机动画、军事仿真和虚拟现实等领域中的一个经典问题，多OrientedPolytope，k—DOP)等。年来一直受到较多的关注。1．2MapReduc

7、e近年来研究人员对碰撞检测问题进行深入的研究，提出MapReduce是云计算的一种关键技术，是一个编程模型，了许多高效的算法。但是，由于虚拟环境和虚拟对象的几何也是一个处理和生成超大数据集的算法模型的相关实现j。复杂度及实时性要求的日益增高，使得碰撞检测的计算复杂用户首先创建一个Map函数处理一个基于(key，value)对的度呈指数级增长，碰撞检测需要占用相对多的存储空间和处数据集合，然后生成一个中间的(key，value)对的数据集合；理时间。最后再创建一个Reduce函数用