Je t'invite à chercher une autre explication de l'algo parce que le papier que j'ai trouvé via google n'est pas clair du tout.
"on préferera des triangles pour faciliter les calculs" :
aucune raison de triangulariser les polygônes. Avec la technique du balayage, un polygone peut avoir plein d'arêtes.
En fait, on sait si un point sur la ligne de balayage est à l'intérieur du polygône quand le nombre d'arêtes intersectées par la portion gauche de la ligne de balayage est impair. C'est l'un des points clefs de cette méthode.
Donc, une fois qu'on connait les intersections entre les arêtes et la ligne de balayage, il suffit de parcourir les intersections de gauche à droite pour obtenir de façon incrémentale le plus haut polygône visible entre 2 intersections.
"Les polygônes ne doivent pas se superposer" :
au contraire, c'est quand il y beaucoup de poly les uns sur les autres qu'on voit l'avantage du balayage vis à vis de la méthode du peintre.
Quand on balaye l'écran, on gère de façon incrémental une liste des arêtes actives, c'est à dire celles qui intersectent la ligne de balayage. C'est seulement pour ces arêtes qu'on calcule les intersections avec la ligne, les autres sont ignorées (et si on sait en plus ignorer les poly qui sont à l'extérieur de l'écran, c'est encore mieux).
Le x des intersections en cours s'obtient très simplement quand on fait un calcul incrémental par rapport à la ligne de balayage précédente. Le mieux est d'appliquer l'algo de Bresenham qui ne nécessite que des additions et des comparaisons d'entiers.
"il faudra pour chaque pixel tester quels sont les polys presents.
Si trop se superposent, il faut tous les tester a chaque pixel."
alors là pas du tout. c'est toute la différence entre cette technique et l'affichage un à un des polys. Car une fois qu'on connaît 2 intersections successives sur la ligne de balayage, on sait que tous les pixels entre les 2 n'appartiennent qu'à un seule surface, celle du poly visible le plus haut (ou le fond bien-sûr).
Donc, on part de la gauche, on va d'intersection en intersection, on met à jour le compteur de parité pour le polygône de l'arête intersectée, et selon le cas, on retire ou on rajoute ce polygone à une liste des polygônes en cours de peinture. Si la liste est triée en profondeur, la surface à afficher est celle du polygône en tête de liste.
Finalement, c'est une technique *très* intéressante parce que tous les calculs peuvent être fait en incrémental... on ne fait que des petites modifs d'une ligne de balayage à l'autre grâce à ce que l'auteur du papier appelle la "cohérence" de l'image.
[^] # Re: "moteur 2D" dit le titre de l'article
Posté par Sylvain Garden . En réponse au journal moteur graphique 2D. Évalué à 1.
"on préferera des triangles pour faciliter les calculs" :
aucune raison de triangulariser les polygônes. Avec la technique du balayage, un polygone peut avoir plein d'arêtes.
En fait, on sait si un point sur la ligne de balayage est à l'intérieur du polygône quand le nombre d'arêtes intersectées par la portion gauche de la ligne de balayage est impair. C'est l'un des points clefs de cette méthode.
Donc, une fois qu'on connait les intersections entre les arêtes et la ligne de balayage, il suffit de parcourir les intersections de gauche à droite pour obtenir de façon incrémentale le plus haut polygône visible entre 2 intersections.
"Les polygônes ne doivent pas se superposer" :
au contraire, c'est quand il y beaucoup de poly les uns sur les autres qu'on voit l'avantage du balayage vis à vis de la méthode du peintre.
Quand on balaye l'écran, on gère de façon incrémental une liste des arêtes actives, c'est à dire celles qui intersectent la ligne de balayage. C'est seulement pour ces arêtes qu'on calcule les intersections avec la ligne, les autres sont ignorées (et si on sait en plus ignorer les poly qui sont à l'extérieur de l'écran, c'est encore mieux).
Le x des intersections en cours s'obtient très simplement quand on fait un calcul incrémental par rapport à la ligne de balayage précédente. Le mieux est d'appliquer l'algo de Bresenham qui ne nécessite que des additions et des comparaisons d'entiers.
"il faudra pour chaque pixel tester quels sont les polys presents.
Si trop se superposent, il faut tous les tester a chaque pixel."
alors là pas du tout. c'est toute la différence entre cette technique et l'affichage un à un des polys. Car une fois qu'on connaît 2 intersections successives sur la ligne de balayage, on sait que tous les pixels entre les 2 n'appartiennent qu'à un seule surface, celle du poly visible le plus haut (ou le fond bien-sûr).
Donc, on part de la gauche, on va d'intersection en intersection, on met à jour le compteur de parité pour le polygône de l'arête intersectée, et selon le cas, on retire ou on rajoute ce polygone à une liste des polygônes en cours de peinture. Si la liste est triée en profondeur, la surface à afficher est celle du polygône en tête de liste.
Finalement, c'est une technique *très* intéressante parce que tous les calculs peuvent être fait en incrémental... on ne fait que des petites modifs d'une ligne de balayage à l'autre grâce à ce que l'auteur du papier appelle la "cohérence" de l'image.