Dans le domaine de la synthèse d'image, la simulation de l'apparence visuelle des matériaux nécessite, la résolution rigoureuse de l'équation du transport de la lumière. Cela implique d'incorporer dans les modèles tous les éléments pouvant avoir une influence sur la luminance spectrale énergétique reçue par l'œil humain. La caractérisation des propriétés de réflectance des matériaux, encore sujette à de nombreuses recherches, est très évoluée. Cependant, l'utilisation de cartes d'environnement, pour simuler leurs comportements visuels restent essentiellement trichromatiques. Caractériser la lumière naturelle avec précision, est une interrogation ancienne et il n'existe pas aujourd'hui de cartes d'environnement comportant à la fois les informations de luminance spectrale énergétique et de polarisations correspondant à des ciels réels. Il nous est donc apparu nécessaire, de proposer à la communauté de l'informatique graphique des environnements lumineux complets exploitables dans un moteur de rendu adapté en conséquence.Dans ce travail, nous exploitons des résultats issus d'autres domaines scientifiques tels que la météorologie, la climatologie..., pour proposer un modèle de ciel clair, c'est-à-dire sans nuage.Toutes les situations réelles ne pouvant pas être abordées par cette méthode, nous développons et caractérisons un dispositif de capture d'environnement lumineux incorporant à la fois, la gamme dynamique de l'éclairage, la répartition spectrale et les états de polarisation.Nous proposons, dans le but de standardiser les échanges, un format de données utilisable dans un moteur de rendu spectral, exploitant le formalisme de "Stokes - Mueller". / In the field of computer graphics, the simulation of the visual appearance of materials requires, a rigorous solving of the light transport equation. This implies to incorporate into models all elements that can influence the spectral received by human eyes. The characterization of the reflectance properties of materials, still subject to many researches is very advanced. However, the uses of environment maps, to simulate their visual behaviors remain essentially trichromaticity. Characterize the natural light with precision, is an old question. Today, there are no environment maps, including both spectral radiance and polarization informations, corresponding to a real sky. It was therefore necessary for us to design and propose to the computer graphics community a full of bright environments exploitable in a rendering engine adapted accordingly. In this work, we use the results of other scientific fields as meteorology, climatology..., to propose a new model of clear sky. As all actual situations are not addressed by this method, we develop and characterize an environment capturing device both incorporating the light dynamic range, the spectral distribution and the polarization states.

Les données du monde réel ont manifestement une composante géométrique importante et suggère les patterns géométriques signifiants. Les méthodes qui utilisent la nature géométrique des données sont activement développés dans plusieurs domaines scientifiques, comme, par exemple, la géométrie algorithmique, la géométrie discrète, la synthèse d'images, la vision par ordinateur. Dans le travail présent, nous utilisons les structures géométriques afin de modéliser des algorithmes efficaces pour deux domaines, celui de synthèse d'images et de l'optimisation combinatoire. Dans la première partie il s'agit de la structure de données géométriques, appelé une décomposition bien-séparée, et son application pour un des problèmes les plus difficiles dans la synthèse d'images, un efficace rendu photo-réalistique. Une solution consiste à appliquer toute une famille de méthodes de many-lights qui fait une approximation d'illumination globale par calcule individuelle d'illumination avec un grand nombre de VPLs (virtual point light) répartis sur les surfaces. L'application individuelle de chacun VPL résulte dans un grand nombre des calculs. Une des stratégies de la réussite pour réduire les computations est de faire les clusteurs considérés qui sont consideré comme une seul émetteur. Nous utilisons la décomposition bien-séparée de points comme le fondement de la structure des données susceptible de procéder à un calcul préliminaire et de conserver d'une façon compacte un grand nombre des clusterisations individuels potentiels ce qui montre que la clusterisation des VPL plus correspondante peut être extraite de cette structure de données d'une manière efficace. Nous montrons qu'au lieu de regroupper les points et/ou VPL indépendemment il vaut mieux produire les clusteurs sur l'espace de produit du nombre des points à nuancer et un groupe de VPL à la base de l'illumination des paires induite. En plus, nous proposons une technique adaptive afin d'échantillonner pour réduire le nombre des demandes de vérifications de visibilité pour chaque clusteur de l'espace de produit. Notre méthode consiste à détenir chaque émetteur qui peut être rapproché par VPL, matériaux spéculaire et à performer les méthodes précédents réconnus les meilleurs jusqu'au présent. La deuxième partie est consacrée au développement de nouveaux algorithmes d'approximation pour un problème fondamental de NP complet dans la géométrie algorithmique, précisément le problème du hitting set, avec une précision pour le cas d'un groupe de points et d'un groupe de disques, nous souhaiterons calculer les plus petits nombre du points qui touche tous les disques. Il arrive que les algorithmes efficaces à détecter le hitting set repose sur une structure géométrique clée, appelée epsilon-net. Nous donnons un algorithme utilisant uniquement les triangulisations de Delaunay pour construire les epsilon-nets de taille 13.4/epsilon. Nous donnons une implémentation pratique de la technique à calculer les hitting sets dans le temps quasi-linéaire en utilisant des epsilon-nets de petites tailles. Nos résultats aboutissent à une approximation de 13.4 pour le problème de hitting set par un algorithme qui fonctionne même pour les grands ensembles de données. Pour les ensembles de taille plus petite, nous proposons une implémentation de la technique de recherche locale avec une approximation bornes supérieures, avec le résultat obtenu d'approximation de (8 + epsilon) dans le temps O(n^{2.34}) / Real-world data has a large geometric component, showing significant geometric patterns. How to use the geometric nature of data to design efficient methods has became a very important topic in several scientific fields, e.g., computational geometry, discrete geometry, computer graphics, computer vision. In this thesis we use geometric structures to design efficient algorithms for problems in two domains, computer graphics and combinatorial optimization. Part I focuses on a geometric data structure called well-separated pair decomposition and its usage for one of the most challenging problems in computer graphics, namely efficient photo-realistic rendering. One solution is the family of many-lights methods that approximate global illumination by individually computing illumination from a large number of virtual point lights (VPLs) placed on surfaces. Considering each VPL individually results in a vast number of calculations. One successful strategy the reduce computations is to group the VPLs into a small number of clusters that are treated as individual lights with respect to each point to be shaded. We use the well-separated pair decomposition of points as a basis for a data structure for pre-computing and compactly storing a set of view independent candidate VPL clusterings showing that a suitable clustering of the VPLs can be efficiently extracted from this data structure. We show that instead of clustering points and/or VPLs independently what is required is to cluster the product-space of the set of points to be shaded and the set of VPLs based on the induced pairwise illumination. Additionally we propose an adaptive sampling technique to reduce the number of visibility queries for each product-space cluster. Our method handles any light source that can be approximated with virtual point lights (VPLs), highly glossy materials and outperforms previous state-of-the-art methods. Part II focuses on developing new approximation algorithms for a fundamental NP-complete problem in computational geometry, namely the minimum hitting set problem with particular focus on the case where given a set of points and a set of disks, we wish to compute the minimum-sized subset of the points that hits all disks. It turns out that efficient algorithms for geometric hitting set rely on a key geometric structure, called epsilon-net. We give an algorithm that uses only Delaunay triangulations to construct epsilon-nets of size 13.4/epsilon and we provide a practical implementation of a technique to calculate hitting sets in near-linear time using small sized epsilon-nets. Our results yield a 13.4 approximation for the hitting set problem with an algorithm that runs efficiently even on large data sets. For smaller datasets, we present an implementation of the local search technique along with tight approximation bounds for its approximation factor, yielding an (8 + epsilon)-approximation algorithm with running time O(n^{2.34})

Dans ce document, nous présentons une nouvelle approche qui par l'intégration d'une méthode de radiosité hiérarchique avec regroupement, avec une méthode de lancer de particules, permet de simuler efficacement l'ensemble des chemins lumineux. Dans un premier temps, nous présentons une solution permettant cette intégration. Nous restreignons le lancer de particules pour les seuls échanges lumineux où cela se trouve être nécessaire. Pour cela, nous utilisons la structure de liens créee par la méthode de radiosité hiérarchique avec regroupement. Cette structure peut être considérée comme un partionnement de l'espace des échanges lumineux. Puis, nous présentons comment intégrer l'énergie due a ces particules a la solution globale. L'algorithme unifi´ ainsi obtenu permet une détection automatique des régions où un lancer de particules se révèle nécessaire et de plus, il permet une bonne variation entre une première solution rapide offrant une visualisation de ce que peut être un résultat final, et une solution de plus grande qualité, mais avec un temps de calcul plus élevé. Dans un deuxième temps, nous montrons comment cette approche unifiée peut s'adapter au cas dynamique. Nous introduisons pour cela une structure spatiale permettant de détecter efficacement, toujours a l'aide des liens, quelles sont les particules affect´ es par le déplacement d'un objet et qu'il faut donc renvoyer. Pour accélèrer et améliorer le résultat dans ce cadre, nous introduisons une nouvelle méthode de reconstruction des effets lumineux dus aux particules, par l'utilisation de textures. L'algorithme ainsi présenté permet une mise a jour incrémentale rapide pour les scènes dynamiques. Pour finir, nous présentons une méthode de reconstruction finale, qui, en extrayant les informations contenues dans une solution de notre méthode unifiée, permet d'obtenir des images de très hautes qualité, contenant l'ensemble des effets lumineux.

Dans un premier temps, nous mettrons en valeur le contexte technologique matériel et surtout logiciel qui permet aujourd'hui le développement de systèmes de mise en page pour les métiers de l'édition(§ I.1). Dans cette perspective, apparaîtront d'eux mêmes, la motivation et l'intérêt pratique présentés par l'étude détaillée du détourage, opération fondamentale qui consiste à extraire d'une photographie l'image d'un objet y figurant (§ I.2). Nous aborderons, dans la suite de ce chapitre une présentation plus technique des difficultés soulevées par l'automatisation du détourage. Plus précisément, nous présenterons le problème comme relevant à la fois de la segmentation et de l'interprétation d'image (§ I.3).

On peut affirmer, sans grand risque de se tromper, que le XXIème siècle sera, entre autres, celui des images virtuelles. Pour s'en convaincre, il suffit de regarder à quel point notre quotidien a changé ces dernières années. La part consacrée aux images de synthèse ne fait que croître. Prenons par exemple les bulletins météorologiques télévisés qui sont présentés à l'aide d'animations 3D, les films utilisant massivement des effets spéciaux informatiques, les publicités, ... Bien sûr, toutes les industries sont aussi très friandes d'images de synthèse. Et demain, peut-être nous déplacerons nous dans des mondes virtuels pour faire nos achats, aller au travail ou au cinéma ... Il est clair que les images de synthèse sont promises à un bel avenir mais on en "demandera toujours davantage", on cherchera à être plus rapide, plus précis et plus réaliste. Ce mémoire s'inscrit dans cette évolution et présente nos recherches dans ce domaine. Avant de présenter la démarche suivie, il est nécessaire d'aborder deux problèmes, relatifs à la synthèse d'images. Ces problèmes seront le fil directeur de nos travaux. Le premier problème est celui de l'aliassage. On regroupe dans ce terme trois phénomènes visuels qui nuisent au réalisme des images. Le premier, et le plus connu, est le phénomène des marches d'escalier sur les contours des objets. On peut le traiter efficacement avec un lancer de rayons et un suréchantillonnage adaptatif des pixels. Le deuxième est le phénomène des moirés sur les textures, il peut être traité en utilisant des textures filtrées a priori en fonction de différents taux de compression. Enfin, le troisième phénomène est la disparition des petits objets et des petites ombres. C'est un problème complexe, qu'un lancer de rayons conventionnel ne peut résoudre efficacement. En effet, il est impossible d'assurer qu'aucun objet ne se glisse entre les rayons d'épaisseur infinitésimale lancés. C'est, de plus, un problème important puisqu'il produit des effets involontaires de scintillement de petits objets dans les animations. Notons que les difficultés rencontrées avec de petits objets se retrouvent dans d'autres domaines comme l'acoustique ou les télécommunications. On cherche à calculer dans ces disciplines, avec précision, la propagation des ondes dans des environnements particuliers, par exemple un théâtre dans le cas des ondes sonores, ou une ville lors de la détermination de la visibilité entre deux antennes dédiée à une liaison microondes point à point. Le deuxième problème est le temps de calculs nécessaire pour obtenir une image de synthèse réaliste. Un algorithme tel que le tampon de profondeur ("z-buffer"), en général câblé sur les stations graphiques, permet un calcul très rapide des images et des animations. Malheureusement, des effets tels que la réfraction, la pénombre et l'éclairage diffus sont difficiles à réaliser, voire impossible. Ces manques laissent aux images produites un aspect synthétique et irréel. Pour produire des images plus réalistes, on peut utiliser des algorithmes de lancer de rayons et de calcul de radiosité. Le premier propose un très grand nombre d'effets spéciaux comme la réflexion, la réfraction, la pénombre, le flou de bougé, la profondeur de champs, ..., le deuxième crée des éclairages diffus très réalistes. Malheureusement, ces effets, augmentant le réalisme sont coûteux en temps de calculs. On constate en fait que réalisme et rapidité de calcul sont des critères qui ne vont pas souvent ensemble et qu'il faut la plupart du temps choisir entre les deux. Notre travail de recherche a donc consisté à trouver et développer des solutions à ces deux problèmes. Une première solution qui résout efficacement les problèmes d'aliassage et en particulier la disparition des petits objets et des petites ombres, est le remplacement des rayons d'épaisseur infinitésimale du lancer de rayons par des rayons volumiques. On parle alors de lancer de faisceaux. Cette approche n'est pas nouvelle puisque [AMAN 84] remplace les rayons par des cônes, [HECK 84] les remplace par un seul faisceau volumique et [GHAZ 92] les remplace par des pyramides. Ces propositions résolvent en principe les problèmes d'aliassage mais ne permettent pas toujours des effets de réflexion ou de réfraction réalistes et sont limitées à certains types de scènes. Une approche fondée sur [GHAZ 92] résout tous les problèmes d'aliassage, permet des effets de réfraction et de pénombre au moins aussi réaliste qu'un lancer de rayons et peut être utilisée pour des scènes non polygonales comme les scènes "CSG". Nous proposons, entre autres, dans ce mémoire l'étude détaillée de l'algorithme de [GHAZ 92] et des optimisations et extensions apportées [HASE 96][GHAZ 98]. Une autre solution, pour résoudre les problèmes d'aliassage, est de calculer exactement tous les contours visibles des objets à partir d'un point de vue. On parle alors d'algorithme de calcul de visibilité exacte. Pour cela, de manière très schématique, on projette tous les objets sur le plan de l'écran et on les découpe en fonction de leurs parties visibles depuis l'oeil. Cette approche est intéressante parce qu'elle permet de faire abstraction de toutes définitions d'un écran. On peut ainsi modifier la taille de l'image sans la recalculer entièrement et sans perte d'informations. Nous proposons dans ce mémoire un algorithme de calcul de visibilité exacte fondé sur le modèle des cartes généralisées et sur un lancer de faisceaux. Le modèle des cartes simplifie les différents découpages entre polygones et autorise une représentation des contours intégrant les propriétés d'adjacence entre les arêtes. Les faisceaux permettent de positionner très précisément les objets les uns par rapport aux autres et optimisent le nombre d'objets à traiter. Notre solution tient de plus compte des effets d'ombres portées, de réflexion et approche les effets de réfraction. Une solution pour diminuer les temps de calcul est de diminuer le nombre d'objets à traiter. Pour cela, il existe plusieurs approches comme les volumes englobants, les subdivisions spatiales régulières ou adaptatives, les "BSP", ... Mais toutes ces solutions ont leurs limites, en particulier lorsque l'on travaille avec des scènes décrites avec plusieurs dizaines de milliers de polygones ou lors d'animation. Nous proposons une approche qui, plutôt que de chercher les objets visibles, cherche ceux qui sont cachés afin de les exclure des traitements. Ces objets sont en général situés derrière d'autres objets très imposants qui rendent une partie de la scène non visible. Nous proposons donc des solutions pour trouver ces objets imposants et pour déterminer rapidement les objets qu'ils cachent. Ce mémoire se décompose en cinq chapitres. Dans le 1er chapitre, nous étudions les algorithmes fondés sur des variantes du lancer de rayons et les algorithmes qui utilisent, d'une manière ou d'une autre, des faisceaux. Pour synthétiser la présentation, nous avons classé les différentes approches en quatre catégories : * les algorithmes fondés sur des ensembles de rayons lancés en même temps ; * les algorithmes utilisant exclusivement des faisceaux ; * les algorithmes hybrides utilisant à la fois des rayons et des faisceaux ; * les algorithmes utilisant ponctuellement les faisceaux pour résoudre un problème. Le 2ième chapitre présente les résultats de l'analyse et de l'implémentation de l'algorithme de "lancer de faisceaux pyramidaux" proposé par [GHAZ 92] pour des scènes polygonales. Nous verrons que les problèmes d'aliassage sont résolus mais que les temps de calculs restent importants. Une extension de cet algorithme aux scènes non polygonales ("CSG") est présentée. Le chapitre 3 reprend l'algorithme de "lancer de faisceaux pyramidaux" pour améliorer ses performances. Plusieurs points de cet algorithme sont optimisés pour finalement améliorer très sensiblement les temps de calculs. Une nouvelle extension permettant des effets de pénombre avec des sources lumineuses volumiques est décrite. Le chapitre 4 propose un nouvel algorithme de visibilité. Il est fondé sur les "cartes généralisées" [LIEN 89c] et sur un lancer de faisceaux. Cet algorithme permet de produire une description de tous les contours des objets, des ombres, des réflexions et des réfractions sur le plan image. La construction de ces contours est facilitée par le modèle topologique utilisé et en particulier par les propriétés d'adjacence dont on dispose. Le dernier chapitre présente une méthode permettant de diminuer le nombre d'objets à traiter dans un algorithme de visibilité. Pour cela, des faisceaux sont lancés à partir du point de vue sur des polygones imposants afin de déterminer les objets de la scène manifestement cachés. Cette approche est exploitée dans un algorithme de calcul de la radiosité.

Les travaux de recherche dont ce mémoire est l'objet sont dédiés à la visualisation à différents niveaux de détail de données scientifiques. Les données scientifiques abordées sont de deux types. Les premières sont définies sur des grilles tridimensionnelles uniformes; le domaine d'application correspondant étant alors la visualisation de données d'origines médicales provenant de coupes tomographiques ou de scanners IRM. Les secondes sont définies sur des réseaux triangulaires irréguliers, planaires ou sphériques; les domaines d'applications correspondants étant entre autres la visualisation de données topographiques (terrain visualization), ou encore de données provenant de calculs par éléments finis.

Les images réalistes peuvent être obtenues en simulant le transport de lumière à l'aide de méthodes de type Monte-Carlo. La possibilité d'utiliser des sources de lumières réalistes pour synthétiser des images contribue grandement au réalisme physique des images obtenues. Parmi les modèles existants, ceux qui reposent sur les cartes d'environnements ou des champs lumineuse sont particulièrement intéressants parce qu'ils permettent d'une part, de capturer adéquatement les effets de champs proches et champs lointains et d'autre part, ils peuvent être mesurés de manière directe. Comme les sources de lumières mesurées peuvent contenir des hautes fréquences et peuvent être de haute dimensionnalité (4D), leur utilisation dans le contexte de la synthèse d'images temps-réel pose des problèmes de performance. Dans cette thèse, nous nous recherchons un compromis entre précision de la représentation et efficacité de la simulation. Le travail effectué repose sur un échantillonnage de haute qualité des sources de lumière pour les méthodes non-biaisées de Monte Carlo. Nous introduisons de nouvelles techniques d'échantillonnage pour le rendu physico-réaliste avec des cartes d'environnement qui varient temporellement ainsi que pour des sources de lumière des champs lumineuse. Les résultats obtenus montrent que l'on peut obtenir un rendu physiquement réaliste, précis et temps réel avec des sources lumière réalistes.

Modéliser avec des squelettes est une alternative très séduisante aux "points de contrôle" souvent placés à l'extérieur des formes : cette approche, analogue à un fil de fer dans une forme modelée, permet de créer des modèles de toutes géométries et topologies. Pour cela, il faut que les formes définies par chacun des squelettes soient capable de se mélanger de manière lisse. Introduites en informatique graphique dans les années 90, les surfaces implicites sont la principale solution à ce problème. Elles constituent un modèle puissant à la fois pour la modélisation d'objets tridimensionnels et pour leur animation: leur construction par squelette et leurs capacités de mélange par sommation des champs potentiels qui les définissent permettent en effet la conception progressive et le stockage compact d'objets volumiques, ainsi que l'animation de déformations pouvant comprendre des changements de topologie. Les surfaces implicites, et plus particulièrement les surfaces de convolution, forment donc un modèle particulièrement adapté à la modélisation par squelette. Toutefois, elles présentent un certain nombre de défaut qui les ont rendu inutilisables en pratique. Cette thèse propose de nouveaux modèles implicites à squelettes, s'inspirant de la convolution mais basés aussi sur des déformations de l'espace. Ils permettent : - une génération plus aisée de forme le long de squelettes formés de courbes (des arc d'hélices), - un meilleur contrôle des formes tant au niveau de leur épaisseur que de leur mélange, notamment - nos modèles sont invariant par homothétie ce qui les rend plus intuitif, - la génération de surfaces ayant une topologie plus proche de celle des squelettes, - la génération de détails fins engendrés par un bruit procédural, les détails se comportant de manière cohérente avec la surface (et les squelettes) sous-jacente.

Nous étudions la mise en œuvre d'algorithmes parallèles sur des ordinateurs a mémoire distribuée. A travers plusieurs exemples issus de la programmation dynamique, de l'algèbre linéaire et du traitement d'images, nous exposons les problèmes lies a la programmation de ces machines: topologie d'interconnexion, stratégie d'allocation des données, équilibrage des calculs et minimisation du volume de communication inter-processeurs. Les exemples étudiés sont pour la plupart des algorithmes séquentiels couteux en temps de calcul et en place mémoire, et pour lesquels il est très intéressant d'avoir une parallélisation efficace. Nous avons choisi des problèmes dont l'implémentation sur des machines a mémoire distribuée n'est pas aisée, essentiellement a cause de la grande interdépendance entre les différentes taches composant les algorithmes

La synthèse d'images réalistes nécessite la modélisation précise des interactions de la lumière avec la matière (réflexion, réfraction, diffusion) et des échanges d'énergie lumineuse entre les objets de la scène. Cette modélisation, très complexe si l'on ne fait pas d'hypothèses restrictives, peut être efficacement réalisée par simulation de Monte Carlo. Dans le présent travail, nous définissons tout d'abord une méthode complète d'illumination de scène, fondée sur une simulation de Monte Carlo d'un modèle "particulaire" de la lumière. Dans un premier temps, nous développons cette simulation pour les milieux participants. Nous diminuons la variance de la simulation par un calcul exact de l'absorption. Nous étendons ensuite ce travail aux objets surfaciques et proposons une technique de regroupement de photons pour obtenir une efficacité constante à chaque pas de calcul. Dans la deuxième partie de ce travail, nous étudions l'application de cette méthode à la visualisation des champs scalaires tri-dimensionnels, puis l'application de certaines techniques issues de la synthèse d'images (facettisation, de données volumiques, partitionnement spatial, images de distance, ...) à la simulation de la diffusion des gaz, présentant de nombreuses similitudes avec la simulation de la diffusion de la lumière.