Les travaux présentés proposent une méthode appelée GeoSpecif. L'objectif de cette méthode est de proposer une assistance à la recherche de spécifications géométriques. Cette méthode doit, de plus, s'intégrer au cycle de conception. Ces travaux sur la spécification sont basés sur deux outils : le Torseur des Petits Déplacements, pour la simulation, le langage GeoSpelling, pour l'expression de la spécification. Le produit est modélisé par deux vues, une première géométrique (correspondant aux pièces) et une seconde architecturale (correspondant à l'assemblage). La méthode peut être décomposée en plusieurs étapes : éprouver le mécanisme nominal afin de vérifier la robustesse de la conception, générer une architecture avec défauts afin de trouver des solutions pour gérer les mécanismes hyperstatiques, mettre en place une spécification, sur les éléments influents, exprimée dans le langage GeoSpelling. Un mécanisme industriel a servi d'application à ces résultats, il s'agit d'un manchon d'hélicoptère Eurocopter®. La méthode permet ainsi de passer d'une simulation des variations géométriques des pièces grâce à l'outil Torseur des Petits Déplacements à une spécification exprimée dans le langage GeoSpelling. Elle peut être appliquée sur toute sorte de mécanisme hyperstatique, sans changer son comportement, grâce à l'introduction des interfaces à l'issue de la définition de la séquence de mise en position. Elle propose une assistance au concepteur à toutes les étapes de la conception. La spécification qui résulte de la simulation est, grâce à cette méthode, plus proche du besoin fonctionnel des pièces.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Nous considérons le problème de concevoir des représentations compactes ou succinctes de structures de données géométriques. Dans ce cadre, en plus des questions de simple compression, l'attention est portée sur l'étude de structures de données nécessitant une petite quantité de ressources mémoire et permettant de répondre à des requêtes locales en temps O(1). L'une des contributions de cette thèse consiste à proposer un cadre algorithmique général pour la conception de représentations compactes de structures telles que les graphes planaires et les maillages surfaciques. Comme application nous présentons différentes structures spécialement conçues pour représenter de manière compacte la connectivité (ou information combinatoire) de certaines classes de graphes localement planaires. Pour le cas des triangulations planaires à m faces, nous proposons une représentation compacte de l'information combinatoire nécessitant asymptotiquement 2:175 bits par triangle pour le coût en espace et qui permet la navigation entre triangles adjacents, ainsi que d'autres requêtes locales d'incidence entre sommets, en temps constant : cette structure est ainsi optimale pour la classe des triangulations ayant un bord de taille arbitraire. Une telle représentation reste valide et optimale dans le cas de triangulations d'une surface de genre g borné : O(g lgm) bits supplémentaires sont alors nécessaires. Cette représentation est bien adaptée pour faire une mise à jour locale efficace de la triangulation. Plus précisément, il est possible d'effectuer des mises à jour en temps O(1) amorti après insertion de sommets, et en temps O(log2m) amorti après suppression de sommets et flip d'arêtes. Et en ce qui concerne les triangulations et les graphes planaires 3-connexes, correspondant aux maillages triangulaires et polygonaux homéomorphes à une sphère, nous proposons les premières représentations succinctes optimales : elles atteignent l'entropie respective des deux classes, 2 bits par arête pour les graphes 3-connexes, et 1:62 bits par triangle (ou 3:24 bits par sommet) pour les triangulations. Ces structures permettent aussi l'accès en temps O(1) aux informations associées aux sommets, notamment leurs coordonnées. Cependant nous ne traitons pas ici la compression de cette information géométrique.

Les travaux présentés dans cette thèse traitent de l'utilisation de la Réalité Virtuelle (RV) et plus particulièrement du retour d'effort pour améliorer l'interaction dans les applications de Conception Assistée par Ordinateur (CAO). Dans ce document, nous décrivons le rôle actuel du Product Lifecycle Management (PLM) dans l'industrie, et plus spécifiquement la place tenue par l'outil CAO. Celui-ci offre de nombreuses fonctionnalités pour l'édition d'une maquette en trois dimensions, mais, actuellement, ne bénéficie pas pleinement des méthodes d'interactions les plus récentes. Notre positionnement de recherche concerne l'utilisation des dispositifs de visualisation ainsi que les nouvelles méthodes d'interaction offertes par la RV, pour rendre l'édition de forme plus intuitive. Toutefois, de nombreuses applications industrielles du PLM, telles que l'assemblage ou l'ergonomie, utilisent déjà des solutions de RV pour augmenter l'interaction avec le produit. Afin de bien appréhender les solutions haptiques que nous proposons, un rappel des principaux concepts de la CAO est effectué, en particulier relatif à ses modèles de données (B-Rep, graphe d'historique, persistent naming). On décrit également les informations perceptibles autour de trois principales catégories : référents, informations géométriques et guides, puis les retours tactiles et d'efforts envisagés pour traduire les différents types d'informations que l'on peut rencontrer. Le travail du concepteur s'articulant autour de deux catégories de tâches : la sélection et la modification de la maquette CAO, nous avons structuré nos travaux de recherche en haptique autour de ces deux grandes classes. De fait, nous abordons ensuite les problématiques de sélection dans une maquette 3d, sélection assistée par des retours haptiques adaptés, et ce en particulier pour permettre une perception fine des composants topologiques. Dans un second temps, nous présentons deux tâches représentatives des activités de modification en CAO : l'édition de courbes et surfaces et l'extrusion. Ces deux fonctionnalités permettent de montrer l'apport de l'haptique pour la manipulation de paramètres sur deux types d'édition CAO très différents. Nous nous intéressons à l'impact de différents facteurs comme le contexte de réalisation de la tâche, la manipulation simultanée des paramètres, la cohabitation de multiples retours haptiques, ou la prise en main, par les tilisateurs, des solutions haptiques. L'analyse des expérimentations relatées dans cette thèse montre des résultats mitigés sur l'apport de l'haptique. Si ce canal sensorimoteur est généralement plebiscité, il convient néanmoins de faire attention au paramétrage des retours d'effort et à la mise en relation des différentes méthodes haptiques, au risque de gener le travail de l'utilisateur du système CAO. Au demeurant, une fois cet écueil évité, les perspectives de l'intégration de l'interaction haptique pour l'aide 'a l'édition CAO semblent prometteuses. Nous concluons cette recherche en esquissant la méthodologie d'intégration RV-CAO qu'il conviendrait de suivre pour mener à bien une évaluation complète de nos solutions avec des utilisateurs CAO experts.

Les réseaux spatiaux sont des réseaux dans lesquels les sommets occupent une position dans l'espace Euclidien. Les interactions dans ces réseaux sont déterminées par cette géometrie sous-jacente des sommets. Les réseaux de communications offrent un vaste champ d'application et une source de nouveaux modèles autour de ce thème. La thèse aborde trois sujets dans des domaines differents. Le premier concerne l'étude de certains arbres couvrant géométriques de processus ponctuels de Poisson. Ces travaux portent notamment sur le phenomene "petit monde", les arbres couvrants radiaux et l'arbre couvrant minimal. Un autre sujet de recherche porte sur la stabilité stochastique de réseaux de files d'attente pour lesquelles les files ont des interactions spatiales. La dernière partie de la thèse aborde des thèmes reliés à la géometrie stochastique: une étude du modèle de feuilles mortes et un travail sur la sensibilité de fonctionnelles de processus ponctuels de Poisson.

En dépit des progrès réalisés en vision par ordinateur et en photogrammétrie, la reconstruction tridimensionnelle de scènes à partir de photographies reste un problème extraordinairement complexe et loin d'être résolu. Dans cette thèse, nous nous intéressons au domaine plus restreint de la reconstruction automatique de bâtiments à partir d'images aériennes en multi-recouvrement. En décalage par rapport aux méthodes à base de modèles prédéfinis, notre approche utilise une modélisation très générique des bâtiments comme polyèdres sans surplomb. Pour pallier le manque de robustesse inhérent à la plupart des approches génériques, des contraintes a priori sont introduites dans la sélection de la meilleure représentation favorisant ainsi, sans les imposer, des choix correspondant à des situations récurrentes dans un environnement urbain: parallélisme, horizontalité, orthogonalité, symétrie verticale de certaines facettes. Par ce raisonnement, le système concilie à la fois les problématiques de généricité et de généralisation. La stratégie générale se compose de quatre étapes majeures. La première consiste à extraire des images trois types de primitives tridimensionnelles qui serviront à construire les modèles de bâtiments puis à sélectionner la meilleure représentation: segments 3D, facettes planes, discontinuités altimétriques. Dans un deuxième temps, l'algorithme extrait, à partir de l'arrangement de plans déduit des primitives planes, toutes les hypothèses de bâtiments modélisés comme surfaces polyédriques continues et sans surplomb. Il est prouvé, à cet effet, que cette procédure se ramène à la recherche exhaustive des cliques maximales d'un graphe adéquat. Dans l'ensemble de toutes ces hypothèses, la sélection du modèle final se fait, dans un troisième temps, par le biais d'une formulation bayésienne qui prend en compte différents types d'observation. La complexité du modèle de bâtiment et les contraintes a priori sur les primitives telles qu'orthogonalité, parallélisme, symétrie, horizontalité sont naturellement introduites dans cette formulation pour concilier adéquation aux données et simplicité de formes. Enfin, les contraintes détectées sur les primitives sont effectivement introduites dans la reconstruction. L'algorithme utilise alors une paramétrisation implicite du bâtiment qui assure l'application des contraintes sur le modèle final. La méthodologie de recherche de l'ensemble des formes admissibles par cliques maximales constitue, avec l'intégration de contraintes dans le processus de choix de la représentation et de recalage du modèle, les contributions majeures du système présenté. Des résultats et une évaluation sur images aériennes prouvent la validité de cette approche qui permet de traiter des bâtiments aux formes arbitrairement complexes et de pallier, le cas échéant, les défauts de focalisation. Malgré cette généricité, le système se révèle tolérant aux erreurs des détecteurs de primitives et présente des caractéristiques intéressantes pour la modélisation de scènes péri-urbaines.

La théorie des codes géométriques s'est développée au début des années 80 sur l'impulsion d'un article de V.D. Goppa publié en 1981. Etant donnée une courbe algébrique projective lisse X sur un corps fini, on dispose de deux constructions de codes correcteurs d'erreurs. Une construction dite fonctionnelle qui fait intervenir certaines fonctions rationnelles sur X et une construction différentielle qui fait appel à certaines 1-formes différentielles rationnelles sur X . L'étude de ces codes construits sur des courbes a donné lieu à la publication de plusieurs centaines d'articles. Parallèlement à ces travaux, une généralisation de la construction fonctionnelle à des variétés algébriques de dimension quelconque est proposée par Y. Manin dans un article publié en 1984. On dénombre quelques dizaines de travaux publiés portant sur l'étude de tels codes. Cependant, aucun développement n'a été effectué dans le sens d'une généralisation de la construction différentielle. Dans cette thèse nous proposons une construction différentielle de codes sur des surfaces algébriques. Nous étudions ensuite les propriétés de ces codes et plus particulièrement leurs relations avec les codes fonctionnels. De façon un peu surprenante, on observe l'apparition d'une différence majeure avec le cas des courbes. En effet, si sur une courbe l'orthogonal d'un code fonctionnel est différentiel, ce fait est en général faux sur une surface. Ce résultat motive l'étude des orthogonaux de codes fonctionnels. Des formules pour l'estimation de la distance minimale de tels codes sont données en utilisant des propriétés de systèmes linéaires sur une variété. On montre également que, sous certaines conditions sur la surface, ces codes sont somme de codes différentiels et que des réponses à certains problèmes ouverts de géométrie algébrique "à la Bertini" fourniraient des informations supplémentaires sur les paramètres de ces codes.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Engendrer en temps-réel des déformations visuellement réalistes d'objets 3D, comme par exemple le corps et les vêtements de personnages, est un point crucial en animation, que ce pour des applications au jeu vidéo ou à la production cinématographique. Les méthodes de déformations géométriques actuelles rapides telles que le "skinning" ou l'animation physique à basse résolution ne capturent cependant pas certains comportements naturels essentiels. En particulier les déformations à volume constant du corps, le gonflement des muscles pour un personnage, ou la génération de plis sur ses vêtements dus au fait que leurs surfaces doivent rester développable. Cette thèse présente une série de méthodes rendant les modèles géométriques "actifs", c'est à dire capables de maintenir un certain nombre de contraintes intrinsèques de la surface portant sur le volume englobé ou sur le caractère développable de celle-ci. Nous étudions trois exemples: - l'ajout de contraintes locales de volumes lors de l'animation d'une créature virtuelle par skinning. - l'ajout de plis de vêtements modélisant une surface quasi-inextensible à partir d'une animation à basse résolution donnée en entrée. - la génération d'une surface de type papier froissé, basée sur la préservation de l'isométrie vis-à-vis d'un patron planaire. Dans tous ces modèles, notre approche est procédurale. Elle se base sur la déformation progressive et, potentiellement, le raffinement dynamique de la géométrie juste avant l'étape de rendu. / Generating visually realistic deformation of 3D objects in real-time for character body or garment is essential for the animation field, both for video games applications and movie production. Current fast deformation methods such as "skinning", or low resolution physically based simulations fail to capture some important natural behaviors. For instance constant volume deformation of a body, muscle bulging of a character, or wrinkling its garment which must be modeled by a developable surface. This thesis presents several methods making a geometrical models "active", that is to say able to maintain a certain number of intrinsic constraints of the surface linked to its bounded volume, or its developability. We develop three case studies - The addition of local volume constraints during skinning animation of a virtual creature. - The addition of wrinkles on garments to model stretch minimizing surface starting from a general low resolution animation provided as input. - The generation of folded paper looking surface based on length preservation with respect to its planar pattern. For every cases, we rely on a procedural approach based on progressive deformation, and eventually, on-the-fly refinement of the geometry just before the rendering stage.