La génération d'images de synthèse pour la production cinématographique n'a cessé d'évoluer durant ces dernières décennies. Pour le non-expert, il semble que les effets spéciaux aient atteint un niveau de réalisme ne pouvant être dépassé. Cependant, les logiciels mis à la disposition des artistes ont encore du progrès à accomplir. En effet, encore trop de temps est passé à attendre le résultat de longs calculs, notamment lors de la prévisualisation d'effets spéciaux. La lenteur ou la mauvaise qualité des logiciels de prévisualisation pose un réel problème aux artistes. Cependant, l'évolution des cartes graphiques ces dernières années laisse espérer une potentielle amélioration des performances de ces outils, notamment par la mise en place d'algorithmes hybrides rasterisation/ lancer de rayons, tirant profit de la puissance de calcul de ces processeurs, et ce, grâce à leur architecture massivement parallèle. Cette thèse explore les différentes briques logicielles nécessaires à la mise en place d'un pipeline de rendu complexe sur carte graphique, permettant une meilleure prévisualisation des effets spéciaux. Différentes contributions ont été apportées à l'entreprise durant cette thèse. Tout d'abord, un pipeline de rendu hybride a été développé (cf. Chapitre 2). Par la suite, différentes méthodes d'implémentation de l'algorithme de Path Tracing ont été testées (cf. Chapitre 3), de façon à accroître les performances du pipeline de rendu sur GPU. Une structure d'accélération spatiale a été implémentée (cf. Chapitre 4), et une amélioration de l'algorithme de traversée de cette structure sur GPU a été proposée (cf. Section 4.3.2). Ensuite, une nouvelle méthode de décorrélation d'échantillons, dans le cadre de la génération de nombres aléatoires a été proposée (cf. Section 5.4) et a donné lieu à une publication [Dufay et al., 2016]. Pour finir, nous avons tenté de combiner l'algorithme de Path Tracing et les solutions Many Lights, toujours dans le but d'améliorer la prévisualisation de l'éclairage global. Cette thèse a aussi donné lieu à la soumission de trois mémoires d'invention et a permis le développement de deux outils logiciels présentés en Annexe A. / Image synthesis for movie production never stopped evolving over the last decades. It seems it has reached a level of realism that cannot be outperformed. However, the software tools available for visual effects (VFX) artists still need to progress. Indeed, too much time is still wasted waiting for results of long computations, especially when previewing VFX. The delays or poor quality of previsualization software poses a real problem for artists. However, the evolution of graphics processing units (GPUs) in recent years suggests a potential improvement of these tools. In particular, by implementing hybrid rasterization/ray tracing algorithms, taking advantage of the computing power of these processors and their massively parallel architecture. This thesis explores the different software bricks needed to set up a complex rendering pipeline on the GPU, that enables a better previsualization of VFX. Several contributions have been brought during this thesis. First, a hybrid rendering pipeline was developed (cf. Chapter 2). Subsequently, various implementation schemes of the Path Tracing algorithm have been tested (cf. Chapter 3), in order to increase the performance of the rendering pipeline on the GPU. A spatial acceleration structure has been implemented (cf. Chapter 4), and an improvement of the traversal algorithm of this structure on GPU has been proposed (cf. Section 4.3.2). Then, a new sample decorrelation method, in the context of random number generation was proposed (cf. Section 5.4) and resulted in a publication [Dufay et al., 2016]. Finally, we combined the Path Tracing algorithm with the Many Lights solution, always with the aim of improving the preview of global illumination. This thesis also led to the submission of three patents and allowed the development of two software tools presented in Appendix A.

Le travail présenté ici a pour thème le développement et la mise en oeuvre d'une méthode d'implicitisation et d'inversion ainsi que son application à la visualisation de surfaces polynomiales et rationnelles parametrées par la technique du lancer de rayons. l'implicitisation est un problème d'élimination pour lequel les méthodes de résultant s'avèrent mieux adaptées à notre application. la méthode de dixon (1908) pour les surfaces obtenues par produit tensoriel (surfaces de bi-degré) est particulièrement bien adaptée. Nous proposons une extension algorithmique de cette méthode qui conserve ses propriétés de simplicité et de compacité. la programmation en langage REDUCE a permis une expérimentation sur de nombreux exemples: elle montre que l'équation implicite est obtenue, et ceci de façon efficace, bien que la justification théorique de l'algorithme reste incomplète. L'étude de cette dernière nous a amené à considérer les problèmes de paramétrisations non fidèles et de l'apparition de facteurs parasites. Ensuite le problème de l'inversion (identification et détermination des paramètres d'un point de la surface rationnelle) est résolu complètement. Nous proposons enfin une application numérique de ces algorithmes (en langage C) au problème de l'intersection d'une Bezier rationnelle et d'une demi-droite (rayon). les aspects de stabilité numérique et d'optimisation sont mis en avant: à chaque surface est associée une table pre-calculée, permettant d'obtenir simplement l'équation d'intersection dans le paramètre rayon. Les images données attestent des qualités numériques de cette méthode d'implicitisation-inversion<br />~

Modéliser et visualiser des complexes architecturaux reste aujourd'hui un problème difficile, à cause de la grande masse de données qu'un bâtiment meublé peut représenter. L'objectif de cette thèse est la création d'une chaîne complète allant de la modélisation géométrique jusqu'à la simulation d'éclairage. Nous proposons tout d'abord un modèle à base topologique permettant de représenter des grands bâtiments. Cette structure est une hiérarchie de cartes généralisées munies de partitions multiples. Un prototype de modeleur a été développé autour d'une version optimisée de ce modèle et quelques bâtiments ont été modélisés. De nombreuses informations (géométrie, topologie et sémantique) peuvent être extraites de notre modèle pour optimiser les algorithmes de visualisation. Nous montrons comment accélérer un lancer de rayons à l'aide des informations de modélisation et proposons un algorithme rapide d'illumination globale basé sur un lancer de photons.

L'exploration des diverses solutions liées au problème de l'éclairement global en synthèse d'images a vu l'émergence de deux disciplines fort différentes. La plus ancienne est l'application d'un principe utilisé par les physiciens dans les calculs d'échanges thermiques. Dans le cas de la synthèse d'images, ce ne sont en fait que les grandeurs échangées qui diffèrent et les ondes infrarouges sont remplacées par la lumière visible. Ce ne sont donc plus des échanges thermiques qui sont traités, mais uniquement des échanges lumineux entres différentes surfaces : la radiosité. Plus récemment, nous avons vu l'application de concepts mathématiques statistiques (les méthodes de Monte-Carlo) à un algorithme de lancer de rayons : l'équation de rendu et sa résolution par le suivi de chemins. Le travail présenté dans cette thèse fait partie de cette seconde famille. Les vecteurs d'éclairement indirect (VEI) obtenus à l'aide du lancer de rayons,s'appliquent dans le cadre de scènes d'intérieur et utilisent, pour leur calcul,une méthode de Monte-Carlo. Les recherches que nous avons menées ont pour but de développer cette jeune méthode que sont les VEI. Nous avons,pour cela,tenté d'explorer différentes voies, parfois en appliquant des principes connus,parfois en proposant des méthodes originales. Le résultat est une collections de propositions permettant de calculer les VEI plus rapidement et plus précisément. Ces propositions se séparent en deux groupes bien distincts dont le premier est l'étude du calcul d'un VEI. Le second propose des améliorations pour visualiser l'éclairement indirect calculé avec les VEI.

Le photoréalisme est l'un des thèmes de la recherche en synthèse d'images. Il s'agit de produire des images visuellement indiscernables de photographies, pour des scènes virtuelles simulant des scènes réelles. Cette approche se scinde en deux domaines indépendants : la modélisation géométrique décrit la forme et la position des objets, alors que la modélisation énergétique explicite les propriétés de la lumière émise par les sources, et ses interactions avec les matériaux des objets. Nous nous situons dans ce deuxième cadre. Nous présentons une méthode de calcul de l'éclairement global dans un environnement de lancer de rayons. La prise en compte des interréflexions multiples est une opération très couteuse, car elle nécessite un échantillonnage très fin, et génère un très grand nombre de rayons. Notre modélisation vectorielle représente de façon concise l'énergie incidente en une surface, en tenant compte des propriétés du matériau. Elle exploite les cohérences de la scène et de la lumière en réutilisant les valeurs connues lorsque les variations sont modérées, permettant une importante réduction des temps de calcul. Les opérations complexes sont alors remplacées par de simples interpolations vectorielles. La lumière est séparée en composantes indépendantes : directe, indirecte et caustique. Des méthodes optimisées sont adaptées à ces cas particuliers, pour détecter les zones ou l'interpolation est possible. D'autre part, nous proposons une méthode de prise en compte des sources étendues en lancer de rayons, pour obtenir des pénombres douces. Dans le cas des sources planes rectangulaires, une subdivision adaptative découpe la surface en zones d'angles solides proches, vues depuis le point courant. Pour une même précision, le nombre de zones est plus faible que celui obtenu par un découpage régulier classique de la surface. Ce procédé est ensuite étendu à des sources de forme quelconque, puis adapte à la simulation de l'éclairement naturel du ciel.

This thesis takes its place in a context where information on the biophysical state of forest ecosystems at spatial scales only remote sensing can retrieve is in demand more than ever. In order to provide reliable information using validated approaches, the remote sensing research community recognises the need for new and innovative methods, especially in heterogeneous environments like savannas. The recent emergence of terrestrial LiDAR scanners (TLS) and the increase in the computational capability of computers which allow running ray tracing model simulations with a high level of realism hold great potential to improve our understanding of the processes influencing the radiance measured by satellite sensors. This thesis makes use of these two cutting edge technologies for estimating the spatial distribution of tree leaf area, a key element of modeling radiative transfer processes. The first part of the thesis concerns the development of methods for estimating tridimensional leaf area distribution in a savanna environment from TLS measurements. The methods presented address certain issues related to TLs measures affecting the application of classical theories (the probability of light transmission and the contact frequency) to the estimation of leaf area through indirect means. These issues pertain to the cross-section of laser pulses emitted by a TLS and the occlusion effects caused by the interception of laser pulses by material inside the crown. The developed methods also exploit additional information provided by the active nature of the TLS sensor that is not available to passive sensors like hemispherical photography, i.e. the intensity of a pulse return offers the possibility to distinguish between energy interception by wood and foliage. A simplified approach of this method is presented to promote its use by other research groups. This approach consists of a series of parameterisations and represents a significant gain in terms of the required resources to produce the leaf area, estimates. The second part of the thesis explores the combination of the tree representations generated in the first part with a ray tracing model to simulate the interactions of light with tree crowns. This approach is highly innovative and our study showed its potential to improve our understanding of the factors influencing the radiative environment in a savanna. The methods presented offer a solution to map leaf area at the individual tree scale over large areas from very high spatial resolution imagery.

L'un des objectifs lors du développement d'un produit industriel est d'obtenir un prototype numérique valide et réaliste. Cette thèse a pour objectif d'améliorer la qualité des simulations dans le contexte d'un processus de production. Ces processus impliquent souvent un rendu de type "walkthrough", avec une géométrie fixe mais un déplacement continu de l'observateur. Nous nous intéresserons donc plus précisément aux méthodes de rendu physiquement réaliste de scènes complexes pour un scénario "walkthrough". Durant le rendu, l'utilisateur doit pouvoir mesurer précisément la radiance d'un point ou d'une zone donnée, ainsi que modifier en temps réel la puissance des sources lumineuses. Fondée sur la méthode du photon mapping, nos travaux montrent les modifications à apporter aux algorithmes afin d'améliorer à la fois la qualité des images et le temps de calcul du processus de rendu. / One of the goals when developing the product is to immediately obtain a real and valid prototype. This thesis provide new rendering methods to increase the quality of the simulations during the upstream work of the production pipeline. The latter usually requires a walkthrough rendering. Thus, we focuses on the physically-based rendering methods of complex scenes in walkthrough. During the rendering, the end-users must be able to measure the illuminate rates and to interactively modify the power of the light source to test different lighting ambiances. Based on the original photon mapping method, our work shows how some modifications can decrease the calculation time and improve the quality of the resulting images according to this specific context.

Pour répondre à des impératifs croissants de fiabilité et de sûreté, les procédés mis en œuvre dans le cadre du contrôle non destructif sont en constante évolution. Au vu de la complexité des techniques utilisées, la simulation prend une part importante dans leur développement. Nous présentons des travaux ayant abouti à un outil rapide de simulation du champ émis par un traducteur ultrasonore plan quelconque dans des configurations complexes de contrôle non destructif impliquant des géométries maillées sans arêtes saillantes, des matériaux isotropes ou anistropes, homogènes ou hétérogènes et des trajectoires d'ondes pouvant comporter des rebonds et des transmissions. Les fronts d'ondes ultrasonores sont approximés à l'aide d'interpolateurs polynomiaux locaux à des pinceaux de rayons ultrasonores. Ceux-ci sont obtenus au moyen d'un algorithme de recherche de surface par lancer de pinceaux et subdivisions successives. Ils permettent le calcul des grandeurs utiles à la constitution de la réponse impulsionnelle en chaque point d'un échantillonnage du traducteur respectant le critère de Shannon. De cette façon, nous pouvons calculer une réponse impulsionnelle qui, convoluée au signal d'excitation du traducteur, donne le champ ultrasonore. Les performances des simulations ont été accrues par l'exploitation du parallélisme de tâches et des instructions SIMD dans les parties les plus coûteuses du calcul. Enfin, un outil de calcul progressif continu a été développé pour permettre une visualisation interactive d'images de champ. Il exploite une méthode de reconstruction d'images et ordonnance les calculs de champ de manière à accélérer la convergence des images produites / In order to fulfill increasing reliability and safety requirements, non destructive testing techniques are constantly evolving and so does their complexity. Consequently, simulation is an essential part of their design. We developed a tool for the simulation of the ultrasonic field radiated by any planar probes into non destructive testing configurations involving meshed geometries without prominent edges, isotropic and anisotropic, homogeneous and heterogeneous materials, and wave trajectories that can include reflections and transmissions. We approximate the ultrasonic wavefronts by using polynomial interpolators that are local to ultrasonic ray pencils. They are obtained using a surface research algorithm based on pencil tracing and successive subdivisions. Their interpolators enable the computation of the necessary quantities for the impulse response computation on each point of a sampling of the transducer surface that fulfills the Shannon criterion. By doing so, we can compute a global impulse response which, when convoluted with the excitation signal of the transducer, results in the ultrasonic field. The usage of task parallelism and of SIMD instructions on the most computationally expensive steps yields an important performance boost. Finally, we developed a tool for progressive visualization of field images. It benefits from an image reconstruction technique and schedules field computations in order to accelerate convergence towards the final image

La physique de la lumière ainsi que les outils géométriques pour la Conception Assistée par Ordinateur sont à la base des logiciels de simulation des phénomènes lumineux pour la fabrication des systèmes optiques. Ce n'est pas sans difficulté que les industriels conçoivent ces logiciels dont un des principaux handicaps est que les simulations sont très coûteuses en temps. L'objectif principal de ce travail est de rechercher et développer des algorithmes de calcul plus performants. Dans un premier temps, on décrit précisément le modèle du transport des photons dans ce contexte, composé de l'équation de Boltzmann accompagné de conditions de bord, et qui, dans le cas de milieux homogènes par morceaux, se ramène à l'équation de radiosité. Ensuite, on présente les outils géométriques utilisés dans le modeleur hybride CSG (Constructive Solid Geometry) et BRep (Boundary Representation) ainsi que les algorithmes de base nécessaires à la recherche d'intersections entre des demi-droites et des objets géométriques. Puis, un tour d'horizon des méthodes d'accélération des calculs en radiométrie par localisation spatiale est présenté. En tenant compte des contraintes industrielles, une telle méthode d'accélération est alors adaptée au contexte puis développée dans un environnement logiciel existant. Des expérimentations numériques montrent l'efficacité des nouvelles bibliothèques. Enfin, une étude théorique des complexités en temps et en mémoire liées aux méthodes de localisation spatiale, faisant intervenir les sommes de Minkowski d'ensembles géométriques, débouche sur une stratégie consistant à minimiser la complexité en temps pour choisir les paramètres de localisation.

Cette thèse, située dans le cadre de la synthèse d'images de paysages, est consacrée à des représentations d'arbres adaptées soit au rendu de haute-qualité, soit au rendu temps réel. Les techniques de modélisation d'arbres donnent à ce jour de bons résultats en termes de diversité d'espèces et de formes représentables. Cependant, leur représentation géométrique nécessite une multitude de polygones représentant des détails fins, source d'un coût de calcul important et de gros problèmes d'aliassage lors du rendu de l'image. Pourtant, la construction de niveaux de détails par simplification de maillage ne peut s'appliquer à un arbre sans en modifier l'opacité et l'illumination globale, à cause du caractère disparate et non continu du feuillage. En suivant l'idée de représenter un ensemble de primitives (feuilles ou branches) par paquet intégrant les aspects géométriques et photométriques, nous avons conçu deux nouvelles représentations. La première, destinée au rendu haute-qualité, est basée sur le calcul analytique du modèle d'illumination global d'une géométrie représentant un rameau d'aiguilles de conifère. En nous servant des connaissances a priori concernant la distribution géométrique des aiguilles, nous avons mis au point une hiérarchie de trois shaders capables de représenter à une échelle donnée les effets cumulés des niveaux plus fins, sans avoir à les échantillonner, et en tenant compte de l'auto-ombrage et de la visibilité. Le caractère analytique de ces shaders permet à la fois d'accélérer considérablement les temps de calcul et d'obtenir des images de qualité, en particulier avec très peu d'aliassage. La deuxième, destinée au rendu temps réel, se compose d'une hiérarchie d'images correspondant à l'échantillonnage des directions de vue et de lumière, que nous affichons à l'aide de billboards en interpolant les images. Nous y associons une structure de visibilité pré-calculée, basée sur des cubes de visibilité, pour traiter l'auto-ombrage et l'ombrage en temps interactif. Notre implémentation permet l'affichage interactif d'une forêt de 1000 arbres avec illumination, auto-ombrage, ombrage, et avec possibilité de déplacer interactivement la source de lumière