Le code dans cet article a été écrit avec Code::Blocks et la SDL 2.
Vous pouvez trouver
ici un guide pour installer ces logiciels.
Bien qu'il soit basé sur la SDL, je n'utilise pas ses fonctions directement. J'ai écrit une petite bibliothèque
avec quelques fonctions basiques pour faciliter la compréhension et la portabilité dans un autre langage.
Vous pouvez en apprendre plus sur cette bibliothèque
ici.
Le code dans cet article utilise l'algorithme de lignes de Bresenham que j'ai présenté
ici.
Dans l'article précédent on a parlé de l'algorithme de cercle de Bresenham.
Dans cet algorithme, on utilisait une boucle où on incrémentait x, et à l'intérieur de cette boucle, on traçait 8
points symétriquement.
Pour remplir ce cercle, on va tracer une ligne entre chaque couple de points qui sont symétriques par rapport à
l'axe des y.
Elles vont remplir les zones qui sont montrées sur cette image:
On va utiliser la fonction line pour dessiner ça:
void circle(int centerX, int centerY, int radius, Color c)
{
int x = 0;
int y = radius;
int m = 5 - 4 * radius;
while (x <= y)
{
gfx.line(centerX - x, centerY - y, centerX + x, centerY - y, c);
gfx.line(centerX - y, centerY - x, centerX + y, centerY - x, c);
gfx.line(centerX - y, centerY + x, centerX + y, centerY + x, c);
gfx.line(centerX - x, centerY + y, centerX + x, centerY + y, c);
if (m > 0)
{
y--;
m -= 8 * y;
}
x++;
m += 8 * x + 4;
}
}
Et comme dans l'article précédent, on va chronométrer le dessin de 10000 cercles:
// time 10000 circles
sys.StartPerfCounter();
for (int i = 0; i < 10000; i++)
circle(SCREEN_WIDTH / 2, SCREEN_HEIGHT / 2, 150, Color(255, 255, 255));
printf("%f\n", sys.StopPerfCounter());
Télécharger le code source
Télécharger l'exécutable pour Windows
Ce code prend environ 480 ms sur mon ordinateur.
A chaque étape de la boucle, x est incrémenté.
Si vous regardez la zone bleue et la zone verte du cercle, elles correspondent aux fonctions line qui utilisent x
pour la coordonnée y.
Donc une ligne est dessinée à chaque itération.
Mais pour les zones en haut et en bas, on utilise x pour la coordonnée x et y pour la coordonnée y.
Mais y n'est pas décrémenté à chaque itération. Donc on dessine plusieurs lignes à la même coordonnée y.
Pour améliorer ça, on va déplacer 2 des fonctions line dans le test où on décrémente y:
while (x <= y)
{
gfx.line(centerX - y, centerY - x, centerX + y, centerY - x, c);
gfx.line(centerX - y, centerY + x, centerX + y, centerY + x, c);
if (m > 0)
{
gfx.line(centerX - x, centerY - y, centerX + x, centerY - y, c);
gfx.line(centerX - x, centerY + y, centerX + x, centerY + y, c);
y--;
m -= 8 * y;
}
x++;
m += 8 * x + 4;
}
Télécharger le code source
Télécharger l'exécutable pour Windows
Ce code prend environ 435 ms.
La fonction line utilise l'algorithme de Bresenham qui est prévu pour tracer des lignes dans toutes les directions.
Il n'est pas particulièrement optimisé pour les lignes horizontales.
On ferait mieux d'utiliser la fonction rectFill qui a un code plus compact.
On va simplement dessiner des rectangles de 1 pixel de haut.
while (x <= y)
{
gfx.rectFill(centerX - y, centerY - x, centerX + y + 1, centerY - x + 1, c);
gfx.rectFill(centerX - y, centerY + x, centerX + y + 1, centerY + x + 1, c);
if (m > 0)
{
gfx.rectFill(centerX - x, centerY - y, centerX + x + 1, centerY - y + 1, c);
gfx.rectFill(centerX - x, centerY + y, centerX + x + 1, centerY + y + 1, c);
y--;
m -= 8 * y;
}
Télécharger le code source
Télécharger l'exécutable pour Windows
Ce code est un peu plus rapide. Il prend environ 410 ms.
Utiliser des boucles simples
La fonction rectFill utilise 2 boucles imbriquées.
Même si la boucle y n'est exécutée qu'une seule fois, ça rajoute quelques instruction inutiles.
Alors pourquoi on n'écrirait pas de simple boucles à la place ?
while (x <= y)
{
for (int xx = centerX - y; xx <= centerX + y; xx++)
gfx.setPixel(xx, centerY - x, c);
for (int xx = centerX - y; xx <= centerX + y; xx++)
gfx.setPixel(xx, centerY + x, c);
if (m > 0)
{
for (int xx = centerX - x; xx <= centerX + x; xx++)
gfx.setPixel(xx, centerY - y, c);
for (int xx = centerX - x; xx <= centerX + x; xx++)
gfx.setPixel(xx, centerY + y, c);
y--;
m -= 8 * y;
}
Télécharger le code source
Télécharger l'exécutable pour Windows
Encore une fois, c'est un peu plus rapide. Cette version tourne en à peu près 400 ms.
Dans le programme précédent on utilise 2 boucles for successives avec les mêmes paramètres.
Essayons de les fusionner:
while (x <= y)
{
for (int xx = centerX - y; xx <= centerX + y; xx++)
{
gfx.setPixel(xx, centerY - x, c);
gfx.setPixel(xx, centerY + x, c);
}
if (m > 0)
{
for (int xx = centerX - x; xx <= centerX + x; xx++)
{
gfx.setPixel(xx, centerY - y, c);
gfx.setPixel(xx, centerY + y, c);
}
y--;
m -= 8 * y;
}
Télécharger le code source
Télécharger l'exécutable pour Windows
Cette version prend entre 360 et 370 ms.
La fonction pixelPos2D utilise une multiplication, mais comme on dessine des lignes horizontale, les pixels sont à
des positions successives dans le tableau de l'écran.
Alors on a seulement besoin d'un incrément au lieu d'une coûteuse multiplication pour chaque pixel.
On va utiliser une nouvelle fonction setPixel qui prend l'index du pixel au lieu de ses coordonnées:
inline void setPixel(int pos, Color c)
{
mPixels2D[pos] = c;
}
Et notre boucle de dessin va maintenant devenir:
while (x <= y)
{
int pos1 = gfx.pixelPos2D(centerX - y, centerY - x);
int pos2 = gfx.pixelPos2D(centerX - y, centerY + x);
for (int xx = centerX - y; xx <= centerX + y; xx++)
{
gfx.setPixel(pos1++, c);
gfx.setPixel(pos2++, c);
}
if (m > 0)
{
int pos1 = gfx.pixelPos2D(centerX - x, centerY - y);
int pos2 = gfx.pixelPos2D(centerX - x, centerY + y);
for (int xx = centerX - x; xx <= centerX + x; xx++)
{
gfx.setPixel(pos1++, c);
gfx.setPixel(pos2++, c);
}
y--;
m -= 8 * y;
}
Télécharger le code source
Télécharger l'exécutable pour Windows
Cette version est juste un peu plus rapide, elle prend entre 350 et 360 ms.
On arrive à un niveau où il est important des prendre en compte la façon dont les caches de données du CPU
fonctionnent.
Maintenant, dessiner 2 pixel différents dans la même boucle est moins efficace, car ils ne sont pas dans la même
ligne de cache.
Alors on va séparer les boucles qu'on avait fusionnées auparavant...
while (x <= y)
{
int pos = gfx.pixelPos2D(centerX - y, centerY - x);
for (int xx = centerX - y; xx <= centerX + y; xx++)
gfx.setPixel(pos++, c);
pos = gfx.pixelPos2D(centerX - y, centerY + x);
for (int xx = centerX - y; xx <= centerX + y; xx++)
gfx.setPixel(pos++, c);
if (m > 0)
{
pos = gfx.pixelPos2D(centerX - x, centerY - y);
for (int xx = centerX - x; xx <= centerX + x; xx++)
gfx.setPixel(pos++, c);
pos = gfx.pixelPos2D(centerX - x, centerY + y);
for (int xx = centerX - x; xx <= centerX + x; xx++)
gfx.setPixel(pos++, c);
y--;
m -= 8 * y;
}
Télécharger le code source
Télécharger l'exécutable pour Windows
Ce code prend autour de 285 ms.
On peut encore optimiser un peu en évitant l'indirection où on utilise un index dans le tableau de pixels.
Maintenant on va utiliser des pointeurs sur ces pixels.
Dans le code suivant, j'ai mis mPixels2D en public dans Graphics.h et notre boucle de dessin ressemble à ça:
while (x <= y)
{
Color* ptr = &gfx.mPixels2D[gfx.pixelPos2D(centerX - y, centerY - x)];
for (int xx = centerX - y; xx <= centerX + y; xx++)
*ptr++ = c;
ptr = &gfx.mPixels2D[gfx.pixelPos2D(centerX - y, centerY + x)];
for (int xx = centerX - y; xx <= centerX + y; xx++)
*ptr++ = c;
if (m > 0)
{
ptr = &gfx.mPixels2D[gfx.pixelPos2D(centerX - x, centerY - y)];
for (int xx = centerX - x; xx <= centerX + x; xx++)
*ptr++ = c;
ptr = &gfx.mPixels2D[gfx.pixelPos2D(centerX - x, centerY + y)];
for (int xx = centerX - x; xx <= centerX + x; xx++)
*ptr++ = c;
y--;
m -= 8 * y;
}
Télécharger le code source
Télécharger l'exécutable pour Windows
Cette dernière version prend environ 240 ms, c'est 2 fois plus rapide que la première.
Comme ça ne me plait pas trop de laisser mPixels2D en public, je vais inclure cette fonction dans Graphics.cpp pour
les futures versions de ma lib.
