04 — L'algorithme de Möller-Trumbore

Ce que tu vas apprendre

• L'idée derrière Möller-Trumbore : un changement de repère
• Pourquoi il est si rapide (rien à pré-calculer)
• Le code complet, ligne par ligne
• Ce qu'il renvoie : la distance et les coordonnées barycentriques

Prérequis

• L'intersection rayon-plan et le produit vectoriel

Publié en 1997 par Tomas Möller et Ben Trumbore, l'algorithme de Möller-Trumbore est sans doute la routine d'intersection la plus exécutée de l'histoire du rendu. Il résout l'intersection rayon-triangle d'un seul coup — plan et test d'appartenance — sans avoir besoin de stocker l'équation du plan du triangle. C'est l'un de ces petits bijoux d'algorithmie qui valent le détour.

L'idée : un changement de repère

Plutôt que de calculer le plan puis de tester « dedans/dehors » séparément, Möller-Trumbore change de repère. Il exprime le point d'intersection directement dans le repère du triangle, en coordonnées barycentriques (u, v) — un système où le triangle devient un triangle de référence simple. Le problème se ramène alors à résoudre un système linéaire 3×3, qu'on traite par la règle de Cramer (des produits mixtes de vecteurs).

Le résultat est un triplet (t, u, v) :

• t : la distance le long du rayon (le point d'impact est O + t·D) ;
• (u, v) : les coordonnées barycentriques, qui disent où dans le triangle on a tapé.

Le test d'appartenance devient trivial : le point est dans le triangle si u ≥ 0, v ≥ 0 et u + v ≤ 1. Pas de plan à stocker, pas de calcul séparé. Tout sort du même système.

Le code, ligne par ligne

cppbool intersectTriangle(const Vec3f& O, const Vec3f& D,        // rayon O + t·D
                       const Vec3f& v0, const Vec3f& v1, const Vec3f& v2,
                       float& t, float& u, float& v)
{
  Vec3f edge1 = v1 - v0;                  // deux côtés du triangle
  Vec3f edge2 = v2 - v0;
  Vec3f pvec  = cross(D, edge2);
  float det   = dot(edge1, pvec);

  // det ≈ 0 → rayon parallèle au triangle
  if (fabs(det) < 1e-8) return false;
  float invDet = 1 / det;

  Vec3f tvec = O - v0;
  u = dot(tvec, pvec) * invDet;
  if (u < 0 || u > 1) return false;       // hors du triangle

  Vec3f qvec = cross(tvec, edge1);
  v = dot(D, qvec) * invDet;
  if (v < 0 || u + v > 1) return false;   // hors du triangle

  t = dot(edge2, qvec) * invDet;          // distance
  return t > 0;                           // devant la caméra ?
}

Décortiquons :

• edge1, edge2 : deux arêtes du triangle issues de v0 — elles forment la base du repère barycentrique.
• det : le déterminant du système. S'il est ~ 0, le rayon est parallèle au triangle, on s'arrête.
• u : calculé par produit scalaire, rejeté immédiatement s'il sort de [0, 1]. Ce rejet anticipé évite des calculs inutiles — c'est une partie de ce qui rend l'algorithme rapide.
• v : pareil, avec le test u + v ≤ 1 qui ferme le triangle.
• t : la distance, calculée en dernier, une fois qu'on sait qu'on est dans le triangle.

Pourquoi il est rapide

Deux raisons. D'abord, il ne stocke rien : pas d'équation de plan pré-calculée, donc moins de mémoire et un meilleur comportement de cache quand on parcourt des millions de triangles. C'est tout le sens du titre du papier d'origine, Fast, Minimum Storage Ray/Triangle Intersection. Ensuite, les rejets anticipés (sur u, puis v) coupent le calcul dès qu'on sort du triangle, sans aller au bout. Sur une scène où la plupart des rayons ratent la plupart des triangles, ces sorties précoces font toute la différence.

Ce qu'on en fait

Les (u, v) renvoyés ne servent pas qu'au test d'appartenance : ce sont les coordonnées barycentriques, la clé pour interpoler les attributs du triangle (normales, couleurs, coordonnées de texture) au point d'impact. C'est exactement le sujet de l'article suivant — sans elles, un maillage aurait l'air facetté et terne.

Sources

• Möller, T., & Trumbore, B. (1997). Fast, Minimum Storage Ray/Triangle Intersection. Journal of Graphics Tools, 2(1), 21-28. DOI : 10.1080/10867651.1997.10487468 — PDF original (Cornell)
• Scratchapixel. Ray-Tracing: Rendering a Triangle — Möller-Trumbore Ray-Triangle Intersection. scratchapixel.com
• Möller–Trumbore intersection algorithm. Wikipedia