Show item record

dc.contributor.advisorStewart, Neil Frederick
dc.contributor.authorLéger, Étienne
dc.date.accessioned2017-05-26T14:23:42Z
dc.date.availableNO_RESTRICTIONfr
dc.date.available2017-05-26T14:23:42Z
dc.date.issued2017-03-28
dc.date.submitted2016-12
dc.identifier.urihttp://hdl.handle.net/1866/18761
dc.subjectdétectionfr
dc.subjectinterférencefr
dc.subjectintersectionfr
dc.subjectauto-intersectionfr
dc.subjectsurfacefr
dc.subjectparamétriquefr
dc.subjectBézierfr
dc.subjectsubdivisionfr
dc.subjectdetectionfr
dc.subjectinterferencefr
dc.subjectparametricfr
dc.subject.otherApplied Sciences - Computer Science / Sciences appliqués et technologie - Informatique (UMI : 0984)fr
dc.titleComparaison de méthodes de détection automatique d’intersections sur surfaces paramétriquesfr
dc.typeThèse ou mémoire / Thesis or Dissertation
etd.degree.disciplineInformatiquefr
etd.degree.grantorUniversité de Montréalfr
etd.degree.levelMaîtrise / Master'sfr
etd.degree.nameM. Sc.fr
dcterms.abstractLa 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.fr
dcterms.abstractThe 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.fr
dcterms.languagefrafr


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show item record

This document disseminated on Papyrus is the exclusive property of the copyright holders and is protected by the Copyright Act (R.S.C. 1985, c. C-42). It may be used for fair dealing and non-commercial purposes, for private study or research, criticism and review as provided by law. For any other use, written authorization from the copyright holders is required.