Le rendu par lancer de rayons
(ray tracing)

ALGORITHME

AVANTAGES

INCONVÉNIENTS

EXEMPLES

MATHÉMATIQUES

OPTIMISATIONS

CONCLUSION

Version
texte long

RETOUR

Algorithme de rendu pour l'obtention d'images de qualité photo-réaliste

• Diffusions
• Réflexions spéculaires
• Transmissions
• Ombres portées
• Elimination des parties cachées
• ...

Principe

Pour déterminer comment ils ont été créés, on suit en sens inverse le parcours des rayons lumineux qui s'impriment sur la rétine de l'observateur.
En partant depuis l'œil de l'observateur, on traverse l'écran virtuel sur lequel est matérialisée l'image créée, puis on "entre" dans la scène de manière à déterminer de quel(s) objet(s) un rayon lumineux provient, et ainsi, à déterminer ses caractéristiques chromatiques.

Parcours des rayons lumineux de l'observateur vers la scène
(en réalité de la scène vers l'observateur)

On traite le rayon primaire partant de l’observateur et passant par chaque pixel de l'écran virtuel de manière à déterminer la couleur attribuée à ce pixel.

Lors du parcours d'un rayon lumineux dans une scène, deux cas sont possibles :

(1) Aucun objet n'intercepte le rayon.

-> La couleur est celle du fond (noir ou autre).

(2) Un ou plusieurs objets interceptent le rayon.

• On trouve l'objet le plus proche de la source du rayon (l'observateur pour les rayons primaires, une intersection rayon-objet pour les rayons secondaires).

• En fonction des caractéristiques de cet objet vis à vis de la lumière, la "teinte" du rayon est calculée par somme des composantes de lumière (a) diffusée, (b) réfléchie et (c) transmise par l'objet au point d'intersection (composantes qui ont "créé" ce rayon "incident").

Recomposition d'un rayon incident
au niveau de l'interface entre deux matériaux
Parcours réalisé par le lancer de rayons inverse du parcours réel

Phénomène récursif

Chaque intersection entre un rayon et un objet entraine le calcul de l'ensemble des rayons ayant pu générer ce rayon (diffusions, réflexion spéculaire, transmission).
 -> Phénomène intrinséquement récursif
 -> Programmation d'un algorithme récursif

On classifie les rayons en fonction de leur "rôle" au sein de la récursivité.

Gestion de rayons primaires, de rayons secondaires et de rayons d'ombre

Calcul des différentes composantes

(a) Pour calculer la valeur diffusée on doit :
    - Déterminer le point d'intersection P entre l'objet et le rayon incident
    - Lancer un rayon de P vers chacune des sources lumineuses présentes dans la scène pour déterminer si ce rayon est intercepté ou non par un objet (à l'ombre ou non)
    - Pour chaque rayon non intercepté, appliquer une formule adaptée au calcul de la lumière diffuse (loi de Lambert ou autre) avec utilisation des coefficients de diffusion de la surface de l'objet
    - Sommer le résultat de chacun de ces calculs pour obtenir la quantité globale de lumière diffusée au point P

(b) Pour calculer la valeur obtenue par réflexion on lance récursivement l'algorithme de lancer de rayons sur le rayon secondaire défini avec pour origine le point P et pour direction la direction de réflexion du rayon initial puis en pondérant la valeur obtenue par les coefficients de réflexion de la surface de l'objet.

Le rayon incident, le rayon réfléchi et la normale à l'interface au point d'incidence sont dans le même plan.
L'angle de réflexion qr est tel que qr = -qi où qi est "l'angle d'incidence" par rapport à la normale à l'interface au niveau du point de réflexion.

Les rayons secondaires de réflexion sont exclusivement tracés dans le milieu inter-objets.

(c) Pour calculer la valeur obtenue par transmission on lance récursivement l'algorithme de lancer de rayons sur le rayon secondaire défini avec pour origine le point P et pour direction la direction de transmission puis en pondérant cette valeur par les coefficients de transmission de la surface de l'objet.

Lors d'une réfraction, la direction du rayon incident est modifiée selon la loi de Snell :

ni sin(qi) = nt sin(qt)

où ni est l’indice de réfraction du matériau dans lequel se propage le rayon incident, nt est l’indice de réfraction du matériau dans lequel se propage le rayon transmis, qi est "l'angle d'incidence" par rapport à la normale à l'interface orientée dans le milieu incident et calculée au niveau du point de transmission et qt est "l'angle de transmission" par rapport à -.
Le rayon incident, le rayon de transmission et la normale à l'interface au point d'incidence sont dans le même plan.

Attention, les rayons secondaires de transmission sont tracés dans le milieu inter-objets mais aussi dans les objets "transparents".
-> Cette caractéristique contraint le programmeur à gérer les entrées/sorties des rayons des objets.

Remarque

En fonction de ni, nt et qi, la valeur de qt peut ne pas être définie (cas où le rayon incident fait un angle avec la normale suffisant pour ne pas être transmis et être totalement réfléchi (effet miroir)).

Indices de réfractions de matériaux courants
Valeurs variables en fonction de la température
et de la longueur d'onde (jaune dans le tableau)

Algorithme simplifié

/* Calcul et retour d'une image au moyen    */
/* de l'algorithme de lancer de rayons      */
/* s : La scene visualisée                  */
/*     (composée d'objets et de lumières)   */
/* o : L'observateur visualisant la scène   */
/*     (défini par sa position              */
/*     et les caractéristique de son écran  */
/*     virtuel de visualisation)            */

Image lancerDeRayons(Scene s,Observateur o)
  Image image <- créer image de résolution égale
                 à celle de l'écran de o
  pour chaque pixel p d'indice (l,c) de l'écran de o
    Rayon r <- rayon passant par l'observateur et par p
    image[l][c] <- lancerRayon(s,r)
  finpour
finfonction

/* Calcul et retour de la couleur           */
/* d'un rayon au moyen de l'algorithme      */
/* de lancer de rayons                      */
/* s : La scène traversée                   */
/*     (composée d'objets et de lumières)   */
/* r : Le rayon                             */
/*     (caractérisé par un point d'émission */
/*     et une direction)                    */

Couleur lancerRayon(Scene s,Rayon r))
  Objet o <- objet de s dont l'intersection avec r
             est la plus proche de la source de r
  si o n'existe pas
    retourner noir
    sinon
    Point p <- point d'intersection entre r et o
    Rayon rr <- rayon réfléchi de r en p sur o
    Coefficients kr <- coefficients de réflexion de o
    Couleur cr <- lancerRayon(s,rr) * kr
    Rayon rt <- rayon transmis de r en p vis à vis de o
    Coefficients kt <- coefficients de transmission de o
    Couleur ct <- lancerRayon(s,rt) * kt
    Couleur cd <- noir
    pour chaque lumiere sl de s
      Rayon rd <- rayon de p vers sl
      si rd non intercepté par un objet de s
        cd <- cd+diffusion(sl,o,rd)
      finsi
    finpour
    retourner cr+cd+ct
  finsi
finfonction

Inconvénients du lancer de rayons

Temps d'exécution

Les calculs implantés sont obligatoirement réalisés en réel et font appel à des opérations mathématiques non triviales réalisées en grand nombre.
Exemple : Sans tenir compte des rayons secondaires et des rayons d'ombre, un million x mille = un milliard de tests d'intersection pour une image de un million de pixels de résolution et une scène composée de mille objets.
   -> Les temps d'exécution sont longs.

Récursivité

A chaque interception d'un objet par un rayon, outre les rayons d'ombre, on lance potentiellement deux rayons : un rayon pour la gestion de la transparence et un rayon pour la gestion de la réflexion spéculaire.
   -> On peut assister à une explosion exponentielle du nombre total de rayons tracés à l'intérieur de la scène. Si n est le niveau de profondeur de la récursivité, il y a au maximum de l'ordre de 2ⁿ rayons tracés pour chaque pixel.

Pour obtenir un certain réalisme le niveau de récursivité doit être poussé assez loin (au moins 8, habituellement 10 à 12 voire 14) et donc les temps de calcul peuvent être très longs (plusieurs heures par image pour des scènes complexes).

Problèmes de calcul d'illumination

L’illumination est "moyennement" locale.
Toute illumination provient d’une diffusion sous l'éclairage d'une source de lumière répertoriée comme telle. Cet éclairage est soit direct, soit le résultat d'un nombre de réflexions spéculaires ou de transmissions successives égal au maximum au niveau de profondeur de récursivité utilisé.
Dans la réalité toutes les surfaces et tous les milieux sont récepteurs et émetteurs de lumière et les réflexions et transmissions sont infinies.
   -> En lancer de rayon, il peut apparaitre des zones non éclairées qui auraient dû l'être un peu.
   -> En lancer de rayon, il peut apparaitre des zones illuminées très cruement qui n'auraient peut-être pas du être illuminées aussi fortement.

Ce problème peut être partiellement résolu en attribuant une composante de lumière ambiante à chacun des éléments de la scène (composante, souvent constante car on ne sait pas la calculer précisément avec l'algoritme de ray-tracing, ajoutée aux autres).

Tel quel, le lancer de rayons ne peut pas restituer un effet de "caustique" tel que l'obtention d’une concentration ou d’une atténuation énergétique en certaines zones lors de la propagation de la lumière à l'intérieur d'une loupe. En effet, cet algorithme de rendu ne modélise que très imparfaitement les transferts d'énergie (la notion d'énergie par unité de surface n'est pas modélisée correctement).

Réfraction de la lumière au fond d'une piscine
(http://photos.massal.net/swimming-pool/swimming-pool-deep-blue-water-caustics-california-p.html)

On ne peut pas restituer la diffusion de la lumière dans les matériaux (en particulier l’air).
   -> Certains éclairages peuvent être non réalistes.
   -> Certaines ombres peuvent être non réalistes.

Avantages du lancer de rayons

Réalisme

Des effets tels que les réflexions et les transparences sont restitués intrinsèquement. Aucun autre algorithme n'est capable de modéliser ces effets de manière aussi satisfaisante.

Comparaison entre affichages OpenGL et lancer de rayons

OpenGL  Lancer de rayons Apport des ombres portées à gauche et des réflexions spéculaires à droite OpenGL Lancer de rayon Meilleure gestion géométrique des transparences en lancer de rayons qu'en Z-Buffer : décalage des images vues à travers un parallélépipède rectangle, inversion des images vue à travers une sphère Obtention de résultats conformes à la réalité

Programme GLUt

Exécutable GLUt

Enter pour amorcer le calcul de l'image en lancer de rayons dans sa fenêtre +/- pour augmenter/diminuer le rapport n = ni/nt Espace pour entrer le rapport n = ni/nt au clavier dans la fenêtre console s/S pour changer de scène

Les parties cachées sont éliminées de manière intrinsèque. Au niveau 1 de la récursivité, on est en présence d’un algorithme très voisin du Z-Buffer dans ses résultats : le Ray Casting.
Les ombres portées sont intrinsèques au modèle.

Objets de base évolués

Pas de décomposition de la scène en facettes triangulaires ou surfaces élémentaires planes (contrairement au Z-Buffer).
   -> Les objets courbes apparaissent réellement courbes.

Les opérations de base utilisées sont les tests d'intersection objet<->rayon. Ces tests sont implantés au moyen des équations cartésiennes et paramétriques par résolution de systèmes d’équations.

Classiquement les objets modélisant une scène affichée en lancer de rayons sont des objets représentables par équation(s) mathématique(s) : des sphères, des parallélépipèdes rectangles, des cônes, des surfaces contrôlées, … (affectés de rotations, translations, zooms).

Bien entendu, on peut aussi aussi utiliser des ensembles de facettes.

Algorithme facilement parallèlisable

Les rayons primaires sont indépendants les uns des autres.
   -> Parallèlisation par distribution des pixels à calculer.

l \ c	c%2 = 0	c%2 = 1
l%2 = 0	1	2
l%2 = 1	3	4

Distribution des rayons primaires sur 4 processeurs
Numéro de processeur affecté aux pixels
en fonction de leurs numéros de ligne et de colonne

Exemples

Des ombres portées

Des réflexions

 Des transmissions à travers des billes d'indices de réfraction 1.333, 1.5, 2.5 et 4
(de gauche à droite et de bas en haut).

Noter l'inversion des objets.

Quelques problèmes mathématiques classiques

Calcul du rayon réfléchi

Soient :

• le vecteur normé inverse à la direction d’incidence de la source,
• le vecteur normé réfléchi,
• la normale à l’interface orientée dans le matériau où se propage le rayon incident.

Sachant que abs(qi) = abs(qr), on établit :

Calcul du rayon transmis

Soient :

•  le vecteur normé inverse à la direction d’incidence de la source,
•  le vecteur normé transmis,
•  la normale à l’interface orientée dans le matériau où se propage le rayon incident,
•  le vecteur normé perpendiculaire à situé dans le plan déterminé par et ,
• ni et nt les indices de réfraction des milieux incident et de transmission.

Si on pose n = , on obtient :

Ce qui nous conduit pour finir à

qui ne contient que des quantités connues.

Calculs d'intersection

Intersection entre une sphère et un rayon

On désire connaître la position de(s) l'intersection(s) entre un rayon lumineux quelconque et une sphère de rayon r centrée sur l'origine.

Le système d'équations à résoudre est formé de l'équation paramétrique de la droite définie par le rayon lumineux et l'équation cartésienne de la sphère :

Par substitution on obtient :

(a₁t + b₁)²+(a₂t + b₂)²+(a₃t + b₃)² = r²

(a₁²+a₂²+a₃²)t² + 2(a₁b₁+a₂b₂+a₃b₃)t + b₁²+b₂²+b₃² = r²

équation du second degré en t impliquant 0, 1 ou 2 racines et donc 0, 1 ou 2 intersections en fonction des conditions initiales.

Intersection entre une facette triangulaire et un rayon

On désire connaître la position de l'intersection (si elle existe) entre un rayon et une facette triangulaire connue par les coordonnées dans l’espace de ses trois sommets A, B et C.

On a donc : A = , B = et C = .

B-A =, C-A =.

Le système à résoudre est pour déterminer la position de l'intersection entre le rayon et le plan de la facette.

-> .

On doit résoudre ce système de trois équations linéaires à trois inconnues

La solution est :

D = -z₁y₃x₂+y₁z₃x₂+x₃z₁y₂ +y₃x₁z₂-z₃x₁y₂-x₃y₁z₂

D doit être différent de 0. Si D est égal à 0, le rayon est parallèle à la facette.

u = -(-y₃x₂z_A-y₃x_Pz₂+y₃x₂z_P+y₃x_Az₂
+x₃y₂z_A-x₃y₂z_P+x₂z₃y_A-x₂z₃y_P
+x_Pz₃y₂+x₃y_Pz₂-x₃y_Az₂-x_Az₃y₂)/D

v = (-x₃z₁y_A-x₃y₁z_P+x₃z₁y_P+x₃y₁z_A
+z₃x₁y_A+y₁z₃x_P+z₁y₃x_A-z₃x₁y_P
-y₃x₁z_A-y₁z₃x_A+y₃x₁z_P-z₁y₃x_P)/D

t = (-x_Pz₁y₂+x_Py₁z₂+x_Az₁y₂-x_Ay₁z₂
-x₁y₂z_A+x₁y₂z_P-x₁y_Pz₂+x₁y_Az₂
-x₂z₁y_A-x₂y₁z_P+x₂z₁y_P+x₂y₁z_A)/D

Pour que le point d’intersection soit à l’intérieur du triangle ABC, il faut que :

• u soit positif,
• v soit positif,
• u+v soit inférieur ou égal à 1.

Si on pose dx = x_P - x_A, dy = y_P - y_A, dz = z_P - z_A

D = z₁y₃x₂-y₁z₃x₂-x₃z₁y₂-y₃x₁z₂+z₃x₁y₂+x₃y₁z₂

v = -

u =

t = -

Optimisations

Les optimisations classiques mises en œuvre autour de l'algorithme du lancer de rayons portent sur trois facteurs clés :

• Le calcul des intersections -> Amélioration des tests d'intersection

• Le nombre de calculs d'intersection -> Diminution de ce nombre

• Le nombre de rayons tracés -> Diminution du nombre de rayons primaires et diminution du nombre rayons secondaires

Le calcul des intersections

Le test d'intersection rayon-objet est l'opération de base de tout algorithme de lancer de rayon. Son optimisation pour les différents objets pris en compte permet des gains de temps substantiels.

Représentation mémoire des objets

Tout objet sera représenté sous la forme d'un objet canonique (exemple : le cube de centre O et de rayon 1.0 pour tous les parallélépipèdes rectangles) auquel on applique une matrice de transformation M en coordonnées homogènes.

Test d'intersection avec un rayon R :

• Appliquer à R la matrice M^-1 pour obtenir le rayon R',

• Déterminer l'intersection entre R' et l'objet canonique,

• S'il y a une intersection, calculer sa position et les rayons réfléchi et transmis

• Appliquer la matrice M pour déterminer ces rayons dans l'espace de modélisation.

Boites englobantes

La réalisation d'un test d'intersection pour un objet canonique peut entraîner une charge de calcul importante (par exemple, pour le tore il n'y a pas de solution analytique mais uniquement des solutions numériques par approximations successives).

En englobant strictement chaque objet dans une "boite" géométrique simple (de test d'intersection simple), définie en coordonnées globales, on pourra réaliser une économie substantielle car un rayon qui ne touche pas la boite ne pourra pas toucher l'objet qu'elle contient.

Le nombre de calculs d'intersections

L'acquisition de connaissances sur la position des objets à l'intérieur de la scène peut éviter la réalisation obligatoire d'une recherche systématique d'intersection lors du test d'un rayon vis à vis d'une scène.

Décomposition en voxels

Une technique classique consiste à décomposer l'espace en voxels et à associer à chaque voxel v la liste des objets partiellement ou totalement inclus dans v.

Plutôt que de parcourir séquentiellement tous les objets de la scène à la recherche de l'intersection la plus proche de la source d'un rayon, on analyse les listes d'objets associées aux voxels, voxel après voxel sur le trajet du rayon depuis le voxel d'émission.

Sitôt qu'une intersection est trouvée, il n'est plus nécessaire de parcourir d'autres voxels car toute autre intersection est forcément plus éloignée du point d'émission.

Le nombre de rayons tracés

Une solution simple pour diminuer le nombre de rayons primaires consiste à effectuer préalablement au lancer de rayon une projection des objets de la scène sur l'écran de visualisation. On saura ainsi quels sont les pixels en lesquels aucun objet n'apparaît.

Le problème de la diminution du nombre de rayons secondaires est complexe et ne sera pas traité ici.

Conclusion

Le lancer de rayons est correct du point de vue géométrique pour le placement des rayons lumineux à l'intérieur d'une scène.

Il est en revanche beaucoup moins correct du point de vue énergétique car les phénomènes que l’on désire rendre relèvent de transports d’énergie, aspect que le lancer de rayons ne traduit que partiellement. Ces phénomènes sont beaucoup plus complexes que ceux que l’on peut modéliser par de simples calculs géométriques.

Un avantage déterminant du lancer de rayons pour l'obtention d'images photoréalistes est toutefois que cet algorithme permet de rendre les réflexions et les transparences.

Par rapport à un algorithme du Z-Buffer + Gouraud ou Phong, les images sont de bien meilleure qualité, mais les temps de calcul sont généralement considérablement plus longs (multipliés par 100, 1000 ou plus voire beaucoup plus).