Comparaison de méthodes de détection automatique d’intersections sur surfaces paramétriques

Abstract

La question de déterminer si un modèle géométrique a des intersections non prévues est commune à plusieurs domaines : simulations numériques, CAO/DAO, animation, infographie, etc. C’est un problème dont la complexité varie avec la représentation choisie pour créer le modèle. Pour les surfaces paramétriques c’est un problème difficile à résoudre, mais pour lequel plusieurs solutions ont été proposées. Ces solutions diffèrent les unes des autres dans leurs angles d’approche, leur complexité et la justesse de leurs résultats. Dans ce mémoire, nous tenterons de comparer certaines de ces méthodes. Nous nous concentrerons sur les méthodes dites failsafe, c’est-à-dire qui permettent assurément de détecter la possibilité d’une intersection s’il y en a une. Ces méthodes sont celles utilisées pour toutes les applications critiques, donc pour lesquelles un modèle mal formé aurait des conséquences importantes. Ce mémoire est à teneur principalement théorique. Nous comparerons les méthodes, dans un premier temps, sur leur puissance de résolution. Nous discuterons, dans un deuxième temps, de coût calculatoire. Nous avons finalement fait quelques implémenta- tions pour appuyer nos observations théoriques, mais nous n’avons pas fait une analyse empirique approfondie des coûts calculatoires. Ceci reste à faire. Nous verrons entre autre qu’il existe un ordre partiel entre certaines des méthodes, mais pas toutes. Par exemple, la méthode test-point est strictement plus puissante que la séparation des enveloppes convexes, mais elle est ni plus ni moins puissante que la méthode Volino-Thalmann.

The question of determining if a given geometric model has extraneous intersections is common to many domains: numerical simulation, CAD/CAM, animation, computer graphics, etc. The complexity of this problem varies with the representation chosen to generate the model. For parametric surfaces, it is a hard problem, but for which many solutions have been proposed. Those solutions differ from one another by their underlying ideas, their complexity and the exactitude of the result they give. In this thesis, we will try to compare some of these methods. We will concentrate on the class of methods we call failsafe, the methods that will surely detect the possibility of an intersection if there is one. Those are the methods used in all critical applications, the applications in which a malformed model would have important consequences. The work of this thesis is mostly theoretical. First, we will compare the different techniques on their power of resolution. Then, we will discuss the execution cost of the different methods. We did some implementations while working on this thesis, but only as a way to support our theoretical observations. A complete empirical study of the execution times of the different methods would be left to do. We will see that there is a partial order between some of the methods in their strength, but not all of them. For example, the test-point method is strictly stronger than the separation of the convex hulls method, but is neither stronger nor weaker than the Volino- Thalmann method.