No description available.

La synthèse d'images, qui consiste à développer des algorithmes pour générer des images à l'aide d'un ordinateur, est devenue incontournable dans de nombreuses disciplines. Les méthodes d'affichage interactives permettent à l'utilisateur d'explorer des environnements virtuels en réalisant l'affichage des images à une cadence suffisamment élevée pour donner une impression de continuité et d'immersion. Malgré les progrès réalisés par le matériel, de nouveaux besoins supplantent toujours les capacités de traitement, et des techniques d'accélération sont nécessaires pour parvenir à maintenir une cadence d'affichage suffisante. Ce travail s'inscrit précisemment dans ce cadre. Il est consacré à la problématique de l'élimination efficace des objets masqués, en vue d'accélérer l'affichage de scènes complexes. Nous nous sommes plus particulièrement intéressé aux méthodes de précalcul, qui effectuent les calculs coûteux de visibilité durant une phase de prétraitement et les réutilisent lors de la phase de navigation interactive. Les méthodes permettant un précalcul complet et exact sont encore hors de portée à l'heure actuelle, c'est pourquoi des techniques approchées leur sont préférée en pratique. Nous proposons trois méthodes de ce type. La première, présentée dans le chapitre 4, est un algorithme permettant de déterminer de manière exacte si deux polygones convexes sont mutuellement visibles, lorsque des écrans sont placés entre eux. Nos contributions principales ont été de simplifier cette requête, tant du point de vue théorique que du point de vue de l'implémentation, ainsi que d'accélérer son temps moyen d'exécution à l'aide d'un ensemble de techniques d'optimisation. Il en résulte un algorithme considérablement plus simple à mettre en oeuvre que les algorithmes exacts existant dans la littérature. Nous montrons qu'il est également beaucoup plus efficace que ces derniers en termes de temps de calcul. La seconde méthode, présentée dans le chapitre 5, est une approche originale pour encoder l'information de visibilité, qui consiste à stocker l'ombre que générerait chaque objet de la scène s'il était remplacé par une source lumineuse. Nous présentons une analyse des avantages et des inconvénients de cette nouvelle représentation. Finalement, nous proposons dans le chapitre 6 une méthode de calcul de visibilité adaptée aux scènes d'intérieur. Dans ce type d'environnements, les graphes cellules-portails sont très répandus pour l'élimination des objets masqués, en raison de leur faible coût mémoire et de leur grande efficacité. Nous reformulons le problème de la génération de ces graphes en termes de segmentation d'images, et adaptons un algorithme classique, appelé «watershed», pour les obtenir de manière automatique. Nous montrons que la décomposition calculée de la sorte est proche de la décomposition classique, et qu'elle peut être utilisée pour l'élimination des objets masqués.

Cette thèse traite de la modélisation, l'illumination et le rendu temps-réel de milieux participants à l'aide du GPU. Dans une première partie, nous commençons par développer une méthode de rendu de nappes de brouillard hétérogènes pour des scènes en extérieur. Le brouillard est modélisé horizontalement dans une base 2D de fonctions de Haar ou de fonctions B-Spline linéaires ou quadratiques, dont les coefficients peuvent être chargés depuis une textit{fogmap}, soit une carte de densité en niveaux de gris. Afin de donner au brouillard son épaisseur verticale, celui-ci est doté d'un coefficient d'atténuation en fonction de l'altitude, utilisé pour paramétrer la rapidité avec laquelle la densité diminue avec la distance au milieu selon l'axe Y. Afin de préparer le rendu temps-réel, nous appliquons une transformée en ondelettes sur la carte de densité du brouillard, afin d'en extraire une approximation grossière (base de fonctions B-Spline) et une série de couches de détails (bases d'ondelettes B-Spline), classés par fréquence.%Les détails sont ainsi classés selon leur fréquence et, additionnées, permettent de retrouver la carte de densité d'origine. Chacune de ces bases de fonctions 2D s'apparente à une grille de coefficients. Lors du rendu sur GPU, chacune de ces grilles est traversée pas à pas, case par case, depuis l'observateur jusqu'à la plus proche surface solide. Grâce à notre séparation des différentes fréquences de détails lors des pré-calculs, nous pouvons optimiser le rendu en ne visualisant que les détails les plus contributifs visuellement en avortant notre parcours de grille à une distance variable selon la fréquence. Nous présentons ensuite d'autres travaux concernant ce même type de brouillard : l'utilisation de la transformée en ondelettes pour représenter sa densité via une grille non-uniforme, la génération automatique de cartes de densité et son animation à base de fractales, et enfin un début d'illumination temps-réel du brouillard en simple diffusion. Dans une seconde partie, nous nous intéressons à la modélisation, l'illumination en simple diffusion et au rendu temps-réel de fumée (sans simulation physique) sur GPU. Notre méthode s'inspire des Light Propagation Volumes (volume de propagation de lumière), une technique à l'origine uniquement destinée à la propagation de la lumière indirecte de manière complètement diffuse, après un premier rebond sur la géométrie. Nous l'adaptons pour l'éclairage direct, et l'illumination des surfaces et milieux participants en simple diffusion. Le milieu est fourni sous forme d'un ensemble de bases radiales (blobs), puis est transformé en un ensemble de voxels, ainsi que les surfaces solides, de manière à disposer d'une représentation commune. Par analogie aux LPV, nous introduisons un Occlusion Propagation Volume, dont nous nous servons, pour calculer l'intégrale de la densité optique entre chaque source et chaque autre cellule contenant soit un voxel du milieu, soit un voxel issu d'une surface. Cette étape est intégrée à la boucle de rendu, ce qui permet d'animer le milieu participant ainsi que les sources de lumière sans contrainte particulière. Nous simulons tous types d'ombres : dues au milieu ou aux surfaces, projetées sur le milieu ou les surfaces / This thesis deals with modeling, illuminating and rendering participating media in real-time using graphics hardware. In a first part, we begin by developing a method to render heterogeneous layers of fog for outdoor scenes. The medium is modeled horizontally using a 2D Haar or linear/quadratic B-Spline function basis, whose coefficients can be loaded from a fogmap, i.e. a grayscale density image. In order to give to the fog its vertical thickness, it is provided with a coefficient parameterizing the extinction of the density when the altitude to the fog increases. To prepare the rendering step, we apply a wavelet transform on the fog's density map, and extract a coarse approximation and a series of layers of details (B-Spline wavelet bases).These details are ordered according to their frequency and, when summed back together, can reconstitute the original density map. Each of these 2D function basis can be viewed as a grid of coefficients. At the rendering step on the GPU, each of these grids is traversed step by step, cell by cell, since the viewer's position to the nearest solid surface. Thanks to our separation of the different frequencies of details at the precomputations step, we can optimize the rendering by only visualizing details that contribute most to the final image and abort our grid traversal at a distance depending on the grid's frequency. We then present other works dealing with the same type of fog: the use of the wavelet transform to represent the fog's density in a non-uniform grid, the automatic generation of density maps and their animation based on Julia fractals, and finally a beginning of single-scattering illumination of the fog, where we are able to simulate shadows by the medium and the geometry. In a second time, we deal with modeling, illuminating and rendering full 3D single-scattering sampled media such as smoke (without physical simulation) on the GPU. Our method is inspired by light propagation volumes, a technique whose only purpose was, at the beginning, to propagate fully diffuse indirect lighting. We adapt it to direct lighting, and the illumination of both surfaces and participating media. The medium is provided under the form of a set of radial bases (blobs), and is then transformed into a set of voxels, together with solid surfaces, so that both entities can be manipulated more easily under a common form. By analogy to the LPV, we introduce an occlusion propagation volume, which we use to compute the integral of the optical density, between each source and each other cell containing a voxel either generated from the medium, or from a surface. This step is integrated into the rendering process, which allows to animate participating media and light sources without any further constraint

[pt] Este trabalho apresenta uma nova proposta para a implementação de um sistema de partículas em GPU. A simulação é feita inteiramente no processador gráfico, o que elimina a transferência de dados entre a CPU e a GPU. O sistema proposto é capaz de simular partículas de diferentes diâmetros em ambientes confinados, incluindo tratamento de colisão entre partículas, restrições e colisão de partículas com o ambiente. A detecção de colisão entre as partículas é feita com base numa estrutura de subdivisão do espaço em uma grade regular de células. Em GPUs atuais, o sistema é capaz de simular um milhão de partículas a taxas iterativas. Também é proposto um método flexível para modelar os obstáculos que compõe o ambiente, permitindo a criação de diferentes cenas sem necessidade de re-codificação de shaders. O sistema é composto por diferentes shaders, responsáveis por cada etapa da simulação. Um programa de fragmentos é responsável por fazer a atualização da posição das partículas. Em seguida, um programa de vértices faz a montagem da estrutura de subdivisão espacial. As etapas seguintes (detecção e tratamento de colisão e de restrições) são efetuadas apenas por programas de fragmentos usando a técnica de relaxação. / [en] This work presents a new proposal for the implementation of a GPU-based particle system. The simulation runs entirely on the graphic processor, thus eliminating data transfer between the CPU and the GPU. The proposed system is able to simulate particles with different diameters in confined environments, including support for inter-particle collisions, constraints, and particle-obstacle collisions. Inter-particle collision detection is accomplished by subdividing the space into a regular grid of cells. On modern graphics cards, the system is able to simulate up to one million particles at interactive rate. It is also proposed a flexible approach for modeling the obstacles that define the environment, allowing the creation of different scenes without relying on shader re-coding. The system is divided in different shaders responsible for each stage of the simulation. One fragment program is responsible to advance the particles in time. After that a vertex program builds the space subdivision structure. The following stages (collision detection and response, and constraint solving) are performed only by fragment programs using the relaxation method.

La synthèse de textures est une technique qui génère une texture automatiquement grâce à un algorithme. Cette technique permet de réduire le temps de création des textures et le coût mémoire étant donné que seuls les algorithmes et leurs paramètres ont besoin d'être stockés. Cependant, des difficultés sont souvent rencontrées lors de l'utilisation des textures synthétisées. D'abord, les paramètres de ces textures sont difficiles à manipuler. Ensuite, l'algorithme de synthèse génère souvent les textures sous forme de tableaux de pixels nécessitant beaucoup de mémoire. Pour aborder ces difficultés, nous proposons les approches suivantes : pour améliorer la visualisation de l'espace des textures synthétisées, nous proposons de construire un résumé de cet espace: une seule image statique qui résume, dans un espace limité de pixels, les apparences produites par un synthétiseur donné. De plus, pour améliorer la sélection de paramètres, nous augmentons les curseurs qui contrôlent les paramètres avec des bandes visuelles révélant les changements qui se produisent quand l'utilisateur manipule les curseurs. Pour permettre à l'utilisateur d'interagir de manière interactive avec les résumés visuels, nous nous reposons sur un algorithme de synthèse par patch permettant de générer les textures de façon rapide grâce à une implémentation parallèle sur le processeur graphique. Au lieu de générer le résultat de ce synthétiseur sous forme d'un tableau de pixels, nous représentons le résultat dans une structure compacte et nous utilisons une méthode rapide permettant de lire des pixels directement à partir de cette structure / Texture synthesis is a technique that algorithmically generates textures at rendering time. The automatic synthesis reduces authoring time and memory requirements since only the algorithm and its parameters need to be stored or transferred. However, two difficulties often arise when using texture synthesis: First, the visualization and parameters selection of synthesized textures are difficult. Second, most synthesizers generate textures in a bitmap format leading to high memory usage. To address these difficulties we propose the following approaches: First, to improve the visualization of synthesized textures we propose the idea of a procedural texture preview: A single static image summarizing in a limited pixel space the appearances produced by a given synthesizer. The main challenge is to ensure that most appearances are visible, are allotted a similar pixel area, and are ordered in a smooth manner throughout the preview. Furthermore, to improve parameters selection we augment sliders controlling parameters with visual previews revealing the changes that will be introduced upon manipulation. Second, to allow user interactions with these visual previews we rely on a fast patch-based synthesizer. This synthesizer achieves a high degree of parallelism and is implemented entirely on the GPU. Finally, rather than generating the output of the synthesizer as a bitmap texture we encode the result in a compact representation and allow to decoding texels from this representation during rendering

A seamless blending of the real and virtual worlds is key to increased immersion and improved user experiences for augmented reality (AR). Photorealistic and non-photorealistic rendering (NPR) are two ways to achieve this goal. Non-photorealistic rendering creates an abstract and stylized version of both the real and virtual world, making them indistinguishable. This could be particularly useful in some applications (e.g., AR/VR aided machine repair, or for virtual medical surgery) or for certain AR games with artistic stylization. Achieving temporal coherence is a key challenge for all NPR algorithms. Rendered results are temporally coherent when each frame smoothly and seamlessly transitions to the next one without visual flickering or artifacts that distract the eye from perceived smoothness. NPR algorithms with coherence are interesting in both general computer graphics and AR/VR areas. Rendering stylized AR without coherence processing causes the final results to be visually distracting. While various NPR algorithms with coherence support have been proposed in general graphics community for video processing, many of these algorithms require thorough analysis of all frames of the input video and cannot be directly applied to real-time AR applications. We have investigated existing NPR algorithms with coherence in both general graphics and AR/VR areas. These algorithms are divided into two categories: Model Space and Image Space. We present several NPR algorithms with coherence for AR: a watercolor inspired NPR algorithm, a painterly rendering algorithm, and NPR algorithms in the model space that can support several styling effects.

Thesis (M. S.)--Electrical and Computer Engineering, Georgia Institute of Technology, 2009. / Committee Chair: Jayant, Nikil; Committee Member: Altunbasak, Yucel; Committee Member: Sivakumar, Raghupathy. Part of the SMARTech Electronic Thesis and Dissertation Collection.

Dans cette thèse, nous avons proposé un modèle multi-échelle pour l'animation de rivière. Nous avons présenté un nouveau modèle pour chaque échelle. A l'échelle macro, nous avons proposé une méthode procédurale permettant de générer une rivière réaliste à la volée. A l'échelle méso nous avons amélioré un modèle phénoménologique basé sur une représentation vectorielle des ondes de choc près des obstacles, et proposé une methode pour la reconstruction adaptative de la surface de l'eau. A l'échelle micro, nous avons présenté une méthode adaptative pour texturer des surfaces de grande étendue avec des performances indépendantes de la scène. Nous avons également propos é une méthode d'advection de texture. Ces deux modèles reposent sur notre schéma d'échantillonnage adaptatif. En combinant ces modèles, nous avons pu animer des rivières de taille mondiale en temps réel, tout en étant contr?olable. Les performances de notre système sont indépendantes de la scène. La vitesse procédurale et l'échantillonage en espace écran permettent à notre système de fonctionner sur des domaines illimités. Les utilisateurs peuvent observer la rivière de très près ou de très loin à tout moment. Des vagues très détaillées peuvent être affichées. Les différents parties des rivières sont continues dans l'espace et dans le temps, même lors de l'exploration ou de l'édition de la rivière par un utilisateur. Cela signifie que l'utilisateur peut éditer les lits des rivières ou ajouter des îles à la volée sans interrompre l'animation. La vitesse de la rivière change dès que l'utilisateur en édite les caractéristiques, et l'utilisateur peut auss modifier son apparence avec des textures.

Au cours des deux dernières décennies, les applications temps réel ont montré des améliorations colossales dans la génération de rendus photoréalistes. Cela est principalement dû à la disponibilité de modèles 3D avec une quantité croissante de détails. L'approche traditionnelle pour représenter et visualiser des objets 3D hautement détaillés est de les décomposer en un maillage basse fréquence et une carte de déplacement encodant les détails. La tessellation matérielle est le support idéal pour implémenter un rendu efficace de cette représentation. Dans ce contexte, nous proposons une méthode générale pour la génération et le rendu de maillages multi-résolutions compatibles avec la tessellation matérielle. Tout d'abord, nous introduisons une métrique dépendant de la vue capturant à la fois les distorsions géométriques et paramétriques, permettant de sélectionner la le niveau de résolution approprié au moment du rendu. Deuxièmement, nous présentons une nouvelle représentation hiérarchique permettant d'une part des transitions temporelles et spatiales continues entre les niveaux et d'autre part une tessellation matérielle non uniforme. Enfin, nous élaborons un processus de simplification pour générer notre représentation hiérarchique tout en minimisant notre métrique d'erreur. Notre méthode conduit à d'énormes améliorations tant en termes du nombre de triangles affiché qu'en temps de rendu par rapport aux méthodes alternatives. / In the last two decades, real-time applications have exhibited colossal improvements in the generation of photo-realistic images. This is mainly due to the availability of 3D models with an increasing amount of details. Currently, the traditional approach to represent and visualize highly detailed 3D objects is to decompose them into a low-frequency mesh and a displacement map encoding the details. The hardware tessellation is the ideal support to implement an efficient rendering of this representation. In this context, we propose a general framework for the generation and the rendering of multi-resolution feature-aware meshes compatible with hardware tessellation. First, we introduce a view-dependent metric capturing both geometric and parametric distortions, allowing to select the appropriate resolution at rendertime. Second, we present a novel hierarchical representation enabling on the one hand smooth temporal and spatial transitions between levels and on the other hand a non-uniform hardware tessellation. Last, we devise a simplification process to generate our hierarchical representation while minimizing our error metric. Our framework leads to huge improvements both in terms of triangle count and rendering time in comparison to alternative methods.

In computer graphics, the complex phenomenon of color appearance, involving the interaction of light, matter and the human visual system, is modeled by the multiplication of RGB triplets assigned to lights and materials. This efficient heuristic produces plausible images because the triplets assigned to materials usually function as color specifications. To predict color, spectral rendering is required, but the O(n) cost of computing reflections with n-dimensional point-sampled spectra is prohibitive for real-time rendering. Typical spectra are well approximated by m-dimensional linear models, where m << n, but computing reflections with this representation requires O(m^2) matrix-vector multiplication. A method by Drew and Finlayson [JOSA A 20, 7 (2003), 1181-1193], reduces this cost to O(m) by “sharpening” an n x m orthonormal basis with a linear transformation, so that the new basis vectors are approximately disjoint. If successful, this transformation allows approximated reflections to be computed as the products of coefficients of lights and materials. Finding the m x m change of basis matrix requires solving m eigenvector problems, each needing a choice of wavelengths in which to sharpen the corresponding basis vector. These choices, however, are themselves an optimization problem left unaddressed by the method's authors. Instead, we pose a single problem, expressing the total approximation error incurred across all wavelengths as the sum of dm^2 squares for some number d, where, depending on the inherent dimensionality of the rendered reflectance spectra, m <= d << n, a number that is independent of the number of approximated reflections. This problem may be solved in real time, or nearly, using standard nonlinear optimization algorithms. Results using a variety of reflectance spectra and three standard illuminants yield errors at or close to the best lower bound attained by projection onto the leading m characteristic vectors of the approximated reflections. Measured as CIEDE2000 color differences, a heuristic proxy for image difference, these errors can be made small enough to be likely imperceptible using values of 4 <= m <= 9. An examination of this problem reveals a hierarchy of simpler, more quickly solved subproblems whose solutions yield, in the typical case, increasingly inaccurate approximations. Analysis of this hierarchy explains why, in general, the lowest approximation error is not attained by simple spectral sharpening, the smallest of these subproblems, unless the spectral power distributions of all light sources in a scene are sufficiently close to constant functions. Using the methods described in this dissertation, spectra can be rendered in real time as the products of m-dimensional vectors of sharp basis coefficients at a cost that is, in a typical application, a negligible fraction above the cost of RGB rendering. / Graduate