Benchmarking Contact Detection Algorithms Used in Polyhedral Particle System
Yuval Keissar, Michael H. Gardner, Nicholas Sitar · International Journal for Numerical and Analytical Methods in Geomechanics · 2025
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.