Le Projet Doom

L'algorithme de reperage des murs

Les "anciens" algos

En 3D il existe deux catégories d'algorithmes d'affichages : Les méthodes bourines (du style algorithme du peintre et Z-buffer), où l'on affiche presque tous les polygones à afficher (on se contente d'en suprimer quelques-uns à l'aide de quelques critères simples), et où on les affiches de façon à ce que seuls ceux se situant sur le devant de la scène soient visibles. Mais il y a aussi des méthodes plus fines, comme le ray-tracing et son dérivé le ray-casting (et la méthode que je vais vous expliquer et que l'on pourait appeler propagation triangulaire), où l'on passe beaucoup de temps à savoir quels seront les polygones visibles afin de n'afficher que ceux là...

Chaque méthode à ses avantages et ses inconvenients mais sur HP une méthode "bourine" n'est même pas envisageable tellement elle est gourmande en calcul (sur un ordinateur ça passe parce qu'il y a des cartes 3D qui gèrent très bien ces méthodes). Il nous faut donc employer une méthode fine.

A ce jour tous les dooms existants utilisent une méthode proche du ray-casting, qui est une adaptation du ray-tracing en 2D (c'est d'ailleurs la méthode utilisée dans le vrai Doom je crois). Cela consiste à construire un plan du niveau de jeu, et à tracer des rayons depuis le point de vision selon plusieurs angles, jusqu'à ce qu'on rencontre un mur. On sait alors quels murs sont visibles et à quelle position, il ne reste plus qu'à les afficher...

Le Ray-Casting ou lancé de rayons.

ray casting

Le problème est que le lancé de rayon est analogue à un tracé de ligne, puisque le plan est quadrillé comme un écran. Comme il faut lancer un assez grand nombre de rayons pour avoir un résultat corect, cela représente une assez grosse perte de temps. Dans la dernière version de mon doom, on lance 35 rayons et cela represente autant de temps de calcul que l'affichage en lui même... A chaque carré du cadrillage du plan, il faut faire un test et effectuer des instructions liées au tracé de ligne (Bresenheim for ever !). L'idée à l'origine de mon algo est de diminuer le nombre de tests à faire.

Mon algorithme : la propagation tiangulaire

Pour cela on n'utilise plus vraiment un plan, mais on divise le monde en triangles : chaque angle d'un mur est le sommet d'un triangle. Les cotés des triangles correspondent soit à des murs soit à des espaces vides. L'idée est que l'on part du triangle sur lequel est le joueur, et on cherche la ou les arêtes visibles. Si l'arête est un mur, on recupère ses coordonées et on l'affiche, sinon, on passe au triangle adjacent, et là encore on recherche les arêtes visibles...

Propagation Triangulaire

propagation triangulaire

Dans le cas d'un monde très complexe, on dépasse rarement la 50aine de triangles à analyser, ce qui est largement inférieur au nombre de carés traversés par le ray-casting. Le problème est que le test pour savoir si une arête est visible est beaucoup plus couteux. Il faut donc l'optimiser à fond pour que ce soit interessant. Mais on peut tout de suite repérer un avantage de la méthode : alors qu'un plan n'est qu'une approximation des coordonnées des murs liée au cadrillage, on travaille ici avec des coordonnées exactes... De même, les murs peuvent subire n'importe quelle configuration sans être déformés par une approximation liée au découpage en cadrillage.

Revenons au problème des triangles : suposons que l'on ait analysé le triangle ABC sur l'image précédente, et que l'on ai remarqué que l'arête BC est visible et ne correspond pas à un mur. On va alors chercher à savoir ce que l'on voit entre les points B et C (je rappelles qu'un point corresponds à l'angle d'un mur donc on sait que des murs ne sont pas loins de ces points). On s'interesse alors au triangle adjacent BCD. Dans le triangle BCD on connait déjà l'arête BC puisqu'on vient de la traverser, on va donc s'interesser aux arêtes BD et CD (le nom des arêtes n'a pas été choisi au hasard !). Appellons O le point de vision. Puisqu'on ne s'interesse qu'à ce qui est visible entre B et C, l'arête BD n'est visble que si le point D est à droite de la demi-droite [OB). Et de même l'arête CD n'est visible que si D est à gauche de la demi-droite [OC).

On peut remarquer au passage que cet algo permet de gérer facilement le clipping en x (c'est-à-dire qu'il permet de savoir quelles parties de murs tiennent dans l'écran horizontalement) : pour cela il suffit de rajouter deux points virtuels O1 et O2, et l'on sait alors qu'un point X est visible si et seulement si la demi-droite [OX) est à droite de [OO1) et à gauche de [OO2).

Dans l'image d'exemple, on voit donc que l'arête BC est visible, bien que B et C ne le sont pas puisqu'ils se situent respectivement à gauche de [OO1) et à droite de [OO2). On s'interesse donc au triangle BCD, et plus particulièrement aux arêtes BD et CD (on sait qu'il y en a au moins une des deux visible). Or D n'est pas visible, puisque à gauche de [OO1). La seule arête visible est donc DC. On la traverse pour s'interesser au triangle CDE. Comme E est visible les deux arêtes DE et EC sont visibles, on va donc les traiter les unes après les autres. On s'interesse donc à DE, qui ouvre sur le triangle DEF, et F est visible (on notera que pour tester la visibilité on n'utilise plus [OO2) mais [OE) ). Donc les arêtes DF et EF sont visibles. Comme elles correspondent à des murs, on les affiches. On revient à l'arête EC qu'on avait laissée de côté, et on regarde le triangle CEG, etc... Au final on trouve que EH, GH et CG sont visibles et correspondent à des murs, et on les affichera.

Calcul de la visibilité d'un point

Tout l'algo tourne donc autour de la question : "le point X est-il à gauche ou à droite de la demi-droite [OY) ?". Malheureusement cette question demande un calcul mathématique ou une approche géométrique coûteuse en temps de calcul... C'est ce qui me posait problème au départ. La solution que j'ai trouvé est basée sur les trois points suivants :

  • D'une part je ne fait qu'un calcul par point au lieu de deux (alors qu'il y a deux tests par points).

  • D'autre part le calcul que je fait est réutilisé plus tard pour l'affichage.

  • Et finalement ce calcul est très rapide puisqu'il peut se faire en une 20aine d'instructions (moins de 200cycles car ce sont des intructions rapides).

Quel est ce calcul ? Eh bien il s'agit tout simplement de calculer l'abscisse (en pixels) du point à l'écran !!! C'est en fait un calcul très lourd (il faut faire quatre multiplications et une division), et c'est pour ça que je cherchais tout d'abord une autre solution, quand j'ai compris que c'était un calcul que je devais de toute manière faire pour l'affichage... Sauf que j'affiche moins de points que je n'en calcule, mais la différence n'est pas assez importante pour rendre l'algo inintéressant. J'ai de plus optimisé ce calcul. En voici le détail :

L'abscisse du point est connu par la projection du point (coordonnées 3D) sur l'écran (coordonées 2D). On utilise le fait que les rayons lumineux se propagent en ligne droite et le thèorème de Thalès pour trouver l'équation :

Xécran = (largeur de l'écran/2) * (X/Z) + (largeur de l'écran/2)

Où X est la distance du point par rapport à l'axe de vision (positif à droite, négatif à gauche), et Z la distance du point par rapport à l'axe orthogonal à l'axe de vision (positif devant, négatif derière). La largeur de l'écran étant constante (moi j'ai pris 128 pixels, ce qui simplifie les calculs et permet d'avoir 3 pixels libres pour afficher un indicateur quelconque), la multiplication est extrèmement simple. On notera aussi que cette formule correspond à un angle de vision de 45° de part et d'autre de l'axe de vision, ce qui corresponds à peu près au champ de vision humain et simplifie les calculs ;-)

Le premier problème qu'on rencontre est pour trouver X et Z. En effet on ne connait que XP et YP, les coordonées du point dans la carte, XO et YO les coordonées du point de vision dans la carte, et A l'angle que fait l'axe de vision avec l'horizontale de la carte (axe Ouest->Est). Pour ça on utilise les formules de rotation classiques :

X = (XP - XO) cos(A) - (YP - YO) sin(A)
Z = (XP - XO) sin(A) + (YP - YO) cos(A)

(Si A est mesuré dans le sens trigonomètrique, c'est-à-dire le sens contraire des aiguilles d'une montre). Comme vous pouvez le constater c'est un gros calcul complexe, nécessitant 4 multiplications. Bien sûr les sinus et cosinus sont trouvés grâce à des tables au lieu de les calculer (ce qui est d'autant plus faisable que le nombre d'angles possibles est limité. Dans la démo j'utilsai un pas de 2,5°, mais on peu très bien imaginer d'avoir 256 angles possibles). On notera aussi que ces cosinus et sinus sont les mêmes pour tous les points de la carte, on peut donc faire les multiplications en code généré, ce qui est certes plus dur mais aussi beaucoup plus rapide ! On peut donc calculer X et Z en un temps raisonnable (environ 150 instructions me parait envisageable). Notez aussi que Z sera réutilisé pour calculer la hauteur des murs.

Reste le problème de la division. En fait on va ruser, et faire en même temps la multiplication par (largeur de l'écran/2) et calculer l'octant dans lequel se trouve le point ! Vous allez voir que si le résultat est proche de celui d'une division l'algo utilisé n'est pas le même.

Diviser pour mieux régner

Je reviens à notre problème initial : on cherchait à savoir si un point P est à gauche ou à droite d'une demie-droite [OX). Pour cela une première estimation consiste à regarder dans quel cadran est situé le point P par rapport à O, et dans quel cadran se trouve la demi-droite, c'est-à-dire dans quel cadran se trouve le point X par rapport à O. En numérotant les cadrans 0 (Nord-Est), 1 (Sud-Est), 2 (Sud-Ouest) et 3 (Nord-Ouest), je peu avoir une première idée de la position du point par rapport à la demi-droite : soit CP le numéro de cadran de P et CX celui de X, donc de la demi-droite. Si CP = CX-1 alors je sais que le point est à gauche de la droite. Si CP = CX+1 alors je sais que le point est à droite de la demi-droite.
La chose interessante c'est que dans notre algo, le point X est toujours connu parce qu'il a été utilisé dans un autre triangle, on connait donc déjà la valeur de CX ! Il n'y a donc que le calcul de CP à faire pour chaque point.

Mais que se passe-t-il dans le cas ou CP = CX ou CP = -CX (comme on est dans un ensemble à 4 valeurs possibles, CX-2 = -CX) ? On ne sait pas encore de quel coté de [OX) se trouve P ! Eh bien on n'a qu'à rafiner, et au lieu d'utiliser des cadrans, on va utiliser des octants ! On va donc avoir désormais 8 valeurs possibles : 0 (Nord-Nord-Est), 1 (Est-Nord-Est), 2 (Est-Sud-Est), etc... jusqu'à 7 (Nord-Nord-Ouest). Et on saura que P est à gauche si OX-4 < OP < OX, et à droite si OX < OP < OX+4.
Ca marche dans plus de cas, mais on a encore le problème des cas OP = OX et OP = OX-4 = -OX !
Comment faire ? Eh bien il suffit de diviser l'espace en régions encore plus petites, jusqu'à ce que ces régions soient trop petites pour discerner les points de l'écran (c'est-à-dire que 2 points appartenant à une même région sont forcement affichés dans l'écran à la même abscisse Xécran) ! On peut alors considérer que le point n'est pas visible et le foutre indiférement à droite ou à gauche selon ce qui nous arange le plus...

Très bien, mais comment faut-il diviser l'espace et combien de fois pour cela ? Jusqu'à present pour calculer OP on avait juste besoin de savoir le signe de X, le signe de Z et si |X|<|Z|, ce qui est simple à calculer. Pour séparer encore en deux, on pourrait rajouter la séparation : 2|X|<|Z|, ce qui est assez simple à calculer aussi. Et puis pour encore diviser en 2 on pourait rajouter les séparations : 4|X|<|Z| et 4|X|<3|Z|... En généralisant, si on veut découper l'espace en 8*2n régions, il suffit des deux séparations sur les signes de X et de Z et des 2n séparations du style :
2n|X|<k|Z|, pour k allant de 1 à 2n.

Intéressons-nous au premier octant (0), le numéro de la partie de l'espace dans laquelle se trouve P est donné par (k-1) ! Si le point P est dans la partie q, alors on sait que :
q.Z <= (2n).X < (q+1).Z, et donc que q <= 2n.X/Z < q+1. On a un intervalle de valeurs pour 2nX/Z !!!! Maintenant prenez n=6, on a donc 2n = 64 = (largeur de l'écran/2).
Et hop, le résultat qui tue : 64+q < Xécran < 65+q. Pour connaître Xécran, il suffit de connaître q, le numéro de la partie de l'espace contenant le point !!!! Bien sûr cette démarche peut se faire dans l'autre octant qui nous interesse : l'octant 7.

On sait donc maintenant comment diviser l'espace intelligement et combien de fois. Il ne reste plus qu'à trouver une méthode pour calculer q. Il en existe une qui donne la solution en log2(2n) = n = 6 intérations, ce qui est très peu ! La voici (sans les tests pour savoir dans quel octant se trouve P, on suppose que X>0 et:Z>0) :

q <- 0
faire 6 fois : {
X <- X + X
q <- q + q
Si X >= Z
Alors q <- q + 1; X <- X - Z
}

Et voilà ! Comme la boucle est petite, qu'on ne la fait que 6 fois et que ça doit aller très vite, on peu même se payer le luxe de dérouler la boucle, on obtient à la fin 64 labels correspondants aux 64 valeurs de q, et on a juste à faire un LC q suivant le label, même pas besoin de calculer q ! Résultat : on fait six fois "X<-X+X", six tests et au pire six fois "X<-X-Z", soit au pire 18 instructions !!! C'est pas beau la vie ?

A suivre...

Bon allez c'est tout pour aujourd'hui, n'hésitez pas à me dire s'il y a des choses que vous ne comprenez pas, si vous voulez que je vous fasse d'autres dessins, ou même pour participer ;) : écrivez-moi ! Notez qu'il reste ancore plein de trucs à expliquer, l'affichage des sprites n'étant pas le moindre !

email