Fast Efficient Collision Detection

Abstract

Abstract: To speed up collision detection, a novel parallel algorithm for collision detection was proposed. Firstly, spatial Morton codes are used in linear ordering for geometric primitives, this is fast to build bounding volume hierarchies. Secondly, a top-down approach that uses the graph of model to build hierarchies optimized from skeletons connection. Thirdly, both algorithms are combined into a hybrid algorithm that need few memories for GPU construction performance and scalability leading to significantly decreased build time. The experimental results show the algorithm has efficient speedup to construct hierarchies of models with up to several million triangles and is fast for collision detection.

Key words: collision detection, computer graphics, hierarchy, graphics processing unit, parallel computing

CLC Number:

TP 391

YIN Gui-Sheng-1, WANG Hai-Ling-1, 2 , ZHANG Jing-1, NI Jun-2, WANG Jian-3. Fast Efficient Collision Detection[J]. Journal of Shanghai Jiaotong University, 2012, 46(06): 962-966.

References

［1］赵伟,谭睿璞,李文辉.基于混合包围体的 OpenMP并行化碰撞检测算法［J］.软件学报,2008,19(sup.):190201.

〖KG*2〗ZHAO Wei, TAN Ruipu, LI Wenhui.Parallel collision detection algorithm based on mixed BVH and OpenMP［J］. Journal of Software, 2008, 19(sup.): 190201.
［2］唐敏, Dinesh M,童若锋. 基于SIMD指令的柔性物体并行碰撞检测［J］.计算机学报, 2009, 32(10):20422051.

〖KG*2〗TANG Min,Dinesh M,TONG Ruofeng.Parallel collision detection between deformable objects using SIMD instructions［J］.Chinese Journal of Computers, 2009, 32(10): 20422051.

［3］Govindaraju N K, Lin M C, Manocha D, et al. QuickCULLIDE: Fast inter and intraobject collision culling using graphics hardware ［C］∥ Proceedings of IEEE Virtual Reality. USA: IEEE Press, 2005: 5966.

［4］Gre A, Guthe M, Klein R. GPUbased collision detection for deformable parameterized surfaces ［J］. Computer Graphics Forum, 2006, 25(3): 497506.

［5］王海玲,印桂生,陈怀友,等.基于拓扑层次图的碰撞检测算法［J］.计算机应用,2011,31(2):347350.

〖KG*2〗WANG Hailing, YIN Guisheng, CHEN Huaiyou,et al. Collision detection based on topology hierarchy graph ［J］.Journal of Computer Applications, 2011, 31(2): 347350.

［6］Katz S, Tal A. Hierarchical mesh decomposition using fuzzy clustering and cuts ［J］. ACM Transactions on Graphics, 2003, 22(3): 954961.

［7］Horn D. Stream reduction operations for GPGPU applications［M］. USA: AddisonWesley Publishing Company, 2005: 573589.

［8］刘俊涛,刘文予,吴彩华,等.一种提取物体线形骨架的新方法［J］. 自动化学报, 2008,34(6): 617622.

〖KG*2〗LIU Juntao, LIU Wenyu,WU Caihua, et al. A new method of extracting objects’ curveskeleton ［J］.Acta Automatica Sinica, 2008, 34(6): 617622.

[1]	LI Bingchao (李炳超), WEI Jizeng (魏继增), GUO Wei (郭炜), SUN Jizhou (孙济州). Bypass-Enabled Thread Compaction for Divergent Control Flow in Graphics Processing Units [J]. J Shanghai Jiaotong Univ Sci, 2021, 26(2): 245-256.
[2]	WANG Wei, LU Sikui, YANG Chengzhong, FENG Qingsong. Optimization of Subgrade Structure Parameters of Ballasted Track Passenger Dedicated Line [J]. Journal of Shanghai Jiao Tong University, 2021, 55(1): 48-55.
[3]	WANG Mingzheng, WANG Yijie, WANG Tianyu, HOU Linzao, LI Mian . New Approach for Information Security Evaluation and Management of IT Systems in Educational Institutions [J]. J Shanghai Jiaotong Univ Sci, 2020, 25(6): 689-699.
[4]	HUANG Ganyu (黄甘雨), PAN Qiaoyi (潘荍仪), ZHAO Shuangying (赵双楹), GAO Yucen (高宇岑), GAO Xiaofeng (高晓沨). Prediction of COVID-19 Outbreak in China and Optimal Return Date for University Students Based on Propagation Dynamics [J]. J Shanghai Jiaotong Univ Sci, 2020, 25(2): 140-146.
[5]	ZHAO Zhijian, YU Ke, MA Yuehua, PAN Jun, YANG Gewen. Evaluation of Radar Anti-jamming Performance Based on AHP-Cloud Model [J]. Air & Space Defense, 2020, 3(1): 65-72.
[6]	WANG Yunlong，SHEN Jiaqi，WANG Qingpeng，WU Dehua,JIN Chaoguang. Evaluation Technology of Design Scheme for Liquified Natural Gas Bunker Vessel [J]. Journal of Shanghai Jiaotong University, 2018, 52(6): 693-697.
[7]	ZHANG Ying (张颖), LI Peisong (李培嵩), MAO Lin (毛林). Research on Improved Low-Energy Adaptive Clustering Hierarchy Protocol in Wireless Sensor Networks [J]. Journal of Shanghai Jiao Tong University (Science), 2018, 23(5): 613-619.
[8]	WU Changzheng1，YUE Yi1,2，WEI Baochen1，LIU Dianfu3. Self-Collision Detection and Motion Planning for Dual-Arm Robot [J]. Journal of Shanghai Jiaotong University, 2018, 52(1): 45-53.
[9]	CHEN Luyun,YANG Nian. Model Updating Analysis of Structural Dynamic Problem Based on Multi-Level Weight Coefficients [J]. Journal of Shanghai Jiaotong University, 2017, 51(12): 1415-1421.
[10]	ZHAO Xia* (赵夏), MA Sheng (马胜), CHEN Wei (陈微), WANG Zhiying (王志英). Exploiting Parallelism in the Simulation of General Purpose Graphics Processing Unit Program [J]. Journal of shanghai Jiaotong University (Science), 2016, 21(3): 280-288.
[11]	WANG Xiaoqinga,b，JIN Xianlonga,b，CAO Yuana. ThreeDimensional Simulation of Water Hammer of LargeScale Water Conveyance Tunnel [J]. Journal of Shanghai Jiaotong University, 2016, 50(01): 98-102.
[12]	Jin-hong XIE, Xiao-peng LI, Jian-mei GAO. Design and Application of SDH Fiber Optic Network for Offshore Oil and Gas Field [J]. Ocean Engineering Equipment and Technology, 2015, 2(3): 209-214.
[13]	BAO Yidong1, 2,WU Dongmei1. A Novel Algorithm for Collision Detection Based on Octree of Adaptive Subdivision and Encoding [J]. Journal of Shanghai Jiaotong University, 2015, 49(08): 1114-1122.
[14]	ZHANG Shilun1,ZHANG Mengxi1,JI Suiwang2,CHEN Qiang2,LUO Kangjun2. Loose Media Slope Stability Evaluation Based on Fuzzy Analysis [J]. Journal of Shanghai Jiaotong University, 2015, 49(07): 1035-1039.
[15]	WANG Jian1，PANG Yongjie1，YANG Zhuoyi1，HU Zhonghui2. Application of Improved FAHP in Evaluation of AUV Overall Performance [J]. Journal of Shanghai Jiaotong University, 2015, 49(02): 275-280.