Top

Evolutionary Intelligence

Published in:

01-02-2021 | Special Issue

An improved optimal algorithm for collision detection of hybrid hierarchical bounding box

Authors: Baiqiang Gan, Qiuping Dong

Published in: Evolutionary Intelligence | Issue 4/2022

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Collision detection is currently a hot issue in virtual reality and other fields. The efficiency and accuracy of collision detection directly affect the real-time update effect of the virtual reality environment, and it is also an important indicator that affects the user's interactive experience. In a complex virtual reality scene, if the traditional collision detection algorithm (Sphere-OBB) is adopted and the tree structure traversal is used to realize the bounding box traversal detection, the accuracy remains unchanged, but the detection complexity is reduced. If the RAPID collision detection algorithm is used, the separated axis test method and the two-layer hybrid hierarchical surrounding tree structure are used, although the amount of calculation is large, the detection efficiency is improved. Using the separation axis (SAT) algorithm and using the separation axis theorem to determine the vector axis can save a lot of calculation time. The purpose of this research is to propose an improved hybrid-level bounding box collision detection optimization algorithm (ASO) based on the traditional hybrid-level bounding box collision detection algorithm. Firstly, based on the spatio-temporal correlation theory, the hybrid hierarchical bounding box hierarchical tree structure is improved to AABB and OBB from top to bottom. The synchronous descent rule is used to realize the traversal of nodes, and then the triangle area weighting method is used to improve the calculation method of the bottom OBB bounding box node center, solve the bounding box vertex covariance matrix, and improve the efficiency and accuracy of collision detection. The experimental results show that the algorithm proposed in this paper is 35.6% faster than the RAPID detection speed and 29.9% faster than the separation axis (SAT) detection speed under the same accuracy. In the multi-object collision detection, compared with the latest research, the algorithm in this paper shortens the intersection detection time, improves the collision detection efficiency, and meets the real-time update requirements of complex virtual reality scenes.

previous article Design of distributed temperature-measuring system based on 1-wire bus for ultra-kilometre frozen deep well

next article Distributed optimal dispatch of integrated electricity and natural gas system considering the pipeline storage characteristics

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Lv Z (2020) Virtual reality in the context of Internet of Things. Neural Comput Appl 32:9593–9602CrossRef

Wohlgenannt I, Simons A, Stieglitz S (2020) Virtual reality. Bus Inf Syst Eng 62:455–461CrossRef

Li R, Xu D (2020) Distribution of landscape architecture based on 3D images and virtual reality rationality study. IEEE Access 8:140161–140170CrossRef

Carol M, Huttar KBS (2020) Virtual reality and computer simulation in social work education: a systematic review. J Social Work Educ 56(1):131–141CrossRef

Xing D, Liu F, Liu S, Xu D (2018) Efficient collision detection and detach control for convex prisms in precision manipulation. IEEE Trans Ind Inf 14(12):5316–5326CrossRef

Hui YQ, Wen HL, Wei Z (2020) Human-vehicle collision detection algorithm based on image processing. Int J Patt Recogn Artif Intell 34(8):2055015CrossRef

Römer UJ, Fidlin A, Seemann W (2020) The normal parameterization and its application to collision detection. Mech Mach Theory 151:103906CrossRef

Wang F, Qian Z, Lin Y, Zhang W (2020) Design and rapid construction of a cost-effective virtual haptic device. IEEE/ASME Trans Mechatron. https://doi.org/10.1109/TMECH.2020.3001205CrossRef

Liu G, Huang X, Guo W (2015) Multilayer obstacle-avoiding X-architecture Steiner minimal tree construction based on particle swarm optimization. IEEE Trans Cybern 45(5):989–1002

10.

Jong MK, Yeongho S, Hoe MK, Taesoo K (2020) Interactive character posing with efficient collision handling. Comput Anim Virtual Worlds 30(3):e1923

11.

Wang X, Zhang J, Zhang W (2020) The distance between convex sets with Minkowski sum structure: application to collision detection. Comput Optim Appl 77:465–490MathSciNetMATHCrossRef

12.

Xie M, Niu X (2020) A 3D roaming and collision detection algorithm applicable for massive spatial data. PLoS One 15(2):e0229038CrossRef

13.

Li J, Wang MY (2017) Optimization of hybrid hierarchical bounding box collision detection algorithm under the background of big data. J Jilin Univ (Sci Ed) 553(3):673–677

14.

Kabanov AA, Tokarev DA (2020) Collision detection and avoidance method for two cooperative robot manipulators. In: IOP conference series: materials science and engineering, vol 709, pp 044021

15.

Jin YX, Cheng QF, Zhang JR, Qi X, Ma B, Jia Y (2020) Self-collision detection algorithm based on fused DNN and AABB-circular bounding box. J Image Graph 25(8):1674–1683

16.

Zheng XX, Xie MH, Zhang YY (2017) Fast collision detection algorithm based on spatial partition and linear programming. Comput Eng Appl 53(23):236–240

17.

Guo Y, Wang J, Zhou X, Tan Z, Qiu K (2020) A hybrid framework based on warped hierarchical tree for pose estimation of texture-less objects. IEEE Access 8:179813–179822CrossRef

18.

Floyd MC, Christophe D, Taku K (2020) Binary ostensibly-implicit trees for fast collision detection. Comput Graph Forum 39(2):509–521CrossRef

19.

Yu RY, Zhao JL (2018) Collision detection algorithm based on axis aligned bounding box and space partition. Chin J Image Graph 23(12):1925–1937

20.

Tang YH, Hou J, Wu TT et al (2018) Hybrid collision detection algorithm based on particle transformation and bounding box. J Harbin Eng Univ 39(10):1695–1701

21.

Xiao L, Mei G, Cuo MSl (2020) Comparative investigation of GPU-accelerated triangle–triangle intersection algorithms for collision detection. Multimed Tools Appl. https://doi.org/10.1007/s11042-020-09066-3CrossRef

22.

Wang H, Zhang X, L. Zhou X (2020) Intersection detection algorithm based on hybrid bounding box for geological modeling with faults. IEEE Access 8:29538–29546CrossRef

23.

Jin YX, Qin ZP, Li Z (2017) Collision detection algorithm for deformable body based on R-sphere bounding sphere. Comput Eng Des 38(1):92–96

24.

Xu J, Liu Z, Yang C, Li L, Pei Y (2020) A pseudo-distance algorithm for collision detection of manipulators using convex-plane-polygons-based representation. Robot Comput Integrat Manuf 66:10199

25.

Tang M, Tong R, Wang W, Manocha D (2014) Fast and exact continuous collision detection with Bernstein sign classification. ACM Trans Graph 33(6):1–8MATHCrossRef

26.

Tian Y, Li Y, Pan L, Morris H (2020) Research on group animation design technology based on artificial fish swarm algorithm. J Intell Fuzzy Syst 38:1137–1145CrossRef

27.

Park J, Baek H (2020) Stereo vision-based obstacle collision avoidance for a quadrotor using ellipsoidal bounding box and hierarchical clustering. Aerosp Sci Technol 103:105882CrossRef

28.

Capellman J, Salin L (2020) Collision detection. MonoGame mastery. Apress, BerkeleyCrossRef

29.

Xia C, Zhang B, Wang H, Qiao S, Zhang A (2020) A minimum-volume oriented bounding box strategy for improving the performance of urban cellular automata based on vectorization and parallel computing technology. GIScience Remote Sens 57(1):91–106CrossRef

30.

Song T, Shu T, Mei Z et al (2016) A collision detection algorithm based on spatial partitioning and hybrid bounding box. Firepower Command Control 41(11):94–97

31.

Weghorst H, Hooper G, Greenberg DP (1984) Improved computational methods for ray tracing. ACM Trans Comput Graph 3(1):52–69CrossRef

32.

Gottschalk S, Lin M, Manocha D (1996) OBB Tree: a hierarchical structure for rapid interference detection. In: Proceedings of the 23rd annual conference on computer graphics and interactive techniques, pp 171–180

33.

Liu D, Shi G (2020) Ship collision risk assessment based on collision detection algorithm. IEEE Access 8:161969–161980CrossRef

34.

Friston SJ, Steed A (2018) Real-time collision detection for deformable characters with radial fields. IEEE Trans Visual Comput Graph 99:1–12

35.

Malzer C, Baum M (2020) A hybrid approach to hierarchical density-based cluster selection. In: 2020 IEEE international conference on multisensor fusion and integration for intelligent systems (MFI). Karlsruhe, Germany, pp 223–228

36.

Chen C, Pan Y, Li D, Zhang S, Zhao Z, Hong J (2020) A virtual-physical collision detection interface for AR-based interactive teaching of robot. Robot Comput Integr Manuf 64:101948CrossRef

37.

Geng C, Gao F (2018) An improved algorithm of the collision detection based on OBB. In: 2018 Second international conference of sensor network and computer engineering. Atlantis Press, pp 35–38

38.

Qian J, Zheng Y, Qi D (2020) Multi-scale rotated bounding box-based deep learning method for electric railway detection. In: 2020 39th Chinese control conference (CCC), Shenyang, China, pp 7166–7171

39.

Wang C, Zhang ZL, Long Y, Wang SD (2018) Improved hybrid bounding box collision detection algorithm. J Syst Simul 30(11):4236–4243

40.

Melero FJ, Aguilera Á, Feito FR (2019) Fast collision detection between high resolution polygonal models. Comput Graph 83:97–106CrossRef

41.

Zhang H, Zhang P, Hou H (2019) An improved collision detection algorithm for hair simulation study. In: 2019 IEEE 3rd advanced information management, communicates, electronic and automation control conference, Chongqing, China, pp 1408–1411

Title: An improved optimal algorithm for collision detection of hybrid hierarchical bounding box
Authors: Baiqiang Gan
Qiuping Dong
Publication date: 01-02-2021
Publisher: Springer Berlin Heidelberg
Published in: Evolutionary Intelligence / Issue 4/2022
Print ISSN: 1864-5909
Electronic ISSN: 1864-5917
DOI: https://doi.org/10.1007/s12065-020-00559-6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 4/2022

Construction of cascaded depth model based on boosting feature selection and classification

A comparative analysis of meta-heuristic optimization algorithms for feature selection and feature weighting in neural networks

An algorithm for solving FEVM problem based on SPSO algorithm

The analysis and research of STEAM education based on the TAM algorithm model to improve the learning effectiveness of higher vocational engineering students

A new differential evolution algorithm for cooperative fuzzy rule mining: application to anomaly detection

Simulation of urban pattern evolution trend based on satellite GIS and remote sensing

Premium Partner