> TechDemo
PrograZine issue #9 - http://www.citeweb.net/discase/9/3DFLAT.htm Edito Sommaire Contribution Contacts


Le tracage de polygones FLAT(I)
par Plouf - plouf@skynet.be 		Initié DOS QBasic
> fichiers attachés
3dflat.bas



 Le tracage de polygones ----------------------- Par Plouf (plouf@skynet.be) Première partie : le polygone FLAT
    Le polygone flat est le polygone remplit uniformément avec une seule couleur.

    Je suppose ici que vous savez afficher des pixels sur l'écran, car ce n'est pas le but de ce tutoriel. Le programme que je fournis est fait en QBasic car c'est un langage que tout le monde connait, et n'est en aucun cas optimisé d'aucune manière, c'est votre problème d'en faire quelque chose de rapide :) Meme si l'algo en lui-meme est très rapide. De toutes façons, la traduction dans d'autres langages est immédiate et ne demande pas que je m'y attarde.
>Le polygone FLAT
>1) Le triangle

    Je vais d'abord traiter le cas du triangle pour devenir plus général par après.

    Comme toujours dans l'affichange plein, il faut décomposer l'image en lignes si possible horizontales, tracer ces lignes, et c'est ce que je vous propose de faire. 
                        /|
                       / |
                      /  |
                     /   |      <--- Ceci est un triangle
                    /    |      Bon mon ASCII est pouri mais ça fera l'affaire :)
                   /     |
                  /      |
                 /       |
                /        |
                ___      |
                   ___   |
                      ___|
l

     Ce triangle va donc être dessiné comme suit :
                         1
                        ..
                       ...
                      ....      On se rend bien compte que pris du haut vers le bas,
                     .....      ce triangle se décompose en deux parties, une ou ça
                    ......      s'élargit, et une ou au contraire ca se rétrécit.
                   .......
                  ........      Tracons le triangle 13X, la question est de savoir
                 .........      pour chaque Y compris entre 1 et 3 où notre
                ..........      ligne commence, et où elle se termine, en clair on
               3.........X      doit connaitre pour chaque Y, le X des droites 13 et 1X
                   .......      mais ça c'est tres facile, un simple coeficient angulaire
                      ...2      fera l'affaire.
l

     Il faut donc dans un premier temps, aller de Y1 à Y3 en suivant 2droites, puis de Y3 à Y2 en resuivant deux autres droites (en fait, 1X et X2 sont les mêmes)

     En pratique, il faut commencer par trier les points selon leur hauteur, passer de 1 à 2 puis de 2 à 3 en ordre de hauteur, ce qui nous fait :
  • 1) Trier les 3points par hauteur décroissante
  • 2) Pour chaque Y de 1 à 2, trouver X1 et X2 et tracer une ligne horizontale
  • 3) Pour chaque Y de 2 à 3, trouver X1 et X2 et tracer une ligne horizontale
  • 4) Rajouter une cueillere à café de Nesquick
  • 5) C'est pret! Régalez-vous
>2) En général

     Car dans la vie, il n'y a pas que les triangles... Vous avez vu que pour 3points, il y a deux étapes. Bah pour N points, il y à N-1 étapes...

     Le principe est le suivant : on part du sommet du polygone et on va se balader sur les cotes, en partant d'une part vers la droite (X1), et d'autre part vers la gauche (X2), en veillant à ce que ces deux points restent toujours à meme hauteur. Il suffit dès lors de les relier pour chaque Y.

     Suivons ces points : j'apelle to1 l'indice du prochain point du polygone par lequel passera le premier point baladeur, et to2 pour le second point baladeur. Nous allons les faire descendre de dy, dy étant la différence de hauteur de la première étape, donc la difference de hauteur entre le point de départ et le premier point que l'on rencontre quand on descent :
                      départ=x1=x2
                       /\                -
                      /  \               |  dy
                     /    \              |
                    /      \to1          -
                   /       |
                  /        |      Evidemment le problème ici se situe à savoir quel
                 /         |      est l'indice de to1 et de to2, ainsi que connaitre
                /          |      dy. On voit que dy est toujours la distance entre
               /           /      un des to et le point de départ, mais lequel?
              /           /
          to2 ------------
l

     Faisons les choses dans l'ordre : si je connais l'indice du point de départ, je peux dire que to1=dep+1 et to2=dep-1 (en cyclant éventuellement, genre si on obtient -1 ca veut dire qu'il s'agit du dernier point) car les points dans les tableaux doivent former un polygone convexe, donc ils doivent se suivre dans l'ordre horlogique ou antihorlogique (que ca soit l'un ou l'autre n'a pas d'importance) to1 et to2 sont donc connus, reste dy. C'est là que le tri va intervenir.

     Il faut trier les points par rapport à leur hauteur, mais attention, si on fait ça, on risque de perde le mouvement "horlogique" des points dont on a un besoin vital! Il ne faut donc pas trier les points mais créer une liste O d'indices, l'ordre des points comme s'il apparaitraient si ils étaient triés.

     Par exemple, si Y(1)=50, Y(2)=20, Y(3)=100 on aurait O(1)=2 O(2)=1 O(3)=3

     Et le premier point, le fameux point de depart, est de coordonée X(O(1)),Y(O(1)), et dy=Y(O(2))-Y(O(1))

     Vous suivez toujours?

     Donc on à tout ce qu'il nous faut pour faire la première étape.
                       /\               
                      /..\              
                     /....\      Voilà à quoi devrait ressembler la situation après
                 x2 /......\x1   la première étape. Que voyons-nous?
                   /       |       -que x1 et x2 sont a la meme hauteur, forcément
                  /        |       -que x1 est arrivé à to1 et que to1 s'est déplacé
                 /         |       -que x2 n'est pas encore à to2 et que donc ce
                /          |        dernier ne bouge pas.
               /           /to1   
              /           /
          to2 ------------
l

     Donc après chaque étape, il faut se poser la question : qui de X1 ou de X2 est arrivé à sont point de destination? Le savoir est tres facile, il suffit de comparer la valeur Y a laquelle on est arrivé aux Y respectifs de to1 et to2. Et une fois qu'on à la réponse, on deplace celui qu'il faut, en incrémentant s'il sagit de to1 ou en décrémentant si il s'agit de to2

     A present, si c'est déjà la 7eme fois que vous le relisez, vous devriez avoir compris le principe :)
>Programme QBasic :

     Dans cet exemple, on crée d'abord une liste de point correspondant à un polygone de n cotés inscrit dans un cercle, puis on donne cette liste à manger à la routine.

     Si certaines choses ne vous paraissent pas claires (seulement certaines?), n'hésitez surtout pas à me mailer :)

     Ce programme a un défaut : si les deux derniers points (dans le sens de la hauteur) sont à meme hauteur, la toute dernière ligne ne sera pas tracée. Si quelqu'un trouve une solution élégante à ce problème, qu'il en fasse profiter tout le monde :)
SCREEN 13
n = 7
DIM x(0 TO n - 1) AS INTEGER, y(0 TO n - 1) AS INTEGER

'remplit les points pour faire un polygone inscrit dans un cercle
pi2 = ATN(1) * 8
FOR i = 0 TO n - 1
  x(i) = 70 * COS(i * pi2 / n + pi2 / 8 + 1) + 159
  y(i) = 70 * SIN(i * pi2 / n + pi2 / 8 + 1) + 99
NEXT i

'la routine commence ici
'il va nous falloir des tableaux temporaires
DIM o(0 TO n - 1) AS INTEGER, tmy(0 TO n - 1) AS INTEGER

'initialisons le tri
FOR i = 0 TO n - 1: o(i) = i: tmy(i) = y(i): NEXT i
'et trions
FOR i = 0 TO n - 2
  FOR j = i + 1 TO n - 1
    trv = i
    IF tmy(j) < tmy(i) THEN trv = j
    SWAP tmy(i), tmy(trv)
    SWAP o(i), o(trv)
  NEXT j
NEXT i

'ok, c'est partit
'voici la position initiale
y = y(o(0))
x1 = x(o(0))
x2 = x1

'les destinations respectives dans un sens et dans l'autre
to1 = o(0) + 1:  y(to1) THEN dx1 = (x(to1) - x1) / (y(to1) - y) ELSE x1 = x(to1)
  IF y <> y(to2) THEN dx2 = (x(to2) - x2) / (y(to2) - y) ELSE x2 = x(to2)
  'tracons l'etape
  FOR y = y TO y(o(pnt + 1)) - 1
    LINE (x1, y)-(x2, y)
    x1 = x1 + dx1
    x2 = x2 + dx2
  NEXT y
  'il faut a present savoir qui est arrivé
  IF y = y(to1) THEN
    'c'est le premier qui est arrivé
    to1 = to1 + 1: IF to1 = n THEN to1 = 0
  ELSE
    'c'est le second qui est arrivé
    to2 = to2 - 1: IF to2 = -1 THEN to2 = n - 1
  END IF
NEXT pnt
'on trace le petit point qui manque tout en bas
PSET (x1, y)
l
Cet article est la propriété de Plouf. La copie et la diffusion sont libres sauf dans un but lucratif sans accord explicite de l'auteur.