吉林大学学报(工学版) ›› 2017, Vol. 47 ›› Issue (5): 1598-1603.doi: 10.13229/j.cnki.jdxbgxb201705036

• • 上一篇    下一篇

基于优化算子的快速碰撞检测算法

曲慧雁1, 2, 赵伟3, 4, 秦爱红5   

  1. 1.吉林大学 计算机科学与技术学院,长春 130012;
    2.吉林农业大学 信息技术学院,长春 130118;
    3.长春工程学院 机电学院,长春 130012;
    4.浙江传媒学院 电子信息学院,杭州 310018;
    5 浙江传媒学院 新媒体学院,杭州 310018
  • 收稿日期:2016-05-10 出版日期:2017-09-20 发布日期:2017-09-20
  • 通讯作者: 赵伟(1967-),男,教授,博士后.研究方向:虚拟现实,人机交互技术.E-mail:prince1205@163.com
  • 作者简介:曲慧雁(1980-),女,副教授,博士.研究方向:虚拟现实,图形图像处理.E-mail:quhuiyan68@163.com
  • 基金资助:
    吉林省自然科学基金面上重点项目(20140101196JC); 浙江省自然科学基金面上项目(LY15F020017,LY15F020016); 吉林省教育厅“十三五”科学技术研究重点项目(吉教科合字[2016]第174号,[2017]JJKH20170990KJ)

A fast collision detection algorithm based on optimization operator

QU Hui-yan1, 2, ZHAO Wei3, 4, QIN Ai-hong5   

  1. 1.College of Computer Science & Technology, Jilin University, Changchun 130012,China;
    2.School of Information Technology, Jilin Agricultural University,Changchun 130118,China;
    3.School of Mechanical and Electrical, Changchun Engineering Institute,Changchun 130012,China;
    4.School of Electronics and Information Technology Zhejiang University of Media and Communications, Hangzhou 310018,China;
    5.School of New Media,Zhejiang University of Media and Communications, Hangzhou 310018,China
  • Received:2016-05-10 Online:2017-09-20 Published:2017-09-20

RICH HTML

1   

PDF (PC)

332

摘要： 针对复杂人机交互实时性的要求,提出了一种基于优化算子的SIMD并行碰撞检测算法。引入了优化算子,将搜索空间限定在非均匀的局部极小区域,减少了蚁群的搜索时间。在多蚁群求解过程中,将子任务使用负载均衡策略分配到多核处理器的各个处理核心上并行执行,实验结果表明:与经典的I-COLLIDE、MPI及Pipelining等算法相比,本文提出的算法较好地解决了人机交互中的碰撞检测问题。

关键词: 人工智能, 碰撞检测, 并行算法, 优化算子, 平衡包围盒

Abstract: To meet the real-time requirement in complex human-computer interaction, a Single Instruction, Multiple Data (SIMD) parallel collision detection algorithm based on optimization operator is proposed. By introduction of optimization operator, the search space is confined in a non-uniform local minimum area, reducing the colony search time. In the process of solving the multiple ant colony, the load balancing strategy is used to assign the sub-tasks to each processing core on multi-core processors for parallel execution. Results show that, compared with the classic I-COLLIDE, MPI and Pipelining algorithms, the proposed algorithm has better performance in solving the human-computer interaction in collision detection.

Key words: artificial intelligence, collision detection, parallel algorithm, optimization operator, balance bounding box

中图分类号: 

  • TP391
[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].吉林大学学报:工学版, 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.
[3] 魏迎梅.虚拟环境中碰撞检测问题的研究[D], 长沙: 国防科技大学计算机学院, 2000.
Wei Ying-mei. Research on collision detection in virtual environment[D].Changsha: School of Computer Science, National University of Defense Technology,2000.
[4] Govindaraju N K,Lin M C,Manocha D.Quick-ULLIDE:fast inter- and intra-object collision detection using graphica processors[J].Proceedings of the IEEE Conference on Virtual Reality,2005,319:59-66.
[5] 郑轶, 宁汝新, 刘检华, 等. 虚拟装配环境下快速碰撞检测方法的研究[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.
[6] Xu Qiang, Lu Xiao-feng, Ma Deng-wu. A Survey of Triangle and Triangle Intersection Test[J]. Computer Simulation, 2006, 23(8):76-78.
[7] 泥宗涛,余英林.基于分层包围盒的连续碰撞检测加速算法[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.
[8] 薛广涛, 李超, 尤晋元. 基于凸多面体剖分的并行碰撞检测算法[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.
[9] Alba E, Leguizamon G, Ordonez G. Analyzing the behavior of parallel ant colony systems for large instances of the task scheduling problem[C]∥20th IEEE International Parallel and Distributed Processing SymPosium,2005:14-23.
[10] 赵伟, 蔡兴盛. 基于解空间划分的PSO改进算法[J]. 吉林大学学报:理学版, 2012, 50(4):725-732.
Zhao Wei,Cai Xing-sheng.A PSO optimization algorithm based on the solution space division[J].Journal of Jilin University(Science Edition),2012,50(4):725-732.
[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): 1604-1611.
[12] 邵克勇, 陈丰, 王婷婷, 王季驰, 周立朋. 无平衡点分数阶混沌系统全状态自适应控制[J]. 吉林大学学报(工学版), 2017, 47(4): 1225-1230.
[13] 王生生, 王创峰, 谷方明. OPRA方向关系网络的时空推理[J]. 吉林大学学报(工学版), 2017, 47(4): 1238-1243.
[14] 马淼, 李贻斌. 基于多级图像序列和卷积神经网络的人体行为识别[J]. 吉林大学学报(工学版), 2017, 47(4): 1244-1252.
[15] 周炳海, 彭涛. 混流装配线准时化物料配送调度优化[J]. 吉林大学学报(工学版), 2017, 47(4): 1253-1261.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 《吉林大学学报(工学版)》编辑部
地址：长春市人民大街5988号　电话：+86-431-85095297　传真：+86-431-85094074　E-mail: xbgxb@jlu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发