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

Previous Articles     Next Articles

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)

242

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

CLC Number: 

  • 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] DONG Sa, LIU Da-you, OUYANG Ruo-chuan, ZHU Yun-gang, LI Li-na. Logistic regression classification in networked data with heterophily based on second-order Markov assumption [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1571-1577.
[2] GU Hai-jun, TIAN Ya-qian, CUI Ying. Intelligent interactive agent for home service [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1578-1585.
[3] WANG Xu, OUYANG Ji-hong, CHEN Gui-fen. Measurement of graph similarity based on vertical dimension sequence dynamic time warping method [J]. 吉林大学学报(工学版), 2018, 48(4): 1199-1205.
[4] ZHANG Hao, ZHAN Meng-ping, GUO Liu-xiang, LI Zhi, LIU Yuan-ning, ZHANG Chun-he, CHANG Hao-wu, WANG Zhi-qiang. Human exogenous plant miRNA cross-kingdom regulatory modeling based on high-throughout data [J]. 吉林大学学报(工学版), 2018, 48(4): 1206-1213.
[5] HUANG Lan, JI Lin-ying, YAO Gang, ZHAI Rui-feng, BAI Tian. Construction of disease-symptom semantic net for misdiagnosis prompt [J]. 吉林大学学报(工学版), 2018, 48(3): 859-865.
[6] LI Xiong-fei, FENG Ting-ting, LUO Shi, ZHANG Xiao-li. Automatic music composition algorithm based on recurrent neural network [J]. 吉林大学学报(工学版), 2018, 48(3): 866-873.
[7] LIU Jie, ZHANG Ping, GAO Wan-fu. Feature selection method based on conditional relevance [J]. 吉林大学学报(工学版), 2018, 48(3): 874-881.
[8] WANG Xu, OUYANG Ji-hong, CHEN Gui-fen. Heuristic algorithm of all common subsequences of multiple sequences for measuring multiple graphs similarity [J]. 吉林大学学报(工学版), 2018, 48(2): 526-532.
[9] YANG Xin, XIA Si-jun, LIU Dong-xue, FEI Shu-min, HU Yin-ji. Target tracking based on improved accelerated gradient under tracking-learning-detection framework [J]. 吉林大学学报(工学版), 2018, 48(2): 533-538.
[10] LIU Xue-juan, YUAN Jia-bin, XU Juan, DUAN Bo-jia. Quantum k-means algorithm [J]. 吉林大学学报(工学版), 2018, 48(2): 539-544.
[11] LI Jia-fei, SUN Xiao-yu. Clustering method for uncertain data based on spectral decomposition [J]. 吉林大学学报(工学版), 2017, 47(5): 1604-1611.
[12] SHAO Ke-yong, CHEN Feng, WANG Ting-ting, WANG Ji-chi, ZHOU Li-peng. Full state based adaptive control of fractional order chaotic system without equilibrium point [J]. 吉林大学学报(工学版), 2017, 47(4): 1225-1230.
[13] WANG Sheng-sheng, WANG Chuang-feng, GU Fang-ming. Spatio-temporal reasoning for OPRA direction relation network [J]. 吉林大学学报(工学版), 2017, 47(4): 1238-1243.
[14] MA Miao, LI Yi-bin. Multi-level image sequences and convolutional neural networks based human action recognition method [J]. 吉林大学学报(工学版), 2017, 47(4): 1244-1252.
[15] ZHOU Bing-hai, PENG Tao. Optimal schedule of just-in-time part distribution for mixed-model assembly lines [J]. 吉林大学学报(工学版), 2017, 47(4): 1253-1261.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright © Journal of Jilin University(Engineering and Technology Edition), All Rights Reserved.
Tel: +86-431-85095297　Fax: +86-431-85094074　E-mail: xbgxb@jlu.edu.cn
Powered by Beijing Magtech Co. Ltd