Dans cette thèse, nous étudions le problème du réflecteur. Etant données une source lumineuse et une cible à éclairer avec une certaine distribution d'intensité, il s'agit de construire une surface réfléchissant la lumière issue de la source vers la cible avec la distribution d'intensité prescrite. Ce problème se pose dans de nombreux domaines tels que l'art ou l'architecture. Le domaine qui nous intéresse ici est le domaine automobile. En effet, cette thèse Cifre est réalisée en partenariat avec l'entreprise Optis qui développe des logiciels de simulation de lumière et de conception optique utilisés dans les processus de fabrication des phares de voiture. Les surfaces formant les réflecteurs des phares de voiture doivent répondre à un certain nombre de critères imposés par les fabricants ainsi que les autorités de contrôle nationales et internationales. Ces critères peuvent être objectifs comme par exemple l'encombrement du véhicule ou encore le respect des normes d'éclairage mais peuvent également être subjectifs comme l'aspect esthétique des surfaces. Notre objectif est de proposer des outils industrialisables permettant de résoudre le problème du réflecteur tout en prenant en compte ces critères. Dans un premier temps, nous nous intéresserons au cas de sources lumineuses ponctuelles. Nous reprenons les travaux d'Oliker, Glim, Cafarrelli et Wang qui montrent que le problème du réflecteur peut être formulé comme un problème de transport optimal. Cette formulation du problème est présentée et mise en œuvre dans un cas discret. Dans un second temps, nous cherchons à prendre en compte les critères imposés par les fabricants de phares de voitures. Nous nous sommes intéressés ici aux contraintes d'encombrement et d'esthétique. La solution choisie consiste à utiliser des surfaces de Bézier définies comme le graphe d'une certaine fonction paramétrée par un domaine du plan. Les surfaces de Bézier permettent d'obtenir des surfaces lisses et la paramétrisation par un domaine du plan permet de gérer l'encombrement et le style d'un réflecteur. Nous avons proposé une méthode heuristique itérative par point fixe pour obtenir ce type surface. Enfin, dans un dernier temps, nous prenons en compte des sources lumineuses non ponctuelles. L'approche proposée consiste à adapter itérativement les paramètres du réflecteur de façon à minimiser une distance entre intensité souhaitée et intensité réfléchie. Ceci nous a conduits à proposer une méthode d'évaluation rapide de l'intensité réfléchie par une surface. Les méthodes développées durant cette thèse ont fait l'objet d'une implémentation dans un cadre industriel en partenariat avec l'entreprise Optis. / The far-field reflector problem consists in building a surface that reflects light from a given source back into a target at infinity with a prescribed intensity distribution. This problem arises in many fields such as art or architecture. In this thesis, we are interested in applications to the car industry. Indeed, this thesis is conducted in partnership with the company Optis that develops lighting and optical simulation software used in the design of car headlights. Surfaces in car headlight reflectors must satisfy several constraints imposed by manufacturers as well as national and international regulatory authorities. These constraints can be objective such as space requirements or compliance with lighting legal standards but can also can be subjective such as the aesthetic aspects of surfaces. Our goal is to provide industrializable tools to solve the reflector problem while taking into account these constraints. First, we focus on the case of point light sources. We rely on the work of Oliker, Glim, Cafarrelli and Wang who show that the reflector problem can be formulated as an optimal transport problem. This formulation of the problem is presented and implemented in a discrete case. In a second step, we take into account some of the constraints imposed by car headlight manufacturers, such as the size and the style of the reflector. The chosen solution consists in using Bezier surfaces defined as the graph of a function parameterized over a planar domain. Bezier surfaces allow to obtain smooth surfaces and the parameterization over a planar domain allows to control the size and style of the reflector. To build the surface, we propose a heuristic based on a fixed-point algorithm. Finally, we take into account extended light sources. We present an approach that iteratively adapts the parameters of the reflector by minimizing the distance between the desired intensity and the reflected intensity. This led us to propose a method that efficiently evaluates the reflection of light on the surface. Methods developed in this thesis were implemented in an industrial setting at our partner company Optis.

L’analyse de tolérances par des ensembles de contraintes repose sur la détermination de l’accumulation de variations géométriques par des sommes et intersections d’ensembles opérandes 6d. Les degrés de liberté des liaisons et les degrés d’invariance des surfaces génèrent des opérandes non-bornés (polyèdres), posant des problèmes de simulation. En 2014, L. Homria proposé une méthode pour résoudre ce problème, consistant à ajouter des limites artificielles(contraintes bouchon) sur les déplacements non-bornés. Même si cette méthode permet la manipulation d’objets bornés (polytopes), les contraintes bouchon augmentent la complexité des simulations. En réponse à cette difficulté, une méthode dérivée est proposée dans cette thèse.Cette méthode consiste à tracer et simplifier les contraintes bouchon au travers des opérations.Puis une seconde stratégie basée sur la décomposition d’un polyèdre en une somme d’un polytope et de lignes droites (associées aux déplacements non-bornés). Cette stratégie consiste à simuler d’une part les sommes de droites, et d’autre part, à déterminer la somme de polytopes dans un sous-espace de dimension inférieur à 6. Ces trois stratégies sont comparées au travers d’une application industrielle. Cela montre que la traçabilité des contraintes bouchons est un aspect fondamental pour contrôler leur propagation et pour réduire le temps de calcul des simulations. Toutefois, cette méthode exige encore de déterminer les limites des déplacements non-bornés. La deuxième méthode, adaptant systématiquement la dimension de l’espace de calcul, elle permet de diminuer davantage le temps de calcul. Ce travail permet d’envisager la mise en oeuvre de cette méthode selon des formulations statistiques avec la prise en compte des défauts de forme des surfaces. / The cumulative stack-up of geometric variations in mechanical systems can be modelled summing and intersecting sets of constraints. These constraints derive from tolerance zones or from contact restrictions between parts. The degrees of freedom (DOF) of jointsgenerate unbounded sets (i.e. polyhedra) which are difficult to deal with. L. Homri presented in 2014 a solution based on the setting of fictitious limits (called cap constraints) to each DOFto obtain bounded 6D sets (i.e. polytopes). These additional constraints, however, increase the complexity of the models, and therefore, of the computations. In response to this situation,we defined a derived strategy to control the effects of the propagation of the fictitious limits by tracing and simplifying the generated, new cap constraints. We proposed a second strategy based on the decomposition of polyhedra into the sum of a polytope and a set of straight lines.The strategy consists in isolating the straight lines (associated to the DOF) and summing the polytopes in the smallest sub-space. After solving an industrial case, we concluded that tracing caps constraints during the operations allows reducing the models complexity and,consequently, the computational time; however, it still involves working in 6d even in caseswhere this is not necessary. In contrast, the strategy based on the operands decompositionis more efficient due to the dimension reduction. This study allowed us to conclude that the management of mechanisms’ mobility is a crucial aspect in tolerance simulations. The gain on efficiency resulting from the developed strategies opens up the possibility for doing statistical treatment of tolerances and tolerance synthesis.

Dans cette thèse, nous nous intéressons à plusieurs problèmes liés à la conception de réseaux géométriques et aux plongements isométriques dans le plan.Nous commençons par étudier la généralisation du problème du réseau de Manhattan classique aux plans normés. Étant donné un ensemble de terminaux, nous recherchons le réseau de longueur totale minimum qui connecte chaque paire de terminaux par un plus court chemin dans la métrique définie par la norme. Nous proposons un algorithme d'approximation facteur 2.5 pour ce problème en temps O(mn^3) avec n le nombre de terminaux et m le nombre de directions de la boule unitaire. Le deuxième problème étudié est une version orientée des réseaux de Manhattan dont le but est de construire un réseau orienté de taille minimum dans lequel pour chaque paire de terminaux u, v est relié par un plus court chemin rectilinéaire de u vers v et un autre de v vers u. Nous proposons un algorithme d'approximation facteur 2 pour ce problème en temps O(n^3) où n est le nombre de terminaux.Nous nous intéressons ensuite à la recherche d'un spanner (un sous-graphe approximant les distances) planaire pour les graphes de disques unitaires (UDG) qui modélise les réseaux ad hoc sans fils. Nous présentons un algorithme qui construit un spanner planaire avec un facteur d'étirement constant en terme de distance de graphe pour UDG. Cet algorithme utilise uniquement des propriétés locales et peut donc être implémenté de manière distribuée.Finalement nous étudions le problème de la reconnaissance des espaces plongeables isométriquement dans le plan l_1 pour lequel nous proposons un algorithme en temps optimal O(n^2) pour sa résolution, ainsi que la généralisation de ce problème aux plans normés dont la boule unitaire est un polygone convexe central symétrique. / In this thesis, we study several problems related to the design of geometric networks and isometric embeddings into the plane.We start by considering the generalization of the classical Minimum Manhattan Network problem to all normed planes. We search the minimum network that connects each pair of terminals by a shortest path in this norm. We propose a factor 2.5 approximation algorithm in time O(mn^3), where n is the number of terminals and m is the number of directions of the unit ball.The second problem presented is an oriented version of the minumum Manhattan Network problem, we want to obtain a minimum oriented network such that for each pair u, v of terminals, there is a shortest rectilinear path from u to v and another path from v to u.We describe a factor 2 approximation algorithm with complexity O(n^3) where n is the number of terminals for this problem.Then we study the problem of finding a planar spanner (a subgraph which approximates the distances) of the Unit Disk Graph (UDG) which is used to modelize wireless ad hoc networks. We present an algorithm for computing a constant hop stretch factor planar spanner for all UDG. This algorithm uses only local properties and it can be implemented in distributed manner.Finally, we study the problem of recognizing metric spaces that can be isometrically embbed into the rectilinear plane and we provide an optimal time O(n^2) algorithm to solve this problem. We also study the generalization of this problem to all normed planes whose unit ball is a centrally symmetric convex polygon.

Les images ont envahi la plupart des publications et des communications contemporaines. Cette expansion s'est accélérés avec le développement de méthodes efficaces de compression spécifiques d'images. Aujourd'hui, la génération d'images s'appuie sur des objets multidimensionnels produits à partir de dessins assistés par ordinateurs, de simulations physiques, de représentations de données ou de solutions de problèmes d'optimisation. Cette variété de sources motive la conception de schémas dédiés de compression adaptés à des classes spécifiques de modèles. Ce travail présente deux méthodes de compression pour des modèles géométriques. La première code des ensembles de niveau en dimension quelconque, de manière directe ou progressive, avec des taux de compression au niveau de l'état de l'art pour les petites dimensions. La seconde méthode code des maillages de n'importe quelle dimension ou topologie, même sans être purs ou variété, plongés dans des espaces arbitraires. Les taux de compression pour les surfaces sont comparables aux méthodes usuelles de compression de maillages comme Edgebreaker.

Cette thèse présente un algorithme robuste et efficace du calcul<br /> d'une forme paramétrée exacte de la courbe d'intersection de deux<br /> quadriques définies par des équations implicites à coefficients rationnels. Pour la première fois, le<br /> paramétrage que nous obtenons contient toutes les informations<br /> topologiques de la courbe et est assez simple pour être exploité<br /> dans des applications géométriques non triviales.<br /><br /> De nombreux progrès, dans différents domaines, ont été<br /> nécessaires pour atteindre ce résultat. Nous avons réalisé une étude<br /> exhaustive de tous les cas possibles d'intersection, d'abord dans<br /> $\Pp^3(\C)$ en nous basant sur les travaux de Segre, puis dans $\Pp^3(\R)$ <br /> en exploitant les résultats d'Uhlig sur la réduction simultanée de<br /> deux formes quadratiques réelles. Cette étude systématique nous a<br /> permis de maîtriser complètement la géométrie inhérente à<br /> l'intersection de deux quadriques. Nous sommes maintenant capables<br /> de déterminer toutes les caractéristiques de la courbe<br /> d'intersection, à savoir son genre, ses points singuliers, le nombre<br /> de ses composantes algébriques et connexes, et les incidences entre<br /> ces composantes. Quand il en existe, nous<br /> trouvons un paramétrage rationnel des composantes de la courbe<br /> d'intersection. En ce sens, notre algorithme est optimal.<br /> Nous avons aussi fait des progrès significatifs sur la complexité de l'expression radicale des<br /> coefficients du paramétrage obtenu.<br /> Notre résultat est quasi-optimal dans le sens où les coefficients du paramétrage<br /> de la courbe d'intersection que nous calculons contiennent au plus<br /> une racine carrée non nécessaire dans leur expression. <br /> De plus, notre résultat est optimal dans le cas le pire,<br /> dans le sens où pour chaque type de courbe d'intersection<br /> (par exemple une quartique régulière, ou une cubique et une droite, ou<br /> deux coniques), il existe des paires de quadriques pour lesquelles le<br /> nombre de racines carrées apparaissant dans l'expression des<br /> coefficients de notre paramétrage est minimal.<br /><br /> Enfin, nous avons réalisé une implantation complète de notre<br /> algorithme en MuPAD qui nous a permis d'afficher des<br /> performances inédites, tant en terme de vitesse d'exécution qu'en terme de<br /> simplicité du résultat obtenu.

La maquette numérique d'un produit occupe une position centrale dans le processus de développement de produit. Elle est utilisée comme représentation de référence des produits, en définissant la forme géométrique de chaque composant, ainsi que les représentations simplifiées des liaisons entre composants. Toutefois, les observations montrent que ce modèle géométrique n'est qu'une représentation simplifiée du produit réel. De plus, et grâce à son rôle clé, la maquette numérique est de plus en plus utilisée pour structurer les informations non-géométriques qui sont ensuite utilisées dans diverses étapes du processus de développement de produits. Une demande importante est d'accéder aux informations fonctionnelles à différents niveaux de la représentation géométrique d'un assemblage. Ces informations fonctionnelles s'avèrent essentielles pour préparer des analyses éléments finis. Dans ce travail, nous proposons une méthode automatisée afin d'enrichir le modèle géométrique extrait d'une maquette numérique avec les informations fonctionnelles nécessaires pour la préparation d'un modèle de simulation par éléments finis. Les pratiques industrielles et les représentations géométriques simplifiées sont prises en compte lors de l'interprétation d'un modèle purement géométrique qui constitue le point de départ de la méthode proposée.

Depuis quelques années, l'évolution des techniques d'acquisition a entraîné une généralisation de l'utilisation d'objets 3D très dense, représentés par des nuages de points de plusieurs millions de sommets. Au vu de la complexité de ces données, il est souvent nécessaire de les analyser pour en extraire les structures les plus pertinentes, potentiellement définies à plusieurs échelles. Parmi les nombreuses méthodes traditionnellement utilisées pour analyser des signaux numériques, l'analyse dite scale-space est aujourd'hui un standard pour l'étude des courbes et des images. Cependant, son adaptation aux données 3D pose des problèmes d'instabilité et nécessite une information de connectivité, qui n'est pas directement définie dans les cas des nuages de points. Dans cette thèse, nous présentons une suite d'outils mathématiques pour l'analyse des objets 3D, sous le nom de Growing Least Squares (GLS). Nous proposons de représenter la géométrie décrite par un nuage de points via une primitive du second ordre ajustée par une minimisation aux moindres carrés, et cela à pour plusieurs échelles. Cette description est ensuite derivée analytiquement pour extraire de manière continue les structures les plus pertinentes à la fois en espace et en échelle. Nous montrons par plusieurs exemples et comparaisons que cette représentation et les outils associés définissent une solution efficace pour l'analyse des nuages de points à plusieurs échelles. Un défi intéressant est l'analyse d'objets 3D acquis dans le cadre de l'étude du patrimoine culturel. Dans cette thèse, nous nous étudions les données générées par l'acquisition des fragments des statues entourant par le passé le Phare d'Alexandrie, Septième Merveille du Monde. Plus précisément, nous nous intéressons au réassemblage d'objets fracturés en peu de fragments (une dizaine), mais avec de nombreuses parties manquantes ou fortement dégradées par l'action du temps. Nous proposons un formalisme pour la conception de systèmes d'assemblage virtuel semi-automatiques, permettant de combiner à la fois les connaissances des archéologues et la précision des algorithmes d'assemblage. Nous présentons deux systèmes basés sur cette conception, et nous montrons leur efficacité dans des cas concrets.

L'ensemble des thématiques abordées s'inscrivent dans le contexte de la modélisation et du calcul géométrique.

De nos jours, les objets virtuels sont devenus omniprésents. On les trouve dans de nombreux domaines comme le divertissement (cinéma, jeux vidéo, etc.), la conception assistée par ordinateur ou encore la réalité virtuelle. Nous nous intéressons en particulier à la modélisation d'objets 3D dans le domaine de la création artistique. Ici, la création d'images riches nécessite de faire appel à des modèles très détaillés et donc extrêmement complexes. Les surfaces de subdivision, traditionnellement utilisées dans ces domaines, voient leur complexité croître rapidement lorsqu'on ajoute des détails, et la gestion de la connectivité du maillage de contrôle devient trop contraignante. Une approche standard pour gérer la complexité de tels modèles est d'utiliser des représentations différentes pour la forme générale de la surface et les détails. Cependant, ces détails sont représentés par des cartes matricielles qui ne possèdent pas la plupart des avantages des représentations vectorielles, et cela complexifie certaines tâches, comme par exemple l'animation. Dans cette thèse, nous proposons deux nouvelles représentations vectorielles, la première pour les surfaces de base, la deuxième pour les détails. Nous utilisons pour cette dernière une représentation vectorielle appelée images de diffusion permettant de créer des variations lisses à l'aide d'un ensemble réduit de contraintes. Cela nous permet de représenter aussi bien la géométrie que la couleur ou d'autres paramètres nécessaires au rendu de façon purement vectoriel, en conservant des contrôles de haut niveau. Notre première contribution est une représentation de surfaces, baptisée LS3, issue de la combinaison entre surfaces de subdivision et -point set surfaces. Cette approche réduit notablement les artefacts des surfaces de subdivision aux alentours de sommets dits extraordinaires, qui sont connus pour poser problème. Nous présentons une analyse numérique des propriétés de ces surfaces, qui tend à montrer que du point de vue de la continuité elles se comportent au moins aussi bien que les schémas de subdivision linéaires traditionnels. Notre deuxième contribution est un solveur pour les images de diffusion dont le principal avantage est de produire en sortie une autre représentation vectorielle légère et très rapide à évaluer. Nous illustrons la force de note solveur sur de nombreux exemples difficiles ou impossibles à réaliser avec les méthodes précédentes. Pour conclure, nous montrons comment combiner nos deux contributions pour obtenir une représentation de surface entièrement vectorielle capable de représenter des détails sans avoir à manipuler la connectivité d'un maillage.

Un problème fondamental en géométrie algorithmique est celui du calcul de la topologie d'une courbe plane donnée par son équation implicite. Ce problème peut être vu comme celui du calcul d'un graphe qui approche la courbe et qui possède la même topologie que cette dernière. Une étape importante dans les algorithmes calculant la topologie d'une courbe plane concerne le calcul des points singuliers et points extrêmes (en x) de celle-ci. Ce problème se ramène naturellement à celui de la résolution de systèmes bivariés définis par la courbe et ses dérivées par rapport aux variables qui la définissent. Cette thèse porte sur l'étude, l'élaboration et l'implantation d'algorithmes robustes et efficaces pour la résolution de systèmes définis par des polynômes en deux variables à coefficients entiers. Plus précisément, nous nous somme intéressé au calcul d'une Représentation Univariée Rationnelle des solutions. Une telle représentation est constitué d'un polynôme univarié et de deux fonctions rationnelles qui envois les racines du polynôme univarié sur les coordonnées des points solutions du système. Nous présentons dans un premier temps un algorithme théorique pour calculer la RUR d'un système bivarié qui améliore la meilleure borne de complexité connue d'un facteur d^2, ou d désigne le degré des polynômes de départ, et qui permet d'obtenir une nouvelle borne sur la taille des polynômes de cette RUR. Dans un second temps, nous présentons un algorithme de calcul de RUR efficace en pratique. Cet algorithme, basé sur des choix aléatoires et sur l'utilisation du calcul multi-modulaire est probabiliste. Nous en présentons une première version Monte-Carlo, puis nous montrons comment tester la correction du résultat ce qui fourni un algorithme Las-Vegas. Cet algorithme est efficace à la fois en théorie et en pratique à en juger par l'analyse de complexité en moyenne et les nombreux testes effectués.