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]	WANG Feng, CHEN Tielin, FAN Rong, LI Yuepeng. Large-Scale Numerical Simulation and Application of Hydraulic Fracturing in Soil [J]. Journal of Shanghai Jiao Tong University, 2026, 60(3): 463-472.
[2]	Huang Wenhan, Deng Xiaotie. Boundedly Rational Agents in Sequential Posted Pricing [J]. J Shanghai Jiaotong Univ Sci, 2026, 31(2): 390-404.
[3]	Fang Xingyu, Wei Xianming, Sun Jintao, Xu Linsen. Collision Detection for Vacuum Wafer Transfer Robot [J]. J Shanghai Jiaotong Univ Sci, 2026, 31(1): 99-105.
[4]	GU Chenxing, QUAN Jichuan, HUANG Zhixiong, LIU Guibin. Aerial Target Threat Assessment Model Based on Improved AHP-CRITIC-TOPSIS [J]. Air & Space Defense, 2025, 8(4): 68-77.
[5]	YU Chao, TONG Yingli, LIU Hao, CHEN Changqin, SUN Haifang, SONG Kunming. Weight Analysis of Comprehensive Evaluation Index of FPSO Oil， Gas and Water Separation System Based on Analytic Hierarchy Method [J]. Ocean Engineering Equipment and Technology, 2025, 12(2): 144-151.
[6]	Li Tao, Zhao Zhigang, Zhu Mingtong, Zhao Xiangtang. Cable Vector Collision Detection Algorithm for Multi-Robot Collaborative Towing System [J]. J Shanghai Jiaotong Univ Sci, 2025, 30(2): 319-329.
[7]	MA Xiaolong, XU Xinpeng, REN Shulei, LI Chen, CUI Shan. Architecture Design of Guidance Head Signal Processing Module Based on GP-GPU Technology Application [J]. Air & Space Defense, 2025, 8(2): 84-92.
[8]	XIA Yu, WANG Lei. Risk Assessment Method for Marine Engineering Project Bidding Based on Back Propagation Neural Network [J]. Journal of Shanghai Jiao Tong University, 2023, 57(S1): 46-53.
[9]	GUAN Yanmin, YANG Caihong, KANG Zhuang, ZHOU Li. Application of an Improved GPU Acceleration Strategy for the Smoothed Particle Hydrodynamics Method [J]. Journal of Shanghai Jiao Tong University, 2023, 57(8): 981-987.
[10]	JIANG Yi, FU Juncheng, LI Zewen, ZHANG Yuqing, YIN Jungang, YAO Jiangang. A Comprehensive Evaluation Model of Buildings Based on Improved TOPSIS [J]. Journal of Shanghai Jiao Tong University, 2023, 57(7): 868-877.
[11]	ZHANG Zelong, ZHANG Yingchao, WU Bo, DONG Wei, FAN Youben. Real-Time Laser Speckle Imaging of Blood Flow with High Gray Level and High Resolution [J]. Journal of Shanghai Jiao Tong University, 2023, 57(5): 552-559.
[12]	PANG Na1 (庞娜), LUO Wenguang1∗ (罗文广), WU Ruoyuan1 (吴若园), LAN Hongli1 (蓝红莉), QIN Yongxin1 (覃永新), SU Qi2 (苏琦). Safety Evaluation of Commercial Vehicle Driving Behavior Based on AHP-CRITIC Algorithm [J]. J Shanghai Jiaotong Univ Sci, 2023, 28(1): 126-135.
[13]	CHEN Renpeng, WANG Zhiteng, WU Huaina, LIU Yuan, MENG Fanyan. Risk Assessment for Shield Tunneling Beneath Buildings Based on Interval Improved TOPSIS Method and FAHP Method [J]. Journal of Shanghai Jiao Tong University, 2022, 56(12): 1710-1719.
[14]	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.
[15]	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.