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

• 论文 • 上一篇    下一篇

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

赵伟1, 曲慧雁2, 3   

  1. 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 Wei1, QU Hui-yan2, 3   

  1. 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

摘要: 针对人机交互系统中碰撞检测实时性,精确性的要求,本文提出了一种基于云计算模型的快速碰撞检测算法.①提出一种新的分裂平面构建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
[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.
[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.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 刘松山, 王庆年, 王伟华, 林鑫. 惯性质量对馈能悬架阻尼特性和幅频特性的影响[J]. 吉林大学学报(工学版), 2013, 43(03): 557 -563 .
[2] 初亮, 王彦波, 祁富伟, 张永生. 用于制动压力精确控制的进液阀控制方法[J]. 吉林大学学报(工学版), 2013, 43(03): 564 -570 .
[3] 李静, 王子涵, 余春贤, 韩佐悦, 孙博华. 硬件在环试验台整车状态跟随控制系统设计[J]. 吉林大学学报(工学版), 2013, 43(03): 577 -583 .
[4] 胡兴军, 李腾飞, 王靖宇, 杨博, 郭鹏, 廖磊. 尾板对重型载货汽车尾部流场的影响[J]. 吉林大学学报(工学版), 2013, 43(03): 595 -601 .
[5] 王同建, 陈晋市, 赵锋, 赵庆波, 刘昕晖, 袁华山. 全液压转向系统机液联合仿真及试验[J]. 吉林大学学报(工学版), 2013, 43(03): 607 -612 .
[6] 张春勤, 姜桂艳, 吴正言. 机动车出行者出发时间选择的影响因素[J]. 吉林大学学报(工学版), 2013, 43(03): 626 -632 .
[7] 马万经, 谢涵洲. 双停车线进口道主、预信号配时协调控制模型[J]. 吉林大学学报(工学版), 2013, 43(03): 633 -639 .
[8] 于德新, 仝倩, 杨兆升, 高鹏. 重大灾害条件下应急交通疏散时间预测模型[J]. 吉林大学学报(工学版), 2013, 43(03): 654 -658 .
[9] 肖赟, 雷俊卿, 张坤, 李忠三. 多级变幅疲劳荷载下预应力混凝土梁刚度退化[J]. 吉林大学学报(工学版), 2013, 43(03): 665 -670 .
[10] 肖锐, 邓宗才, 兰明章, 申臣良. 不掺硅粉的活性粉末混凝土配合比试验[J]. 吉林大学学报(工学版), 2013, 43(03): 671 -676 .