Benchmarking Contact Detection Algorithms Used in Polyhedral Particle System
Open Access
- 29 September 2025
- journal article
- Published by Wiley in International Journal for Numerical and Analytical Methods in Geomechanics
- Vol. 50 (1) , 53-64
Abstract
A critical assessment of contact detection algorithms routinely used for simulating convex polyhedra in the Discrete Element Method is presented herein. Specifically, we focus on accuracy and computational efficiency and discuss the advantages and limitations of four different algorithms: the coupled Gilbert–Johnson–Keerthi – Expanding Polytope Algorithm (GJK‐EPA), Fast Common Plane coupled with the Intersection Polygon Method (FCP‐IPM), GJK‐EPA coupled with IPM (GJK‐EPA‐IPM), and the Linear Programming Algorithm (LP). These algorithms were implemented within the same open source software framework to allow an objective assessment of their performance. Although in this case the Discrete Element Method (DEM) is used as the particulate solver, the characteristics of the selected contact detection algorithms are independent of this choice. The results show that the GJK‐EPA algorithm, although often preferred for its speed, lacks the necessary accuracy to reproduce the physics of even a very simple dynamic problem. The same issue arises with all the other algorithms except the modified FCP‐IP algorithm. These results raise serious concerns about the veracity of results of dynamic analyses involving simulations involving large assemblies of polyhedral particles in which any of these algorithms have been or are being used. Unfortunately, in many situations, an empirical assessment of the behavior of the assembly will have masked the inherent inaccuracy of the results.Keywords
Funding Information
- National Science Foundation (CMMI‐2342788)
This publication has 27 references indexed in Scilit:
- waLBerla: A block-structured high-performance framework for multiphysics simulationsComputers & Mathematics with Applications, 2021
- Contact theoryScience China Technological Sciences, 2015
- Optimal parameters for a hierarchical grid data structure for contact detection in arbitrarily polydisperse particle systemsComputational Particle Mechanics, 2014
- Energy-conserving contact interaction models for arbitrarily shaped discrete elementsComputer Methods in Applied Mechanics and Engineering, 2012
- An algebraic approach to continuous collision detection for ellipsoidsComputer Aided Geometric Design, 2011
- Shortest link method for contact detection in discrete element methodInternational Journal for Numerical and Analytical Methods in Geomechanics, 2006
- A fast contact detection algorithm for 3-D discrete element methodComputers and Geotechnics, 2004
- Efficient Collision Detection for Moving Ellipsoids Using Separating PlanesComputing, 2004
- An augmented spatial digital tree algorithm for contact detection in computational mechanicsInternational Journal for Numerical Methods in Engineering, 2002
- NBS contact detection algorithm for bodies of similar sizeInternational Journal for Numerical Methods in Engineering, 1998