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.