Raycasting

Modèle conceptuel

On peut utiliser le ray casting de deux manières différents, avec une camera ponctuelle (comme sur la partie gauche de l'illustration) pour avoir une image avec de la perspective, ou avec une caméra "à l'infini", pour avoir de la perspective cavalière, comme sur des dessins d'usine. Dans le modèle de la caméra ponctuelle, on a un point focal (la caméra) et une matrice de pixels carré (l'écran), on appelle longueur focale la distance qui les séppare. Les rayons lumineux partent du point focal et traverse les pixels, on prend généralement un rayon par pixel.

Lorsque que la distance focal est infinie, on est dans le cas d'une caméra à l'infini. Les rayons lumineux sont parallèles les uns aux autres, ce qui donne comme nom à ce point de vue le nom de vue parallèlle. Bien que la vue avec de la perspective est plus naturelle pour produire des images, certaines applications nécessite des rayons qui soient uniformément distribués.

Pour un souci de simplicité de modélisation, on se place dans le cas dune caméra ponctuelle et on utilisera le système de coordonnée suivant : l'axe Z est orthogonal à l'écran (donc les axes X et Y forment le plan qui contient l'écran), l'axe Y est la verticale, le point focal (celui d'où partent les rayons) est sur l'axe -Z.

Un rayon est simplement une droite dans l'espace. Il peut donc être paramamétré par un point (X₀, Y₀, Z₀) et un vecteur (D_x, D_y, D_z), les points (X, Y, Z) de la droite sont paramétrés par un paramètre t tel que :

${\displaystyle {\begin{aligned}X&=X_{0}+t\cdot D_{x}\\Y&=Y_{0}+t\cdot D_{y}\\Z&=Z_{0}+t\cdot D_{z}\end{aligned}}}$

Si le vecteur directeur est normalisé, alors le paramètre t donne la distance à (X₀, Y₀, Z₀) le long de la ligne. Pour substituer un vecteur quelconque par un vecteur normalisé, il suffit de prendre :

${\displaystyle {\begin{aligned}{\text{dist}}&={\sqrt {D_{x}^{2}+D_{y}^{2}+D_{z}^{2}}}\\D_{x}^{'}&=D_{x}\ /{\text{ dist}}\\D_{y}^{'}&=D_{y}\ /{\text{ dist}}\\D_{z}^{'}&=D_{z}\ /{\text{ dist}}\end{aligned}}}$

En connaissant les paramètres géométriques des objets dans l'environnement. Il suffit de trouver toutes les intersections entre ces objets et le rayon. Cela nous donne deux tableaux :

1. Distance sur le rayon : ${\displaystyle t[1],t[2],...t[n]}$ (trié par selon les t croissants)
2. Surface intersectée : ${\displaystyle S[1],S[2],...,S[n]}$

On détermine ensuite l'intersection dont la distance est minimale après l'écran. C'est les propriétés de la surface intersectée qui servira à déterminer la couleur du pixel.

Dessin de contours

Pour dessiner les bords visibles d'un solide, on génère un rayon par pixel. Si la surface associée au le pixel localisé en ${\displaystyle {\it {(X,Y)}}}$ est différente de celle en ${\displaystyle {\it {(X-1,Y)}}}$, alors on dessine une arrête verticale longue d'un pixel en ${\displaystyle {\it {(X-{\frac {1}{2}},Y)}}}$. De même, si la surface associée au le pixel localisé en ${\displaystyle {\it {(X,Y)}}}$ est différente de celle en ${\displaystyle {\it {(X,Y-1)}}}$, alors on dessine une arrête horizontale longue d'un pixel en ${\displaystyle {\it {(X,Y-{\frac {1}{2}})}}}$. Comme ce dessin consiste uniquement en des traits verticaux et horizontaux, son rendu sera irrégulier à basse résolution.

Cette méthode a été décrite par Roth et a été employé sur les images ci-contre. A des fins d'optimisations, des boîtes englobantes(qui consiste à englober les ensembles de forme complexes dans des pavés plus grand pour diminuer le nombre de calcul), la mise à jour dynamique des boîtes et la cohérence. Pour chaque image, l'écran a été échantilloné avec une taille d'environ 100x100 (i.e. 10 000 rayons). Les nouvelles arrêtes étaient localisés avec de la dichotomie. Puis, pour chaque arrêtes, on lance un rayon additionnel des deux côtés de l'arrête. Chaque image a été dessiné sur tube Tetronix avec une résolution de 780x780.

Images ombragées

Pour faire une image ombragée, on utilise cette fois encore un seul rayon par pixel de l'écran. Cependant, cette fois, on va tracer aussi tracer des rayons depuis des sources lumineuses vers le point d'intersection avec la surface. Puis, à partir des propriétés de la surface, des distances aux sources lumineuses et des angles entre les rayons de l'écran et ceux de la, on calcule la valeur du pixel. Pour être plus précis, la luminosité apporté par une source

Calculer de volumes et de moments d'inertie

Le volume volume (et les grandeurs semblables) d'un solide délimité par des surfaces courbées est calculable facilement par en approchant par des sommes comme en intégration, en approchant le solide par des pavé droits. Pour cela, on prend une photo "en profondeur" du solide avec une vue parallèle. On lance des rayons depuis l'écran à travers le solide, de manière à partitionner le solide en éléments de volume. Ces éléments forment des parallépipèdes rectangles dont deux dimensions sont constantes et égales aux dimensions ${\displaystyle S}$ du pixel de l'écran (i.e. l'écart entre les rayons). La troisième dimension, variable, est défini par la somme des distances entre les entrées et les sorties, alors le volume détecté par le rayon est :

${\displaystyle S\times S\times {\frac {t[2]-t[1]+t[4]-t[3]+\ldots +t[n]-t[n-1]}{L}}}$

où ${\displaystyle L}$ est la norme du vecteur directeur (qui vaut donc 1 si il a été normalisé),

et où chaque ${\displaystyle {\tfrac {t[i]\ -\ t[i-1]}{L}}}$ est la longueur du rayon dans le solide.

Images réalistes ombragées

On décit dans cette section décrit le programme d'échelle de gris par ray casting développé par Scott Roth et Daniel Bass au GM Research Labs en 1979. Pour créer des images, le programme laisse le contrôle à l'utilisateur des paramètres suivants :

• La caméra
  • la direction de la caméra et sa position
  • la distance focale (ou l'angle que forme
  • le facteur de zoom
• L'éclairement
  • le nombre de sources de lumières
  • l'intensité et la localisation de chacune des sources de lumières
  • la possibilité de calculer les ombres
  • l'intensité de la lumière ambiante
• Les propriétés des surfaces
  • le pourcentage diffusé
  • le pourcentage réfléchi
  • le pourcentage transmis

L'image ci-dessus a été générée par le programme avec deux sources de lumière d'intensités différentes et avec des ombres.

Les algorythmes comme celui-ci qui implémente une lumière réaliste sont relativement simple à mettre au point, mais sont couteux en calculs. Par exemple, la figure ci-contre illustre que, pour un pixel, on doit tracer plusieurs rayon supplémentaires pour une seule source afin de déterminer le résultat.

Pour générer une image, le programme va pour chaque lancer un rayon qui part du point focal. Lorsque le rayon intersecte une surface en partie transparente, il la traverse. Lorsque le rayon atteint une surface réflechissante, on crée un rayon réflechi pour savoir ce qui est visible. Pour chaque surface intersectée, on trace un rayon vers les sources lumineusses (les "shadow feeler") pour voir si celles-ci sont occultées par une surface.

Turner Whitted appelle les rayons secondaires et additionnels de "tracer de rayons récursifs". Il a modélisé la réfraction pour les objets transparents en générant des rayons secondaires depuis la surface visible à un angle déterminé par l'indice de réfraction de la surface. Whitthed fait la remarque qu'une pièce rempli de mirroirs serait coûteuses à simuler, et suggère de limiter le nombre de récursion par prudence.

Recherche binaire récursive

On lance un premier rayon au centre de l'écran, puis récursivement sur les deux moitiés et ainsi de suite. Lorsque deux rayons voisins ont touché le même mur, on arrête la recherche et on rend les tranches intermédiaires avec une interpolation fondée sur le z-mapping.

Technique intéressante pour des résolutions très faibles et des espaces très découpés, si bien que dans l'arrière plan le nombre de polygones devient plus grand que le nombre de pixels.

Rendu à travers des portails

On ne lance des rayons que sur les points du secteur (polygone) où se trouve la caméra. Puis on recommence récursivement sur les secteurs adjacents avec de nouveaux cônes de vision définis par les rayons lancés sur les points des portails (murs invisibles qui connectent deux secteurs).

La recherche s'arrête quand les sous-cônes de vision ne traversent plus aucun portail.

Le cône de vision est ainsi décomposé en une série de sous-cônes qui vont permettre de trier les faces avant leur rendu.

Z ordering pré-rendu

Technique utilisée dans Doom. On ne lance plus que deux rayons pour le frustum clipping des faces. Leur ordre de rendu est précalculé avec un arbre BSP et le clipping entre les faces s'effectue sur un axe à une dimension.

La recherche des faces s'arrête quand tous les pixels ont été remplis.

Plus rapide que la précédente, elle présente l'inconvénient de ne fonctionner qu'avec des espaces statiques.

Liens externes

• (fr) Explications du RayCasting
• Raycaster interactif pour MSDOS en 64 octets (avec source code)

• Portail de l’imagerie numérique
• Portail du jeu vidéo