La modélisation géométrique d'un problème de gestion de la fabrication des mélanges (faisabilité simultanée de deux mélanges) fait apparaître des polytopes nouveaux résultant de la somme de triangles particuliers qui dans ce contexte sont appelés convexes de 2-mélanges. De façon plus générale, la somme de triangles peut être considérée comme la généralisation des zonotopes (somme de segments). De ce point de vue, l'étude menée ici fait apparaître que la propriété de zone associée à un segment du zonotope se généralise à trois demi-zones associées à chaque triangle; et que la complexité combinatoire (nombre de faces du polytope), par rapport au nombre de sommandes, est du même ordre de grandeur que celle des zonotopes. On traite également le problème de la construction de tels polytopes, des algorithmes optimaux en temps sont proposés. Concernant le problème particulier des mélanges, le premier cas non trivial est celui de mélanges à trois composantes qui nous place en dimension 6. L'appartenance d'un point au convexe de 2-mélanges détermine la faisabilité simultanée des mélanges. Les facettes de ce polytope sont décrites, en détail, dans le cas de la dimension 6, dans le but d'obtenir des conditions de faisabilité des deux mélanges. Le problème de la décomposition de polytopes en somme de Minkowski de polytopes plus simples est exposé, ainsi que les principaux résultats existant.

Dans cette thèse, nous proposons une méthode de résolution des problèmes de la géométrie algorithmique posés pour des objets courbes (par opposition aux objets "linéaires" : ensembles de points, segments, polygones ...). Les objets que nous étudions sont des courbes de Bézier composites, choisies, d'une part, pour le réalisme qu'elles assurent dans la modélisation géométrique, et d'autre part, pour la facilité du traitement algorithmique que leurs propriétés offrent. Notre approche met l'accent sur les aspects topologiques des problèmes abordés, en évitant les incohérences que la résolution en arithmétique flottante d'équations algébriques de degré élevé (générées par le traitement direct des courbes) peut le plus souvent introduire. Cet objectif est atteint par l'utilisation d'approximations polygonales convergentes, qui dans le cas des courbes de Bézier sont naturellement fournies par les polygones de controle par l'intermédiaire de la subdivision de de Casteljau. Deux des problèmes fondamentaux de la géométrie algorithmique sont traités ici, l'enveloppe convexe et les arrangements, les deux en dimension 2. Dans le cas des arrangements, la notion de topologie (combinatoire) est bien connue ; dans celui de l'enveloppe convexe, nous la définissons rigoureusement. Pour les deux problèmes, nous montrons qu'il est possible d'obtenir toute l'information topologique définissant (de manière, il est vrai, implicite, mais correcte et complète) la solution exacte en travaillant exclusivement sur les approximations polygonales des objets donnés. Les résultats théoriques obtenus sont concrétisés par des algorithmes dont la convergence et la correction sont démontrées et pour lesquels des études de cout sont réalisées. Des exemples illustrent le fonctionnement de ces algorithmes, validant la méthode proposée.

La résolution efficace de certaines questions de géométrie algorithmique, par exemple les calculs de visibilité ou l'approximation de forme, soulève de nouvelles questions de géométrie des droites, domaine classique dont l'origine remonte à la seconde moitié du 19e siècle. Ce mémoire s'inscrit dans ce cadre, et étudie les nombres de Helly de certains ensembles de droites, un indice reliée à certains théorèmes de la base apparaissant en optimimisation combinatoire. Formellement, le nombre de Helly d'une famille d'ensembles d'intersection vide est le cardinal de sa plus petite sous-famille d'intersection vide et minimale pour l'inclusion relativement à cette propriété. En 1957, Ludwig Danzer a formulé la conjecture que pour tout $d \ge 2$ il existe une constante $h_d$ telle que pour toute famille $\{B_1, \ldots, B_n\}$ de boules deux à deux disjointes et de même rayon, le nombre de Helly de $\{T(B_1), \ldots, T(B_n)\}$ est au plus $h_d$; ici, $T(B_i)$ désigne l'ensemble des droites coupant $B_i$. Danzer a, de plus, spéculé que la constante $h_d$ (minimale) croît strictement avec $d$. Nous prouvons que de telles constantes existent, et que $h_d$ est au moins $2d-1$ et au plus $4d-1$ pour tout $d \ge 2$. Cela prouve la première conjecture et étaye la seconde. Nous introduisons, pour étudier les conjectures de Danzer, un analogue local du nombre de Helly que nous appellons nombre d'épinglement et qui se rattache à la notion d'immobilisation étudiée en robotique. Nous montrons que le nombre d'épinglement est borné pour toute famille (suffisament générique) de polyèdres ou d'ovaloides de $R^3$, deux cas où les nombres de Helly peuvent être arbitrairement grands. Un théorème de Tverberg énonce que si $\{B_1, \ldots, B_n\}$ est une famille de convexes du plan disjoints et congruents par translation alors le nombre de Helly de $\{T(B_1), \ldots, T(B_n)\}$ est au plus $5$. Quoique relativement différentes, notre preuve et celle de Tverberg exploitent toutes deux le fait que toute intersection d'au moins deux $T(B_i)$ a un nombre borné de composantes connexes, chacune contractile. Par des considérations sur l'homologie de projections de complexes et d'ensembles simpliciaux, nous unifions ces deux preuves et montrons que cette condition topologique suffit à établir une borne explicite sur le nombre de Helly.

Beaucoup de programmes de visualisation, de planification de trajectoire, etc., utilisent intensivement des calculs de visibilité. Si ces calculs de visibilité ne constituent qu'une petite partie de ces programmes, ils sont en revanche responsables d'une grande partie du temps d'exécution de ces programmes: leur efficacité est donc cruciale. Les algorithmes traditionnels de calculs de visibilité ont deux défauts: ils effectuent - inutilement - des calculs sur des objets non visibles et refont tous ces calculs à chaque nouvelle requête, même si les changements avec la requête précédente sont minimes. Pour remédier à ces inconvénients dans le cadre de scènes polygonales bidimensionnelles, nous nous servons d'une structure de données - le complexe de visibilité - qui code toutes les relations de visibilité entre objets d'une scène. Après avoir montré comment construire de façon optimale le complexe de visibilité, nous montrons comment il permet d'utiliser la cohérence spatiale de la scène dans les calculs de polygones de visibilité. Nous montrons aussi comment il permet d'utiliser la cohérence temporelle dans le maintien d'une vue autour d'un point se déplaçant dans la scène. Nous étudions ces algorithmes non seulement d'un point de vue théorique mais aussi d'un point de vue pratique. Nous avons programmé ces algorithmes et effectué des comparaisons expérimentales entre algorithmes. Nous nous sommes aussi intéressés aux problèmes de dégénérescences et d'imprécisions des calculs numériques qui se posent dès que les programmes sont exécutés sur des données «réelles»

Les problèmes de visibilité sont centraux pour bien des applications en synthèse d'images. Les exemples les plus classiques sont le calcul de vue, les limites d'ombres, la visibilité mutuelle de paires de points, etc. Nous présentons tout d'abord une étude théorique des propriétés de visibilité tridimensionnelle dans l'espace des rayons lumineux. Nous regroupons les rayons qui voient le même objet, ce qui définit le complexe de visibilité 3D. Les frontières de ces groupes de rayons décrivent les événements visuels de la scène (limites d'ombres, apparition d'objets lors du déplacement d'un observateur, etc.). Nous simplifions le complexe de visibilité en un graphe de l'espace des droites que nous appelons le squelette de visibilité. Les événements visuels sont les arcs de ce graphe, et notre algorithme de construction évite le traitement complexe des ensembles 1D de droites correspondants. Nous calculons uniquement les extrémités (droites à 0 degré de liberté) de ces ensembles, et les événements visuels sont déduits topologiquement grâce à un catalogue d'adjacences. Notre implémentation montre que le squelette est plus robuste, plus général et plus efficace que les structures antérieures. Nous avons appliqué le squelette de visibilité à la simulation de l'éclairage, où il permet des calculs plus précis de manière plus rapide. Nous avons également développé un précalcul pour l'affichage de scènes très complexes. Nous calculons l'ensemble des objets potentiellement visibles depuis un volume de l'espace. Notre méthode est la première qui prend en compte l'occultation due à la conjonction de plusieurs bloqueurs dans ce contexte. Nos tests d'occultation sont effectués grâce à des projections étendues sur des plans, ce qui les rend simples, efficaces et robustes. Nous proposons enfin un vaste tour d'horizon des travaux sur la visibilité dans différents domaines.

No description available.

La géométrie algorithmique a pour but de concevoir et d'analyser des algorithmes pour résoudre des problèmes géométriques. C'est un domaine récent de l'informatique théorique, qui s'est très rapidement développé depuis son apparition dans la thèse de M. I. Shamos en 1978. La randomisation permet d'éviter le recours à des structures compliquées, et s'avère très efficace, tant du point de vue de la complexité théorique, que des résultats pratiques. Nous nous sommes intéressés plus particulièrement à la conception d'algorithmes dynamiques : en pratique, il est fréquent que l'acquisition des données d'un problème soit progressive. Il n'est évidemment pas question de recalculer le résultat à chaque nouvelle donnée, d'où la nécéssité d'utiliser des schémas (semi-)dynamiques. Nous introduisons une structure très générale, le graphe d'influence, qui permet de construire de nombreuses structures géométriques : diagrammes de Voronoï, arrangements de segments... Nous étudions les algorithmes, à la fois du point de vue de la complexité théorique, de leur mise en oeuvre pratique et de l'efficacité des programmes.

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.

Le volume des données décrivant les solides tridimensionnels est sans cesse en augmentation. Une des principales causes de ce phénomène est le gain en résolution des modalités d'acquisition, qu'elles soient volumiques ou surfaciques. Par voie de conséquence, l'analyse de ces informations devient de plus en plus coûteuse et lourde à mettre en oeuvre, requérant des capacités de traitement ou de stockage importantes. Une phase de traitement, en aval du processus de numérisation est indispensable : les données doivent être structurées non seulement pour accélérer leur gestion mais aussi pour améliorer et favoriser la compréhension de leur contenu. Enfin, cette phase se doit d'être flexible afin d'être applicable à des domaines variés d'expertise. Nous proposons au travers de ce travail de thèse un modèle permettant de transformer tout solide numérisé en une entité répondant aux critères énoncés précédemment. Le Squelette Ellipsoïdal (ou E-Squelette) décompose les structures géométriques en sous-structures pertinentes tout en prélevant les informations importantes aux yeux de l'expert. En sortie de ce processus, on dispose de capacités de vision multi-échelle de la géométrie, enrichie des informations extraites. Des comparaisons dépendant de l'échelle de vision sont autorisées entre E-Squelettes, assurant le suivi temporel et la reconnaissance automatique d'objets solides 3D. Enfin, les données présentent de très importants taux de compression, et peuvent être transmises de manière progressive par réseau. L'erreur d'approximation est mesurable et contrôlable en terme de géométrie, ce qui garantit le contrôle de la validité des données transformées. Nous montrerons comment le E-Squelette s'applique à l'imagerie médicale et peut enrichir les moyens d'observation et de diagnostic.

Le lancer de rayon est un algorithme permettant de représenter des scènes 3D de façon très réaliste. Son principe, simple et puissant, repose sur les lois de l'optique géométrique : l'image que voit un observateur est le fruit des interactions entre des photons 6mis par des sources lumineuses et des objets possédant des propriétés géométriques et optiques. L'utilisation d'un modèle basé sur la physique permet une bonne approche des phénomènes naturels suivants : l'éclairement par des sources lumineuses, la réflexion de la lumière sur des objets et la transmission de la lumière à travers des objets transparents. L'algorithme dérivant de ce modèle possède pourtant un inconvénient majeur : le temps de traitement d'une image est très important. Bien que de nombreuses méthodes d'accélération aient été proposées pour tenter d'améliorer sa vitesse d'exécution, ce problème demeure bien présent. Toutefois, avec le développement actuel des machines parallèles à mémoire distribuée et des réseaux d'ordinateurs, une voie d'accélération très prometteuse se développe : la parallélisation. De plus, la mise en commun des capacités ''mémoire" de chaque composante d'une architecture parallèle rend possible le traitement de scènes comportant un plus grand nombre d'objets aux propriétés de plus en plus complexes. Le chapitre 1 présente l'algorithme de lancer de rayon ainsi que les accélérations séquentielles proposées dans la littérature. D apparaît que les techniques les plus efficaces sont basées soit sur l'utilisation de volumes englobants soit sur des subdivisions de l'espace. Malgré ces optimisations, la parallélisation demeure la source d'accélération au plus fort potentiel. Le chapitre 2 recense les différents types d'architectures parallèles et expose les familles d'algorithmes utilisées pour la parallélisation du lancer de rayon sur des machines parallèles à mémoire distribuée. Deux stratégies permettent une distribution de la base de données : 1' envoi de rayons et l'envoi d'objets. Dans le chapitre 3, après avoir présenté nos contraintes, nous comparons les algorithmes parallèles pouvant y répondre grâce à leur modélisation. Les résultats obtenus vont nous amener à proposer deux nouveaux algorithmes de parallélisation basés sur un nouveau type de flot. Enfin, dans le chapitre 4 nous présentons nos résultats expérimentaux et leur analyse. Nos tests sont réalisés sur des machines massivement parallèles et sur un réseau de stations de travail.