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

Anomaly

Ce second article présente les algorithmes utilisés pour tracer les figures géométriques simples.

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

- Auteur : Anomaly

- Parution : 30 janvier 2006

- Mise à jour : 25 mars 2015

- Licence : Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright ® 2006 Anomaly. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- 1. Introduction

- 2. Figures géométriques simples

- 2-1. Pixels "sécurisés"

- 2-2. Barres (rectangles pleins)

- 2-3. Lignes horizontales et verticales

- 2-4. Rectangles

- 3. Lignes quelconques

- 3-1. Principe

- 3-2. Implémentation

- 4. Cercles et disques

- 4-1. Principe

- 4-2. Implémentation

- 5. Conclusion

1 - Introduction

La SDL ne contient que très peu de fonctions, presque tout est à faire soi-même. Il existe bien entendu des bibliothèques diverses qui ajoutent diverses fonctions, mais elles sont rarement installées sur les systèmes Linux et la plupart sont sous licence GPL, ce qui oblige les programmes qui en dépendent d'être aussi en GPL.

Nous allons donc tout simplement écrire nos propres routines en n'utilisant seulement que la bibliothèque SDL de base. Ce n'est pas bien difficile et c'est très instructif. Si vous n'êtes pas intéressés par l'aspect théorique des algorithmes de tracés, vous pouvez sauter sans problème les parties "Principes" de cet article.

Cette partie sera très peu dépendante de la SDL ; vous pourrez réutiliser ces routines pour n'importe quel autre système graphique, pour peu que vous disposiez d'une instruction pour poser un pixel.

2 - Figures géométriques simples

2-1 - Pixels "sécurisés"

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.

2-2 - Barres (rectangles pleins)

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

Nous verrons plus loin comment tracer des lignes d'inclinaison quelconque, mais prévoir des fonctions spécifiques pour les lignes horizontales et verticales est utile, car elles seront bien plus rapides et nous permettront de remplir rapidement des surfaces.

Nous allons simplement utiliser la même fonction SDL_FillRect() avec une des deux dimensions à 1 pour obtenir la ligne concernée.

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);
}

Ces deux fonctions prennent 4 paramètres : les coordonnées, la largeur (pour la ligne horizontale) ou la hauteur (pour la ligne verticale), et le code couleur.

Le tracé de ligne horizontale sera toujours plus rapide que celui de ligne verticale (parce que les pixels se suivent en mémoire vidéo). C'est pourquoi nous utiliserons de préférence le tracé de ligne horizontale pour faire du remplissage.

2-4 - Rectangles

Rien de sorcier là-dedans, nous allons nous contenter de tracer quatre lignes avec les deux fonctions précédentes.

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);
}

Le format d'appel est le même que celui de la fonction barre() : les coordonnées, les dimensions et le code couleur.

3 - Lignes quelconques

3-1 - Principe

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.

3-2 - Implémentation

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é.

4 - Cercles et disques

4-1 - Principe

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.

4-2 - Implémentation

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.

5 - Conclusion

Cet article vous a présenté la manière de tracer les figures géométriques élémentaires à l'aide de la seule fonction de posage de points. Il est facile de réutiliser ces fonctions pour une autre bibliothèque en utilisant une autre implémentation de setPixel().

Voici un programme contenant toutes les fonctions présentées ainsi qu'une fonction générale de test qui poussent les fonctions de tracés à leurs limites (il faut enfoncer une touche pour passer des lignes aux cercles).

Partie précédente