Improved Hybrid Bounding Box Collision Detection Algorithm

doi:10.16182/j.issn1004731x.joss.201811023

Abstract

Abstract: For the construction of the oriented bounding box (OBB) takes a long time and the efficiency of the scene collision detection algorithm is not high, a fast-adaptive hybrid bounding box collision detection algorithm is proposed, which optimizes the bounding box of hierarchy and the way of storage. A large number of objects that cannot be intersected are excluded by means of the eight-tree space division and the rough detection of the sphere, and the exact intersecting test of the OBB can be made. The experimental result shows that compared with the OBB algorithm, the complexity of the bounding box construction is reduced, and the more the number of objects in the scene, the higher the accuracy of collision detection.

Key words: collision detection, space division, hybrid bounding box, spheres, oriented bounding box (OBB)

CLC Number:

TP391.9

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.

References

[1] Pi Xuexian, Yang Xudong, Li Sikun.High-perform ance navigation and rendering of very-largescale landscape and seascape[C]//Computer A ided Design and Computer Graphics,2005 Ninth International Conference, 2005.
[2] SONG Tao, SHU Tao, MEI Zhao, et al.A Collision Detection Algorithm Based on Spatial Partitioning and Hybrid Bounding B[J]. Firepower and Command Control (S1002-0640), 2016, 41(11): 94-97.
[3] JIANG Guangyan.Research and Application of Collision Detection Algorithm Based on Bounding Box [D]. Chengdu: University of Electronic Science and Technology of China, 2012.
[4] M Teschner, S Kimmerle, B Heidelberger, et al.Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPs[J]. IEEE Transactions on Visualization & Computer Graphics (S1077-2626), 2002, 4(1): 21-36.
[5] LAI K-C, KANG S-C.Collision detection strategies for virtual construction simulation[J]. Automation in Construction(S0926-5805), 2009, 18(6): 724-736.
[6] GAN Jianhong, PENG Qiang, DAI Pei-dong, et al.Improved Collision Detection Algorithm Based on Oriented Bounding Box[J]. Journal of System Simulation(S1004-731X), 2010, 23(10): 2169-2173.
[7] DIMITORY D, KNAUER C, KRIEGEL K, et al.Bounds on the quality of the PCA bounding boxes[C]. Computational Geometry: Theory and Applications. Amsterdam: Elsevier, 2009, 42(8): 772-789.
[8] WANG Wei, MA Jun, LIU Wei.Research and Application of Collision Detection Based on Oriented Bounding Box[J]. Computer Simulation (S1006-9348), 2009, 26(9): 180-183.
[9] YU Haijun, MA Chunyong, ZHANG Tao, et al.Fast collision detection algorithm based on image space[J]. Journal of Computer Applications (S1001-9081), 2013, 33(2): 530-533.
[10] CHEN Chen, ZHANG Weiming, CHU Ning.Optimized collision detection algorithm based on bounding volume hierarchy and triangular facets[J]. Manufacturing Technology and Machine Tools (S1005-2402), 2013.
[11] Wang Wei, Zhou Cheng, Yang Yun, et al.Virtual Maintenance-oriented collision detection algorithm[J]. Computer Applications and Software (S1000-386X), 2016, 33(4): 235-238.
[12] GUO Lingyun, ZHENG Yanbin, LIU Jingjing.Fast collision detection algorithm based on spatio--temporal correlation[J]. Computer Applications and Software (S1000-386X), 2013, 30(5): 174-176.
[13] JIANG Xiaolu, LIU Yuan.New collision detection algorithm based on hybrid hierarchical bounding box[J]. Computer Engineering and Applications (S1002-8331), 2012, 48(6): 143-145.
[14] SHI Xusheng, QIAO Lihong, ZHU Zuowei.Algorithm of Collision Detection Based on Improved Orieted Bounding Box[J]. Journal of Hunan University(Natural Sciences)(S1674-2974), 2014, 41(5): 26-31.