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.
| Identifer | oai:union.ndltd.org:umontreal.ca/oai:papyrus.bib.umontreal.ca:1866/18761 |
| Date | 12 1900 |
| Creators | Léger, Étienne |
| Contributors | Stewart, Neil Frederick |
| Source Sets | Université de Montréal |
| Language | French |
| Detected Language | French |
| Type | Thèse ou Mémoire numérique / Electronic Thesis or Dissertation |
Page generated in 0.0022 seconds