M2 - Images

TP 2 - Rendu indirect


Travail à rendre : pour la semaine du 14/12/2009

   Cette deuxième partie à rendre concerne la construction de la hiérarchie accélératrice, son utilisation pour accélérer les calculs d'intersections (Partie 1 du tp) et le calcul de l'éclairage indirect (Partie 2 du tp).

    Vous apporterez un soin particulier à expliquer vos calculs d'éclairage indirect en Monte Carlo, quelle pdf vous utilisez dans chaque cas, quelle méthode de tirage aléatoire et quels sont les calculs associés.
 
   
    Vous rendrez votre rapport en pdf et une archive .tar.gz de vos sources (ainsi qu'un makefile).
    Le rapport et l'archive porterons le nom des personnes associées au tp. Vous transmettrez le rapport et l'archive en utilisant le mail de l'université en précisant vos noms et numéros d'étudiants.



    L'objectif de ce TP est de programmer la méthode décrite dans l'article :

    "Micro-Rendering for Scalable, Parallel Final Gathering"
    T. Ritschel, T. Engelhardt, T. Grosch, H.-P. Seidel, J. Kautz, C. Dachsbacher   
    [pdf]


    La méthode se décompose en 2 étapes  :

    Les parties suivantes du tp détaillent la réalisation de ces 2 étapes. Vous pouvez réaliser ces 2 étapes dans l'ordre que vous préferrez, d'abord la partie calculs, puis la partie accélération avec la hiérarchie d'englobants, ou le contraire, ca n'a pas d'importance.


Partie 1 : construction de la hiérarchie d'englobants.

    Pour réduire le nombre d'intersections calculées pour chaque rayon nécessaire au rendu de l'image, l'article propose d'utiliser une hiérarchie de sphères englobantes. La méthode de construction proposée est similaire à la méthode classique (cf. CM4, page 16).

    Il y a toutefois une différence importante : la hiérarchie de sphères est utilisée pour faire deux choses différentes :

angle solide d'un noeud et d'un pixel                             parcours recursif



   
    Dans l'exemple ci-dessus, le noeud A occuppe un angle solide plus grand que celui du pixel, par contre les noeuds B, D et E ont des angles solides juste inférieurs.

    Dans le parcours classique d'une hiérarchie d'englobants, le parcours continue récursivement jusqu'aux feuilles des noeuds B, D et E et ne calcule les intersections qu'avec les objets (ou triangles) associés à ces feuilles, ce qui permet de gagner énormement de temps (lorsque la hiérarchie est "bien" construite). Cet algorithme fait implicitement l'hypothese que les objets sont suffisament gros pour être visibles par l'observateur, ce qui parait raisonnable.

    L'article propose d'arrêter tout de suite le parcours et de ne calculer l'intersection du rayon qu'avec les sphères englobantes des noeuds B, D et E, sans continuer dans les 3 sous-arbres correspondants. Cette modification de l'algorithme permet de réduire encore plus efficacement le nombre de calculs d'intersections, mais les intersections sont "approximatives", puisqu'elles sont calculées sur les sphères englobantes des objets, et pas sur les objets eux mêmes. L'algorithme suppose aussi que les objets sont plus petits qu'un pixel, ce qui est vrai dans le cas des objets associés aux noeuds D et E ( et F, G) et lorsque l'on calcule une image de très faible résolution (8x8, par exemple).

    Algorithme de construction.

    L'algorithme de construction est lui même décomposé en 2 parties. La première calcule une représentation approchée des objets de la scène qui à l'avantage  de simplifier la construction de la hiérarchie. Cette première partie remplace chaque objet par un ensemble de disques définis par un point, un rayon, une matière et une normale, cf. l'exemple ci-dessous (les disques sont plus espacés que dans la réalité, afin de donner une idée de la représentation, et leur centre est placé sur les sommets des triangles au lieu d'être au centre des triangles).


    geometrie remplacee par des disques


    Cette première étape simplifie grandement la construction de l'englobant d'un ensemble d'objets. Il est plus simple de déterminer la sphère englobante d'un ensemble de disques (ou de points), que de trouver une sphère qui englobe un objet quelconque. Un autre avantage est de pouvoir utiliser n'importe quel type d'objet, à partir du moment ou l'on est capable de le remplacer par un ensemble de disques orientés.

    étape 1 : construire l'ensemble de disques de chaque objet.

    Pour un triangle, le plus simple est de subdiviser récursivement le triangle en 4, tant que l'aire du triangle est supérieure à un seuil fixé. Lorsque l'aire est inférieure au seuil, il suffit de construire le disque en utilisant le centre du triangle et en calculant le rayon du disque afin qu'il ait la même aire que le triangle. Pour couper un triangle en 4 et préserver son aspect, le plus simple est de couper chaque arete au milieu.

    Pour une sphère, on peut utiliser le même principe et découper récursivement la surface de la sphère jusqu'à obtenir des patchs carrés suffisament petits.

    Q1. écrivez la fonction de préparation pour les objets de votre choix.

    étape 2 : construire la hiérarchie de sphères englobantes.

    Les objets de la scène sont maintenant représentés par un ensembles de n disques, noté disques[0 .. n). L'algorithme récursif, pour une séquence [p .. q) quelconque, est très simple :

    trier disques[p .. q) selon l'axe le plus long de leur boite englobante,
    calculer la sphère englobante des disques[p .. q) ainsi que leur matiere moyenne (couleur diffuse) et leur normale moyenne,
    couper l'ensemble au milieu : m= ( p + q ) / 2,
    stocker le noeud dans l'arbre : centre de la sphere, rayon, normale, couleur + 2 pointeurs sur les fils gauche et droit.
    recommencer pour le fils gauche, disques[p .. m) et et le fils droit, disques[m .. q).

  
    Dans un premier temps, calculez le centre de la sphere englobante comme la moyenne des centres des disques, et son rayon comme la distance du disque le plus éloigné du centre de la sphere + rayon du disque associe. Cette approximation est correcte mais ne produit pas toujours la plus petite sphere englobante.

    Q2. Quel critère d'arret utiliser pour la construction de la hiérarchie ?

    Q3. Sachant que cette hiérarchie va servir à "lancer" des rayons, peut-on améliorer sa qualité ? comment ? est ce que l'heuristique SAH est utilisable dans ce cas ?

    Q4. Pour tester votre hiérarchie, écrivez la fonction d'intersection avec un rayon. que constatez-vous ?

    Quel est le gain par rapport à la méthode de base (faire tous les calculs d'intersection) ? quel gain entre cette hiérarchie et la version de meilleure qualité ?
    Quelle est l'influence de la résolution de l'image ?
    Quelle est l'influence du seuil de subdivision des objets ? existe-t-il une relation entre la taille des objets, le seuil de subdivision et la résolution de l'image ?
    Comment subdiviser les objets afin de ne pas introduire de defauts visibles dans l'image ?

    Vous aurez également besoin de calculer l'angle solide d'une sphère de rayon r, se trouvant à une distance d de l'origine du rayon : Omega= pi . r2 / d2


    Q5. question bonus : utilisez une sphere englobante de meilleure qualité. Les 2 méthodes suivantes sont équivalentes :
    Quelles sont les différences dans la hiérarchie construite ? quels gains obtenez vous par rapport à la première approximation ?

Partie 2 : rendu indirect.

    L'objectif du rendu indirect est de prendre en compte, pour chaque point visible, p, l'ensemble des points qui réfléchissent de l'énergie vers p, au lieu de se contenter de l'ensemble des points des sources de lumière. Les exemples ci-dessous illustrent la différence de rendu (direct à gauche, indirect à droite).


eclairage direct sel                           eclairage indirect

    Une autre différence notable est que les ombres des objets ne seront plus noires.

    L'algorithme de rendu est classique : cf. CM7&8 :

       pour chaque pixel (x, y) de l'image
          générer le rayon (o, d)
          trouver le point p visible le long du rayon
          calculer l'éclairage direct au point p (et réfléchi vers l'origine du rayon), en utilisant éclairage direct(p, o)
          calculer l'éclairage indirect au point p (et réfléchi vers l'origine du rayon), en utilisant éclairage indirect(p, o)
          calculer l'énergie totale réfléchie vers l'origine du rayon (éclairage direct + éclairage indirect)
          stocker la couleur correspondante dans le pixel (x, y) de l'image
   
       éclairage direct ( point p, point o )
          pour chaque source de lumière de la scène
             pour chaque point r à la surface de la source
                choisir le point r
                générer le rayon (p, r)
                calculer l'énergie incidente au point p et déterminer la visibilité de p et r
                calculer et accumuler l'énergie émise par le point r vers le point p, puis réfléchie par le point p vers le point o

       éclairage indirect ( point p, point o )
          pour chaque direction d de l'hemisphere centrée sur le point p et orientée le long de la normale du point p
             choisir la direction d
             génerer le rayon (p, d)
             trouver le point q visible le long du rayon
             calculer l'énergie incidente au point q et réfléchie vers p, en utilisant éclairage direct(q, p)
             calculer et accumuler l'énergie émise par le point q vers le point p, puis réfléchie par le point p vers le point o

    Lorsque la hiérachie de sphères englobantes sera construite, il faudra l'utiliser pour accélérer les calculs d'intersections de l'éclairage indirect.

    Q6. Quels gains apporte la hiérarchie de sphères ?

    Q7. Quels gains apporte l'intersection approximative lors du parcours de la hiérarchie ? comment déterminer l'angle solide associé à chaque rayon dans la fonction éclairage indirect( ) ?

        intuition : quel est l'angle solide dans le cas ou la pdf est constante (rappel : l'angle solide d'une hemisphère est 2pi stéradians),
        ou encore : si on utilisait un découpage régulier de l'hemisphère, quel serait l'angle solide de chaque rayon ?


    Q8. Modifiez éclairage direct pour n'utiliser qu'un seul rayon (cf. CM8). que constatez-vous ?

    Q9. Modifiez la fonction de rendu pour générer plusieurs rayons par pixel, au lieu d'un seul. que constatez vous ?


    remarque : il est très fortement conseillé de mettre au point votre programme en utilisant les variantes les plus simples de chaque étape. par exemple, commencez par utiliser des densités constantes pour choisir les points et les directions. une fois cette "première" version fonctionnelle, modifiez-la pour tester d'autres solutions.


Annexes : maillage triangulé.

télécharger rt + scènes de test + exemple d'utilisation

documentation