Le rendu par lancer de rayons
(ray tracing)

PRINCIPE

ALGORITHME

AVANTAGES

INCONVÉNIENTS

EXEMPLES

MATHÉMATIQUES

OPTIMISATIONS

CONCLUSION

 

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.

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

Le programme Aux

Le programme GLUt

Exécutable Aux

Exécutable GLUt

Rayons primaires, rayons secondaires
et rayons d'ombre

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

Le programme Aux

Le programme GLUt

Exécutable Aux

Exécutable GLUt

Phénomène physique réel:
décomposition d'un rayon incident
au niveau de l'interface entre deux matériaux

(a) 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

(b) La valeur obtenue par réflexion est calculée en lançant 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.

Angle de réflexion

Le programme GLUt

Exécutable GLUt

Calcul des caractéristiques géométriques
d'un rayon réfléchi

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

(c) La valeur obtenue par transmission est calculée en lançant 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.

Angle de transmission

Le programme GLUt

Exécutable GLUt

Calcul des caractéristiques géométriques
d'un rayon transmis

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

Algorithme simplifié

Programme lancerDeRayons
  scene s
  rayon r
  tableau_de_couleur teinte
  s <- scène à afficher
  pour chaque pixel p(x,y) de l'écran
    r <- rayon passant par l'observateur et p
    teinte[x,y] <- lancerRayon(s,r)
  finpour
finprogramme

couleur lancerRayon(scene s,rayon r)
  couleur cr,ct,cd
  rayon rr,rt,rd
  coefficient kr,kt
  point p
  objet o
  début
  o <- objet de la scène s dont l'intersection
  avec r est la plus proche de la source de r
  si o n'existe pas
    retourner(noir)
    sinon
    p <- point d'intersection entre r et o
    rr <- rayon réfléchi de r en p sur o
    rt <- rayon transmis de r en p vis à vis de o
    kr <- coefficients de réflexion de o
    kt <- coefficients de transmission de o
    cr <- lancerRayon(s,rr) * kr
    ct <- lancerRayon(s,rt) * kt
    cd <- noir
    pour chaque lumiere sl de s
      rd <- rayon de p vers sl
      si rd non intercepté par un objet
        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.
Tout 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).

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.

Le programme GLUt

Exécutable GLUt

Affichages OpenGL (à gauche)
et en lancer de rayons (à droite)
En haut: apport des ombres portées et des réflexions
En bas: Meilleurs gestions des transparences
par décalage des images à travers une surface plane
et inversion des images à travers une surface sphérique

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.

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'équation à 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.

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.

Le programme Aux

Le programme GLUt

Exécutable Aux

Exécutable GLUt

Répartition des objets dans un espace voxels

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 programme Aux

Le programme GLUt

Exécutable Aux

Exécutable GLUt

Parcours d'un rayon dans un espace voxels

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