Collision Detection Algorithm Based on Data Parallelism

Authors: Zhen Peng, Baifeng Wu

Abstract:

Modern computing technology enters the era of parallel computing with the trend of sustainable and scalable parallelism. Single Instruction Multiple Data (SIMD) is an important way to go along with the trend. It is able to gather more and more computing ability by increasing the number of processor cores without the need of modifying the program. Meanwhile, in the field of scientific computing and engineering design, many computation intensive applications are facing the challenge of increasingly large amount of data. Data parallel computing will be an important way to further improve the performance of these applications. In this paper, we take the accurate collision detection in building information modeling as an example. We demonstrate a model for constructing a data parallel algorithm. According to the model, a complex object is decomposed into the sets of simple objects; collision detection among complex objects is converted into those among simple objects. The resulting algorithm is a typical SIMD algorithm, and its advantages in parallelism and scalability is unparalleled in respect to the traditional algorithms.

Keywords: Data parallelism, collision detection, single instruction multiple data, building information modeling, continuous scalability.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1129097

References:

[1] X. Yang, T. M. Wang and D. Q. Xu, "Fast BVH construction on GPU," Journal of Zhejiang University, vol. 46, pp. 84-89, 2012.
[2] D. Peng, T. Min and A. T. Ruofeng, "Parallel Collision Detection on Multi-core Platform," Jisuanji Fuzhu Sheji Yu Tuxingxue Xuebao/Journal of Computer-Aided Design and Computer Graphics, vol. 23, pp. 833-838, 2011.
[3] M. Tang, M. Dinesh, R. F. Tong, "Parallel Collision Detection Between Deformable Objects Using SIMD Instructions," Chinese Journal of Computers, vol. 32, pp. 2042-2051, 2009.
[4] W. Zhao and L. Li, "A New K-DOPs Collision Detection Algorithms Improved by GA," in International Conference on Wireless Communications and Applications, 2011, pp. 58-68.
[5] W. Zhao, C. Chen and L. Li, "The Collision Detection Algorithm Based on the MapReduce of Cloud Computing," System simulation technology and its application Changchun, 2010, pp. 96-100.
[6] W. Zhao, C. Chen and L. Li, "Parallel Collision Detection Algorithm Based on OBB Tree and MapReduce," in Entertainment for Education. Digital Techniques and Systems: 5th International Conference on E-learning and Games, Edutainment 2010, Changchun, China, August 16-18, 2010. Proceedings, X. Zhang, S. Zhong, Z. Pan, K. Wong, and R. Yun, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010, pp. 610-620.
[7] J. Pan and D. Manocha, "GPU-Based Parallel Collision Detection for Real-Time Motion Planning," Springer Tracts in Advanced Robotics, vol. 68, pp. 211-228, 2010.
[8] M. Anderson, M. Brodowicz, L. Dalessandro, J. DeBuhr, and T. Sterling, "A Dynamic Execution Model Applied to Distributed Collision Detection," in Supercomputing: 29th International Conference, ISC 2014, Leipzig, Germany, June 22-26, 2014. Proceedings, J. M. Kunkel, T. Ludwig and H. W. Meuer, Eds. Cham: Springer International Publishing, 2014, pp. 470-477.
[9] P. Cai, C. Indhumathi, Y. Cai, J. Zheng, Y. Gong, S. L. Teng, and W. Peng, "Collision Detection Using Axis Aligned Bounding Boxes" Springer Singapore, 2014, pp. 1-14.
[10] R. Erbes, A. Mantel, E. Schömer, and N. Wolpert, "Parallel Collision Queries on the GPU," Lecture Notes in Computer Science, vol. 7686, pp. 84-95, 2013.
[11] Y. J., P. J. and B. M., "GPU-based collision detection for sampling-based motion planning," in Ubiquitous Robots and Ambient Intelligence (URAI), 2013 10th International Conference on, 2013, pp. 215-218.
[12] Y. Zou, X. Zhou, G. Ding, Y. He, M. Jia, "A GPGPU-Based Collision Detection Algorithm," in Image and Graphics, 2009. ICIG '09. Fifth International Conference on, 2009, pp. 938-942.
[13] X. Zhang, YJ. Kim, "Interactive Collision Detection for Deformable Models Using Streaming AABBs," IEEE Transactions on Visualization and Computer Graphics, vol. 13, pp. 318-329, 2007-01-01 2007.
[14] HA. Aly, QAE. Elawady, "A new narrow phase collision detection algorithm using height projection," in Education and Research Conference (EDERC), 2010 4th European, 2010, pp. 111-115.
[15] X. Zhang, YJ. Kim, "Scalable Collision Detection Using p-Partition Fronts on Many-Core Processors," IEEE Transactions on Visualization and Computer Graphics, vol. 20, pp. 447-456, 2014-01-01 2014.
[16] X. Liu and L. Cao, "Parallel Octree Collision Detection Based on MPI," Journal of Computer-Aided Design & Computer Graphics, pp. 184-187+192, 2007-02-28 2007.
[17] T. H. Wong, G. Leach and F. Zambetta, "An adaptive octree grid for GPU-based collision detection of deformable objects," The Visual Computer, vol. 30, pp. 729-738, 2014-01-01 2014.
[18] F. Tsuda, R. Nakamura, "A Technique for Collision Detection and 3D Interaction Based on Parallel GPU and CPU Processing," in Games and Digital Entertainment (SBGAMES), 2011 Brazilian Symposium on, 2011, pp. 36-42.
[19] R. Xu, L. Kang, H. Tian., "A G-Octree Based Fast Collision Detection for Large-Scale Particle Systems," in Computer Science and Electronics Engineering (ICCSEE), 2012 International Conference on, 2012, pp. 269-273.
[20] W. Fan, B. Wang, J. Paul, and J. Sun, "An octree-based proxy for collision detection in large-scale particle systems," Science China Information Sciences, vol. 56, pp. 1-10, 2013-01-01 2013.
[21] O. S. Lawlor and L. V. Kalée, "A voxel-based parallel collision detection algorithm,", 2002, pp. 285-293.
[22] G. Baciu, WSK. Wong, "Image-based techniques in a hybrid collision detector," IEEE Transactions on Visualization and Computer Graphics, vol. 9, pp. 254-271, 2003-01-01 2003.
[23] H. Jang and J. Han, "Fast collision detection using the A-buffer," The Visual Computer, vol. 24, pp. 659-667, 2008-01-01 2008.
[24] L. Wang, Y Shi, R. Li, "An image-based collision detection optimization algorithm," in Signal and Information Processing (ChinaSIP), 2015 IEEE China Summit and International Conference on, 2015, pp. 220-224.
[25] R. E. Ladner and M. J. Fischer, "Parallel Prefix Computation," Journal of the ACM, vol. 27, pp. 831-838, 1980-01-01 1980.
[26] R. P. Brent, "The Parallel Evaluation of General Arithmetic Expressions," Journal of the ACM, vol. 21, pp. 201-206, 1974-01-01 1974.