This article provides a review of the state-of-the-art techniques for collision detection in multibody dynamics, highlighting the unique requirements and constraints of engineering simulations. Specifically, the article compares the most popular narrow-phase algorithms which are widely used for distance computation and intersection testing between convex shapes. Additionally, broad-phase algorithms are examined in detail, emphasizing their role in reducing computational complexity during pairwise collision checks. Part of the article is dedicated to the collision detection of concave shapes, frequently encountered in multibody dynamics where geometries are often imported from CAD tools as highly detailed and complex models. Furthermore, the article identifies several open problems in the field, such as the need for scalable algorithms capable of handling large-scale systems with high degrees of freedom, handling of deformable bodies, better integration with modern CAD workflows and GPU computing.
CundallPAStrackODL. A discrete numerical model for granular assemblies. Geotechnique1979; 29: 47–65.
2.
GilbertEGJohnsonDWKeerthiSS. A fast procedure for computing the distance between complex objects in three-dimensional space. IEEE J Robot Autom1988; 4: 193–203.
3.
CohenJLinMManochaD, et al.I-COLLIDE: an interactive and exact collision detection system for large-scale environments. In Proceedings of the 1995 symposium on Interactive 3D graphics. ACM, p. 189.
4.
GottschalkSLinMManochaD. OBBTree: a hierarchical structure for rapid interference detection. In: Proceedings of the 23rd annual conference on computer graphics and interactive techniques, pp. 171–180.
5.
FloresPAmbrósioJ. On the contact detection for contact-impact analysis in multibody systems. Multibody Syst Dyn2010; 24: 103–122.
6.
AcaryVBrogliatoB. Numerical methods for nonsmooth dynamical systems: applications in mechanics and electronics. Vol. 35. Berlin: Springer Science & Business Media, 2008.
7.
TasoraAMangoniDBenattiS, et al.Solving variational inequalities and cone complementarity problems in nonsmooth dynamics using the alternating direction method of multipliers. Int J Numer Methods Eng2021; 122: 4093–4113.
8.
LinMCannyJF. A fast algorithm for incremental distance calculation. In: ICRA. Vol. 91. pp. 9–12.
9.
MirtichB. V-clip: fast and robust polyhedral collision detection. ACM Transactions On Graphics (TOG)1998; 17: 177–208.
10.
Van Den BergenG. A fast and robust GJK implementation for collision detection of convex objects. J Graph Tools1999; 4: 7–25.
11.
Van Den BergenG. Proximity queries and penetration depth computation on 3D game objects. In Game developers conference. Vol. 170. p. 209.
12.
SnethenG. Xenocollide: complex collision made simple. In: Jacobs S (ed) Game programming gems 7. Charles River Media, 2008, pp. 165–178.
13.
AvrilQGourantonVArnaldiB. New trends in collision detection performance. In: VRIC. Vol. 11. p. 53.
14.
López-Adeva Fernández-LayosPMerchanteLF. Convex body collision detection using the signed distance function. Computer-Aided Design2024; 170: 103685
15.
LopesDSSilvaMTAmbrosioJA, et al.A mathematical framework for rigid contact detection between quadric and superquadric surfaces. Multibody Syst Dyn2010; 24: 255–280.
16.
PazoukiAMazharHNegrutD. Parallel collision detection of ellipsoids with applications in large scale multibody dynamics. Math Comput Simul2012; 82: 879–894.
17.
Van Den BergenG. Collision detection in interactive 3D environments. US: CRC Press, 2003.
BlinnJF. A generalization of algebraic surface drawing. ACM Trans Graph1982; 1: 235–256.
20.
OleynikovaHMillaneATaylorZ, et al. Signed distance fields: a natural representation for both mapping and planning. In: RSS 2016 workshop: geometry and beyond-representations, physics, and scene understanding for robotics. University of Michigan, p. 1.
21.
FuhrmannASobotkaGGroßC. Distance fields for rapid collision detection in physically based modeling. In Proceedings of GraphiCon. Vol. 2003. Citeseer, pp. 58–65.
22.
MacklinMErlebenKMüllerM, et al.Local optimization for robust signed distance field collision. Proc ACM Comput Graph Interact Tech2020; 3: 8:1–8:17.
23.
ErlebenK. Methodology for assessing mesh-based contact point methods. ACM Trans Graphcs (TOG)2018; 37: 1–30.
24.
NarangYStoreyKAkinolaI, et al.Factory: fast contact for robotic assembly. arXiv preprint arXiv:220503532, 2022.
25.
XuHBarbičJ. Continuous collision detection between points and signed distance fields. In: Workshop on virtual reality interaction and physical simulation. Vol. 8. p. 1.
26.
BridsonRFedkiwRAndersonJ. Robust treatment of collisions, contact and friction for cloth animation. In: Proceedings of the 29th annual conference on Computer graphics and interactive techniques. SIGGRAPH ’02. New York, NY: Association for Computing Machinery, pp. 594–603. Available at: https://doi.org/10.1145/566570.566623.
27.
TeschnerMKimmerleSHeidelbergerB, et al.Collision detection for deformable objects. In: Computer graphics forum. Vol. 24. Wiley Online Library, pp. 61–81.
28.
CurtisSTamstorfRManochaD. Fast collision detection for deformable models using representative-triangles. In: Proceedings of the 2008 symposium on Interactive 3D graphics and games, pp. 61–69.
29.
BaraffDWitkinAKassM. Untangling cloth. ACM Trans Graph2003; 22: 862–870.
30.
VolinoPMagnenat-ThalmannN. Resolving surface collisions through intersection contour minimization. ACM Trans Graph2006; 25: 1154–1159.
31.
ChoiJRhimSChoiJH. A general purpose contact algorithm using a compliance contact force model for rigid and flexible bodies of complex geometry. Int J Non Linear Mech2013; 53: 13–23.
32.
ChoiJRyuHSKimCW, et al.An efficient and robust contact algorithm for a compliant contact force model between bodies of complex geometry. Multibody Syst Dyn2010; 23: 99–120.
33.
SnyderJM. Interval analysis for computer graphics. In: Proceedings of the 19th annual conference on computer graphics and interactive techniques, pp. 121–130.
34.
RedonSKheddarACoquillartS. Fast continuous collision detection between rigid bodies. In: Computer graphics forum. Vol. 21. Wiley Online Library, pp. 279–287.
35.
ProvotX. Collision and self-collision handling in cloth model dedicated to design garments. In: Computer animation and simulation’97: proceedings of the eurographics workshop in Budapest, Hungary, 2–3 September 1997, pp. 177–189. Springer.
36.
WangZTangMTongR, et al.Tightccd: efficient and robust continuous collision detection using tight error bounds. In: Computer graphics forum, Vol. 34. Wiley Online Library, pp. 289–298.
TangMTongRWangZ, et al.Fast and exact continuous collision detection with Bernstein sign classification. ACM Trans Graph2014; 33: 1–8.
39.
WangBFergusonZSchneiderT, et al.A large-scale benchmark and an inclusion-based algorithm for continuous collision detection. ACM Trans Graph2021; 40: 1–16.
40.
LiMFergusonZSchneiderT, et al.Incremental potential contact: intersection-and inversion-free, large-deformation dynamics. ACM Trans Graph2020; 39.
41.
LöschnerFLongvaAJeskeS, et al.Higher-order time integration for deformable solids. Comput Graph Forum2020; 39: 157–169.
42.
FergusonZLiMSchneiderT, et al.Intersection-free rigid body dynamics. ACM Trans Graph2021; 40: 183:1–183:16.
43.
LanLKaufmanDMLiM, et al.Affine body dynamics: fast, stable & intersection-free simulation of stiff materials. arXiv preprint arXiv:220110022, 2022.
44.
HauserK. Robust contact generation for robot simulation with unstructured meshes. In: Robotics research: the 16th international symposium ISRR, pp. 357–373. Springer.
45.
BergenGvd. Efficient collision detection of complex deformable models using AABB trees. J Graph Tools1997; 2: 1–13.
46.
Le GrandS. Broad-phase collision detection with CUDA. GPU Gems2007; 3: 697–721.
47.
MazharHHeynTNegrutD. A scalable parallel method for large collision detection problems. Multibody Syst Dyn2011; 26: 37–55.
48.
MeisterDOgakiSBenthinC, et al.A survey on bounding volume hierarchies for ray tracing. In: Computer graphics forum. Vol. 40. Wiley Online Library, pp. 683–712.
49.
WaldIBoulosSShirleyP. Ray tracing deformable scenes using dynamic bounding volume hierarchies. ACM Trans Graph2007; 26: 6-es.
50.
TeschnerMHeidelbergerBMüllerM, et al.Optimized spatial hashing for collision detection of deformable objects. In: VMV. Vol. 3, pp. 47–54.
51.
MirtichB. Efficient algorithms for two-phase collision detection. In: Practical motion planning in robotics: current approaches and future directions, 1997.
52.
EitzMLixuG. Hierarchical spatial hashing for real-time collision detection. In: IEEE international conference on shape modeling and applications 2007 (SMI’07), pp. 61–70. IEEE.
LauterbachCMoQManochaD. gproximity: hierarchical GPU-based operations for collision and distance queries. Comput Graph Forum2010; 29: 419–428.
56.
KnottD. CInDeR: collision and interference detection in real time using graphics hardware. Ph.D. Thesis, University of British Columbia, 2003. Available at: https://doi.org/10.14288/1.0051703.
57.
IiiKZaferakisALinM, et al.Fast 3D geometric proximity queries between rigid and deformable models using graphics hardware acceleration. UNC-CH Technical Report TR02-004, 2002.
CoumansE. Bullet physics simulation. In: ACM SIGGRAPH 2015 courses. SIGGRAPH ’15. New York, NY: Association for Computing Machinery, pp. 7:1–7:1. ISBN 9781450336345. Available at: https://doi.org/10.1145/2776880.2792704.
60.
ThomaszewskiBPabstSBlochingerW. Parallel techniques for physically based simulation on multi-core processor architectures. Comput Graph2008; 32: 25–40.
61.
KimDHeoJPHuhJ, et al.HPCCD: gybrid parallel continuous collision detection using cpus and gpus. Comput Graph Forum2009; 28: 1791–1800.
62.
PabstSKochAStraßerW. Fast and scalable cpu/gpu collision detection for rigid and deformable surfaces. Comput Graph Forum2010; 29: 1605–1612.
63.
MazharH. GPU collision detection using spatial subdivision with applications in contact dynamics. In: ASME 2009 international design engineering technical conferences and computers and information in engineering conference, pp. 421–432. American Society of Mechanical Engineers.
64.
LiuFHaradaTLeeY, et al.Real-time collision culling of a million bodies on graphics processing units. ACM Trans Graph2010; 29: 154.
65.
TangMLiuZTongR, et al.PSCC: parallel self-collision culling with spatial hashing on GPUs. Proc ACM Comput Graph Interact Tech2018; 1: 18:1–18:18.
66.
HongYWuWChenH. Real-time collision detection with two-level spatial hashing on GPU. In: Keyser J, Kim YJ and Wonka P (eds) Pacific graphics short papers. The Eurographics Association, p. 1. ISBN 978-3-905674-73-6. Available at: https://doi.org/10.2312/pgs.20141249.
67.
SatheRLakeA. Rigid body collision detection on the GPU. In: ACM SIGGRAPH 2006 research posters. SIGGRAPH ’06. New York, NY: Association for Computing Machinery, pp. 49–52. ISBN 1595933646. Available at: https://doi.org/10.1145/1179622.1179679.
MittalAMangadoddyNBanerjeeR. GPU based discrete element modeling for convex polyhedral shape particles: development and validation. Powder Technol2025; 449: 120407.
70.
WangTChenJLiD, et al.Fast GPU-based two-way continuous collision handling. ACM Trans Graph2023; 42.
71.
CattoE. Iterative dynamics with temporal coherence. In: Game developer conference. Vol. 2, p. 1.
72.
MoravánszkyÁTerdimanP. Fast contact reduction for dynamics simulation. In: Kirmse A (ed) Game programming gems 4. Charles River Media, 2004, pp. 253–263.
73.
AcaryVPérignonF. Siconos: a software platform for modeling, simulation, analysis and control of nonsmooth dynamical systems. SNE Simul News Europe2007; 17: 19–26.
74.
MüllerMChentanezNKimTY, et al.Air meshes for robust collision handling. ACM Trans Graph2015; 34: 1–9.
75.
MyszkowskiKOkunevOGKuniiTL. Fast collision detection between complex solids using rasterizing graphics hardware. Vis Comput1995; 11: 497–511.
76.
GovindarajuNRedonSLinM, et al.CULLIDE: interactive collision detection between complex models in large environments using graphics hardware. In Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on graphics hardware, pp. 25–32. Eurographics Association.
AcaryVBonnefonOBrémondM, et al.An introduction to Siconos. PhD Thesis, INRIA, 2019.
79.
AcaryVBrémondMKapellosK, et al. Mechanical simulation of the exomars rover using siconos in 3DROV. In: ASTRA 2013-12th symposium on advanced space technologies in robotics and automation, p. 1.
80.
CrozetS. Efficient contact determination between solids with boundary representations (B-Rep). PhD Thesis, Université Grenoble Alpes, 2017.
