Mon projet de Ray Tracing !

Récemment, j'ai réalisé un projet de ray tracing, accessible ici : enpeluche/bernstein-raytracer ! Je vais faire une série d'articles pour expliquer le fonctionnement de ce projet, notamment ses aspects mathématiques.

Voici un exemple de ce que l'on peut générer :

Le ray tracing consiste à simuler le trajet de la lumière pour générer une image. Dans la réalité, la lumière part des sources lumineuses et se propage dans toutes les directions. Mais simuler tous ces rayons serait extrêmement coûteux. L’idée du ray tracing est donc de faire l’inverse : on envoie des rayons depuis la caméra vers la scène et on cherche quels objets ils rencontrent.

Ici, on travaille dans l'espace euclidien $\mathbb{R}^3$, muni du produit scalaire usuel, qui induit la norme euclidienne.

Un rayon est défini par la représentation paramétrique suivante : $$R(t) = O + t \cdot D, \quad t \in \R_+,~ O \in \R^3,~ D\in \R^3$$

On normalise la direction ($\|D\|=1$), pour que le paramètre $t$ corresponde à la distance euclidienne parcourue. Ainsi, trouver la distance de l'objet reviendra simplement à trouver la valeur de $t$.

Nous allons dessiner des objets mathématiques définis comme des surfaces implicites. Une surface implicite est définie comme l'ensemble $$S = \{(x,y,z) \in \mathbb{R}^3 \mid f(x,y,z)=0\}$$ Beaucoup d’objets utilisés en ray tracing peuvent être décrits de cette façon.

On cherche les valeurs de $t$ telles que le point du rayon appartienne à la surface. On doit donc résoudre l'équation : $$f(R(t)) = 0 \Rightarrow f(O+tD) = 0$$ On obtient alors un polynôme en $t$, dont le degré dépend de celui de $f$. Trouver les points d'intersection revient à trouver les racines de ce polynôme. La complexité du problème dépend du degré de ce polynôme.

La sphère unité (rayon $1$, centre à l'origine) est définie par l'équation : $$x^2 + y^2 + z^2 - 1 = 0$$ En injectant la représentation du rayon, on obtient : $$(o_x+td_x)^2 + (o_y+td_y)^2 + (o_z+td_z)^2 - 1 = 0$$ En développant, on voit apparaître des motifs géométriques familiers : $\|O\|^2$, $\|D\|^2$, $O \cdot D$ Comme nous avons normalisé la direction, le polynôme se simplifie : $\|O\|^2 - 1 + t(2 \times O \cdot D) + t^2 = 0$ C'est un polynôme de degré $2$. Pour trouver les racines, on utilise le discriminant $\Delta$. Mais avant cela, regardons la géométrie.

La distance au carré entre le rayon et le centre est donnée par $g(t) = \|O+tD\|^2$. Le minimum de cette distance est atteint lorsque $g'(t) = 0$, soit : $$2 O \cdot D + 2t\|D\|^2=0 \Rightarrow t_{min} = -O \cdot D$$ Alors la distance minimale est : $\|O+t_{min}D\|^2 = \|O - (O \cdot D)\,D\|^2 = \|O\|^2 - (O \cdot D)^2$

Donc :

• Si $g(t_{min}) < 1$ : le rayon traverse la sphère.
• Si $g(t_{min}) = 1$ : le rayon touche la sphère.
• Si $g(t_{min}) > 1$ : le rayon manque la sphère.

Revenons au discriminant. On a $\frac{\Delta}{4} = (O \cdot D)^2-\|O\|^2+1 = 1 - g(t_{min})$.

• Si $\Delta < 0$ alors $g(t_{min})> 1$
• Si $\Delta = 0$ alors $g(t_{min}) = 1$
• Si $\Delta > 0$ alors $g(t_{min}) < 1$

Le discriminant nul correspond donc à une racine double du polynôme d’intersection. Géométriquement, cela signifie que le rayon touche la sphère sans la traverser : il est tangent.

Dans le prochain article, nous verrons les méthodes que j'ai mises en place pour évaluer ce polynôme automatiquement pour des surfaces beaucoup plus complexes (comme le cœur de Taubin) via des DAG et de la dérivation symbolique.