La géométrie numérique en temps réel est un domaîne de recherches émergent en informatique graphique.Pour pouvoir générer des images photo-réalistes de haute définition,beaucoup d'applications requièrent des méthodes souvent prohibitives financièrementet relativement lentes.Parmi ces applications, on peut citer la pré-visualisation d'architectures, la réalisation de films d'animation,la création de publicités ou d'effets spéciaux pour les films dits réalistes.Dans ces cas, il est souvent nécessaire d'utiliser conjointement beaucoup d'ordinateurs possédanteux-mêmes plusieurs unités graphiques (Graphics Processing Units - GPUs).Cependant, certaines applications dites temps-réel ne peuvent s'accomoder de telles techniques, car elles requièrentde pouvoir générer plus de 30 images par seconde pour offrir un confort d'utilisationet une intéraction avec des mondes virtuels 3D riches et réalistes.L'idée principale de cette thèse est d'utiliser la synthèse de géométrie,la géométrie numérique et l'analyse géométrique pourrépondre à des problèmes classiques en informatique graphique,telle que la génération de surfaces de subdivision, l'illumination globaleou encore l'anti-aliasing dans des contextes d'intéraction temps-réel.Nous présentons de nouveaux algorithmes adaptés aux architectures matérielles courantes pour atteindre ce but. / Eal-time geometry synthesis is an emerging topic in computer graphics.Today's interactive 3D applications have to face a variety of challengesto fulfill the consumer's request for more realism and high quality images.Often, visual effects and quality known from offline-rendered feature films or special effects in movie productions are the ultimate goal but hard to achieve in real time.This thesis offers real-time solutions by exploiting the Graphics Processing Unit (GPU)and efficient geometry processing.In particular, a variety of topics related to classical fields in computer graphics such assubdivision surfaces, global illumination and anti-aliasing are discussedand new approaches and techniques are presented.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

De nos jours, les images de synthèse occupent une place de plus en plus importante dans des domaines aussi variés que l'ingénierie ou le divertissement. Le matériel informatique a énormément évolué ces dernières années afin de pouvoir suivre cette tendance. Cependant, le matériel ne peut satisfaire seul aux exigences, en terme de qualité et d'interactivité, que requièrent les nouvelles applications. D'où l'intérêt d'algorithmes permettant d'optimiser le temps d'exécution et l'occupation mémoire de telles applications, et notamment celles qui nécessitent une interactivité avec l'utilisateur. Le placage de déplacement tridimensionnel par pixel est une nouvelle technique qui permet d'enrichir visuellement les scènes 3D, en simulant les mesostructures (microreliefs) présentes sur de nombreux types de surface. Cette amélioration s'effectue sans modification de la définition géométrique des objets 3D, et s'appuie uniquement sur le placage de textures dédiées à cet effet. Cette technique contribue ainsi à éviter la saturation du pipeline graphique que peut provoquer le traitement d'un très grand nombre de primitives graphiques. Dans le même esprit, la technique de modélisation et rendu à base d'images, qui est une extension du placage de déplacement 3D par pixel, permet de créer et d'afficher des objets 3D dans leur intégralité, sans passer par le traditionnel maillage polygonal. Au cours de ce travail, nous nous sommes intéressés à l'une des meilleures techniques pour le placage de déplacement 3D par pixel. Il s'agit de la technique de traçage de cônes, dont nous avons pu faire passer les algorithmes de prétraitement des textures d'une complexité quadratique à une complexité linéaire. Nous avons également proposé un nouvel algorithme permettant la prise en charge des textures rectangulaires, car elles étaient très mal gérées par les méthodes existantes. Nous avons aussi développé une nouvelle approche qui rend possible la synchronisation temps réel entre la modification de l'échelle du microrelief et son ombrage. Cette thèse introduit notamment le placage d'extrusion et de révolution. Il s'agit d'une nouvelle technique de modélisation et rendu à base d'images. L'approche que nous avons adoptée permet de créer des géométries sans maillage, par extrusion ou par révolution d'une forme de base, stockée sous forme d'une image 2D binaire. Ce type de géométrie est très utilisé en modélisation 3D, et particulièrement dans la création d'environnements architecturaux. La technique proposée est très performante, que ce soit en terme d'interactivité, ou en terme de qualité visuelle.

Depuis quelques décennies, les communautés d'informatique graphique et de vision ont contribué à l'émergence de technologies permettant la numérisation d'objets 3D. Une demande grandissante pour ces technologies vient des acteurs de la culture, notamment pour l'archivage, l'étude à distance et la restauration d'objets du patrimoine culturel : statuettes, grottes et bâtiments par exemple. En plus de la géométrie, il peut être intéressant de numériser la photométrie avec plus ou moins de détail : simple texture (2D), champ de lumière (4D), SV-BRDF (6D), etc. Nous formulons des solutions concrètes pour la création et le traitement de champs de lumière surfaciques représentés par des fonctions de radiance attachés à la surface.Nous traitons le problème de la phase de construction de ces fonctions à partir de plusieurs prises de vue de l'objet dans des conditions sur site : échantillonnage non structuré voire peu dense et bruité. Un procédé permettant une reconstruction robuste générant un champ de lumière surfacique variant de prévisible et sans artefacts à excellente, notamment en fonction des conditions d'échantillonnage, est proposé. Ensuite, nous suggérons un algorithme de simplification permettant de réduire la complexité mémoire et calculatoire de ces modèles parfois lourds. Pour cela, nous introduisons une métrique qui mesure conjointement la dégradation de la géométrie et de la radiance. Finalement, un algorithme d'interpolation de fonctions de radiance est proposé afin de servir une visualisation lisse et naturelle, peu sensible à la densité spatiale des fonctions. Cette visualisation est particulièrement bénéfique lorsque le modèle est simplifié. / Vision and computer graphics communities have built methods for digitizing, processing and rendering 3D objects. There is an increasing demand coming from cultural communities for these technologies, especially for archiving, remote studying and restoring cultural artefacts like statues, buildings or caves. Besides digitizing geometry, there can be a demand for recovering the photometry with more or less complexity : simple textures (2D), light fields (4D), SV-BRDF (6D), etc. In this thesis, we present steady solutions for constructing and treating surface light fields represented by hemispherical radiance functions attached to the surface in real-world on-site conditions. First, we tackle the algorithmic reconstruction-phase of defining these functions based on photographic acquisitions from several viewpoints in real-world "on-site" conditions. That is, the photographic sampling may be unstructured and very sparse or noisy. We propose a process for deducing functions in a manner that is robust and generates a surface light field that may vary from "expected" and artefact-less to high quality, depending on the uncontrolled conditions. Secondly, a mesh simplification algorithm is guided by a new metric that measures quality loss both in terms of geometry and radiance. Finally, we propose a GPU-compatible radiance interpolation algorithm that allows for coherent radiance interpolation over the mesh. This generates a smooth visualisation of the surface light field, even for poorly tessellated meshes. This is particularly suited for very simplified models.

The emergence of digital capture devices have enabled the developmentof 3D acquisition to scan the properties of a real object : its shape and itsappearance. This process provides a dense and accurate representation of realobjects and allows to avoid the costly process of physical simulation to modelan object. Thus, the issues have evolved and are no longer focus on modelingthe characteristics of a real object only but on the treatment of data fromacquisition to integrate a copy of reality in a process of image synthesis. In this thesis, we propose new representations for appearance functions from the acquisition with the aim of defining a set of multicale models of low complexity in size working in real time on the today's graphics hardware / L'émergence des périphériques de capture numériques ont permis le développement de l'acquisition 3D pour numériser les propriétés d'un objet réel : sa forme et son apparence. Ce processus fournit une représentation dense et précise d'objets réels et permet de s'abstraire d'un processus des imulation physique coûteux pour modéliser un objet. Ainsi, les problématiquesont évolué et portent non plus uniquement sur la modélisation descaractéristiques d'un objet réel mais sur les traitements de données issues de l'acquisition pour intégrer une copie de la réalité dans un processus de synthèse d'images. Dans ces travaux de thèse, nous proposons de nouvelles représentations pour les fonctions d'apparence issues de l'acquisition dont le but est de définir un ensemble de modèles multi-échelles, de faible complexité en taille, capable d'e^tre visualisé en temps réel sur le matériel graphique actuel.

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.

Etant donné un ensemble de caméras filmant une même scène, le rendu à base de vidéos consiste à générer de nouvelles images de cette scène à partir de nouveaux points de vue. L'utilisateur a ainsi l'impression de pouvoir déplacer une caméra virtuelle dans la scène alors qu'en réalité, toutes les caméras sont fixes. Certaines méthodes de rendu à base de vidéos coûteuses en temps de calcul se basent sur une reconstruction 3d de la scène et produisent des images de très bonne qualité. D'autres méthodes s'orientent plutôt vers le rendu temps réel. C'est dans cette dernière catégorie que s'inscrit la méthode de Plane Sweep sur laquelle porte la majeure partie de nos travaux. Le principe de la méthode des Plane Sweep consiste à discrétiser la scène en plans parallèles et à traiter séparément chaque point de ces plans afin de déterminer s'ils se trouvent ou non sur la surface d'un objet de la scène. Les résultats obtenus permettent de générer une nouvelle image de la scène à partir d'un nouveau point de vue. Cette méthode est particulièrement bien adaptée à une utilisation optimale des ressources de la carte graphique ce qui explique qu'elle permette d'effectuer du rendu en temps réel. Notre principale contribution à cette méthode concerne la façon d'estimer si un point d'un plan représente la surface d'un objet. Nous proposons d'une part un nouveau mode de calcul permettant d'améliorer le résultat visuel tout en rendant la navigation de la caméra virtuelle plus souple. D'autre part, nous présentons une adaptation de la méthode des Plane Sweep permettant de gérer les occlusions partielles. Compte tenu des applications du rendu à base de vidéos en réalité virtuelle, nous proposons une amélioration des Plane Sweep appliquée à la réalité virtuelle avec notamment la création de paires d'images stéréoscopiques permettant de visualiser en relief la scène reconstruite. Notre amélioration consiste à calculer la seconde vue à moindre coût alors qu'une majorité des méthodes concurrentes sont contraintes d'effectuer deux rendus indépendants. Cette amélioration est basée sur un partage des données communes aux deux vues stéréoscopiques. Enfin, dans le cadre de l'utilisation des Plane Sweep en réalité virtuelle, nous présentons une méthode permettant de supprimer les mouvements pseudoscopiques. Ces mouvements pseudoscopiques apparaissent lorsque l'observateur se déplace devant une image stéréoscopique, il ressent alors une distorsion des proportions de la scène virtuelle et voit les objets se déplacer de façon anormale. La méthode de correction que nous proposons est applicable d'une part à des méthodes classiques de rendu d'images de synthèse et d'autre part à la méthode des Plane Sweep. Toutes les méthodes que nous présentons utilisent largement les possibilités du processeur de la carte graphique à l'aide des shader programs et génèrent toutes des images en temps réel. Seuls un ordinateur grand public, un dispositif d'acquisition vidéo et une bonne carte graphique sont suffisants pour les faire fonctionner. Les applications des Plane Sweep sont nombreuses, en particulier dans les domaines de la réalité virtuelle, du jeu vidéo, de la télévision 3d ou de la sécurité.

La représentation des surfaces du monde réel dans la mémoire d'une machine peut désormais être obtenue automatiquement via divers périphériques de capture tels que les scanners 3D. Ces nouvelles sources de données, précises et rapides, amplifient de plusieurs ordres de grandeur la résolution des surfaces 3D, apportant un niveau de précision élevé pour les applications nécessitant des modèles numériques de surfaces telles que la conception assistée par ordinateur, la simulation physique, la réalité virtuelle, l'imagerie médicale, l'architecture, l'étude archéologique, les effets spéciaux, l'animation ou bien encore les jeux video. Malheureusement, la richesse de la géométrie produite par ces méthodes induit une grande, voire gigantesque masse de données à traiter, nécessitant de nouvelles structures de données et de nouveaux algorithmes capables de passer à l'échelle d'objets pouvant atteindre le milliard d'échantillons. Dans cette thèse, je propose des solutions performantes en temps et en espace aux problèmes de la modélisation, du traitement géométrique, de l'édition intéractive et de la visualisation de ces surfaces 3D complexes. La méthodologie adoptée pendant l'élaboration transverse de ces nouveaux algorithmes est articulée autour de 4 éléments clés : une approche hiérarchique systématique, une réduction locale de la dimension des problèmes, un principe d'échantillonage-reconstruction et une indépendance à l'énumération explicite des relations topologiques aussi appelée approche basée-points. En pratique, ce manuscrit propose un certain nombre de contributions, parmi lesquelles : une nouvelle structure hiérarchique hybride de partitionnement, l'Arbre Volume-Surface (VS-Tree) ainsi que de nouveaux algorithmes de simplification et de reconstruction ; un système d'édition intéractive de grands objets ; un noyau temps-réel de synthèse géométrique par raffinement et une structure multi-résolution offrant un rendu efficace de grands objets. Ces structures, algorithmes et systèmes forment une chaîne capable de traiter les objets en provenance du pipeline d'acquisition, qu'ils soient représentés par des nuages de points ou des maillages, possiblement non 2-variétés. Les solutions obtenues ont été appliquées avec succès aux données issues des divers domaines d'application précités.

La cryptographie visuelle consiste à partager entre plusieurs « Shadow Images » (SIs) un secret qui ne se révèlera à l'oeil de l'observateur qu'à leur superposition. Depuis les travaux de Naor et Shamir, ce procédé cryptographique a été étendu à Des schémas numériques variés, adaptés à diverses problématiques. En revanche, les travaux concernant son implémentation physique sont peu nombreux à ce jour. Cette thèse est consacrée à l'implémentation de la cryptographie visuelle sur des SIs imprimés en demi-tons en vue de l'authentification de documents. Le SI associé au document peut être imprimé sur support opaque ou transparent, les autres SIs étant imprimés sur films transparents. Nous avons résolu la difficulté de leur superposition par une méthode de Fourier permettant le recalage de la structure quasi-périodique d'un SI. La précision de cette méthode nous a permis de développer un système optique de superposition par projection. On verra que les phénomènes physiques responsables du rendu visuel de SIs superposés sont propices à une protection contre la copie illicite du SI associé à un document. La complexité de ces phénomènes et leur dépendance au type d'impression imposent une modélisation physique pour obtenir un rendu précis. Cette approche nous a conduit à considérer la problématique de la reproduction des couleurs et à développer des modèles spectraux adaptés à la superposition de supports imprimés non diffusants et/ou diffusants, en réflexion et en transmission. La précision de ces modèles prédictifs est tout à fait satisfaisante au regard de celle habituellement obtenue dans le domaine de la reproduction des couleurs. Cela nous a permis d'introduire une approche originale de la cryptographie visuelle par ajustement de couleur (color matching) : une même couleur, à une tolérance près basée sur la vision humaine, est générée par différents demi-tons imprimés sur les supports à superposer. La couleur du message peut ainsi constituer un secret partagé entre les SIs de la même façon que l'est le contenu du message. Chaque SI pris individuellement ne laisse fuir aucune information sur la couleur du message, qui ne sera révélée qu'à leur superposition. Cela peut permettre de prévenir une attaque par falsification du SI associé au document (cheating attack ). De plus, le rendu des couleurs étant très dépendant du système d'impression utilisé, une reproduction fidèle à partir d'un système d'impression différent est difficile. La difficulté peut être encore accrue par l'utilisation de caractéristiques d'impression non standard / In this thesis, we will focus on the physical implementation of visual cryptography, which consists in sharing a secret message between several unmeaning images, so-called shadow images, at least one of them being printed. By the principle of the method, no information leaks about the message until the images are properly stacked together. As the alignment of the shadow images hampers the deployment of the visual cryptography in practice, we develop a dedicated image registration method. In contrast with existing methods, ours is not intrusive. We make use of the particular shape of the elementary constituents of the shadow images, the shares, to extract in the Fourier domain the main parameters of the geometrical transformations occurring between the superposed images. We prove that this method allows subpixel accuracy in shadow images registration. We benefit from such ability by implementing visual cryptography in an image projection configuration : the digital shadow image is projected onto the printed one. In this way, the registration is performed automatically by using a digital camera (the resulting superposition being observable by the eye). For the purpose of authentication, one has to deal with specific attacks: the shadow image attached to a given document could be tampered with or copied. In order to prevent such attacks, we have increased the di_culty to reproduce the shadow image by considering color. This approach requires a complete management of colors. Thanks to recent advances in color reproduction, we are able to predict the reflectance and transmittance spectra of supports printed in color. In this thesis, we develop new spectral prediction models namely for piles of printed transparencies as well as for transparencies stacked onto papers, all printed in color. Thus, we are able to predict the color of each share in a shadow image to be printed and to achieve color matching i.e. we are able to reach a color by various combinations of superposed colors. Such a prediction allowed us to introduce a new approach in visual cryptography: color matching when revealing the secret message to be shared into two (or more) shadow images, in order to authenticate the shadow images provider. As the prediction models are sensitive to the calibration of the printing system (printer, inks, supports, halftoning and geometry measurement conditions), the use of special materials will increase the di_culty to generate visually acceptable fake pairs of shadow images

Les surfaces nanostructurées permettent d’obtenir des effets colorés gonio-apparents lorsque les nanostructures présentent des dimensions de l’ordre des longueurs d’onde du spectre visible. ces couleurs sont habituellement modélisées par le biais d’interactions de types «interférences» ou «cristaux photoniques» entre le rayonnement lumineux et une structure modèle. dans cette thèse, l’anodisation d’aluminium est utilisée comme méthode de structuration à l’échelle submicronique. cette technique présente l’avantage d’être mature industriellement et de permettre de structurer de grandes surfaces. des effets colorés sont observés même si les structures obtenues ne sont pas parfaitement ordonnées. le but de cette thèse est de comprendre les phénomènes optiques mis en jeu dans l’obtention de ces effets. ce manuscrit se divise donc en deux parties principales, toutes deux basées sur une étude de la littérature existante. afin d’établir un parallèle entre caractérisation expérimentale et simulation numérique, la première partie présente l’outil de caractérisation optique développé. la seconde est dédiée à l’étude des effets colorés de certaines surfaces d’aluminium anodisé. cette partie propose une compréhension des phénomènes d’interaction de la lumière avec la structure d’aluminium anodisé se basant sur les caractérisations optiques et microstructurales des échantillons, associées à une modélisation de l’interaction entre rayonnement et matière structurée. cette étude montre que les structures réelles présentent un ordre à courte distance. les effets colorés sont simulés par la méthode modale de fourier par le biais de structures modèles avec un certain niveau de désordre. / Nano-structured surfaces allow obtaining of colored gonio-apparent effects when the nano-structures dimensions are of the order of the visible spectrum wavelengths. these colors are usually modeled by means of the interactions type so-called « interferences type » ou « photonic crystals type » between the luminous radiation and a model structure. in this thesis, the anodization of aluminum substrates is used to produce surface structures at the submicron scale. this technique is industrially mature and allows to structure large surfaces. color effects were observed even if obtained structures are not perfectly ordered. the aim of this thesis is the understanding of the optical phenomena involved in the production of such effects. this manuscript is divided into two main parts, both based on the existing literature analysis. in order to draw a parallel between experimental characterization and numerical simulations, one part presents the instrumental development of the optical characterization instrument. the second one is dedicated to the study of color effect of certain anodized aluminum surfaces. this part proposes an understanding of the interaction phenomena between the light and the anodized aluminum structure, based on the optical and microstructural characterization of the samples, associated to a modeling of the interaction between light and structured matter. this study shows that such structures present a short-distance order. the color effects are simulated numerically by fourier modal method by the means of model-structures with certain disorder degree.