# Ray tracing

Le lancer de rayons$^,$, ou lancer de rayon$^,$, également appelé ray tracing, est une technique de calcul d'optique par ordinateur, utilisée pour le rendu en synthèse d'image ou pour des études de systèmes optiques. Elle consiste à simuler le parcours inverse de la lumière : on calcule les éclairages de la caméra vers les objets puis vers les lumières, alors que dans la réalité la lumière va de la scène vers l'œil.
Cette technique reproduit les phénomènes physiques (principe du retour inverse de la lumière de Fermat, lois de Snell-Descartes) que sont la réflexion et la réfraction. Une mise en œuvre naïve du ray tracing ne peut rendre compte de phénomènes optiques tels que les caustiques, l'illumination globale ou encore la dispersion lumineuse (il faut une approche plus élaborée du ray tracing, faisant appel à des techniques probabilistes de type méthode de Monte-Carlo, Metropolis ou à la radiosité pour résoudre ces problèmes).
En revanche, contrairement à d'autres algorithmes de synthèse d'image, elle permet de définir mathématiquement les objets à représenter et non pas seulement par une multitude de facettes.

## Historique

Le ray tracing fut présenté pour la première fois par Arthur Appel en 1968$^,$.

## Principe
### Description

Cette technique de rendu consiste, pour chaque pixel de l'image à générer, à lancer un rayon depuis le point de vue (la « caméra ») dans la « scène 3D ». Le premier point d'impact du rayon sur un objet définit l'objet concerné par le pixel correspondant.
Des rayons sont ensuite lancés depuis le point d'impact en direction de chaque source de lumière pour déterminer sa luminosité (est-il éclairé ou à l'ombre d'autres objets ?). Cette luminosité, combinée avec les propriétés de la surface de l'objet (sa couleur, sa rugosité, etc.), ainsi que d'autres informations éventuelles (angles entre la normale à l'objet et les sources de lumières, réflexions, transparence, etc.), déterminent la couleur finale du pixel.
Cette technique fonctionne à rebours des modèles physiques qui, eux, lancent des rayons de lumière depuis les sources lumineuses vers l'œil ou la caméra en passant par les objets, alors que le ray tracing procède de la caméra vers les sources de lumières. L'expérience montre en effet que cette manière de procéder est nettement plus performante dans la plupart des cas (par contre, pour résoudre des caustiques par exemple, une méthode directe depuis les sources ou mixte est souvent préférée).
Différentes techniques permettent d'accélérer ce traitement lourd. Dans le cadre d'objets polygonaux (constitués de triangles par exemple), dessiner l'objet de façon classique (voir la rastérisation) permet de déterminer précisément quels pixels seront réellement visibles, et permet de ne lancer de rayons que pour ces pixels limités. Les différentes techniques de détermination des surfaces cachées permettent de la même manière de minimiser le nombre de rayons à lancer.
Ces calculs préliminaires peuvent être réalisés par un processeur dédié afin de limiter le traitement à faire par le processeur principal. Le ray tracing étant très gourmand en calcul vectoriel, l'utilisation de l'accélération matérielle, conçue pour ce calcul vectoriel (shader), peut grandement aider à optimiser le résultat final.

### Algorithme de ray tracing récursif

Avant 1979, les algorithmes de ray tracing se contentaient seulement de lancer des rayons puis de déterminer la couleur de l'objet pour chaque rayon sans implémentation récursive. En 1979, Turner Whitted (en) proposa une approche récursive, c'est-à-dire d'utiliser l'algorithme de ray casting à partir du point concerné pour calculer sa couleur. Cela offre une meilleure précision physique, notamment pour les reflets.

### Exemple du calcul de l'intersection d'un rayon et d'un triangle

Un moyen simple et efficace pour calculer l'intersection d'un rayon avec un triangle consiste à calculer les coordonnées du point d'intersection I dans la base $({\vec {u}},{\vec {v}},{\vec {r}})$. Il suffit de résoudre l'équation vectorielle ${\overrightarrow {OO_{t}}}+I_{u}{\vec {u}}+I_{v}{\vec {v}}={\overrightarrow {OO_{r}}}+I_{r}{\vec {r}}$. À l'aide de la règle de Cramer, du produit mixte et en posant ${\vec {n}}={\vec {u}}\wedge {\vec {v}},{\overrightarrow {O_{tr}}}={\overrightarrow {O_{t}O_{r}}}$ on obtient :
    $I_{r}=-{\frac {{\vec {n}}\cdot {\vec {O_{tr}}}}{{\vec {n}}\cdot {\vec {r}}}}\ ;I_{u}={\frac {\left({\overrightarrow {O_{tr}}}\wedge {\vec {v}}\right)\cdot {\vec {r}}}{{\vec {n}}\cdot {\vec {r}}}}\ ;I_{v}={\frac {\left({\vec {u}}\wedge {\overrightarrow {O_{tr}}}\right)\cdot {\vec {r}}}{{\vec {n}}\cdot {\vec {r}}}}$
Il suffit ensuite de vérifier que $0\leq I_{u}\leq 1\ ,0\leq I_{v}\leq 1\ ,I_{r}\geq 0\ ,I_{u}+I_{v}\leq 1$.
Il est très simple d'étendre cette méthode à des rectangles et même à des polygones grâce au théorème de Jordan.

## Années 2000 à 2020 : promesses et réalités

Avec la généralisation des processeurs multi-cœurs et de l'utilisation de bibliothèques logicielles mettant en œuvre cette technologie comme OpenMP, OpenCL, CUDA ou Vulkan, l'algorithme du ray tracing voit ses possibilités étendues. En effet, cet algorithme se prête particulièrement bien au parallélisme, chaque point de l'image pouvant être calculé indépendamment des autres. L'immense majorité des logiciels de création graphique basés sur le ray tracing utilisent une implémentation multithread, permettant la prise en charge des processeurs multi-cœurs.
Avec l'apparition de chipsets graphiques multi-cœurs programmables (GPGPU) et des langages de programmation associés (OpenCL ou CUDA par exemple), et avec des moteurs comme LuxRender (open source), Iray et OptiX de NVIDIA, la bibliothèque Embree de Intel ou encore Firerays d'AMD, le ray tracing prend de plus en plus d'importance dans les applications de synthèse d'image en temps réel.
Le ray tracing permet la génération d'images très réalistes, mais peut requérir en contrepartie un temps de calcul très important, en fonction de la complexité de la scène 3D à produire. Jusqu'en 2001, la puissance des ordinateurs ne permettait pas le calcul d'images en temps réel. Depuis, sous certaines conditions, de nombreuses optimisations de l'algorithme permettent un rendu en temps interactif (quelques images par seconde), voire réellement fluide (au-delà de 25 images par seconde).
L'utilisation d'architectures massivement parallèles dédiées telles que les processeurs graphiques ou les cartes accélératrice comme le MIC d'Intel, que ce soit par le biais d'outils dédiés ou par l'utilisation de structures logicielles telles que CUDA, OpenCL ou OpenMP, améliore grandement les performances des outils de rendu par ray tracing et tend à en démocratiser l'usage (Blender propose notamment la possibilité de déporter des opérations de rendu par ray tracing sur GPU à l'aide de la bibliothèque Luxrays).
Dans les années 2010, des jeux commerciaux à large diffusion utilisant cette technique sont prévus$^,$.
Ces méthodes informatiques pour la prédiction d'images trouvent aussi depuis les années 1990 leurs homologues dans divers domaines, en particulier la prédiction de la propagation d'ondes sonores ou de micro-ondes (téléphonie mobile) dans les milieux complexes. Le modèle physique sous-jacent aux algorithmes de ray tracing (le principe de Fermat) est en effet commun à l'optique et l'acoustique, à quelques raffinements près, liés aux longueurs d'onde manipulées (phénomène de diffraction notamment).
Les consoles de jeu de neuvième génération le feront en temps réel.

## Le début de l’utilisation du ray tracing

Le ray tracing est présenté la première fois en 1968 par Arthur Appel, mais il fait réellement son apparition en 1986. Il est d’abord utilisé pour la réalisation de films de grandes maisons d'animation tels que DreamWorks ou encore Pixar. L’accomplissement de cette technique expérimentale ne fut utilisé que partiellement car cette méthode est trop onéreuse. En 2006, Pixar décide de promouvoir ce procédé pour la réalisation du film Cars car cette simulation de la lumière en temps réel permet de rajouter du réalisme au projet, notamment pour la réflexion de la lumière sur la carrosserie, pour les ombres, ainsi que pour l'occlusion ambiante. Cela a permis de démocratiser cette technique aux yeux des maisons de production de films.
Cette méthode n’apparait dans le monde du jeu vidéo que le 23 août 2018 lors de la conférence d’un grand constructeur de cartes graphiques. Lors de cette conférence, NVIDIA présente cette nouvelle manière qui permet d’améliorer le réalisme : la réflexion des flammes, le reflet des miroirs… Ce qui n’était que de vastes calculs permettant une représentation abstraite du reflet des matières tels que le verre, le métal ou encore l’eau est maintenant un véritable algorithme qui permet une représentation bien plus fidèle. Le seul bémol à l’utilisation de ce procédé, ce sont les ressources qu’il utilise. En effet, le calcul de la trajectoire de la lumière a un coût, les ressources devant être allouées aux calculs. Pour les consoles utilisant le ray tracing, la perte du nombre d’images par seconde dépend de nombreux facteurs (le jeu, la qualité des graphismes, la qualité du ray tracing, les composants de l’ordinateur …). Les tests de comparaisonssont nombreux. Pour une définition Full HD, la perte du nombre d’images par seconde pour un jeu tel que Control est de 20%, ce qui peut donc nuire à sa fluidité. Une solution est d'utiliser l’intelligence artificielle, qui permet une qualité d'image similaire tout en réduisant la définition, c'est la technologie DLSS chez Nvidia et FSR chez AMD (bien que la technologie FSR ne soit pas basée sur de l'intelligence artificielle ou du deep learning, elle upscale l'image de manière "intelligente").