并行化碰撞检测算法综述

doi:10.16182/j.issn1004731x.joss.201711001

摘要/Abstract

摘要： 随着不同应用领域对实时碰撞检测算法需求的增长,利用多核CPU和GPU的并行处理能力来提高碰撞检测算法的处理速度已经得到了广泛的关注。文中回顾了碰撞检测算法的发展历史并从多个角度对目前现有的算法进行了分类归纳;介绍了十余种代表性的基于CPU和GPU并行化碰撞检测算法,并从算法的可扩展性和存储空间消耗以及任务量均衡化等方面分析了这些算法的优缺点。最后总结了并行化碰撞检测算法研究中存在的问题和新的发展方向以及常用的实验测试数据。

关键词: 碰撞检测, 综述, GPU, 并行化算法

Abstract: The demand for real-time collision detection is increasing in different applications. Exploiting the parallel computing capability of multi-core CPUs and GPUs to accelerate the speed of collision detection algorithms has attracted abroad attention. This paper reviews the development history of collision detection algorithms and classified the existing algorithms from multiple perspectives. Moreover, we analyze the strengths and weaknesses of more than ten representative parallel collision detection algorithms based on multi-core CPUs and GPUs from the aspects of the scalability, memory consumption and workload balancing. Finally, the problem of present parallel collision detection research and potential direction of following research and some representative benchmark data sets are presented.

Key words: collision detection, survey, GPU, parallel algorithms

中图分类号:

TP391

刘复昌, 王双建, 潘志庚, 王金荣. 并行化碰撞检测算法综述[J]. 系统仿真学报, 2017, 29(11): 2601-2608.

Liu Fuchang, Wang Shuangjian, Pan Zhigeng, Wang Jinrong. Survey on Parallel Collision Detection Algorithms[J]. Journal of System Simulation, 2017, 29(11): 2601-2608.

参考文献

[1] Bentley J L, Ottmann T A.Algorithms for reporting and counting geometric intersections[J]. IEEE Transactions on Computers (S0018-9340 ), 1979, 28(9): 643-647.
[2] Ahuja N, Chien R T, Yen R, Bridwell N.Interference detection and collision avoidance among three dimensional objects[C]// Proceedings of the Annual National Conference on AI 1980. Stanford University, 1980: 44-48.
[3] Canny J F.Collision detection for moving polyhedral[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence (S0162-8828), 1986, 8(2): 200-209.
[4] Bonner S, Kelley R B.A representation scheme for rapid 3-d collision detection[C]// Proceedings of IEEE International Symposium on Intelligent Control 1988. Arlington, 1988: 320-325.
[5] Moore M, Wilhelms J.Collision detection and response for computer animation[J]. ACM Computer Graphics (S0097-8930), 1988, 22(4): 289-298
[6] O'Sullivan C, Dingliana J. Realtime collision detection and response using sphere-trees[C]// Proceeding of the Spring Conference on Computer Graphics 1999. Bratislava, 1999: 83-92.
[7] Palmer I, Grimsdale R.Collision detection for animation using Sphere-Trees[J]. Computer Graphics Forum (S0167-7055), 1995, 14(2): 105-116.
[8] Bergen G. van den.Efficient collision detection of complex deformable models using AABB trees[J]. Journal of Graphics Tools, 1997, 2(4): 1-14.
[9] Larsson T, Moller T A.Collision detection for continuously deforming bodies[J]. Proceedings of Eurographics 2001. Manchester, 2001: 325-333.
[10] Gottschalk S, Lin M, Manocha D.OBB-Tree: A Hierarchical Structure for Rapid Interference Detection[C]// Proceeding of ACM SIGGRAPH 1996. Dallas, 1996: 171-180.
[11] Klosowski J, Held M, Mitchell J S B, Sowizral H, Zikan K. Efficient collision detection using bounding volume hierarchies of k-DOP[J].IEEE Transaction on Visualization and Computer Graphics (S1077-2626), 1998, 4(1): 21-37.
[12] Zachmann G.Rapid collision detection by dynamically aligned DOP-Trees[C]// Proceedings of IEEE, VRAIS 1998. Atlanta, 1998: 90-97.
[13] Ehmann S, Lin M C.Accurate and fast proximity queries between polyhedral using convex surface decomposition[J]. Proceedings of the Eurographics. Manchester, 2001: 500-510.
[14] Wan H G, Fan Z W, Gao S M, et al.A parallel collision detection algorithm based on hybrid bounding volume hierarchy[J]. Proceedings of CAD & Graphics 2001. Kunming, 2001: 512-528.
[15] Moller T.A fast triangle-triangle intersection test[J]. Journal of Graphics Tools, 1997, 2(2): 25-30.
[16] Lin M C, Canny J.Efficient algorithms for incremental distance computation[C]// Proceedings of IEEE International Conference on Robotics and Automation 1991. Sacramento, 1991: 1008-1014.
[17] Gilbert E G, Johnson D W, Keerthi S S.A fast procedure for computing the distance between objects in three-dimensional space[J]. IEEE Journal on Robotics and Automation, 1998, 4: 193-203.
[18] Lin M C, Gottschalk S.Collision detection between geometric models: a survey[C]// Proceedings of IMA Conference on Mathematics of Surface 1998, 1998: 37-56.
[19] Jimenez P, Thomas F, Torras C.Collision detection: a survey[J]. Computers and Graphics (S0097-8493), 2001, 25(2): 269-285.
[20] Hubbard P M.Real-time collision detection and time-critical computing[C]// In SIVE 95, The First Workshop on Simulation and Interaction in Virtual Environments. Iowa City, Iowa, 1995, 1: 92-96.
[21] Dingliana J, O'Sullivan C. Graceful degradation of collision handling in physically based animation[J]. Proceedings of Eurographics 2000. Computer Graphics Forum (S0167-7055), 2000, 19(3): 239-247.
[22] Dingliana J, O'Sullivan C. Bradshaw G. Collisions and adaptive levels of detail[J]. SIGGRAPH 2001 Sketches Program, LA, 2001.
[23] Redon S, Kheddar A, Coquillart S.An algebraic solution to the problem of collision detection for rigid polyhedral objects[C]// Proceedings of IEEE Conference on Robotics and Automation. San Francisco, 2000.
[24] Canny J.Collision detection for moving polyhedral[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence (S0162-8828), 1986, 8: 200-209.
[25] Kim B, Rossignac J.Collision prediction for polyhedral under screw motions[C]// Proceedings of ACM Conference on Solid Modeling and Applications 2003. Seattle, 2003.
[26] Abdel-Malekl K, Yang J, Blackmore D, Joy K.Swept volume: Foundations, perspectives, and applications[J]. International Journal of Shape Modeling, 2006, 12(1): 87-127.
[27] Redon S, Kheddar A, Coquillart S.Fast continuous collision detection between rigid bodies[J]. Proceedings of Eurographics 2002. Computer Graphics Forum (S0167-7055), 2002, 21(3): 279-288.
[28] Schwarzer F, Saha M, Latombe J C.Exact collision checking of robot paths[J]. Workshop on Algorithmic Foundations of Robotics(WAFR), Nice, 2002.
[29] Agarwal P K, Basch J, Guibas L J, Hershberger J, Zhang L.Deformable free space tiling for kinetic collision detection[C]// Proceedings of 4^th Workshop Algorithm Foundations of Robotics(WAFR) 2000. Hanover, 2000.
[30] Kirkpatrick D, Snoeyink J, Speckmann B.Kinetic collision detection for simple polygons[C]// Proceedings of 16^th Annual ACM Symposium Computational Geometry 2000. HongKong, 2000.
[31] Bergen G. van den.Ray casting against general convex objects with application to continuous collision detection[J]. Journal of Graphics Tools, 2004.
[32] Mirtich B V.Impulse-based dynamic simulation of rigid body systems[C]// Acm Symposium on Interactive 3d Graphics. University of California, Berkeley, 1996.
[33] Mirtich B.Timewarp rigid body simulation[J]. Proceedings of ACM SIGGRAPH 2000. New Orleans, Louisiana, 2000: 193-200.
[34] Bullet Physics library, http://www.continuousphysics.com.
[35] Zhang X Y, Lee M K, Kim Y J.Interactive continuous collision detection for rigid non-convex polyhedral[J]. Proceedings of Pacific Graphics 2006. Taipei, The Visual Computer, 2006, 22: 9-11.
[36] Zhang X Y, Redon S, Lee M K, et al.Continuous collision detection for articulated models using Taylor models and temporal culling[J]. Proceedings of ACM SIGGRAPH 2007. San Diego, ACM Transactions on Graphics, 2007, 26(3), 15.
[37] Brochu T, Edwards E, Bridson R.Efficient geometrically exact continuous collision detection[J]. Proceedings of ACM SIGGRAPH 2012. Los Angeles, ACM Transactions on Graphics, 2012, 31(4), 96.
[38] Wald I, Philipp S, Carsten B, Markus W.Interactive rendering with coherent ray tracing[J]. Proceedings of the Eurographics 2001. Manchester, 2001: 153-164.
[39] Ericson C.Real-Time Collision Detection[M]. New York: Morgan Kaufmann, 2004.
[40] Lin M C, Gregory A, Ehmann S, Gottschalk S, Taylor R.Contact determination for real-time haptic interaction in 3D modeling, editing and painting[J]. Proceedings of the workshop for PHANTOM User Group 1999. New York, 1999: 43-50.
[41] 唐敏, Manocha Dinesh, 童若锋. 基于SIMD指令的柔性物体并行碰撞检测. 计算机学报, 2009, 32(10): 2042-2051.
(Tang M, Manocha D, Tong R F.Parallel collision detection between deformable objects using SIMD instructions[J]. Chinese Journal of Computer, 2009, 32(10): 2042-2051.)
[42] Kim D, Heo J P, Yoon S E.PCCD: parallel continuous collision detection[C]// International Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 2009, New Orleans, Louisiana, USA, August 3-7, 2009, Poster Proceedings, 2009: 1-1.
[43] Tang M, Manocha D, Tong R F.MCCD: Multi-Core collision between deformable models using front-based decomposition[J]. Graphical Models (S1524-0703), 2010, 72(2): 7-23.
[44] Kim Y J, Lee Y.Simple and parallel proximity algorithms for general polygonal models[J]. Computer animation and virtual worlds (S1546-4261), 2010, 21: 365-374.
[45] Tang M, Manocha D, Tong R.Multi-Core collision detection between deformable models[C]// Proceedings of SIAM/ACM Joint Conference on Geometric and Physical Modeling 2009, San Francisco, 2009: 335-360.
[46] Tang M, Curtis S, Yoon S E, Manocha D.ICCD: Interactive continuous collision detection between deformable models using connectivity-based culling[J]. IEEE Transactions on Visualization and Computer Graphics (S1077-2626), 2009, 15(4): 544-557.
[47] Larsen E, Gottschalk S, Lin M C, Manocha D.Fast proximity queries with swept sphere volumes[C]// Chapel Hill, USA: University of North Carolina: TR99-018, 1999.
[48] Baciu G, Wong S K, Sun H.Recode: An image-based collision detection algorithm[J]. Proceedings of Pacific Graphics 1998. Singapore, 1998: 497-512.
[49] Hoff K, Zaferakis A, Lin M, Manocha D.Fast and simple 2d geometric proximity queries using graphics hardware[C]// Proceedings of ACM Symposium on Interactive 3D Graphics 2001. Research Triangle Park, 2001: 145-148.
[50] Knott D, Cinder D P.Collision and interference detection in real-time using graphics hardware[J]. Proceedings of Graphics Interface 2003. Halifax, 2003: 73-80.
[51] Myszkowski K, Okunev O G, Kunii T L.Fast collision detection between complex solids using rasterizing graphics hardware[J]. The Visual Computer, 1995, 11(9): 497-512.
[52] Shinya M, Forgue M C.Interference detection through rasterization[J]. The Journal of Visualization and Computer Animation, 1991, 2(4): 131-134.
[53] Vassilev T, Spanlang B, Chrysanthou Y.Fast cloth animation on walking avatars[C]// Proceedings of Eurographics 2001. Manchester, Computer Graphics Forum, 2001, 20(3): 260-267.
[54] 范昭炜. 实时碰撞检测技术研究[D]. 杭州: 浙江大学计算机学院, 2003.
(Fan Zhaowei.Research on real time collision detection[D]. [Ph.D. Thesis]. Hangzhou: Zhejiang University College of Computer Science, 2003.)
[55] Govindaraju N K, Lin M C, Manocha D.Fast and reliable collision culling using graphics hardware[C]// Proceedings of the ACM symposium on Virtual reality software and technology 2004. HongKong, 2004, 2-9.
[56] Sud A, Govindaraju N, Gayle R, et al.Fast proximity computation among deformable models using discrete voronoi diagrams[J]. Proceedings of ACM SIGGRAPH 2006. Boston, 2006: 1144-1153.
[57] Govindaraju N, Redon S, Lin M, Manocha D.CULLIDE: Interactive collision detection between complex models in large environments using graphics hardware[C]//Proceedings of ACM SIGGRAPH/ Eurographics Workshop on Graphics Hardware 2003. San Diego, 2003: 25-32.
[58] Heidelberger B., Teschner M., Gross M.Real-time volumetric intersections of deforming objects[C]// Proceeding of Vision, Modeling and Visualization 2003. Munchen, 2003.
[59] Kim Y J, Otaduy M A, Lin M C, Manocha D.Fast penetration depth computation for physically-based animation[C]// Proceedings of ACM Symposium on Computer Animation 2002. San Antonio, 2002.
[60] NVIDIA: CUDA programming guide 1.0[EB/OL]. (2007). http://developer.nvidia.com/ object/cuda.html.
[61] The Khronos Group Releases OpenCL 1.0 Specification [EB/OL]. (2008) http://www.khronos.org/ news/press/releases/the_khronos_group_releases_opencl_1.0_specification/.
[62] Grand S L.Broad-phase collision detection with CUDA[M]. In GPU Gems 3, Addison-Wesley, 2008, 697-721.
[63] Kim D, Heo J P, Huh J, Kim J, Yoon S E.HPCCD: Hybrid parallel continuous collision detection using cpus and gpus[J]. Proceedings of Pacific Graphics 2009, Computer Graphics Forum (S0167-7155), 2009, 28(7): 1791-1800.
[64] Pabst S, Koch A, Strasser W.Fast and scalable CPU/GPU collision detection for rigid and deformable surfaces[C]. Computer Graphics Forum, 2010, 29(5): 1605-1612.
[65] Lauterbach C, Mo Q, Manocha D. gProximity: Hierarchical GPU-based operations for collision and distance queries[C]// Proceedings of Eurographics 2010, Norrkoping, Computer Graphics Forum, 2010, 29(2): 419-428.
[66] Liu F C, Harada T, Lee Y, Kim Y J. Real-time collision culling of a million bodies on graphics processing units[J]. Proceedings of ACM SIGGRAPH ASIA2010, ACM Transactions on Graphics, 2010, 29(6), Article No. 154.
[67] Baraff D.Dynamic simulation of non-penetration rigid bodies [D]. Cornell University, Ithaca, 1992.
[68] Cohen J, Lin M, Manocha D, Ponamgi M.I-COLLIDE: An interactive and exact collision detection system for large-scale environment[C]//Proceedings of ACM Interactive 3D Graphics Conference, 1995:189-196.
[69] Tang M, Manocha D, Lin J, Tong R.F. Collision-Streams: Fast GPU-based collision detection for deformable models[C]//Proceedings symposium Interactive 3D Graphics and Games, 2011: 63-70.
[70] Curtis S, Tamstorf R, Manocha D.Fast collision detection for deformable models using representative- triangels[C]//Proceedings of the 2008 Symposium on Interactive 3D graphics and games, 2008: 61-69.
[71] Pan J, Manocha D.GPU-based parallel collision detection for fast motion planning[J]. Journal of Robotics Research (S0278-3646), 2012, 31(2):187-200.
[72] Gunther J, Popov S, Seidel H P, et al.Realtime ray tracing on GPU with BVH-based packet traversal[C]// Proceedings of IEEE Symposium on Interactive Ray Tracing, 2007: 113-118.
[73] Aila T, Laine S.Understanding the efficiency of ray traversal on GPUs[C]//Proceedings of High Performance Graphics, 2009: 145-149.
[74] Zhang X Y, Kim Y J.Scalable collision detection using p-Partition fronts on many-core processors[J] IEEE Transactions on Visualization and Computer Graphics (S1077-2626), 2014, 20(3): 447-456.
[75] Tang M, Tong R F, Wang Z D, et al.Fast and exact continuous collision detection with Bernstein sign classification[J]. ACM Transactions on Graphics, 2014, 33(6): 186.
[76] Dynamic Benchmarks[DB/OL]. http://gamma.cs.unc.edu/ DYNAMICB/.
[77] FracturingModels[DB/OL].http://sglab.kaist.ac.kr/models/.