Journal of System Simulation ›› 2017, Vol. 29 ›› Issue (11): 2601-2608.doi: 10.16182/j.issn1004731x.joss.201711001
Special Issue: 特约稿件
Liu Fuchang, Wang Shuangjian, Pan Zhigeng, Wang Jinrong
Received:
2016-05-12
Published:
2020-06-05
CLC Number:
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 4th 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 16th 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/. |
[1] | Lin Ma, Xuesong Zhang, Xinlin Lei, Tie Bao. Design and Implementation of A Hybrid Solver on CPU and GPU Multi-target Machines [J]. Journal of System Simulation, 2022, 34(4): 670-678. |
[2] | Shu Liang, Zhang Jie, Yang Yanfang, Yang Miao, Wu Ziran. Dynamic Control of Twin-workshop Model of Circuit Breaker Considering Takt Time Constraints [J]. Journal of System Simulation, 2021, 33(6): 1277-1287. |
[3] | Jia Chunyang, Zou Xiangjun, Li Jinhui, Zeng Zeqin, Wang Jie. Interactive Assembly Simulation Platform for Complex Gearbox in Virtual Environmen [J]. Journal of System Simulation, 2020, 32(9): 1736-1743. |
[4] | Xie Cui, Geng Junmei, Li Jian, Dong Junyu. Surgery Simulation of Internal Fixation for Compression Fractures [J]. Journal of System Simulation, 2019, 31(7): 1351-1357. |
[5] | Li Xing, Fu Yanfang, Wang Liang, Lu Chengtao. Dynamic Collision Optimization Algorithm Based on Ray Detection [J]. Journal of System Simulation, 2019, 31(11): 2393-2401. |
[6] | Shi Min, Wang Junzheng, Mao Tianlu, Liu Yaning. Physically-based Interactive Virtual Clothing Animation Simulation [J]. Journal of System Simulation, 2018, 30(7): 2583-2592. |
[7] | Jing Qianfeng, Shen Helong, Yin Yong, Liu Xiuwen. Real-time Collision Detection of Coastline in Navigation Simulator [J]. Journal of System Simulation, 2018, 30(7): 2682-2688. |
[8] | Wang Chao, Zhang Zhili, Long Yong, Wang Shaodi. Improved Hybrid Bounding Box Collision Detection Algorithm [J]. Journal of System Simulation, 2018, 30(11): 4236-4243. |
[9] | Shao Xuqiang, Song Yu. Real-time Simulation of Realistic Melting in Fluid-solid Interaction [J]. Journal of System Simulation, 2017, 29(3): 502-508. |
[10] | XueChuanyu, Dong Hongwei, Zhang Mingmin, Pan Zhigeng. Real-time Simulation on Virtual Dressing Based On Virtual Human Body Model [J]. Journal of System Simulation, 2017, 29(11): 2847-2855. |
[11] | Xiang Nan, Zhang Mingmin, Zhu Lingyun. Paralleled Dynamic Crowd Emotion Contagion Algorithm [J]. Journal of System Simulation, 2016, 28(9): 1964-1969. |
[12] | Zhai Xiaoming, Yin Yong, Shen Helong. Real-time Rendering of Large-scale River in Inland River Ship Simulator [J]. Journal of System Simulation, 2016, 28(9): 2023-2028. |
[13] | Li Wei, Wang Pengjie, Song Haiyu. Survey on Pedestrian Detection Based on Statistical Classification [J]. Journal of System Simulation, 2016, 28(9): 2186-2194. |
[14] | Wang Jun, Liu Dong. Research on Cholecystectomy Virtual Surgery Simulation Training Platform [J]. Journal of System Simulation, 2016, 28(8): 1853-1862. |
[15] | Han Min, Zhang Haichao, Bian Maosong, Zheng Danchen. Flow Visualization Based on Enhanced Streamline Line Integral Convolution [J]. Journal of System Simulation, 2016, 28(12): 2933-2938. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||