04 — Implémenter l'algorithme

Ce que tu vas apprendre

• La structure complète de l'algorithme, en pseudo-code
• Comment tester l'intersection d'un rayon avec une sphère
• Pourquoi il faut garder le plus proche objet touché, et pas n'importe lequel
• Le coût de tout ça, et pourquoi le ray tracing a longtemps été lent

Prérequis

• L'article précédent : rayons primaires et rayons d'ombre
• Savoir lire une boucle for et une équation du second degré

On a l'intuition complète. On va la couler en pseudo-code. L'algorithme de base d'Appel tient en une double boucle imbriquée : pour chaque pixel, on lance un rayon, on cherche ce qu'il touche, et on calcule une couleur. Voici le squelette.

Le squelette : une double boucle

cppfor (int j = 0; j < imageHeight; ++j) {
  for (int i = 0; i < imageWidth; ++i) {
    Ray primRay;
    computePrimRay(i, j, &primRay);   // rayon depuis l'œil vers le pixel (i, j)

    Point  pHit;       // point d'intersection
    Normal nHit;       // normale à la surface en ce point
    float  minDist = INFINITY;
    Object *object = NULL;

    // 1. Trouver l'objet le plus proche touché par le rayon primaire
    for (int k = 0; k < objects.size(); ++k) {
      if (Intersect(objects[k], primRay, &pHit, &nHit)) {
        float distance = Distance(eyePosition, pHit);
        if (distance < minDist) {     // plus proche que tout ce qu'on a vu ?
          object  = &objects[k];
          minDist = distance;
        }
      }
    }

    if (object != NULL) {
      // 2. Tester l'ombre : un rayon du point vers la lumière
      Ray shadowRay;
      shadowRay.direction = lightPosition - pHit;
      bool isInShadow = false;
      for (int k = 0; k < objects.size(); ++k) {
        if (Intersect(objects[k], shadowRay)) { isInShadow = true; break; }
      }
      // 3. Colorer
      pixels[i][j] = isInShadow ? 0 : object->color * light.brightness;
    }
  }
}

Trois étapes, dans l'ordre : trouver l'objet visible, tester l'ombre, colorer. C'est tout l'algorithme. Le reste de la série ne fait que muscler l'étape 3 (la couleur) et l'étape 1 (l'intersection).

Garder le plus proche, toujours

Un rayon peut traverser plusieurs objets alignés. Celui qu'on voit, c'est le premier rencontré — le plus proche de l'œil. D'où la variable minDist : on parcourt tous les objets, et on ne garde un candidat que s'il est plus proche que le meilleur trouvé jusque-là. Oublier ce test, c'est afficher l'objet du fond par-dessus celui de devant. C'est la version ray tracing du problème de la profondeur (le z-buffer en rasterization).

Le test d'intersection : rayon contre sphère

Tout repose sur la fonction Intersect. Prenons le cas le plus simple et le plus courant en pédagogie : la sphère. Un rayon est un point de départ O (l'œil) plus une direction D :

P(t) = O + t·D,   avec t ≥ 0

t est la distance le long du rayon. Une sphère de centre C et de rayon r, c'est l'ensemble des points à distance r de C :

‖P − C‖² = r²

On remplace P par O + t·D et on développe. On tombe sur une équation du second degré en t :

a·t² + b·t + c = 0
  avec  a = D·D     (= 1 si D est normalisé)
        b = 2·D·(O − C)
        c = (O − C)·(O − C) − r²

Le discriminant Δ = b² − 4ac tranche d'un coup :

• Δ < 0 → pas de solution réelle : le rayon manque la sphère.
• Δ = 0 → une solution : le rayon est tangent.
• Δ > 0 → deux solutions t₀ et t₁ : le rayon entre et ressort. On garde la plus petite valeur positive — le point d'entrée, le plus proche de l'œil.

Une fois t connu, le point touché est pHit = O + t·D, et la normale (utile pour l'ombrage et les reflets) est la direction du centre vers ce point, normalisée : nHit = (pHit − C) / r. Tout l'algèbre tient en quelques lignes, et c'est pour ça que les sphères sont les cobayes universels des ray tracers : leur intersection est exacte et triviale. Si tu veux l'implémenter pas à pas en C++, le tutoriel Ray Tracing in One Weekend de Peter Shirley déroule exactement ce calcul.

Et la couleur ?

Dans ce squelette minimal, la couleur est volontairement bête : si le point voit la lumière, on prend la couleur de l'objet multipliée par l'intensité de la lampe ; sinon, du noir. C'est un éclairage binaire, sans nuance. Les vrais modèles d'ombrage (diffus de Lambert, spéculaire, etc.) raffinent ce calcul en tenant compte de l'angle entre la normale et la lumière — un sujet à part entière qu'on traitera dans la série « Shading & lumière » du parcours. Ici, le point est juste de montrer où la couleur se calcule.

Le prix à payer

Regarde les boucles imbriquées : pour chaque pixel, on teste tous les objets ; et pour chaque objet touché, on relance une boucle sur tous les objets pour l'ombre. Sur une image d'un million de pixels et une scène de milliers d'objets, ça fait beaucoup. Quand Appel a publié l'idée en 1968, il notait que son rendu demandait plusieurs milliers de fois plus de calcul qu'un simple tracé fil de fer. C'est la raison pour laquelle le ray tracing est resté un truc de labo pendant des décennies, avant que la puissance des machines et les structures d'accélération (qu'on verra dans une série dédiée) le rendent praticable.

L'algorithme de base est complet. L'article suivant lui ajoute ce qui fait sa réputation : les reflets et la transparence, via la récursivité.

Sources

• Scratchapixel. Implementing the Raytracing Algorithm. scratchapixel.com
• Appel, A. (1968). Some Techniques for Shading Machine Renderings of Solids. AFIPS. DOI : 10.1145/1468075.1468082
• Shirley, P. Ray Tracing in One Weekend, sections « Adding a Sphere » et « Surface Normals and Multiple Objects ». raytracing.github.io
• Scratchapixel. A Minimal Ray-Tracer — détail des intersections rayon-objet (sphère, plan, disque…). scratchapixel.com