En 2020, chaque mois, Charlotte Truchet et Serge Abiteboul nous racontent des histoires d’algorithmes. Des blockchains aux algorithmes de tri en passant par le web, retrouvez tous leurs textes, ainsi que des petits défis mathématiques, dans le Calendrier Mathématique 2020 et dans la série binaire associée… Antoine Rousseau

Mars : Dessine-moi un mouton

Jusqu’à la fin du siècle dernier, le traitement d’images faisait appel à des lentilles, des filtres, des bancs de marbre, etc. Et puis les images sont devenues numériques, ouvrant la porte à les traitements algorithmiques de plus en plus puissants. Nous nous baladons avec des téléphones qui prennent des photos avec des millions de pixels et réalisent des traitements logiciels qui auraient fait pâlir d’envie les professionnels du traitement d’image de la fin du siècle dernier. Un téléphone intelligent offre une énorme gamme de fonctionnalités depuis la mise au point automatique jusqu’à la reconnaissance de visage. Ces mêmes téléphones vont bientôt nous ouvrir à des mondes nouveaux de réalités virtuelles ou augmentées. Tout cela s’appuie sur des algorithmes de géométrie.

Considérons une version très simplifiée d’un tel algorithme : le ray tracing. On dispose du modèle d’un monde en 3 dimensions et on aimerait construire une vue de ce monde depuis un point particulier, censé représenter un oeil, un appareil photo. Intuitivement, on lance un rayon depuis ce point de vue et on cherche quand et où ce rayon rencontrera un objet du modèle 3D. Le ray tracing permet de dessiner ce qu’on voit à partir de ce point de vue. Une balle devient un rond et un objet derrière la balle est représenté que partiellement, le point de vue ne voit pas la partie cachée par la balle.   

Dans le modèle 3D, on peut représenter un objet par un petit triangle, un carré, ou un parallélépipède. Pour calculer le point d’intersection d’une ligne droite avec de tels objets, il suffit de résoudre des équations vectorielles. Pour réaliser le ray tracing,  on a donc à effectuer un très grand nombre de calculs. Comme les calculs pour chaque point de l’image peuvent être faits indépendamment, on peut les réaliser en parallèle. Ces applications graphiques ont d’ailleurs conduit à de super avancées pour des processeurs massivement parallèles.  

Avec cet algorithme, on peut calculer l’objet visible en chaque point. On peut alors lancer des rayons depuis chaque point d’impact vers les sources de lumière pour déterminer sa luminosité. Observez que dans le monde réel, les rayons lumineux vont de la source de lumière vers le point de vue. Ici, on <<remonte>> le chemin des rayons jusqu’à la source de lumière.

Serge Abiteboul et Charlotte Truchet