Licence d'Informatique

340 - Informatique Graphique

Rappel

Pour dessiner un polygone rempli, on doit procéder en deux étapes : remplir la Table Globale des Arêtes (TGA) puis créer une Table des Arêtes Actives (TAA) dans laquelle les arêtes de la TGA sont transférées au fur et à mesure d'un balayage vertical. C'est ce qui est fait dans la fonction suivante :

typedef struct {
  int longueur;
  Point sommet[MAX_SOMMETS];
} Polygone;
 
void remplir_polygone(Polygone* poly, Couleur c,
                      int largeur, int hauteur)
{
  TAA* taa;
  TGA* tga;
  int x0, y0, x1, y1, y;
  int i;
  
  tga = nouvelle_TGA(largeur, hauteur);
  /* debut de remplissage de la TGA */
  x0 = poly->sommet[0].x;
  y0 = poly->sommet[0].y;
  for (i = 1; i < poly->longueur; i++) {
    x1 = poly->sommet[i].x;
    y1 = poly->sommet[i].y;
    insere_arete(tga, x0, y0, x1, y1);
    x0 = x1;
    y0 = y1;
  }
  x1 = poly->sommet[0].x;
  y1 = poly->sommet[0].y;
  insere_arete(tga, x0, y0, x1, y1);
  /* fin du remplissage de la TGA */
 
  taa = nouvelle_TAA();
  /* debut du dessin du polygone rempli */  
  for (y = 0; y != hauteur; y++) {
    transfert_aretes(tga, taa, y);
    ordonne_aretes(taa);
    while (segment_suivant(taa, &x0, &x1)) {
      dessine_segment(x0, x1, y, c);
    }
    maj_ligne_suivante(taa, y+1);
  }
  /* fin du dessin du polygone rempli */
  detruire_TAA(taa);  
  detruire_TGA(tga);
}
 

L'interface utilisé pour le remplissage de polygone est le suivant :

• nouvelle_TGA : Entier x Entier -> TGA
• insere_arete : TGA x Point x Point -> TGA
• nouvelle_TAA : -> TAA
• transfert_aretes : TGA x TAA x Entier -> TAA
• ordonne_aretes : TAA -> TAA
• segment_suivant : TAA -> Booléen x Réel x Réel x TAA
• maj_ligne_suivante : TAA -> TAA
• detruire_TAA : TAA
• detruire_TGA : TGA

TGA * nouvelle_TGA(int largeur, int hauteur)

crée une TGA pour une image dont la largeur et la hauteur sont données.

void insere_arete(int x0, int y0, int x1, int y1)

insère une nouvelle arête dans cette table.

TAA * nouvelle_TAA()

crée une TAA initialement vide.

void transfert_aretes(TGA *, TAA *, int y)

transfère toutes les arêtes naissant à une ligne donnée de la TGA.

void ordonne_aretes(TAA *)

ordonne toutes les arêtes de la TAA suivant la valeur de leur champ $x$.

bool segment_suivant(TAA *, int * x0, int * x1)

permet de parcourir toutes les arêtes de la TAA. À chaque appel, cette fonction retourne les abscisses du début et de la fin du segment horizontal à tracer sur la ligne courante. Lorsqu'il ne reste plus de segment à tracer, la fonction retourne la valeur \textit{faux}.

void maj_ligne_suivante(TAA *, int y)

met à jour la TAA pour la ligne suivante, c'est-à-dire détruit toutes les arêtes se terminant à la ligne suivante et incrémente la valeur $x$ des autres arêtes.

Clipping

On veut modifier le programme de remplissage de polygone pour qu'il clippe les arêtes.

• Que doit-on faire des arêtes dont les extrémités sont entièrement placées sous la fenêtre (valeurs de y négatives) ?
• Même question pour les arêtes dont les extrémités sont entièrement placées au-dessus de la fenêtre (valeurs de y supérieures à la hauteur) ?
• Même question pour les arêtes placées entièrement à gauche ou à droite de la fenêtre ?
• Que faire des arêtes coupant la ligne y = 0 ?
• Que faire des arêtes coupant la ligne y = hauteur ?
• Écrire les procédures insere_arete et dessine_segment en suivant vos conclusions.

Règles de remplissage

Il existe deux règles pour déterminer si un point est dans un polygone. On considère une demi-droite partant du point et allant vers l'infini dans n'importe quelle direction et on s'intéresse aux intersections de cette demi-droite et des arêtes du polygone. Dans la première règle, on se contente de compter les intersections. Si le compte est pair, le point est à l'extérieur du polygone, sinon, il est à l'intérieur (règle pair/impair). Dans la seconde règle, on oriente les arêtes du polygone et on ajoute 1 chaque fois qu'une arête coupe la demi-droite dans le sens des aiguille d'une montre et -1 dans l'autre sens. Si la somme est nulle, le point est à l'extérieur, sinon, il est à l'intérieur (règle du nombre d'enroulement non nul). La figure ci-dessous donne un exemple.

• Quelle information faut-il ajouter à la structure d'arête pour pourvoir compter le nombre d'enroulement ?
• Modifiez la procédure insere_arete pour mettre à jour cette information.
• Modifiez la procédure segment_suivant pour utiliser cette information.
• Faut-il modifier une autre partie du programme de tracé de polygone ?

Travail à réaliser

Le code source du programme sera donné au cours des TD.

Le modifier pour le clipping. Le modifier pour le remplissage. Rendre les sources et un dossier contenant les réponses aux questions posées.

Le travail doit être rendu le mercredi 10 avril au début du TD.