Le rendu par lancer de rayons
(ray tracing)

PRINCIPE

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.

Un rayon primaire par pixel de l'écran virtuel


Vue extérieure
Rayon correspondant au pixel en bas à droite


Vue extérieure
Lancers successifs des rayons correspondant
à tous les pixels


Vue depuis la position de l'observateur

Programme GLUt

Exécutable GLUt

Enter pour switcher entre les affichages
"tous les rayons" et "un seul rayon"
Espace pour augmenter le nombre de rayons tracés
ou déplacer le rayon tracé
m pour changer de point de vue :
extérieur ou observateur
+/- pour augmenter/diminuer
la résolution de l'écran virtuel
Touches de curseur et souris pour changer
le point de vue extérieur

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 optique réel de décomposition
d'un rayon lumineux incident (jaune)
au niveau de l'interface entre deux milieux
en un rayon réfléchi (rouge),
un rayon transmis (bleu)
et de la lumière diffusée (vert)


Composantes01v.gif (8231 octets)

Programme GLUt

Exécutable GLUt

n, N, m et M pour modifier le facteur n = ni/nt
1, 2, 3, 4, 5 et 6 pour modifier la position
de la source (sphère jaune) du rayon incident
Touches de curseur et souris pour manipuler la scène

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 = -qiqi est "l'angle d'incidence" par rapport à la normale à l'interface au niveau du point de réflexion.

Calcul des caractéristiques géométriques
d'un rayon réfléchi (rouge)
à partir d'un rayon incident (jaune)

Programme GLUt

Exécutable GLUt

1, 2, 3, 4, 5 et 6 pour modifier la position
de la source (sphère jaune) du rayon incident
Touches de curseur et souris pour manipuler la scène

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.

Calcul des caractéristiques géométriques
d'un rayon transmis (bleu)
à partir d'un rayon incident (jaune)

Programme GLUt

Exécutable GLUt

n, N, m et M pour modifier le facteur n = ni/nt
1, 2, 3, 4, 5 et 6 pour modifier la position
de la source (sphère jaune) du rayon incident
Touches de curseur et souris pour manipuler la scène

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)).

Matériel Indice
Vide 1.0
Air 1.000293
Eau 1.33
Verre 1.5
Diamant 2.42

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 2n 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 :

(a1t + b1)2+(a2t + b2)2+(a3t + b3)2 = r2

(a12+a22+a32)t2 + 2(a1b1+a2b2+a3b3)t + b12+b22+b32 = r2

é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 = -z1y3x2+y1z3x2+x3z1y2 +y3x1z2-z3x1y2-x3y1z2

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

u = -(-y3x2zA-y3xPz2+y3x2zP+y3xAz2
+x3y2zA-x3y2zP+x2z3yA-x2z3yP
+xPz3y2+x3yPz2-x3yAz2-xAz3y2)/D

v = (-x3z1yA-x3y1zP+x3z1yP+x3y1zA
+z3x1yA+y1z3xP+z1y3xA-z3x1yP
-y3x1zA-y1z3xA+y3x1zP-z1y3xP)/D

t = (-xPz1y2+xPy1z2+xAz1y2-xAy1z2
-x1y2zA+x1y2zP-x1yPz2+x1yAz2
-x2z1yA-x2y1zP+x2z1yP+x2y1zA)/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 = xP - xA, dy = yP - yA, dz = zP - zA

D = z1y3x2-y1z3x2-x3z1y2-y3x1z2+z3x1y2+x3y1z2

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.

Boites englobantes


Un parallélépipède dans une sphère englobante


Une surface paramétrique bicubique dans un cube

Programme GLUt

Exécutable GLUt

Enter pour switcher entre affichages

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.

Répartition des objets dans un espace voxels


Décomposition en voxels


Association d'une liste d'objets à chaque voxel

Programme GLUt

Exécutable GLUt

Enter pour switcher entre affichages

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.

Parcours d'un rayon dans un espace voxels


Rayon


Suite de voxels parcourue par le rayon

Programme GLUt

Exécutable GLUt

Enter pour switcher entre affichages :
rayon seul, rayon+voxels de Bresenham,
rayon+tous les voxels traversé,
trace du parcours du rayon dans les voxels
(Espace pour avancer)

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).