On Minkowski difference-based contact detection in discrete/discontinuous modelling of convex polygons/polyhedra: Algorithms and implementation

Abstract

Purpose

Contact detection for convex polygons/polyhedra has been a critical issue in discrete/discontinuous modelling, such as the discrete element method (DEM) and the discontinuous deformation analysis (DDA). The recently developed 3D contact theory for polyhedra in DDA depends on the so-called entrance block of two polyhedra and reduces the contact to evaluate the distance between the reference point to the corresponding entrance block, but effective implementation is still lacking.

Design/methodology/approach

In this paper, the equivalence of the entrance block and the Minkowski difference of two polyhedra is emphasised and two well-known Minkowski difference-based contact detection and overlap computation algorithms, GJK and expanding polytope algorithm (EPA), are chosen as the possible numerical approaches to the 3D contact theory for DDA, and also as alternatives for computing polyhedral contact features in DEM. The key algorithmic issues are outlined and their important features are highlighted.

Findings

Numerical examples indicate that the average number of updates required in GJK for polyhedral contact is around 6, and only 1 or 2 iterations are needed in EPA to find the overlap and all the relevant contact features when the overlap between polyhedra is small.

Originality/value

The equivalence of the entrance block in DDA and the Minkowski difference of two polyhedra is emphasised; GJK- and EPA-based contact algorithms are applied to convex polyhedra in DEM; energy conservation is guaranteed for the contact theory used; and numerical results demonstrate the effectiveness of the proposed methodologies.

Citation

Feng, Y.T. and Tan, Y. (2020), "On Minkowski difference-based contact detection in discrete/discontinuous modelling of convex polygons/polyhedra: Algorithms and implementation", Engineering Computations, Vol. 37 No. 1, pp. 54-72. https://doi.org/10.1108/EC-03-2019-0124