TD2 Remplissage

Tracer un disque

On supposera disposer d'une fonction SegHori(x1, x2, y) trançant un segment horizontal. Ecrire un algorithmes qui n'utilise que des opérations sur les entiers pour tracer un disque (constitué de pixels à l'intérieur d'un cercle).

Stratégie : rajouter des appels à SegHori dans l'algo de tracer de cercle de Bresenham.

 disque (rayon R, couleur C)
  x=0; y=R; d=3-2*R;  // initialisation
  tant que (x =< y) faire
    SegHori(-x,  x,  y, C);  // octants II et III
    SegHori(-x,  x, -y, C);  // octants VI et VII
    SegHori(-y, -x,  x, C);  // octant IV
    SegHori( x,  y,  x, C);   // octant I
    SegHori(-y, -x, -x, C);  // octant V
    SegHori( x,  y, -x, C);  // octant VIII
    si ( d>0 ) {d=d+4*x+6;}
    sinon {d=d + 4*(x-y) + 10; y=y-1; }
    x=x+1;

Remplir un Polygône par Balayage

Soit un polygône quelconque, qui peut n'être ni régulier, ni convexe, ni simple.

Structures de données

Pour le sommet, l'arête et le polygone : comment organiser le stockage des données?

  • sommet : un point? ou un point et la liste des arêtes incidents? juste un point
  • arêtes : deux extrémités donc deux points? oui, c'est ça
  • polygone : liste chainée des arêtes? oui, plus le nombre d'arêtes.

Le corrigé propose

typedef struct point_t {
  int x,y; } point_t;
 
typedef struct arete_t {
  point_t p1, p2; } arete_t;

typedef struct polygone_t {
  int nb_aretes;
  arete_t *arete; } polygone_t;

Les Coupes

La demi-droite horizontale y=Y0 coupe le polygone en n points x_j. Comment stocker ces intersections? Comment s'en servir pour colorier les points de la droite horizontale qui appartiennent à l'intérieur du polygone?

En fait, ce sera la liste des pixels (point_t) appartenant aux arêtes, triés (ordre croissant) par y et puis par x. Pour un y donné, la liste fournira les points d'instersection successifs.

corrigé

Le corrigé propose une liste chainée mais des seuls xj. Voyons où ça nous menera.

typedef struct Xintersection_t {
  int xj;
  struct Xintersection_t *next; } Xintersection_x_t;

Ensuite, on va supposer qu'il n'y a pas d'intersections avec des sommets : comment serait-ce possible? Mais on traitera cette question plus tard.

  1. Trier les intersections par ordre croissant
  2. InterA = tête de liste;
  3. InterB = InterA→next;
  4. Répéter jusqu' la fin de la liste (==InterB)
    1. SegHori(InterA, InterB, y);
    2. InterA=InterB→next;
    3. InterB=InterA→next;

Calcul des autres points d'intersection

Plusieurs méthodes sont proposées dans le corrigé, dont deux avec des calculs flottants. Passons tout de suite à l'algorithme entier. Le but est de calculer les xj pour y+1; on se limite à l'ensemble des arêtes actives…on verra plus tard comment gérer les entrées en, et sorties d'activité.

typedef struct arete_active_t {
  int xj;
  int DyFoisDistCD;
  int DX, Dy;
  struct arete_active_t *next; } arete_active_t;

Le principe est d'utiliser la connaissance de la pente de l'arête pour calculer l'incrément en x lorsque y augment par 1.

  1. y = quelque chose
  2. Tant que y n'a pas été augmenté
    1. trier les arêtes actives par xj croissant
    2. AA = PremièreAreteActive
    3. BB = AA.next
    4. Repeter jusqu'à epuisement des arêtes actives :
      1. SegHori (AA.xj, BB.xj, y);
      2. AA = BB.next
      3. BB = AA.next
    5. pour toutes les aretes actives (AA) :
      1. AA.DyFoisDistCD = AA.DyFoisDistCD + AA.Dx
      2. Tant que AA.DyFoisDistCD >= AA.Dy / 2
        1. AA.xj = AA.xj + 1
        2. AA.DyFoisDistCD = AA.DyFoisDistCD - AA.Dy
      3. Tant que AA.DyFoisDistCD < - AA.Dy / 2
        1. AA.xj = AA.xj - 1
        2. AA.DyFoisDistCD = AA.DyFoisDistCD + AA.Dy
      4. AA = AA.next
    6. y = y+1 (fin de boucle, goto 2)

Remplissage du tout

On rajoute deux types de structures pour gérer les ensembles d'arêtes actives et inactives

typedef struct arete_t {
  point_t inf, sup;
  struct arete_t *next; } arete_t;
typedef struct arete_active_t {
  int xj;
  int ymax;
  int DyFoisDistCD;
  int DX, Dy;
  struct arete_active_t *next; } arete_active_t;
  1. ET = liste triée des arêtes (d type arete_t) nnon-horizontales de P dans l'ordre croissant de inf.y.
  2. AET = liste vide (initialement) d'arêtes actives.
  3. y = PremiereArete(ET).inf.y : la plus faible valeur de y qui peut avoir une intersection avec un arete (un sommet en l'occurrence, non?).
  4. Tant qu'on n'a pas fini
    1. FIXME à completer plus tard.

Navigation

 
m1ilc/fain_td2.txt · Dernière modification: 2010/01/10 12:30 par suitable
 
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante :CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki