MIM Image / ENS : propositions de projets

Voici quelques suggestions de projets classées par thèmes. Ils pourront être réalisés dans le squelette fournit dans les TD 6 et 7 (ce n'est pas une obligation).

1. Modélisation

La modélisation par arbre de construction est un outil particulièrement puissant. Le squelette fournit en TD est cependant très limité. Toutes les opérations booléennes ne sont pas disponibles (la différence ensembliste, par exemple). Un sujet de projet pourrait concerner la réalisation d'un arbre csg plus complet disposant de :

un noeud permettant de spécifier une transformation quelconque (translation, rotation, changement d'échelle, champ de déformation, etc.). Les algorithmes d'intersection de l'arbre csg avec un rayon devront être modifiés en conséquence.
toutes les opérations ensemblistes (notamment la différence). Au passage, les versions fournies calculent systématiquement les intersections de toutes les opérandes. Un arbre de construction définit implicitement une hiérarchie dans les primitives et il est possible d'utiliser cette structure pour éviter de calculer toutes les intersections. Dans le cas de l'union, par exemple, seul le premier intervalle est utile, il est donc totalement inutile de tous les calculer. Les temps de calcul d'une image devraient directement bénéficier de ces améliorations algorithmiques.
un noeud permettant d'associer des matières aux résultats des opérations booléennes, au lieu d'utiliser les matières des primitives. De même, un arbre de construction étant une représentation volumique, il est possible d'associer des matières différentes à la surface et à l'intérieur des objets.
primitives plus évoluées que le demi-espace et la sphère : des surfaces implicites (blobs, meta-balls, etc.), des surfaces de subdivision (cf. TD sur les carreaux de Bezier), des modèles polygonaux, des fractales 2D (ou 3D, cf. Quat), etc.
primitives modélisant les propriétés du milieu ambiant : du brouillard, de l'eau, de la pluie, l'atmosphère (le ciel), des nuages, de la poussière, etc.
primitives modélisant l'aspect des objets. Cette solution revient à construire deux arbres csg, un pour la géométrie, l'autre pour l'aspect des objets (textures volumiques, procédurales, etc). Des explications plus complètes se trouvent dans la section 3, "Aspect des objets".

2. Animation / Déformation d'objets

Modélisation de mouvements avec un modèle physiquement plausible :

un billard,
animation d'un squelette (cinematique directe ? inverse ?)
course de véhicules ?
déformations d'objets simulées par un système de particules, de masses-ressorts.
définir des trajectoires, les affecter à des objets et visualiser l'animation avec gestion des collisions éventuelles

3. Aspect des objets

L'aspect des objets est pour l'instant très (trop) simple, il est relativement simple de définir des aspects plus "réalistes". La première amélioration pourrait être l'utilisation de textures afin d'ajouter des détails à la surface des objets. L'utilisation de textures 2D implique de pouvoir paramétrer la surface des objets. Malheureusement, les objets étant représentés par un arbre de construction, il est quasiment impossible de paramétrer la surface des opérations booléennes (alors qu'il est en général possible de paramétrer la surface des primitives). Une solution à ce problème consiste à utiliser des textures volumiques définies en 3D. Les objets sont donc "plongés" dans une texture. Les textures volumiques peuvent être soit explicites (leur valeur est connue en tout point de la scène), soit calculée (textures procédurales : mélange de fonctions de turbulences, bruit de Perlin, etc.). Les textures peuvent agir sur différents attibuts : la couleur, la matière, la forme (displacement mapping), le relief (bump mapping), etc. Il est également possible d'utiliser une texture pour paramètrer le milieu ambiant et créer, par exemple, un brouillard de densité variable. Il serait également souhaitable de pouvoir utiliser des textures différentes dans la scène. Une solution élégante consiste à définir un arbre csg afin de décrire l'organisation des textures dans la scène. De même, l'utilisation d'un arbre csg augmenté par des transformations devrait permettre de définir des mélanges ou des superpositions de plusieurs textures ...

En résumé, un projet pourrait ajouter les fonctionnalités suivantes au squelette :

textures volumiques explicites,
textures volumiques procédurales,
affectation de la texture à un attribut des objets (couleur, matière, forme, relief ...),
arbre de construction permettant d'utiliser plusieurs textures volumiques dans la scène (1 seule texture est définie en chaque point de la scène),
arbre de construction permettant de mélanger plusieurs textures volumique (plusieurs textures sont définies en chaque point de la scène),
etc.

Vous pouvez également vous inspirer des langages de programmation de shader (renderman, par exemple, ou maya) afin de construire un système entièrement programmable.

4. Sources de lumières étendues

Dans la version acctuelle du squelette, seules les sources ponctuelles et sphériques uniformes existent. Il est possible de définir une source de forme et de volume quelconque (grace à un arbre csg, par exemple). De même, l'émission des sources de lumières n'est pas nécessairement constante. Il existe des mesures de sources de lumières réelles qui sont utilisables pour le rendu d'une image. Il est également très simple de définir des sources de formes plus "standards" : des néons (cylindre), des spots (point avec une émission non constante), etc.

En résumé, un projet pourrait ajouter les fonctionnalités suivantes au squelette :

sources étendues de forme simple (cylindre, polygone, etc.)
sources étendues de forme complexe (modélisation par un abre csg, par exemple)
sources étendues d'émission non constante :
soit mesurée, cela revient à utiliser des textures (2D ou 3D, cf. section 3, "Aspect des objets"),
soit procédurale cf. spots dans openGL

5. Algorithmes de rendu

Le réalisme des images de synthèse dépend de tous les facteurs évoqués jusqu'à présent : la forme des objets, leur aspect, leur matière, les sources de lumières, et bien sur, de la méthode calcul. Lorsque l'aspect de la scène est décrit de manière correcte, il est nécessaire de reproduire fidèlement les interactions de la lumière avec les matières et les formes de ces objets. La version actuelle du squelette se contente de calculer un éclairement direct avec des sources étendues simples, ce qui est un bon début. La prise en compte de certaines matières nécessite d'étendre la méthode de calcul : les miroirs et les objets transparents, par exemple, nécessitent l'utilisation d'une méthode de calcul récursive (cf. TD7). Cette méthode de calcul à l'avantage d'être particulièrement simple à programmer et fournit des résultats corrects. Cependant, c'est une méthode de calcul d'éclairement local, c'est à dire que les échanges d'énergie entre les objets ne sont pas calculés. Malheureusement, ce sont ces échanges qui sont responsables du "réalisme" de l'image calculée. Le premier avantage d'une méthode de calcul d'éclairement global (qui calcule les échanges d'énergie entre les objets) est de calculer correctement l'énergie présente dans les ombres. En effet, les méthodes de calcul local utilisent une approximation constante de cette énergie : le terme ambiant. L'éclairement global permet également de déterminer correctement l'aspect des matières partiellement réfléchissantes (comportement diffus directionnel) et d'autres effets comme les caustiques : la réflexion ou la réfraction d'une source de lumière sur/à travers un objet.

Plusieurs méthodes d'éclairement global existent :

le suivi de chemins : c'est une modification du lancer de rayon récursif. Il existe deux méthodes symétriques :
soit depuis la position de l'observateur vers les sources de lumières,
soit depuis les sources de lumières vers l'observateur.
intégration de monte-carlo : c'est la version mathématiquement correcte du suivi de chemin. Une intégration numérique correcte permet de créer une classe hybrique de suivi de chemins plus efficace : le suivi bidirectionnel. Cette méthode consiste à tracer un chemin depuis les sources, un autre depuis l'observateur et à les connecter afin de construire un chemin reliant la source de lumière à l'observateur. Ces méthodes reposent sur le calcul de la probabilité de chaque évènement du suivi de chemin : probabilité de choisir un point à la surface d'une source, probabilité de choisir une direction de propagation, probabilité de terminer le chemin, probabilité de choisir une nouvelle direction, etc. Le produit de ces probabilités permet de déterminer la probabilité d'avoir généré le chemin en cours de calcul et de pondérer l'énergie qu'il dépose sur l'observateur. Ces méthodes sont relativement simples mais nécessitent de mettre en place les calculs de probabilités des différents évènements.
"Photon Map" ou distribution de photons : c'est une approximation rapide du suivi de chemin bidirectionnel. Cet algorithme fonctionne en deux passes. La première passe émet des photons depuis les sources de lumières et stocke leurs impacts dans la scène. La deuxième utilise le nombre d'impacts stockés par unité de volume pour estimer les échange d'énergie entre les objets. Cette méthode est une approximation très rapide du suivi de chemin. De plus, il est possible de représenter assez facilement le nombre d'impacts par unité de volume à l'aide d'une texture volumique (cf. sections "sources de lumières étendues" et "aspect des objets").
radiosité : autre approche du calcul de l'éclairement global. Cette méthode est particulièrement adaptée aux scènes comportant des objets diffus. Les matières réfléchissantes sont beaucoup plus complexes à simuler, à l'inverse du suivi de chemin. Cette méthode peut utiliser openGL pour certaines étapes du calcul.
"Instant Radiosity" : approche hybrique entre photon map et radiosité. Cette méthode repose sur un rendu openGL pour mériter son nom (instant ...). Les sources de lumières sont découpées en un petit nombre de photons. Chaque photon est propagé dans la scène sur un petit chemin (quelques rebonds). A tour de rôle, chaque photon est considéré comme la seule source ponctuelle qui éclaire la scène. Chaque scène est visualisée, avec ombres portées, en utilisant openGL. La moyenne de ces images est une approximation de l'éclairement global.

    Les méthodes de calcul d'éclairement global peuvent fournir des images aussi spectaculaires que leur temps de calcul ...

    Toutes les méthodes d'éclairement (local ou global) reposent sur un élément fondamental : déterminer la visibilité, soit de deux points pour le lancer de rayons, soit de deux éléments de surfaces (facettes ou "patch") pour la radiosité. Le lancer de rayon permet de déterminer la visibilité de deux points et se prête bien à une intégration numérique (monte carlo, metropolis, itération stochastique, etc.). A la vue de sa simplicité, c'est souvent le seul moyen utilisé pour déterminer la visibilité lors des calculs d'éclairement (y compris pour la radiosité qui nécessite de calculer la visibilité de deux surfaces). En effet, le lancer de rayon est un simple tri des objets de la scène selon leur abscisse d'intersection avec le rayon : la complexité d'un tri (dans le pire des cas ...) est de l'ordre du log du nombre d'objets. C'est un résultat très interessant mais sa réalisation pratique n'est pas aussi simple. De nombreux auteurs se posent toujours la question ... Une des méthodes efficace pour réaliser ce tri consiste à utiliser des arbres binaires : les arbres de partition spatiale (ou BSP) qui présentent une complexité dans le cas moyen particulièrement interessante. La réalisation de ce type d'amélioration est quasiment obligatoire (et peut consistuer un sujet de projet) : le simple lancer de rayon du TD6 calcule plusieurs dizaines de millions d'intersections. Les méthodes d'éclairement global sont encore plus grosses consommatrices. D'autres approches restent possibles pour accélerer les calculs de visibilité, plusieurs utilisent openGL, mais il est par contre souvent nécessaire de modifier la structure des algorithmes de calcul afin d'en profiter pleinement.

    Il y a quelques années, un groupe de chercheurs a montré que 4 Pentium III 800Mhz peuvent afficher plusieurs millions de polygones plus vite que la plus grosse carte video du marché de l'époque.