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

doi:10.13229/j.cnki.jdxbgxb201602036

吉林大学学报(工学版) ›› 2016, Vol. 46 ›› Issue (2): 578-584.doi: 10.13229/j.cnki.jdxbgxb201602036

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

赵伟¹, 曲慧雁^{2, 3}

1.浙江传媒大学电子信息学院,杭州 310018;
2.吉林大学计算机科学与技术学院,长春 130012;
3.吉林农业大学信息技术学院,长春 130118

收稿日期:2014-07-16 出版日期:2016-02-20 发布日期:2016-02-20
通讯作者: 曲慧雁(1980-) ,女,副教授,博士.研究方向:虚拟现实,图形图像处理.E-mail:quhuiyan68@163.com E-mail:prince1205@163.com
作者简介:赵伟(1967-),男,教授,博士生导师.研究方向:虚拟现实,人机交互技术.E-mail:prince1205@163.com
基金资助:
吉林省自然科学基金重点项目(20140101196JC); 浙江省自然科学基金面上项目(LY15F020017)

Fast collision detection algorithm based on Cloud Map-Reduce model

ZHAO Wei¹, QU Hui-yan^{2, 3}

1.School of Electronics and Information Technology, Zhejiang University of Media and Communications, Hangzhou 310018,China;
2.College of Computer Science & Technology, Jilin University, Changchun 130012, China;
3.School of Information Technology, Jilin Agricultural University, Changchun 130118,China

Received:2014-07-16 Online:2016-02-20 Published:2016-02-20

摘要/Abstract

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

关键词: 人工智能, 碰撞检测, 人机交互, 云计算, 并行技术, Map-Reduce

Abstract: To meet the real-time and accuracy requirements of collision detection in Human-computer Interface (HCI) system, a fast collision detection algorithm is developed based on cloud computing model. First, a new construction method of balanced OBB bounding box tree by split plane is proposed. Second, the concept of marked traversing tree is introduced, and it is marked in depth or breadth traversal using stack on OBB to reduce the number of intersections in collision detection. Third, the task tree is divided using Map-reduce Model (MRM), and it is executed in parallel for the sub-tasks after division by the cloud model, thus to reduce the detection time. Finally, each sub-task result is identified and logical operation on the identified sub-task is carried out; the operation result is used to determine whether collision has taken place or not. Comparative experimental results show that, compared with the classic I-COLLIDE, MPI and Pipelining algorithms, the proposed algorithm has obvious advantages in terms of efficiency and accuracy that can meet the requirements of real-time and accuracy of HCI in complex virtual space.

Key words: artificial intelligent, collision detection, human-computer interaction, cloud computing, parallel technology, Map - Reduce

中图分类号:

TP301.6

赵伟, 曲慧雁. 基于云计算Map-Reduce模型的快速碰撞检测算法[J]. 吉林大学学报(工学版), 2016, 46(2): 578-584.

ZHAO Wei, QU Hui-yan. Fast collision detection algorithm based on Cloud Map-Reduce model[J]. 吉林大学学报(工学版), 2016, 46(2): 578-584.

参考文献

[1] 范昭炜,万华根,高曙明. 基于流的实时碰撞检测算法[J]. 软件学报, 2004,15(10):1505-1514.
Fan Zhao-wei,Wan Hua-gen,Gao Shu-ming.Streaming real time collision detection using programmable graphics hardware[J].Journal of Software, 2004,15(10): 1505-1514.
[2] 郑轶,宁汝新,刘检华,等. 虚拟装配环境下快速碰撞检测方法的研究[J]. 系统仿真学报,2005,17(9): 2167-2170.
Zheng Yi,Ning Ru-xin,Liu Jian-hua,et al.Research on fast collision detection method in virtual assembly environment[J]. Journal of System Simulation, 2005,17(9): 2167-2170.
[3] Lawbr Orion Sky, Kal'e Laxmikant V. A voxel-based paralel collision detection algorithm[C]//Proc of the 2002 International Conference on Supercomputing Conf, New York: USA: ACM, 2002:285-293.
[4] 薛广涛,李超,尤晋元. 基于凸多面体剖分的并行碰撞检测算法[J]. 上海交通大学学报, 2004,38(8):1385-1388.
Xue Guang-tao,Li Chao,You Jin-yuan.Algorithm of parallel collision detection based on dividing a convex polyhedron to tetrahedrons[J]. Journal of Shanghai Jiaotong University, 2004,38(8):1385-1388.
[5] 刘晓平,曹力. 基于MPI的并行八叉树碰撞检测[J]. 计算机辅助设计与图形学学报, 2007,19(2):184-187,192.
Liu Xiao-ping,Cao Li.Parallel Octree collision detection based on MPI[J].Journal of Computer-aided Design & Computer Graphics, 2007,19(2):184-187,192.
[6] 赵伟,何艳爽. 一种快速的基于并行的碰撞检测算法[J].吉林大学学报:工学版, 2008, 38(1):152-157.
Zhao Wei,He Yan-shuang. Rapid algorithm for parallel collision detection[J]. Journal of Jilin University(Engineering and Technology Edition),2008, 38(1):152-157.
[7] 赵伟 ,蔡兴盛.基于解空间划分的PSO改进算法[J].吉林大学学报:理学版,2012,50(4):725-732.
Zhao Wei, Cai Xing-sheng. PSO Improved algorithmg based on the solution space division[J].Journal of Jilin University(Science Edition),2012,50(4):725-732.
[8] Tang M, Curtis S, Yoon S E, et al. ICCD: interactive continuous collision detection between deformable models using connectivity-based culling[J].IEEE Transactions on Visualization and Computer Graphics, 2009,15 (4):544-557.
[9] Tang M, Manocha D, Tong R F. MCCD: Multi-core collision detection between deformable models using front-based decomposition[J]. Graphical Models, 2010, 72:7-23.
[10] Xu Qiang, Lu Xiao-feng, Ma Deng-wu. A survey of triangle and triangle intersection test[J]. Computer Simulation, 2006, 23(8):76-78,145.
[11] 泥宗涛, 余英林. 基于分层包围盒的连续碰撞检测加速算法[J]. 计算机工程与应用,2000,36(10):24-26.
Ni Zong-tao,Yu Ying-lin.Speeding up constant collision detection using layered bounding box[J].Computer Engineering and Applications,2000,36(10):24-26.

相关文章 15

[1]	董飒, 刘大有, 欧阳若川, 朱允刚, 李丽娜. 引入二阶马尔可夫假设的逻辑回归异质性网络分类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1571-1577.
[2]	顾海军, 田雅倩, 崔莹. 基于行为语言的智能交互代理[J]. 吉林大学学报(工学版), 2018, 48(5): 1578-1585.
[3]	王旭, 欧阳继红, 陈桂芬. 基于垂直维序列动态时间规整方法的图相似度度量[J]. 吉林大学学报(工学版), 2018, 48(4): 1199-1205.
[4]	张浩, 占萌苹, 郭刘香, 李誌, 刘元宁, 张春鹤, 常浩武, 王志强. 基于高通量数据的人体外源性植物miRNA跨界调控建模[J]. 吉林大学学报(工学版), 2018, 48(4): 1206-1213.
[5]	黄岚, 纪林影, 姚刚, 翟睿峰, 白天. 面向误诊提示的疾病-症状语义网构建[J]. 吉林大学学报(工学版), 2018, 48(3): 859-865.
[6]	李雄飞, 冯婷婷, 骆实, 张小利. 基于递归神经网络的自动作曲算法[J]. 吉林大学学报(工学版), 2018, 48(3): 866-873.
[7]	刘杰, 张平, 高万夫. 基于条件相关的特征选择方法[J]. 吉林大学学报(工学版), 2018, 48(3): 874-881.
[8]	王旭, 欧阳继红, 陈桂芬. 基于多重序列所有公共子序列的启发式算法度量多图的相似度[J]. 吉林大学学报(工学版), 2018, 48(2): 526-532.
[9]	杨欣, 夏斯军, 刘冬雪, 费树岷, 胡银记. 跟踪-学习-检测框架下改进加速梯度的目标跟踪[J]. 吉林大学学报(工学版), 2018, 48(2): 533-538.
[10]	刘雪娟, 袁家斌, 许娟, 段博佳. 量子k-means算法[J]. 吉林大学学报(工学版), 2018, 48(2): 539-544.
[11]	曲慧雁, 赵伟, 秦爱红. 基于优化算子的快速碰撞检测算法[J]. 吉林大学学报(工学版), 2017, 47(5): 1598-1603.
[12]	李嘉菲, 孙小玉. 基于谱分解的不确定数据聚类方法[J]. 吉林大学学报(工学版), 2017, 47(5): 1604-1611.
[13]	邵克勇, 陈丰, 王婷婷, 王季驰, 周立朋. 无平衡点分数阶混沌系统全状态自适应控制[J]. 吉林大学学报(工学版), 2017, 47(4): 1225-1230.
[14]	王生生, 王创峰, 谷方明. OPRA方向关系网络的时空推理[J]. 吉林大学学报(工学版), 2017, 47(4): 1238-1243.
[15]	马淼, 李贻斌. 基于多级图像序列和卷积神经网络的人体行为识别[J]. 吉林大学学报(工学版), 2017, 47(4): 1244-1252.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

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

Fast collision detection algorithm based on Cloud Map-Reduce model

RICH HTML

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10