Contact Detection for Pairs of Ellipses and Ellipsoids: Analysis, Comparisons, and Improvements

RESUME: Ce travail de recherche offre un cadre theorique pour analyser, comparer et ameliorer les algorithmes de detection de contact entre des paires d’ellipses et d’ellipsoides. On se concentre surtout sur la categorie d’algorithmes qui sont les plus efficaces numeriquement, qui peuvent produire des estimations de la distance de separation et de penetration entre des ellipses et des ellipsoides, et qui peuvent definir un point de contact et une direction normale pour calculer les forces, comme necessaires dans les simulations par elements discrets. Plus precisement, seules les representations analytiques des ellipses et ellipsoides sont etudiees et la detection de contact entre des ellipsoides en mouvement n’est pas traitee ici. La premiere contribution est d’offrir un cadre mathematique pour etudier ces algorithmes, plus particulierement les preuves d’existence et d’unicite de solutions pour certaines classes d’algorithmes de detection de contact, pour decrire rigoureusement des paires d’ellipses en contact presque parfait, avec ou sans chevauchement, et pour analyser globalement les contraintes sur les vecteurs normaux. Ce cadre met en valeur le role cle joue par les differentes definitions de contact trouvees dans la litterature, independamment des strategies de calcul utilisees pour calculer les distance de separation ou de penetration. Plus precisement, on montre que tous les algorithmes etudies peuvent etre exprimes comme des problemes de minimisation, avec ou en l’absence de contraintes non saturees sur les vecteurs normaux aux points de contact, et que des contraintes additionnelles peuvent etre utilisees pour identifier le minimum global parmi les points critiques du probleme de minimisation. Une autre contribution de cette recherche, fondee sur le cadre mathematique propose, est une meilleure classification des algorithmes existants. Ces algorithmes sont compares sur des cas test et leurs forces et faiblesses sont mises en evidence et expliquees par rapport a cette classification. L’utilite presentation d’un algorithme performant combinant de nouvelles idees et d’autres plus anciennes. Cette algorithme appartient a la classe des methodes de potentiel geometrique, lesquelles considerent la solution de deux problemes de minimisation pour determiner un point de contact entre les particules. L’efficacite de l’algorithme repose sur plusieurs ingredients, a savoir une transformation qui associe a une paire d’ellipses (ellipsoides) une ellipse (ellipsoide) centree a l’origine et un cercle (une sphere) unitaire, la construction d’un point initial efficace pour la resolution du probleme de minimisation non lineaire, l’utilisation de la methode de Newton pour le probleme de recherche de racine, et l’imposition d’une contrainte supplementaire pour garantir la convergence vers la racine recherchee. Les resultats de plusieurs exemples numeriques montrent que le nouvel algorithme de detection de contact est plusieurs fois plus rapides que les algorithmes existants a precision comparable. On presente aussi un nouvel algorithme pour generer aleatoirement des paires d’ellipses ou d’ellipsoides permettant de comparer la performance et la precision des algorithmes de detection de contact sur de grands volumes de donnees.----------ABSTRACT: This research provides a theoretical framework to analyze, compare, and improve contact detection algorithms for pairs of ellipses and ellipsoids. We focus primarily on the category of algorithms that are the most computationally efficient and can produce estimates of the separation and penetration distance between ellipses and ellipsoids, and can define a contact point and a normal direction to compute forces, as are necessary in Discrete Element Simulations. Specifically, only analytic representations of the ellipses and ellipsoids are considered and contact detection for moving pairs of ellipsoids is not treated. The first contribution is a mathematical framework for the study of these algorithms, most notably with existence and uniqueness proofs for classes of contact detection algorithms, formal descriptions of pairs of ellipses in near-perfect contact, with or without overlap, and a global analysis of constraints on the normals. The framework highlights the key role played by the different definitions of contact found in the literature, independent of the numerical strategies deployed to estimate the separation/penetration distance. Specifically, it is shown that all the studied algorithms can be expressed as minimization problems, with or without non-binding constraints on the normal(s) at the contact point(s), and that constraints can be used to identify the global minima among the critical points in the minimization problem. Another contribution of this research, based on the mathematical framework introduced, is a better classification of the known algorithms. These algorithms are compared on established test problems and their strengths and weaknesses are highlighted and explained in terms of their classification. The usefulness of the new framework is illustrated with the introduction of a very fast algorithm combining some new and old ideas. The algorithm belongs to the class of geometrical potential methods, which consider the solution of two minimization problems in order to determine a contact point between the particles. The efficiency of the algorithm relies on several ingredients, namely, a transformation that maps the pair of ellipses (ellipsoids) into an ellipse (ellipsoid) centered at the origin and a unit circle (sphere), the construction of an effective initial guess for the solution of the nonlinear minimization problem, the use of Newton’s method for the root finding problem, and the introduction of an additional constraint to guarantee convergence to the desired root. The results from several numerical examples show that the new contact detection algorithm is several times faster than the existing algorithms for comparable accuracy. A novel algorithm to randomly generate pairs of ellipses or ellipsoids is also described and allows one to compare the performance and accuracy of contact detection algorithms on large data sets.