Calculer automatiquement une séquence d'images cinématographiquement cohérente, sur un ensemble d'actions qui se produisent dans un monde 3D, est une tâche complexe. Elle nécessite non seulement le calcul des plans de caméra ( points de vue ) et les transitions appropriées entre ces plans (coupures), mais aussi la capacité d'encoder et de reproduire des éléments de style cinématographique. Les modèles proposés dans la littérature, fondés généralement sur des représentations à machines d'états finis (FSMs), fournissent des fonctionnalités limitées pour construire des séquences de plans et ne permettent pas d'effectuer d'importantes variations de style sur une même séquence d'actions. Dans cette thèse, nous proposons d'abord un modèle cinématographique expressif, basé données, qui peut calculer des variations significatives en termes de style, avec la possibilité de contrôler la durée des prises de vue et la possibilité d'ajouter des contraintes spécifiques à la séquence souhaitée. Le modèle est paramétré de manière à faciliter l'application de techniques d'apprentissage pour reproduire des éléments de style extraits de films réels en utilisant une représentation à base de modèle de Markov caché du processus de montage. Le modèle proposé est à la fois plus général que les représentations existantes, et se révèle être plus expressif dans sa capacité à encoder précisément des éléments de style cinématographique pour des scènes de dialogues. Ensuite, nous introduisons une extension plus générique pour généraliser notre système de montage afin de traiter des contenus cinématographique plus complexes (autres que les dialogues). Il s'agit d'utiliser des Réseaux bayésiens dynamiques à la place des modèles de Markov à états cachés. Enfin, nous avons conçu un outil d'annotation et un format de représentation de données cinématographiques afin de simplifier le processus de création et de manipulation de ses données. Les données collectées serviront comme bases d'apprentissage pour des techniques basées données, telles que les nôtres, ainsi que pour l'analyse de films. / Automatically computing a cinematographically consistent sequence of shots, over a set of actions occurring in a 3D world, is a complex task which requires not only the computation of appropriate shots (viewpoints) and appropriate transitions between shots (cuts), but the ability to encode and reproduce elements of cinematographic style. The models proposed in the literature, generally rule-based, provide limited functionalities to build sequences of shots. These approaches are not designed in mind to easily learn elements of cinematographic style, nor do they allow to perform significant variations in style over the same sequence of actions. In this thesis, we first propose a data-driven model for automated cinematography (framing and editing) that can compute significant variations in terms of cinematographic style, with the ability to control the duration of shots and the possibility to add specific constraints to the desired sequence. By using a Hidden Markov Model representation of the editing process, we demonstrate the possibility of easily reproducing elements of style extracted from real movies. The proposed model is more elaborate in handling dialogue scenes than existing representations, and proves to be more expressive in its ability to precisely encode elements of cinematographic style. Then, we introduce an extension of this model to account for more complex environments (more than dialogues). To this end, we use a more general statistical model: Dynamic Bayesian Network, which enlarges considerably the possibilities in editing and film analysis. We finally designed a data annotation tool and a format to easily create film annotations that would be used for data-driven cinematography or film analysis.

Une image numérique peut être définie comme un ensemble de n-xels sur une grille constituée de n-cubes. La segmentation consiste à calculer une partition d'une image en régions. Les n-xels ayant des caractéristiques similaires (couleur, intensité, etc.) sont regroupés. Schématiquement, à chaque n-xel est attribuée une étiquette, et chaque région de l'image est constituée de n-xels de même étiquette. Les méthodes "de type" Marching cubes et Kenmochi et al. construisent des complexes représentant la topologie de la région d'intérêt d'une image numérique binaire de dimension 3. Dans la première méthode, l'algorithme construit un complexe simplicial, dont 0-cellules sont des points des arêtes de la grille duale. Dans la deuxième méthode, les auteurs construisent un complexe cellulaire sur une grille duale, c.a.d les 0-cellules du complexe sont des sommets de la grille duale. Afin de construire le complexe, Kenmochi et al. calculent (à rotations près) les différentes configurations de sommets blancs et noirs d'un cube, puis, ils construisent les enveloppes convexes des points noirs de ces configurations. Ces enveloppes convexes définissent les cellules du complexe, à rotations près. Le travail développé dans cette thèse étend la méthode de Kenmochi et al. en dimension 4. L'objectif est de construire un complexe cellulaire à partir d'une image numérique binaire définie sur une grille duale. Nous calculons d'abord les différentes configurations de sommets blancs et noirs d'un 4-cube (à isométries près), puis, nous construisons des enveloppes convexes définies par ces configurations. Ces enveloppes convexes sont construites par déformation du 4-cube d'origine, et nous distinguon / A digital image can be defined as a set of n-xels on a grid made up by n-cubes. Segmentation consists in computing a partition of an image into regions. The n-xels having similar characteristics (color, intensity, etc.) are regrouped. Schematically, each n-xel is assigned a label, and each region of the image is made up by n-xels with the same label. The methods "type" Marching cubes and Kenmochi et al. construct complexes representing the topology of the region of interest of a 3-dimensional binary digital image. In the first method, the algorithm constructs a simplicial complex, whose 0-cells are points of the edges of the dual grid. Inthe second one, the authors construct a cell complex on a dual grid, i.e. the 0-cells of the complex are vertices of the dual grid. In order to construct the complex, Kenmochi et al. compute (up to rotations) the different configurations of white and black vertices of a cube, and then, they construct the convex hulls of the black points of these configurations. These convex hulls define the cells of the complex, up to rotations. The work developed in this thesis extends Kenmochi et al. method todimension 4. The goal is to construct a cell complex from a binary digital image defined on a dual grid. First, we compute the different configurations of white and black vertices of a 4-cube, up to isometries, and then, we construct the convex hulls defined by these configurations. These convex hulls are constructed by deforming the original 4-cube, and we distinguishseveral basic construction operations (deformation, degeneracy of cells, etc.). Finally, we construct the cell complex corresponding to the dual image by assembling the cells so o / Una imagen digital puede ser definida como un conjunto de n–xeles en un mallado constituido de n–cubos. Los n–xeles pueden ser identificados con: (1) los n–cubos del mallado, o con (2) los puntos centrales de estos n–cubos. En el primer caso, trabajamos con un mallado primal, mientras que en el segundo, trabajamos con un mallado dual construido a partir del mallado primal. La segmentación consiste en calcular una partición de una imagen en regiones. Los n–xeles que tienen características similares (color, intensidad, etc.) son reagrupados. Esquemáticamente, a cada n–xel se le asocia una etiqueta, y cada región de la imagen está constituida de n–xeles con la misma etiqueta. En particular, si las únicas etiquetas permitidas para los n–xeles son “blanca” y “negra”, la segmentación se dice binaria: los n–xeles negros forman el primer plano (foreground) o región de interés en cuestión de análisis de la imagen, y los n–xeles blancos forman el fondo (background). Ciertos modelos, como los Grafos de Adyacencia de Regiones (RAGs), los Grafos Duales (DGs) y la carta topológica, han sido propuestos para representar las particiones en regiones, y en particular para representar la topología de estas regiones, es decir las relaciones de incidencia y/o adyacencia entre las diferentes regiones. El RAG [27] es un precursor de este tipo de modelos, y ha sido una fuente de inspiración de los DGs [18] y de la carta topológica [9, 10]. Un RAG representa una imagen primal etiquetada por un grafo: los vértices del grafo corresponden a regiones de la imagen, y las aristas del grafo representan las relaciones de adyacencia entre la regiones. Los DGs son un modelo que permite resolver ciertos inconvenientes de los RAGs para representar imágenes de dimensión 2. La carta topológica es una extensión de los modelos anteriores definida para manipular imágenes primales de dimensión 2 y 3, representando no solamente las relaciones topológicas, sino también las relaciones geométricas.

En informatique graphique, le rendu des matériaux occupe une place très importante dans la qualité de l’image finale. De nombreux modèles ont contribué à améliorer l’apparence des matériaux. Aujourd’hui, certains matériaux restent encore difficiles à représenter à cause de leur complexité. Parmi ceux ci,la famille des matériaux anisotropes reste peu étudiée et complexe. Dans cette thèse nous proposons une meilleure compréhension des matériaux anisotropes au travers d’un modèle pour les représenter ainsi qu’un outil permettant de mieux en contrôler l’apparence. Notre modèle de matériaux brossés ou rayés se base sur la simulation du transport lumineux au sein de la micro-géométrie d’une rayure pour restituer tous les détails en conservant des temps de rendus suffisamment courts pour rendre la scène de manière interactive.Notre outil d’édition des reflets anisotropes utilise le champ d’orientation des BRDF pour donner à l’utilisateur l’impression de dessiner ou de déformer des reflets directement sur l’objet. / In computer graphics, material appearance is a fundamental component of the final image quality. Many models have contributed to improve material appearance. Today, some materials remains hard to represent because of their complexity. Among them, anisotopic materials are especially complex and little studied. In this thesis, we propose a better comprehension of anisotropic materials providing a representation model and an editing tool to control their appearance. Our scratched material model is based on a light transport simulation in the micro-geometry of a scratch, preserves all the details and keeps an interactive rendering time. Our anisotropic reflections edition tool uses BRDF orientation fields to give the user the impression to draw or deform reflections directly on the surface.

In this thesis, we focus on "structural information" in computer graphics, that is the information concerning the structure of 3D objects or scenes. More specifically, we define structural information as a two-scale notion, namely the object and the scene levels and propose a way of structuring 3D Geometry at both levels using the information of symmetry and instancing. In the first part of this thesis, we propose an original method to structure the geometry at the object level based on the information of symmetry. Inspired by the work on principal component analysis, we introduce for this purpose the generalized moment functions of a 3D shape. From the symmetry information that we have computed on the objects of the scene, we present in the second part of this thesis an approach to represent an unstructured 3D scene as a hierarchy of instances adapted to common tasks such as rendering or geometry editing.

A rapidly growing computer graphics community has contributed to dramatic increase in complexity with respect to geometry as well as physical phenomena. Simulating, approximating and visualizing geometry consisting of tens of millions of polygons simultaneously tested for collision or visibility is becoming increasingly common. Further, recent technological innovations from graphics card vendors have given impetus to achieving these results at very high frame rates. Despite tremendous developments in graphics hardware, capturing the complete surrounding environment poses a significant challenge. Given the added time constraint for real-time or interactive rates, simplified representations and suitable approximations of physical effects are of key importance.<br /><br />This dissertation focuses on simplified representations and computations to achieve real-time performance for complex tasks and concentrates on a variety of topics including simplification, visibility, soft shadows and voxelization.

Pour le calcul d'ombres en informatique graphique, il est courant de s'intéresser à la vue qu'un observateur a d'une scène géométrique. En particulier, il est important de caractériser les changements structurels, appelés événements visuels, qui se produisent dans cette vue lorsque l'observateur se déplace. En se basant sur la définition combinatoire de la vue proposée par Gigus et Malik et la classification des événements visuels qui en découle, de nombreux travaux se heurtent à des problèmes de complexité en temps et en espace. C'est notamment le cas de la méthode du maillage de discontinuités. Nous suggérons donc une approche nouvelle qui repose sur la remise en cause de cette notion de vue.<br /><br />Pour un ensemble d'objets convexes disjoints, nous proposons une définition topologique de la vue qui fait la part belle aux silhouettes visibles des objets de la scène et nous caractérisons géométriquement les lieux où se produisent les événements visuels. Nous utilisons cette caractérisation pour proposer une méthode qui permet d'extraire les limites entre lumière et pénombre et entre ombre et pénombre dans une scène éclairée par des sources surfaciques. Nous arrivons ainsi à réduire considérablement la taille des objets intermédiaires utilisés pour la construction des limites entre les régions.<br /><br />De plus, nous démontrons les premières bornes théoriques non triviales sur la complexité des limites entre lumière et pénombre ainsi qu'entre ombre et pénombre.

L'objet de ce mémoire est l'étude et la construction d'un modèle de surfaces fondé sur la représentation par un atlas de cartes : <br />L'intérêt d'un tel modèle est qu'il permet de travailler localement sur la sur face sans perte de la cohérence globale, et d'autre part d'hériter des notions de géométrie différentielle attachées à cette représentation pour définir une surface régulière, et donc résoudre intrinsèquement les problèmes de continuité ordinairement rencontrés par les représentations paramétriques par morceaux. Nous avons présenté ce modèle dans le cadre des modèles de surfaces d'usage courant en informatique graphique, puis dans le cadre plus théorique de la géométrie différentielle. <br /> Nous avons ensuite proposé la construction d'un tel modèle à partir d'un nuage de points 3D interpolés au préalable par une surface triangulée qui est une variété de dimension 2, connexe et compacte. Cette construction se déroule en trois étapes. Chaque étape rencontre un problème géométrique auquel nous proposons une solution innovante. En particulier, nous avons démontré que le nerf d'un recouvrement bien formé est une triangulation combinatoire. Nous avons également étudié la para métrisation d'une couronne du plan par un C1-difféomorphisme, ainsi que le raccord continu de surfaces par combinaison convexe.

Les applications graphiques tendent à offrir un rendu interactif de scènes 3D de plus en plus réaliste, résultant en partie de l'accroissement de la richesse géométrique des objets affichés. Le maillage de certains de ces objets est toutefois trop complexe au regard des capacités de traitement des cartes graphiques et doit donc être simplifié afin de conserver un bon niveau d'interactivité. Une méthode élégante pour pallier à la perte des détails les plus fins induits par la simplification consiste à les stocker sous forme de normales dans des textures de grande résolution et de les utiliser lors du calcul de l'éclairage de ces objets. Cette technique de préservation d'apparence repose cependant traditionnellement sur des opérations complexes de paramétrisation 2D de maillages 3D qui sont encore souvent impossibles à réaliser sans l'intervention d'un utilisateur. Nous proposons dans ce mémoire une méthode alternative de préservation de détails basée sur les octree-textures. La création de l'octree est pilotée par la variation des normales à la surface des maillages originaux, adaptant l'échantillonnage des normales à la richesse de détails locale de la surface. Grâce à la nature volumique des octree-textures, aucune opération de paramétrisation n'est requise, rendant le processus de création des textures totalement automatique. Nous proposons un encodage compact de l'octree sous forme de textures 2D exploitables par les GPU programmables, et nous détaillons l'utilisation de ces textures pour le rendu interactif. Nous présentons également un processus de conversion en atlas de textures 2D classiques dans lesquels tous les détails de l'octree-texture sont conservés. Enfin nous montrons l'adéquation de cette représentation des maillages détaillés avec leur visualisation à distance via le réseau. La transmission instantanée du maillage simpliée permet une interaction immédiate avec l'objet 3D pendant que l'affichage se raffine progressivement à mesure du téléchargement des normales les plus précises.

L'édition, la création, et le design digital mènent la flexibilité des ordinateurs vers l'acte de création. La quasi-absence de conséquences par l'expérimentation peut être à la fois une bonne et une mauvaise chose. Bien que la flexibilité des ordinateurs encourage l'exploration d'idées artistiques, elle peut également la freiner, en proposant trop d'options mal-adaptées. Un grand défi pour le développement des logiciels graphiques aujourd'hui est de tirer parti de la flexibilité sans précédent des ordinateurs, tout en offrant à l'utilisateur le niveau de contrôle adapté à ses besoins. La difficulté quand on développe un tel système est fortement influencée par l'attente que l'utilisateur place dans le travail effectué par l'ordinateur. L'ordinateur étant considéré comme un assistant dans le processus de création, on attend de lui qu'il soit 'assez intelligent' pour mériter ce rang. Habituellement, nous n'acceptons pas bien quand le résultat d'une telle assistance n'est pas satisfaisante. Cependant, le niveau d'attente et, par conséquence, de satisfaction, varie en fonction de l'utilisateur. Les utilisateurs novices ont tendance à être moins exigeants et sont satisfaits quand ils peuvent créer des résultats intéressants avec peu d'intervention humaine. Les utilisateurs professionnels, d'un autre côté, ont des besoins différents. Ils recherchent des logiciels assez performants pour automatiser leurs taches, mais qui leur laissent assez de contrôle sur le résultat obtenu. Pour cette catégorie d'utilisateurs, plus l'impact du logiciel sur le résultat est important, plus ils veulent avoir le contrôle sur la façon dont est obtenu ce résultat. Dans cette thèse, nous démontrons que l'ordinateur peut être un assistant précieux dans le processus de création visuel du moment que des systèmes d'interaction adaptés existent. L'adaptation est donc un aspect important car, à différents niveaux, les utilisateurs veulent pouvoir contrôler le résultat afin d'exprimer leur style et leur créativité. La thèse présente deux scénarios différents qui démontrent que la contrôlabilité joue un rôle majeur dans l'expressivité : une technique temps-réel pour grouper des scènes 3d dynamiques pour obtenir automatiquement un résultat sur lequel on peut facilement appliquer un style de rendu arbitraire; et plusieurs dérivées d'une primitive de dessin vectoriel appelée Diffusion Curves qui contraignent et contrôlent la création de dégradés de couleurs complexes. La thèse propose, d'un coté, des représentations mathématiques et algorithmiques adaptées avec différents niveaux de contrôle sur les algorithmes de rendu expressif qui manipulent des scènes bi et tridimensionnelles; et, d'un autre coté, de traduire ces outils en interface intuitive pour l'utilisateur.

Les techniques de rendu en Synthèse d'Images produisent des images d'une scène virtuelle en prenant comme point de départ la définition de cette scène : les objets qui la composent, leur position, leurs matériaux, mais aussi la position de l'observateur. Parmi les techniques de rendu, on distingue les techniques de rendu Photo-Réalistes, qui cherchent à produire une image aussi proche que possible de la réalité, en simulant les échanges lumineux à l'intérieur de la scène. On obtient ainsi une image de la scène avec les effets d'éclairage, à la fois directs et indirects, les reflets, les ombres... La recherche dans le domaine de la simulation de l'éclairage a énormément progressé au cours des dernières années, de telle sorte que la production d'images photoréalistes est désormais un objectif accessible pour le grand public. Plusieurs applications industrielles tirent parti de cette génération d'images photoréalistes : visite virtuelle de bâtiments, jeux vidéo, prototypage virtuel, effets spéciaux, design architectural... Ces applications industrielles ont un effet d'entraînement sur la recherche : les utilisateurs (et les industriels) sont demandeurs d'effets toujours plus réalistes, et les chercheurs sont mis à contribution. Le décalage entre la date de publication d'un nouvel algorithme et son emploi dans un produit industriel s'est considérablement réduit, passant de plus de 10 ans dans les années 1990 à quelques années seulement en 2006. Non seulement ce dynamisme augmente les possibilités d'application industrielle pour nos recherches, mais encore il ouvre de nouvelles directions de recherche, pour combler les besoins accrus en interactivité et en réalisme des utilisateurs. Dans ce mémoire, nous allons nous intéresser à ces problèmes de simulation photo-réaliste de l'éclairage. En particulier, nousallons présenter : la simulation de l'éclairage par des méthodes d'éléments finis multi-échelles (radiosité par ondelettes), la détermination des caractéristiques de la fonction d'éclairage (dérivées, fréquence), et la simulation en temps-réel ou interactif de plusieurs effets lumineux (ombres, reflets spéculaires, éclairage indirect). Ces trois domaines recouvrent l'ensemble de nos travaux pendant cette période.