09 — Vers l'accélération

Ce que tu vas apprendre

• Pourquoi le rendu naïf bute sur un mur de complexité
• La boîte englobante : un filtre simple et puissant
• L'intersection rayon-boîte (méthode des slabs)
• L'idée des structures d'accélération, du O(n) au O(log n)

Prérequis

• La boucle de rendu d'un maillage et son coût linéaire
• Des notions de complexité aident, sans être indispensables

Notre moteur fonctionne, mais il est lent — désespérément lent dès que la scène grossit. La raison est structurelle : tester chaque rayon contre chaque triangle est un algorithme en O(n) par rayon. Cet article montre comment franchir ce mur, et ouvre la porte d'un sujet à part entière : les structures d'accélération.

Le mur du O(n)

Reprenons le coût : pour chaque rayon, on parcourt tous les triangles. Avec P pixels, R rayons par pixel et T triangles, on est en O(P × R × T). Le facteur qui fait mal, c'est T : il croît avec le détail des modèles, et il atteint vite les millions. Multiplier la finesse d'un maillage par 10 multiplie le temps de rendu par 10. Ça ne passe pas à l'échelle.

L'observation clé : l'immense majorité de ces tests sont inutiles. Un rayon qui part vers le coin supérieur gauche de l'image n'a aucune chance de toucher un objet situé en bas à droite. Pourtant, le moteur naïf teste quand même tous ses triangles. Tout l'enjeu de l'accélération est d'éliminer ces tests perdus d'avance.

La boîte englobante

La première parade, simple et déjà très efficace, est la boîte englobante (bounding box) : le plus petit pavé aligné sur les axes qui contient entièrement un objet. Avant de parcourir les milliers de triangles d'un maillage, on teste le rayon contre cette unique boîte :

• s'il rate la boîte, il rate forcément tout ce qu'elle contient → on saute le maillage entier, sans tester un seul triangle ;
• s'il touche la boîte, on déroule alors la boucle sur les triangles.

        ┌─────────────┐
        │   ╱╲  ╱╲     │   le rayon qui rate la boîte
   ─────┼──╳──────────┼── ✗ saute tous les triangles
        │ ╱    ╲╱  ╲   │
        └─────────────┘
   un seul test de boîte protège des milliers de tests de triangles

Sur les pixels qui regardent le vide ou un autre objet, ce filtre élimine d'un coup des maillages entiers. Le gain est immédiat.

Intersecter une boîte : les slabs

Tester un rayon contre une boîte alignée sur les axes est très bon marché, grâce à la méthode des slabs. Une boîte est l'intersection de trois « tranches » (slabs), une par axe : x ∈ [xmin, xmax], idem en y et z. Pour chaque axe, on calcule les deux paramètres t où le rayon entre et sort de la tranche :

tx1 = (xmin − O.x) / D.x      tx2 = (xmax − O.x) / D.x
ty1 = (ymin − O.y) / D.y      ty2 = (ymax − O.y) / D.y
tz1 = (zmin − O.z) / D.z      tz2 = (zmax − O.z) / D.z

tEntrée = max(min(tx1,tx2), min(ty1,ty2), min(tz1,tz2))
tSortie = min(max(tx1,tx2), max(ty1,ty2), max(tz1,tz2))

intersection ⟺ tEntrée ≤ tSortie  (et tSortie ≥ 0)

Quelques divisions, des min et des max : aucune racine carrée, aucun produit vectoriel. C'est précisément parce que ce test est si bon marché qu'on peut se permettre de le faire avant chaque maillage.

Du O(n) au O(log n)

La boîte englobante n'est que le premier pas. L'idée se généralise en structures d'accélération : on range toute la scène dans une hiérarchie de volumes englobants, et un rayon descend dans l'arbre en n'ouvrant que les boîtes qu'il traverse. On passe alors d'un coût linéaire O(n) à un coût logarithmique O(log n) en moyenne — la différence entre une scène qui rend en heures et une qui rend en secondes. Les grandes familles :

• BVH (Bounding Volume Hierarchy) : un arbre de boîtes englobantes imbriquées, la structure reine du ray tracing moderne ;
• grilles (uniform grids) : on découpe l'espace en cellules régulières et on ne teste que les cellules traversées ;
• kd-trees : un découpage récursif de l'espace par des plans.

Chacune mérite son propre traitement — c'est l'objet de la série Rendu avancé du parcours, avec l'éclairage global et le path tracing.

La fin du moteur de base

Cette série a construit un ray tracer complet : génération des rayons caméra, intersection rayon-triangle par Möller-Trumbore, coordonnées barycentriques et ombrage lisse, maillages indexés, transformation d'objets et instances, et la première brique d'accélération. C'est un vrai moteur — lent sans accélération avancée, mais correct et complet. Tout ce qui suit dans le parcours (shading physique, éclairage global, structures d'accélération) vient enrichir cette fondation. L'article suivant en récapitule le vocabulaire.

Sources

• Scratchapixel. Ray-Tracing a Polygon Mesh (Part 2) (boîtes englobantes) et Introduction to Acceleration Structures. scratchapixel.com
• Pharr, M., Jakob, W., & Humphreys, G. (2023). Physically Based Rendering (4ᵉ éd.), chap. « Bounding Volume Hierarchies ». pbr-book.org
• Akenine-Möller, T., Haines, E., Hoffman, N., et al. (2018). Real-Time Rendering (4ᵉ éd.), chap. « Accelerated Spatial Data Structures ». CRC Press.