RayCasting

 

     Introduction :

On peut voir d'après Wikipedia que le Raycasting :

« Le raycasting est une technique de calcul d'images de synthèse 3D. Elle a été utilisée avec succès au début des années 1990 dans les jeux vidéo comme Wolfenstein 3D ou Doom. L'implémentation était alors entièrement logicielle et ne faisait pas appel à du matériel spécifique.

Il tire parti de certaines caractéristiques du monde virtuel :

  • les murs sont des plans, en général perpendiculaires par rapport au sol

  • il n'y a pas de primitives complexes ou alors sous la forme d'approximations planaires

  • les mondes virtuels sont de facto plus simples

Le raycasting produit des images plutôt anguleuses avec des effets de bloc désagréables. Autre limitation courante de la technique du raycasting : le champ de vision est parallèle au sol, il n'est pas possible d'avoir un axe de la caméra entièrement libre. Ceci est particulièrement visible dans les premiers jeux vidéo à vue subjective comme Doom où le champ de vision pointe toujours vers l'avant et ne peut pas regarder le plafond ou le sol. Il n'est pas non plus possible d'effectuer une rotation autour de l'axe de la caméra (roll).

Ceci est dû au fait que le raycasting est essentiellement une technique basée sur un espace en 2D et non pas sur une description complète en 3D du monde.

Tombée en désuétude lors de l'apparition des moteurs entièrement en 3d, cette technique a été remise au goût du jour par les technologies portables comme java ou flash. »

Le Raycasting n'est donc pas un moteur 3D à proprement parlé, c'est plutôt une méthode pour donner l'apparence d'un monde en 3D. Cette méthode fonctionne un peu comme un radar : on lance des rayons depuis un point fixe vers un objet afin d’obtenir des informations utiles pour l'afficher à l’écran. C'est à dire que plus le rayon pour atteindre l'objet et grand, plus l'affichage de l'objet sera petit car étant « loin ».

 

     Le Concept :

La première règle d'importance c'est que votre monde n'est composé que d'un plan en deux dimensions.
Vous allez devoir donner l'illusion qu'il est en trois dimensions.


Notre objectif est de passer de la vue de gauche (Bird Eyes) à la vue de droite (First Person).

L’essentiel de votre jeu se passe dans un univers en deux dimensions (vue de gauche).
Ce que le joueur voit est une projection plate qui simule la profondeur (vue de droite).

La vue de gauche représente le moteur de votre jeu, il est totalement virtuel. C'est-à-dire que vous n’aurez jamais affaire à lui autrement que par du code.

La vue de droite est le résultat visible à l’écran des calculs effectués par le moteur. Vous avez l’impression de vous trouver dans un cul de sac entouré de murs. Alors que ce ne sont que deux trapèzes identiques qui entourent un carré rouge.

Pourtant çà fonctionne et voici comment :


Le projecteur (la caméra) lance des rayons qui permettent de détecter ce qu’il à en face de lui. Plus le rayon va loin dans le décor, plus la distance qui sépare la caméra de l’obstacle est importante. Plus l’obstacle est loin de la caméra et plus l’objet paraîtra petit une fois projeté sur l’écran.

Nous allons voir maintenant comment passer du plan à la vue subjective.

Dans le « moteur » que nous réalisons avec le Raycasting, Nous allons créer des mondes plats avec une unique hauteur de murs, un sol et un plafond. Si nos murs ont une hauteur fixe alors logiquement notre monde est constitué de cubes , il est de fait soumis aux contraintes suivantes :

  • Les murs ont toujours un angle de 90° avec le sol

  • Les murs sont des cubes qui ont tous la même taille

  • Le sol est toujours plat

Il facile d’imaginer un univers en 2 dimensions (une simple grille) pour construire notre monde. Le monde est plat, il est vu du dessus, et il est formé de cases toutes identiques. Les cases vident représente un espace vide ou le joueur peut se déplacer, les cases avec des chiffres représente les murs (en fonction des numéros on a des murs avec des textures différentes : mur rouge, vert, bleu …).


A gauche un schéma avec une caméra qui lance des rayons pour voir ce qu’il y a devant. A droite la même chose mais sous forme de tableau, chaque chiffre correspond a un type d’objet. Espace vide / le sol ( 0 ), un mur gris( 1 ).

 

  L'affichage :

Les paramètres à définir lorsqu'on va projeter les rayons sont :

  • La hauteur de la caméra

  • L’orientation de la camera dans la map (son angle)

  • Le champ visuel de la camera

  • La position de la camera dans la map (posCamX et posCamY)

  • La taille de l’écran de projection

On va déterminer la hauteur de la caméra par rapport à la hauteur du mur.

Le champ visuel représente l'ensemble de l'espace vu par un œil. La plupart des humains ont un champ visuel d’environs 90°. Mais cet angle ne permet pas un rendu réaliste une fois projeté à l’écran. On préférera donc généralement un angle de 60°.


Pour placer correctement la caméra il faut : 

Sa position sur X (posCamX), sur Y (posCamY), dans le plan au sol (la map) et son angle de rotation par rapport aux axes de la map (l’endroit vers lequel elle est tournée). Ces trois attributs permettent de déterminer le champ visuel.


Nous avons également besoin de la distance entre la camera et l’écran de projection.

 

L'écran de projection :

  • Dimensions de l’écran de projection = 320 x 200 (plus c'est grand, plus le nombre de test est important et plus le logiciel aura besoin d'un ordinateur puissant pour ne pas laguer).

  • Centre de l’écran de projection = (160,100)

  • Distance entre la camera et l’écran de projection = 277

  • Angle entre deux rayons consécutifs = 60/320 degrés

Le Raycasting demande beaucoup de ressources pour fonctionner correctement. Plus le nombre de rayons est important, plus les calculs seront lourds et le programme lent. On peut réduire le nombre de rayons en utilisant deux constantes que nous avons fixés au départ :

  • Les murs ont tous la même hauteur

  • La hauteur de la caméra est égale à la moitié de celle des murs.

Au lieu de lancer un rayon pour chaque pixel nous allons lancer un rayon par colonne. Dés qu’un mur est détecté on traite la colonne à afficher à l'écran dans sa globalité et on passe ensuite à la colonne suivante. La taille de la colonne à tracer varie en fonction de la distance parcourue par le rayon.


Les rayons sont projetés à partir de la caméra, depuis sa hauteur. Ils parcourent toute la largeur de l’écran correspondant au champ visuel de la caméra. Nous allons donc lancer 320 rayons, chacun correspondant à une colonne de l'écran.


    Détection des murs :

Principe :

Détecter les murs est, pour l'instant, l'unique but du lancé de rayons. Le rayon doit nous permettre de savoir à quelle distance de la caméra se trouve l'obstacle qu'il rencontre. Or pour savoir si il touche un mur un rayon doit vérifier tous les points par lesquels il passe dans la map. Cette vérification est très gourmande en ressources mais heureusement il est facile de l'optimiser.

Le monde est fait de cubes identiques, donc un mur rempli forcément toute une case de la map.
Il suffit alors de faire la vérification uniquement lorsque qu’il atteint une intersection entre deux cases.

Nous allons essayer de trouver chaque point d’intersection (A,B,C,D,E,F) entre la map et le rayon et vérifier si il s’agit d’un mur ou pas. La meilleure solution pour optimiser les calculs semble être de vérifier les intersections verticales et horizontales séparément.

Cet algorithme mathématique est connu sous le nom de « Digital Differential Analyser»

Dès qu’on tombe sur un mur sur un axe les vérifications s’arrêtent sur cet axe.
Lorsque les deux axes ont été vérifiés on compare les longueurs des rayons pour chaque axe.
La plus courte distance est choisie pour désigner le contact avec le mur.

Détection horizontale :


Xa représente la longueur entre deux points d’intersections sur X, c’est une valeur constante. Ya est la hauteur d’une case de la grille, c’est également une valeur constante.

Voici comment fonctionne cette recherche :

Trouver le premier point d’intersection sur X (X1)

  •      Trouver le multiplicateur (Ya : + le rayon est orienté vers le bas, - il est orienté vers le haut)
  •      Trouver la distance entre deux points d’intersection sur X (X2-X1 donne Xa)
  •      Tant que le prochain point d’intersection n’est pas un mur (pas une case remplie avec un 0) on vérifie le prochain point d’intersection (X2 * Xa, Ya * Ya).
  •      si c’est le cas on arrête la vérification et on calcule la distance parcourue par le rayon

Trouver la distance :

Nous venons d’effectuer deux vérifications sur les axes X et Y. Il faut à présent vérifier la plus courte des deux distances. Dans le schéma ci-dessus D est visiblement plus proche que E. Pour déterminer la longueur du rayon nous devons calculer la distance parcourue. Pour calculer la distance il faut faire appel aux mathématiques.

Voici les formules :

Distance = racine_carrée ( difX² + difY² )

difX: différence entre l'abscisse de la caméra et l'abscisse du mur touché

difY: différence entre l'ordonnée de la caméra et l'ordonnée du mur touché

Soit la formule suivante une formule représentant un mur : ax + by = c. Alors, la distance entre la caméra (posX, posY) et le mur est égale à:

dist = (a * posX + b * posY + c) / (a * sin(angle du rayon)+ b * cos(angle du rayon) )

D'après Thalès, la hauteur du mur correspond alors à :

hauteur = (dist_ecran x hauteur_mur) / dist


     Afficher les murs :

A ce stade la projection subit une distorsion visuelle nommée « Fish Eye effect ». Cela est dû au fait que plus un objet est éloigné et plus le rayon parcours de distance. Ce comportement est tout à fait normal puisque tous les rayons partent d’un seul point. Ceux du bord sont plus longs que ceux du centre alors que le mur est partout à la même distance. La vision humaine est en mesure de corriger ce défaut à l’aide d’une lentille bombée au sein de l'œil. Mais un écran d’ordinateur est parfaitement plat, il n’est donc pas équipé pour corriger ce défaut.

Nous allons devoir simuler l’effet d’une lentille correctrice chargée modifier les bords du champ visuel. En clair, replacer tous les points à la même distance pour qu’ils semblent alignés. Pour cela il faut multiplier la distance calculée par le cosinus de l'angle entre le rayon et la droite perpendiculaire au mur touché.

A chaque fois qu’un rayon touche un mur, on calcule la distance corrigée. A l’aide de la distance on peut connaître la hauteur de la colonne à projeter.

Hauteur de la colonne projetée = (taille d’un mur / distance de la colonne) * distance de la projection

Hauteur de la colonne

Nous obtenons le produit en croix suivant :

(hauteur de la colonne projetée / distance de l’écran ) = ( taille du mur / distance de la colonne )

Le monde est fait de cubes ayant tous la même taille (64). On connaît la distance entre la caméra et l’écran de projection (277). On peut donc simplifier l’équation par :

hauteur de la colonne projetée = 64 / distance de la colonne * 277 (ou comme nous l’avons vu plus haut : hauteur = (277*64)/distance)

Prenons un exemple :

Supposons que le rayon touche un mur à la colonne 200 et à une distance de 330.

  •      La hauteur de la colonne sera de 64/330*277= 54
  •      Le milieu de la projection est défini à 100.
  •      Le milieu de cette tranche doit correspondre avec le milieu de la projection.
  •      Le haut du mur est donc à une hauteur max de 100-(54/2)=73

 

     Afficher le sol et le plafond :

Floor Casting

Pour tracer le sol nous pouvons utiliser une technique nommée le “floor casting”. Elle va nous permettre d’éviter de tracer de nouveaux rayons. 

  •      Il faut trouver une intersection avec le sol (la fin d’un mur). 
  •      Déterminer la position et l’orientation du sol au point d’intersection
  •      Calculer la distance entre la caméra et le point d’intersection.
  •      Projeter le résultat, c'est-à-dire le reste de la colonne jusqu’au bas de l’écran

Tracer le sol

Pour l'optimisation du moteur, on ne tracera le sol qu’à partir du pied des murs.

Algorithme de l'affichage :

  •      Trouve l’endroit ou le mur s’arrête
  •      Trouve l’orientation du sol
  •      Récupère la valeur du pixel touché
  •      Affiche le sur l’écran de projection

On répète l’opération tant qu’on n’a pas atteint le bas de l’écran de projection.

Tracer le plafond :

Les plafonds sont en tous points symétriques avec le sol, hormis la texture qui est souvent différente. 

Les sols et les plafonds étant parfaitement symétriques.
Il est possible de les tracer simultanément sans recalculer quoi que ce soit.
On affiche simplement le même point que le sol mais dans la partie supérieure de l'écran.

 

     Mobilité :

La camera doit pouvoir être mobile, pour cela elle peut se déplacer de plusieurs manières :

  •      Avancer
  •      Reculer
  •      Pivoter 

La position de la caméra est représentée par ses coordonnées dans la map.
Nous avons besoin de sa vitesse de déplacement et de sa vitesse de rotation.

Avancer et reculer

On fixe la vitesse de déplacement à 10 (au choix)
Si la caméra avance on va ajouter un déplacement sur X à la position actuelle de la caméra sur X.
De même pour Y.
Si la caméra recule on inverse ce processus.  

Tourner sur un axe

La rotation est aussi un processus très simple.
Il suffit d’ajouter ou de retirer une valeur à l’angle de rotation de la caméra dans la map.  

Cependant lorsque effectue une rotation avec la caméra il faut appliquer la même rotation à l’écran de projection.
Et ce afin que l’écran se trouve toujours précisément en face de la caméra (perpendiculaire).  

 

     Conclusion :

Nous avons vu ainsi les grands principes du Raycasting et les bases du fonctionnement d'un moteur 3D. Maintenant que le vrai développement peut commencer. Sachez qu’il est possible de pousser beaucoup plus loin le principe à l’aide d’algorithmes complexes. Les moteurs les plus avancés sont surprenants tant les possibilités sont nombreuses et les brides mineures.

Il n'en reste pas moins que cette technique sera toujours limitée et qu'elle ne remplacera jamais un vrai moteur 3D. Elle est en revanche facile d'accès et permettra à de nombreux débutants de lancer à cœur perdu dans l'aventure. 

Créer un site gratuit avec e-monsite - Signaler un contenu illicite sur ce site