07 — Ray tracer un maillage
Ce que tu vas apprendre
- La boucle complète : tester chaque triangle, garder le plus proche
- Récupérer la normale lisse au point d'impact
- Le coût linéaire de cette approche naïve
- Pourquoi il faudra des structures d'accélération
Prérequis
- Möller-Trumbore, les barycentriques et les maillages
Toutes les briques sont là. On peut enfin ray tracer un vrai objet : un maillage de milliers de triangles, rendu avec un ombrage lisse. La boucle est conceptuellement simple — c'est l'aboutissement de toute la série.
La boucle : tester chaque triangle
Pour un rayon donné, on teste tous les triangles du maillage avec Möller-Trumbore, et on garde l'intersection la plus proche (le plus petit t positif), en mémorisant au passage le triangle touché et ses coordonnées barycentriques :
cppbool Mesh::intersect(const Ray& ray, float& tNear, int& triIndex, Vec2f& uv) const
{
bool hit = false;
for (int k = 0; k < numTriangles; ++k) {
const Vec3f& v0 = vertices[faceIndices[3*k + 0]];
const Vec3f& v1 = vertices[faceIndices[3*k + 1]];
const Vec3f& v2 = vertices[faceIndices[3*k + 2]];
float t, u, v;
if (intersectTriangle(ray.O, ray.D, v0, v1, v2, t, u, v) && t < tNear) {
tNear = t; // plus proche que tout ce qu'on a vu
uv = {u, v}; // barycentriques pour l'ombrage
triIndex = k; // quel triangle
hit = true;
}
}
return hit;
}
C'est exactement la « plus proche intersection » de la série fondations, mais déroulée sur tous les triangles d'un maillage au lieu de quelques sphères.
La normale lisse au point d'impact
Une fois le triangle et les barycentriques (u, v) connus, on calcule la normale lisse en interpolant les trois normales de sommet (article 05) :
cppvoid Mesh::getSurfaceProps(int triIndex, const Vec2f& uv, Vec3f& N) const
{
const Vec3f& N0 = normals[faceIndices[3*triIndex + 0]];
const Vec3f& N1 = normals[faceIndices[3*triIndex + 1]];
const Vec3f& N2 = normals[faceIndices[3*triIndex + 2]];
float w = 1 - uv.x - uv.y; // troisième poids barycentrique
N = normalize(w*N0 + uv.x*N1 + uv.y*N2); // ombrage lisse
}
Cette normale interpolée alimente le calcul d'éclairage (le produit scalaire normale·lumière de la série maths). Résultat : la surface paraît lisse, sans facettes visibles, alors que la géométrie reste un assemblage de triangles plats. C'est tout le bénéfice des barycentriques, payé d'une poignée d'opérations.
Le coût : linéaire avec les triangles
Voilà le hic, et il est majeur. Cette boucle teste chaque rayon contre chaque triangle. Le temps de rendu croît donc linéairement avec le nombre de triangles : doubler la finesse du maillage double le temps de calcul. Et comme on lance un rayon par pixel (et plus encore avec les reflets et les ombres), on multiplie.
Scratchapixel donne un ordre de grandeur parlant : une scène de 200 triangles demandait déjà environ 2,5 secondes sur un processeur à 2,5 GHz — pour 200 misérables triangles. Un maillage réaliste en compte des centaines de milliers, parfois des millions. À ce rythme, le rendu naïf est totalement impraticable.
coût ≈ (nb pixels) × (nb rayons/pixel) × (nb triangles)
→ explose dès qu'un maillage devient détailléLa sortie : les structures d'accélération
La solution n'est pas de tester moins finement, mais de tester plus malin : éviter de comparer un rayon à des triangles qu'il ne peut de toute façon pas toucher. Une première parade, déjà efficace, est la boîte englobante : avant de parcourir les triangles d'un maillage, on teste le rayon contre une simple boîte qui l'entoure ; s'il la rate, on saute tout le maillage d'un coup. C'est le point de départ de l'article suivant, et de toute une série dédiée à l'accélération.
Sources
- Scratchapixel. Ray-Tracing a Polygon Mesh (Part 1). scratchapixel.com
- Scratchapixel. Ray-Tracing a Polygon Mesh (Part 2). scratchapixel.com
- Shirley, P. Ray Tracing: The Next Week (maillages et structures d'accélération). raytracing.github.io