Cercles

Cette fiche présente la méthode de dessin des cercles utilisée par Up ! Picture lors de l'interprétation des ordres de dessin d'Up ! Graphical Engine.

Nous rappelons que, pour Up ! Graphical Engine, le repère de coordonnées est orienté de :

Principe du dessin d'un cercle sur une image Bitmap

La méthode de calcul doit être la plus simple et la plus rapide possible. Pour cela, nous évitons au maximum les calculs en nombres réels, l'usage des fonctions trigonométriques.

Modèle de l'image

L'objectif est de tracer un cercle sur une image qui est formée de pixels aux coordonnées entières.

Une image Bitmap est organisée en lignes de pixels modélisées par un tableau d'octets. Selon la palette, un pixel nécessite d'une fraction d'octet à plusieurs octets.

De ce fait, il est plus simple et efficace de tracer :

Ainsi, nous utiliserons deux fonctions :

De plus, nous joignons les lignes élémentaires de même ordonnée pour n'en tracer qu'une seule.

Caractéristiques du cercle

Soit le cercle à tracer de centre P de coordonnées (P.x, P.y) et de rayon R.

Quitte à faire une translation de (P.x, P.y), l'équation du cercle est X^2 + Y^2 = R^2.

Cela revient donc, après translation, à tracer le cercle du point de coordonnées (0, 0) et de rayon R.

Le cercle est tracé par un algorithme similaire à celui employé pour les lignes. Selon la portion de cercle, soit :

Portion de cercle à parcours vertical

Nous supposons que nous traçons la portion de 0 vers 3*Pi/2 dans le sens rétrograde.

Les autres portions se tracent par symétrie horizontale et verticale par rapport au centre.

Initialisation du parcours

Nous commençons donc au point P1 de coordonnées (R, 0) après translation.

Itération du parcours

Pour un point (Pi.x, Pi.y) tracé, compte tenu de l'alignement sur la grille des pixels, la question est de savoir si le prochain point à tracer est soit : Pour cela, nous évaluons une erreur d'alignement donnée par la distance au cercle calculée par application de l'équation du cercle : Donc :

L'erreur moyenne est donc de Pi.x - 1/2. Le principe est alors :

L'erreur initiale est initialisée à l'opposée de l'erreur moyenne, 1/2 - P1.x approximée par 1-R. Elle est négative et elle augmente à chaque itération. Le test de dépassement devient ErreurY >= 0.

Terminaison du parcours

Comme le parcours est vertical, le tracé s'effectue tant que |dY| >= |dX| soit |dY|/|dX| >= 1.

En calculant la variation infinitésimale sur le cercle d'après son équation, nous avons : d(X^2 + Y^2) = d(R^2) soit 2*X*dX + 2*Y*dY = 0 soit dY/dX = -X/Y.

Comme dX<=0 et dY>=0, on obtient X/Y <= 1 soit Y >= X.

Le point d'arrêt est P3.

Optimisation

Une optimisation supplémentaire est possible :

Ainsi :

Portion de cercle à parcours horizontal

Nous supposons que nous traçons la portion de 3*Pi/2 vers 0 dans le sens trigonométrique.

Les autres portions se tracent par symétrie horizontale et verticale par rapport au centre.

Initialisation du parcours

Nous commençons donc au point P3 de coordonnées (0, R) après translation.

Itération du parcours

Pour un point (Pi.x, Pi.y) tracé, compte tenu de l'alignement sur la grille des pixels, la question est de savoir si le prochain point à tracer est soit : Pour cela, nous évaluons une erreur d'alignement donnée par la distance au cercle calculée par application de l'équation du cercle : Donc :

L'erreur moyenne est donc de Pi.y - 1/2. Le principe est alors :

L'erreur initiale est initialisée à l'opposée de l'erreur moyenne, 1/2 - P3.y approximée par 1-R. Elle est négative et elle augmente à chaque itération. Le test de dépassement devient ErreurY >= 0.

Terminaison du parcours

Comme le parcours est horizontal, le tracé s'effectue tant que |dX| &t;= |dY| soit |dX|/|dY| >= 1.

En calculant la variation infinitésimale sur le cercle d'après son équation, nous avons : d(X^2 + Y^2) = d(R^2) soit 2*X*dX + 2*Y*dY = 0 soit dX/dY = -Y/X.

Comme dX>=0 et dY<=0, on obtient Y/X <= 1 soit X >= Y.

Le point d'arrêt est P3.

Optimisation

Une optimisation supplémentaire est possible :

Ainsi :

Algorithme du dessin d'un cercle sur une image Bitmap

L'algorithme est écrit en Up ! 5GL pour faciliter sa lisibilité.

Procedure DessinerCercle(C : Nul Ou Point, Rayon : Entier)
/********************************************************/
Variable
/******/


/* Portion de cercle à parcours vertical. */
ErreurX=1-Rayon;
X=Rayon;
Y=0;
CorrectionErreurX=1-2*Rayon;
CorrectionErreurY=1;
TantQue X>=Y Faire Fin TantQue

/* Portion de cercle à parcours horizontal. */
ErreurY=1-Rayon;
X=0;
Y=Rayon;
CorrectionErreurX=1;
CorrectionErreurY=1-2*Rayon;
X1=0;
X2=0;
TantQue X<=Y Faire Fin TantQue
/* Vidage du résidu du cercle. */
Longueur=X2-X1+1;
DessinerLigneElementaire(C.X+X1, C.Y+Y, Longueur);
DessinerLigneElementaire(C.X+X1, C.Y-Y, Longueur);
DessinerLigneElementaire(C.X-X2, C.Y+Y, Longueur);
DessinerLigneElementaire(C.X-X2, C.Y-Y, Longueur);
Fin Procedure

Gestion de l'épaisseur d'un cercle sur une image Bitmap

L'algorithme précédent ne permet de tracer que des cercles épais d'un pixel, ce qui est rarement le cas !

Voici un exemple d'un cercle épais de quatre pixels :

L'épaisseur Epaisseur est répartie de part et d'autre du cercle sur son orthogonal. Par convention, en cas d'un nombre pair de pixels, il y a une épaisseur de pixels de plus à l'intérieur qu'à l'extérieur.

Calcul des épaisseurs

Les cercles intérieurs et extérieurs sont parcourus en parallèle et des lignes horizontales de pixels sont tracées.

Quand l'ordonnée Y est incluse dans le cercle intérieur, la limite de la ligne horizontale est donnée par le cercle intérieur. Sinon, la limite est la verticale passant par le centre du cercle à dessiner.

Second algorithme du dessin d'un cercle sur une image Bitmap

L'algorithme est écrit en Up ! 5GL pour faciliter sa lisibilité.

Procedure DessinerCercle(C : Nul Ou Point, Rayon : Entier, EpaisseurCercle : Entier=1)
/***********************************************************************************/
Variable
/******/


RayonExterieur=Rayon+EpaisseurCercle/2;
RayonInterieur=RayonExterieur-EpaisseurCercle;

/* Portion de cercle à parcours vertical. */
ErreurXExterieur=1-RayonExterieur;
ErreurXInterieur=1-RayonInterieur;
XExterieur=RayonExterieur;
XInterieur=RayonInterieur;
YExterieur=0;
YInterieur=0;
CorrectionErreurXExterieur=1-2*RayonExterieur;
CorrectionErreurXInterieur=1-2*RayonInterieur;
CorrectionErreurYExterieur=1;
CorrectionErreurYInterieur=1;
TantQue XExterieur>=YExterieur Faire Fin TantQue

/* Portion de cercle à parcours horizontal. */
ErreurYExterieur=1-RayonExterieur;
ErreurYInterieur=1-RayonInterieur;
XExterieur=0;
XInterieur=0;
YExterieur=RayonExterieur;
YInterieur=RayonInterieur;
CorrectionErreurXExterieur=1;
CorrectionErreurYInterieur=1-2*RayonInterieur;
X1=0;
X2=0;
TantQue XExterieur<=YExterieur Faire Fin TantQue
/* Vidage du résidu du cercle. */
Longueur=X2-X1+1;
DessinerLigneElementaire(C.X+X1, C.Y+YExterieur, Longueur);
DessinerLigneElementaire(C.X+X1, C.Y-YExterieur, Longueur);
DessinerLigneElementaire(C.X-X2, C.Y+YExterieur, Longueur);
DessinerLigneElementaire(C.X-X2, C.Y-YExterieur, Longueur);
Fin Procedure