M2 - Images

TP 4 : Lancer de rayons





    Ce TP propose de construire un lancer de rayons. Comme c'est un domaine assez vaste, le sujet propose de se concentrer sur les aspects algorithmiques liés à l'accélération des calculs d'intersection.

    Ce TP sera noté, la section suivante précise le travail à rendre.


Travail à rendre

    Le tp sera rendu en deux temps :
        la premiere partie au début de la séance du 20/11/2007
        la deuxième partie à la fin de l'ue

  1. La première partie à rendre concerne la réalisation du lancer de rayon minimal, c'est à dire les parties 1, 2, 3 et 4 du sujet.

    Le document décrivant votre travail sur cette première partie s'attachera à décrire précisement les repères (et les transformations associées) dans lesquels vous avez choisi de travailler. C'est à dire les réponses aux questions 2.Q1, 3.Q1, 4.Q1 et 4.Q2.
    Vous apporterez un soin particulier à expliquer votre méthode de génération des rayons (dans quel espace, homogène ou réel, transformations associées, etc.).

  2. La deuxième partie est liée aux hiérarchies de volumes englobants et au parcours cohérent, parties 5 et 6 du sujet.

Partie 1 : intersections primitive - rayon

    Une des premières choses à faire est de décrire un objet. Pour un lancer de rayons, un objet est principalement défini par sa position dans l'espace et sa fonction d'intersection (qui permettra de le visualiser).

    Pour avancer rapidement vers un "système" fonctionnel, commencons par un type d'objet simple comme une sphère, un cube, etc.

    Q1: représentez une sphère de centre (0, 0, 0, 1)T et de rayon R.
    Q2. écrivez une fonction d'intersection avec un rayon passé en paramètre capable de renvoyer l'existence de l'intersection ainsi que son abscisse, notée t.

    Un rayon se définit par une origine et une direction. Un point p( t ) le long du rayon se définit par : p( t ) = origine + t . direction
   
    exemple : int sphere_intersecte(const float *origine, const float *direction, float *t)


Partie 2 : placer des objets dans la scène

    Maintenant que nous avons des objets, il faut construire une scène à visualiser. Il suffit de positionner le repère local de chaque objet dans le repère de la scène. cf. les TP 2 & 3 pour les compositions de transformations.

    Q1: attachez un changement de repère à votre objet afin de la positionner dans la scène.
    Q2: représentez un ensemble de primitives : la "scène", écrivez la fonction d'intersection entre un rayon et la scène :

    exemple : int scene_intersection(const SCENE *scene, const float *origine, const float *direction, float *t)

    rappel : lorsque plusieurs objets de la scène intersectent le rayon, seule l'intersection la plus proche de l'origine du rayon est renvoyée.

Partie 3 : placer une caméra

    Le dernier élément d'un lancer de rayon est la caméra.

    Q1. représentez une camera, cf. TP 3.

Partie 4 : générer un rayon

    Nous pouvons commencer à calculer l'image. Il ne reste plus qu'à "générer" un rayon pour chaque pixel de l'image.

    Le plus simple est de le créer dans le repère projectif de la camera et de le transformer dans le repère de la scène.

    Q1: écrivez une fonction qui génère un rayon pour le pixel (x, y) dans le repère de la scène.
   
    exemple : void camera_genere_rayon(const CAMERA *camera, float x, float y, float *origine, float *direction)

    Q2. modifiez la fonction d'intersection entre un rayon et la scène (cf. Partie 2) afin de transformer le rayon pour l'exprimer dans le repère local de l'objet, ce qui vous permettra d'utiliser les fonctions d'intersection de la Partie 1.


Partie 5 : structure accélératrice

    La visualisation de la scène est une opération longue : a priori pour chacun des W*H pixels, il faut calculer N intersections, soit, au total, W*H*N calculs.

    Une solution classique consiste à structurer la scène afin d'éliminer les calculs d'intersections inutiles. L'objectif du TP est d'utiliser une hiérarchie de volumes englobants permettant également de gérer efficacement les scènes dynamiques (ou animéees)

    Toutes les informations relatives à la construction, au parcours et aux optimisations sont disponibles dans l'article cité en référence :
"Ray Tracing Deformable Scenes using Dynamic Bounding Volume Hierarchies".

    Rappels : Structures accélératrices et lancer de rayons


    Hiérarchie de volumes englobants

    Une hiérarchie  de volumes englobants est un arbre dont les noeuds représentent le volume occupé par un sous-ensemble des objets de la scène. Les noeuds internes ne stockent que le volume englobant. Les feuilles, par contre, contiennent en plus la liste des objets de la scène présents dans leur volume englobant. Dernière propriété, le volume englobant d'un noeud est également un englobant de ses fils. Il existe un grand nombre de hiérarchies correctes pour chaque scène, mais certaines permettront d'accélérer les calculs d'intersections en éliminant les volumes non traversés par le rayon.

    Nous nous plaçons dans un cas simple : la hiérarchie sera un arbre binaire et les volumes englobants seront des cubes alignés sur le repère de la scène.

    Construction de la hiérarchie

    L'objectif est de construire la "meilleure" hiérarchie, c'est à dire, celle qui permet de faire le minimum de calculs d'intersections pour trouver l'objet le plus proche de l'origine du rayon. L'idée principale consiste à trouver une hiérarchie qui minimise le nombre de noeuds traversés par le rayon en cours de "propagation", tout en obtenant le bon résultat.

    L'algorithme général construit la hiérarchie en partant de la racine, c'est à dire le volume occupé par l'ensemble des objets de la scène. Ensuite, il faut trouver une coupe dans ce volume qui permette de répartir les objets entre les fils gauche et droit. La construction est récursive et se termine lorsqu'il n'est plus possible de séparer les objets (il n'en reste plus que 1 ou 0).

    Le problème le plus délicat est de choisir où couper un volume englobant afin de répartir les objets entre les fils gauche et droit. La solution simple consiste à répartir "équitablement" les objets entre les deux fils et permet d'obtenir un arbre binaire équilibré. Malheureusement, cette "stratégie" est une des pires pour le calcul d'intersections. En effet, un arbre équilibré ne garanti pas la meilleure séparation des objets : c'est à dire éliminer les noeuds dont le volume n'est pas traversé par le rayon.

    Il faut donc utiliser un autre critère de séparation qui tient compte du rayon. Le plus répandu utilise la probabilité qu'un rayon traverse le fils gauche (ou le droit) sachant que le père est lui aussi traversé par le rayon. Cette probabilité est proportionelle au rapport de l'aire des surfaces des volumes englobants des deux noeuds. Le critère estime le temps d'intersection du rayon avec les objets associés au noeud sachant que l'un des fils sera également intersecté. Il suffit alors de trouver la répartition entre les fils gauche et droit qui minimise le temps d'intersection T :

T= Tgauche + Tdroit
avec Tfils= Tenglobant + A(fils) / A(pere) N(fils) Tobjet
    avec :
Tenglobant : temps d'intersection du rayon avec le volume englobant d'un noeud,
Tobjet : temps d'intersection du rayon avec un objet,
A(noeud) : aire de la surface du volume englobant du noeud (rappel : les volumes englobants sont des cubes dans notre cas),
N(noeud) : nombre d'objets "affectés" au noeud.

    On peut interpréter les différentes parties de cette expression de Tfils :

    A(fils) / A(pere) est proportionel à la probabilité d'intersecter les objets d'un fils connaissant le volume englobant du pere,
    N(noeud) Tobjet représente le temps d'intersection du rayon avec les objets associés au noeud.

    L'algorithme de construction ne teste pas tous les plans de coupe possibles, mais uniquement les plans principaux alignés sur le repère de la scène et passant par le centre du volume englobant de chaque objet. L'algorithme, présenté en détail dans l'article de référence, parcours l'ensemble d'objets dans les deux sens (du min vers le max et réciproquement, le long de chaque axe) et construit de manière incrémentale A(S1), N(S1), A(S2), N(S2) pour chaque plan de coupe candidat.

    Des détails supplémentaires ainsi que l'algorithme de construction se trouvent dans l'article de référence.
    Un algorithme encore plus efficace est décrit dans "On fast Construction of SAH based Bounding Volume Hierarchies".

    Algorithme de Construction simple

étape 1 : précalculer les boites englobantes de chaque primitive ainsi que leur centre.

étape 2 : construction récursive de l'arbre.

construction(S : ensemble de primitives)
// construire l'ensemble de plans de coupe candidats pour chaque axe
pour axe = X, Y, Z
P = S
trier P par P[i].centre[axe] croissant

// énumérer les plans de coupe
pour i = [ 0 .. N(P) [
répartir les primitives placées avant P[i].centre[axe] dans S1
répartir les primitives placées après P[i].centre[axe] dans S2
// la position d'une primitive est déterminée par la position du centre de sa boite englobante
// si P[j].centre[axe] < P[i].centre[axe] alors ajouter la primitive P[j] à S1
// si P[j].centre[axe] > P[i].centre[axe] alors ajouter la primitive P[j] à S2

calculer les boites englobantes de S1 et S2
calculer les aires : A(S1), A(S2) et A(S)
calculer T, le coût du plan candidat

// conserver le candidat de coût minimum
si T < Tmin
Tmin = T
imin = i
axemin = axe
fin si
fin pour
fin pour

construire les fils gauche et droit avec la répartition déterminée pour Tmin

// continuer récursivement la construction des fils gauche et droit
construire(S1)
construire(S2)
fin


    Q1. Quel est le critère d'arrêt de la construction récursive ?
    Q2. Quelle est la complexité de cet algorithme ?
    Q3. Proposez une version incrémentale de l'algorithme afin de répartir efficacement les primitives avant et après P[i].centre[axe], le plan candidat.
        Quelle est la complexité de cette variante de l'algorithme ?

    Parcours "simple"

    Une fois la hiérarchie construite, il ne reste plus qu'à la parcourir afin de calculer l'intersection du rayon avec les objets qu'elle organise.
    L'algorithme effectue un parcours en profondeur de l'arbre et ne traite que les noeuds pouvant intersecter le rayon :

    si le noeud est une feuille
       renvoyer l'intersection du rayon avec les objets associés à la feuille
    fin si
    si le rayon intersecte le volume englobant du fils gauche
       descendre à gauche
    fin si
    si le rayon intersecte le volume englobant du fils droit
       descendre à droite
    fin si
   
    Si les volumes englobants des deux fils se chevauchent, ils seront testés tous les deux, dans un ordre indéterminé, ce qui est particulièrement inefficace.


    rappels : intersection rayon - boite englobante alignée sur les axes
    explications plus complètes : "An Efficient and Robust Ray-Box Intersection Algorithm" + code.tar.gz
   


    Parcours "efficace"

    Nous ne sommes interressés que par l'intersection la plus proche de l'origine du rayon. Dans le cas ou les deux fils sont visités par le parcours, il est préferable de tester en premier les intersections avec le fils le plus proche de l'origine du rayon. L'autre fils ne sera testé que si le rayon traverse le premier fils sans intersection.

    Il existe plusieurs solutions, la plus simple est de commencer par le fils dont le volume englobant se projette le plus près de l'origine du rayon. La solution proposée dans l'article de référence précalcule ce résultat et l'exploite directement sans refaire de calculs, ce qui permet de gagner énormément de temps.

    Q1. Ecrivez les fonctions nécessaires pour construire une hiérarchie de volumes englobants, ainsi que les parcours simple et efficace.
    Q2. Quels gains obtient-on par rapport à la version naïve qui intersecte la totalité des objets de la scène ?

Partie 6 : parcours cohérent

    Les parcours précédents travaillent un rayon à la fois, ce qui est finalement très inefficace puisque des rayons voisins dans l'image en cours de calcul traversent une grande partie de la hiérarchie de la même manière. L'idée fondamentale du lancer de rayons cohérents consiste à exploiter cette cohérence en parcourant la hiérarchie avec un "paquet" de rayons. Le paquet correspond, par exemple, aux rayons générés pour un bloc 8x8 de pixels dans l'image. La principale différence de l'algorithme de parcours consiste à traiter efficacement le cas ou les rayons du paquet doivent descendre dans des fils différents. La solution est simple : tout le paquet descend dans les deux fils.

    Des solutions plus subtiles sont bien sur présentées en détail dans l'article de référence.

    Q1. Ecrivez une fonction de parcours cohérent.
    Q2. Faites varier la taille des paquets et vérifiez les gains obtenus par rapport aux versions précédentes.
    Q3. Modifiez la fonction de parcours cohérent pour intégrer les améliorations présentées dans l'article de référence et comparez les performances des différentes variantes.

Partie Subsidiaire : structure accélératrice dynamique


    cf. article de référence.


Partie Subsidiaire : parallélisation

    Comment modifier votre lancer de rayons afin d'utiliser tous les coeurs d'un processeur ?

    Comment paralléliser la construction de la hiérarchie de volumes englobants ?


Annexes : Références


"Ray Tracing Deformable Scenes using Dynamic Bounding Volume Hierarchies"
Ingo Wald, Solomon Boulos, and Peter Shirley
ACM Transactions on Graphics 26(1), 2007
pdf movie(mov)


"On fast Construction of SAH based Bounding Volume Hierarchies"
Ingo Wald
Eurographics/IEEE Symposium on Interactive Ray Tracing, 2007
pdf