Programmation graphique portable en C avec la SDL - Partie 2: les figures géométriques

Dans la première partie de ce tutoriel, nous avons écrit une fonction setPixel() très rapide, mais qui ne vérifiait pas ses coordonnées. Si vous tentez d'écrire en dehors de l'écran, vous aurez au mieux un pixel mal placé, au pire un plantage du programme.

Voici une version de setPixel() qui contrôle ses arguments et qui n'affiche pas le pixel en cas de coordonnées hors limites :

void setPixelVerif(int x, int y, Uint32 coul)
{
  if (x >= 0 && x < affichage->w &&
      y >= 0 && y < affichage->h)
    setPixel(x, y, coul);
}

Vous vous demandez peut-être pourquoi je n'ai pas intégré le code de vérification directement dans setPixel() plutôt que de créer une nouvelle fonction setPixelVerif() qui appelle la première si les coordonnées sont correctes. La raison est simple : contrôler les paramètres coûte du temps de calcul. Si par exemple, on appelle 100000 fois setPixel() dans une fonction, il sera bien plus efficace de contrôler les coordonnées une fois dans la grande fonction afin de calculer les intervalles à afficher et d'appeler uniquement setPixel() pour les coordonnées valides que de faire 100000 vérifications.

La SDL nous fournit une fonction toute prête pour tracer des barres : la fonction SDL_FillRect(). Bien qu'on pourrait très bien utiliser setPixel() pour tracer la barre, cette fonction est particulièrement optimisée, et peut tirer parti de l'accélération 2D de votre matériel (sur une surface matérielle bien entendu).

Cependant, cette fonction exige une structure en paramètre, c'est pourquoi je préfère écrire une fonction pour faciliter son utilisation.

void barre(int x, int y, int w, int h, Uint32 coul)
{
  SDL_Rect r;
 
  r.x = x;
  r.y = y;
  r.w = w;
  r.h = h;
 
  SDL_FillRect(affichage, &r, coul);
}

barre() prend donc 5 paramètres : les coordonnées du point supérieur gauche, la largeur, la hauteur et le code couleur.

SDL_FillRect() vérifie les coordonnées et supporte parfaitement de dessiner une barre partiellement en dehors de l'écran ; il n'y a donc aucun souci à se faire à ce niveau.

Notez que si on passe NULL en guise de rectangle à cette fonction, SDL_FillRect() remplit l'entièreté de l'écran. Ceci nous donne alors immédiatement une fonction toute prête pour effacer l'écran.

void effacerEcran(void)
{
  SDL_FillRect(affichage, NULL, couleurs[C_NOIR]);
}

2-3. Lignes horizontales et verticales▲

void ligneHorizontale(int x, int y, int w, Uint32 coul)
{
  SDL_Rect r;
 
  r.x = x;
  r.y = y;
  r.w = w;
  r.h = 1;
 
  SDL_FillRect(affichage, &r, coul);
}
 
void ligneVerticale(int x, int y, int h, Uint32 coul)
{
  SDL_Rect r;
 
  r.x = x;
  r.y = y;
  r.w = 1;
  r.h = h;
 
  SDL_FillRect(affichage, &r, coul);
}

2-4. Rectangles▲

void rectangle(int x, int y, int w, int h, Uint32 coul)
{
  ligneHorizontale(x, y, w, coul);
  ligneHorizontale(x, y + h - 1, w, coul);
  ligneVerticale(x, y + 1, h - 2, coul);
  ligneVerticale(x + w - 1, y + 1, h - 2, coul);
}

Tracer une ligne d'inclinaison quelconque n'a en revanche rien d'évident, il va donc nous falloir nous y pencher un peu plus sérieusement. Si vous n'êtes pas intéressés par le fonctionnement général de l'algorithme, vous pouvez sans problèmes vous reporter directement à l'implémentation au point 3.2.

Prenons le cas d'une ligne dont l'angle d'inclinaison est compris entre 0 et 45°. Voici l'image zoomée d'une ligne avec une telle inclinaison :

Comme vous pouvez le constater sur l'illustration, il y a, pour une abscisse X donnée, un et un seul point correspondant. Dessiner la ligne reviendra donc à faire une boucle qui parcourt l'axe des X et qui calcule l'ordonnée Y du point.

Ce n'est pas tout. Quand on a un point de la ligne, le point suivant est toujours soit à la même ordonnée que le précédent, soit un point en dessous. Une solution simple serait donc de disposer d'un compteur flottant auquel on ajoute, à chaque nouveau point, le rapport (x2 - x1) / (y2 - y1). Tant que ce compteur est inférieur à 0.5, on ajoute les points à la même ordonnée que le point précédent. Si le compteur atteint ou dépasse ce seuil, on place le point en dessous et on retire 1 au compteur.

La limitation d'inclinaison peut facilement être levée. Pour un angle d'inclinaison de 45° à 90°, la règle "pour une abscisse X donnée, il n'y a qu'un seul point correspondant" n'est plus valable, mais elle s'applique en revanche aux ordonnées. Il suffit donc de parcourir par les ordonnées au lieu des abscisses. Pour les autres angles, il suffit d'inverser le sens de parcours et/ou décrémenter la coordonnée calculée au lieu de l'incrémenter.

L'algorithme que je vais vous présenter est cependant une variante optimisée de ce principe général : il est connu sous le nom d'algorithme de Bresenham modifié. Le grand avantage de cet algorithme est de n'utiliser que de l'arithmétique entière, et de se limiter à des additions, soustractions et à des multiplications par 2. Même si les opérations flottantes ne sont plus aussi lentes qu'elles l'étaient il y a une quinzaine d'années, les additions/soustractions entière restent toujours bien plus rapides, et les multiplications par 2 peuvent être implémentées par un simple décalage de bits. Cet algorithme est donc très performant.

void echangerEntiers(int* x, int* y)
{
  int t = *x;
  *x = *y;
  *y = t;
}
 
void ligne(int x1, int y1, int x2, int y2, Uint32 coul)
{
  int d, dx, dy, aincr, bincr, xincr, yincr, x, y;
 
  if (abs(x2 - x1) < abs(y2 - y1)) {
    /* parcours par l'axe vertical */
 
    if (y1 > y2) {
      echangerEntiers(&x1, &x2);
      echangerEntiers(&y1, &y2);
    }
 
    xincr = x2 > x1 ? 1 : -1;
    dy = y2 - y1;
    dx = abs(x2 - x1);
    d = 2 * dx - dy;
    aincr = 2 * (dx - dy);
    bincr = 2 * dx;
    x = x1;
    y = y1;
 
    setPixelVerif(x, y, coul);
 
    for (y = y1+1; y <= y2; ++y) {
      if (d >= 0) {
	x += xincr;
	d += aincr;
      } else
	d += bincr;
 
      setPixelVerif(x, y, coul);
    }
 
  } else {
    /* parcours par l'axe horizontal */
    
    if (x1 > x2) {
      echangerEntiers(&x1, &x2);
      echangerEntiers(&y1, &y2);
    }
 
    yincr = y2 > y1 ? 1 : -1;
    dx = x2 - x1;
    dy = abs(y2 - y1);
    d = 2 * dy - dx;
    aincr = 2 * (dy - dx);
    bincr = 2 * dy;
    x = x1;
    y = y1;
 
    setPixelVerif(x, y, coul);
 
    for (x = x1+1; x <= x2; ++x) {
      if (d >= 0) {
	y += yincr;
	d += aincr;
      } else
	d += bincr;
 
      setPixelVerif(x, y, coul);
    }
  }    
}

La fonction ligne() comporte 5 paramètres, les coordonnées du premier point et les coordonnées du deuxième point, ainsi que le code couleur. Les deux points sont interchangeables. Il aurait été fastidieux de tester les limites d'écran dans la fonction elle-même (calculs nécessaires), c'est pourquoi la fonction utilise setPixelVerif(). Enfin, la fonction echangerEntier(), comme son nom l'indique, échange les entiers dont les adresses sont fournies en paramètres ; cela soulage le code de la fonction de tracé.

A l'instar du tracé de ligne quelconque, tracer un cercle d'aspect parfait et sans exiger de calculs complexes se révèle particulièrement délicat. Si vous n'êtes pas intéressés par le fonctionnement général de l'algorithme, vous pouvez directement passer à l'implémentation au point 4.2.

Il existe deux méthodes principales de définir un cercle. La première est la méthode trigonométrique : chaque point du cercle peut être projeté sur l'axe des ordonnées ou des abscisses, la distance entre le centre et ces points projetés s'exprimant alors en fonction du sinus ou du cosinus de l'angle. La deuxième est la méthode polynomiale : elle tire parti du fait que si on projette le point du cercle sur l'axe des abscisses, on obtient un triangle rectangle et on peut donc exprimer les coordonnées à l'aide du théorème de Pythagore. Voici un schéma explicatif :

Cependant, vous vous doutez bien qu'utiliser des racines carrées ou des fonctions trigonométriques n'est pas particulièrement efficace. De plus, il ne s'agit pas seulement de placer des points, mais il faut qu'ils soient reliés entre eux de manière harmonique afin de dessiner un cercle qui ait un aspect régulier.

C'est là que revient notre ami Bresenham, déjà auteur de l'algorithme de tracé de ligne; qui nous présente un algorithme de tracé élégant et surtout très efficace, n'utilisant que de l'arithmétique entière.

Pour commencer, il n'est pas nécessaire de calculer les coordonnées des points du cercle en entier. Il suffit de calculer qu'un simple huitième de ce cercle, par exemple l'arc compris entre 0 et 45 °. Les autres morceaux peuvent être dessinés par symétrie. Ensuite, si on regarde de près la forme de l'arc dans ce cas, on constate une grande similitude avec le tracé de ligne.

Comme vous pouvez le constater sur l'illustration, il y a, pour une ordonnée Y donnée, un et un seul point correspondant. Dessiner la ligne reviendra donc à faire une boucle qui parcourt l'axe des Y et qui calcule l'abscisse X du point. De plus, quand on a un point du cercle, le prochain point aura soit la même abscisse, soit un point à gauche du précédent. C'est donc très proche du tracé de ligne.

void cercle(int cx, int cy, int rayon, int coul)
{
  int d, y, x;
 
  d = 3 - (2 * rayon);
  x = 0;
  y = rayon;
 
  while (y >= x) {
    setPixelVerif(cx + x, cy + y, coul);
    setPixelVerif(cx + y, cy + x, coul);
    setPixelVerif(cx - x, cy + y, coul);
    setPixelVerif(cx - y, cy + x, coul);
    setPixelVerif(cx + x, cy - y, coul);
    setPixelVerif(cx + y, cy - x, coul);
    setPixelVerif(cx - x, cy - y, coul);
    setPixelVerif(cx - y, cy - x, coul);
 
    if (d < 0)
      d = d + (4 * x) + 6;
    else {
      d = d + 4 * (x - y) + 10;
      y--;
    }
 
    x++;
  }
}

Voilà pour le cercle. Pour dessiner un disque (cercle rempli), on va simplement tracer des lignes horizontales entre chaque couple de points situés sur une même ligne. C'est pour cette raison que nous avons implémenté une version "rapide" du tracé de ligne horizontale parce que ça nous permet de remplir rapidement des formes.

void disque(int cx, int cy, int rayon, int coul)
{
  int d, y, x;
 
  d = 3 - (2 * rayon);
  x = 0;
  y = rayon;
 
  while (y >= x) {
    ligneHorizontale(cx - x, cy - y, 2 * x + 1, coul);
    ligneHorizontale(cx - x, cy + y, 2 * x + 1, coul);
    ligneHorizontale(cx - y, cy - x, 2 * y + 1, coul);
    ligneHorizontale(cx - y, cy + x, 2 * y + 1, coul);
 
    if (d < 0)
      d = d + (4 * x) + 6;
    else {
      d = d + 4 * (x - y) + 10;
      y--;
    }
 
    x++;
  }
}

Les deux fonctions prennent 4 paramètres : les coordonnées du centre, le rayon et le code couleur.