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

Ce travail de recherche offre un cadre théorique pour analyser, comparer et améliorer les algorithmes de détection de contact entre des paires d'ellipses et d'ellipsoïdes. On se concentre surtout sur la catégorie d'algorithmes qui sont les plus efficaces numériquement, qui peuvent produire des estimations de la distance de séparation et de pénétration entre des ellipses et des ellipsoïdes, et qui peuvent définir un point de contact et une direction normale pour calculer les forces, comme nécessaires dans les simulations par éléments discrets. Plus précisément, seules les représentations analytiques des ellipses et ellipsoïdes sont étudiées et la détection de contact entre des ellipsoïdes en mouvement n'est pas traitée ici. La première contribution est d'offrir un cadre mathématique pour étudier ces algorithmes, plus particulièrement les preuves d'existence et d'unicité de solutions pour certaines classes d'algorithmes de détection de contact, pour décrire 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 rôle clé joué par les différentes définitions de contact trouvées dans la littérature, indépendamment des stratégies de calcul utilisées pour calculer les distance de séparation ou de pénétration. Plus précisément, on montre que tous les algorithmes étudiés peuvent être exprimés comme des problèmes de minimisation, avec ou en l'absence de contraintes non saturées sur les vecteurs normaux aux points de contact, et que des contraintes additionnelles peuvent être utilisées pour identifier le minimum global parmi les points critiques du problème de minimisation. Une autre contribution de cette recherche, fondée sur le cadre mathématique proposé, est une meilleure classification des algorithmes existants. Ces algorithmes sont comparés sur des cas test et leurs forces et faiblesses sont mises en évidence et expliquées par rapport à cette classification. L'utilité présentation d'un algorithme performant combinant de nouvelles idées et d'autres plus anciennes. Cette algorithme appartient à la classe des méthodes de potentiel géométrique, lesquelles considèrent la solution de deux problèmes de minimisation pour déterminer un point de contact entre les particules. L'efficacité de l'algorithme repose sur plusieurs ingrédients, à savoir une transformation qui associe à une paire d'ellipses (ellipsoïdes) une ellipse (ellipsoïde) centrée à l'origine et un cercle (une sphère) unitaire, la construction d'un point initial efficace pour la résolution du problème de minimisation non linéaire, l'utilisation de la méthode de Newton pour le problème de recherche de racine, et l'imposition d'une contrainte supplémentaire pour garantir la convergence vers la racine recherchée. Les résultats de plusieurs exemples numériques montrent que le nouvel algorithme de détection de contact est plusieurs fois plus rapides que les algorithmes existants à précision comparable. On présente aussi un nouvel algorithme pour générer aléatoirement des paires d'ellipses ou d'ellipsoïdes permettant de comparer la performance et la précision des algorithmes de détection de contact sur de grands volumes de données.

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.