Arc forward intersection decomposition: an exact and efficient algorithm for convex polyhedral contact detection
Journal
Computers and Geotechnics
Journal Volume
192
Start Page
107886
ISSN
0266352X
Date Issued
2026-04
Author(s)
Abstract
Contact detection between convex polyhedra is a central challenge in discrete element method (DEM) simulations. The common plane (CP) approach provides a rigorous framework, and the non-iterative CP formulation by Chang and Chen (2008) guarantees exact solutions. However, its direct implementation has been hindered by high computational complexity. To overcome this bottleneck, this paper introduces the Arc Forward Intersection Decomposition (AFID) algorithm, a novel procedure that achieves both exactness and efficiency in CP contact detection. AFID reduces the complexity of Gaussian map merging to near-linear order by selectively decomposing arc intersections through localized searches based on control vertex data. Numerical experiments demonstrate that AFID consistently identifies the true global maximum of the gap function while significantly reducing computational time, outperforming traditional iterative schemes that are prone to local extrema. Moreover, AFID is especially advantageous for geometrically complex models because it focuses only on the arc intersections that determine contact. By enabling exact and scalable polyhedral contact detection, AFID establishes a robust foundation for large-scale DEM simulations and for constructing benchmark datasets with ground truth, which are essential for advancing AI-based approaches to contact modelling.
Subjects
Common plane
Contact detection
Convex polyhedra
Discrete elements
Gaussian map
Non-iterative algorithm
Publisher
Elsevier Ltd
Type
journal article