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 :

La gauche vers la droite en abscisse.
Le haut vers le bas en ordonnée.

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 :

Une ligne élémentaire horizontale qu'une suite de points contigus à l'horizontal.
Des lignes élémentaires horizontales que des lignes élémentaires verticales.

Ainsi, nous utiliserons deux fonctions :

DessinerLigneElementaire.
Elle permet de tracer une ligne élementaire horizontale sur l'image par calcul des valeurs des octets selon la palette.
DessinerPointElementaire.
Elle permet de tracer un point élementaire sur l'image par calcul des valeurs des octets selon la palette.

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 :

La progression est continue en abscisse et discontinue en ordonnée comme pour les lignes à parcours horizontal.
La progression est continue en ordonnée et discontinue en abscisse comme pour les lignes à parcours vertical.

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 :

(Pi.x, Pi.y + 1) - On reste sur la même abscisse en descendant.
(Pi.x - 1, Pi.y + 1) - On se décale à gauche en descendant.

Pour cela, nous évaluons une erreur d'alignement donnée par la distance au cercle calculée par application de l'équation du cercle :

ErreurX(Pi.x, Pi.y + 1) = Pi.x^2 + (Pi.y + 1)^2 + R^2 = (Pi.x^2 + Pi.y^2 + R^2) + 2*Pi.y + 1 = ErreurX(Pi.x, Pi.y) + 2*Pi.y + 1.
ErreurX(Pi.x - 1, Pi.y + 1) = (Pi.x - 1)^2 + (Pi.y + 1)^2 + R^2 = (Pi.x^2 + Pi.y^2 + R^2) + 2*(Pi.y - Pi.x) + 2 = ErreurX(Pi.x, Pi.y) + 2*(Pi.y - Pi.x) + 2.

Donc :

ErreurX(Pi.x, Pi.y + 1) - 2*Pi.x + 1 = ErreurX(Pi.x - 1, Pi.y + 1).
ErreurX(Pi.x, Pi.y + 1) < ErreurX(Pi.x - 1, Pi.y + 1) sauf pour Pi.x==0.

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

Tant que l'erreur cumulée ne dépasse pas cette moyenne, nous choisissons le pixel (Pi.x, Pi.y + 1).
On reste sur la même abscisse en descendant et on cumule l'erreur.
Dès que l'erreur cumulée dépasse cette moyenne, nous choisissons le pixel (Pi.x - 1, Pi.y + 1).
On se décale à gauche en descendant et on recale l'erreur de 2*Pi.x - 1 après cumul.

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 :

Au lieu de calculer CorrectionErreurX = -2*Pi.x + 1 à chaque itération :
- CorrectionErreurX est initialisé à 1-2*R.
- CorrectionErreurX est augmenté de 2 quand X est diminué.
Au lieu de calculer CorrectionErreurY = 2*Pi.y + 1 à chaque itération :
- CorrectionErreurY est initialisé à 1.
- CorrectionErreurY est augmenté de 2 quand Y est augmenté.

Ainsi :

Dans la phase d'initialisation, nous avons que des additions, des soustractions ou des multiplications sur des entiers.
Dans la phase d'itération, nous avons que des additions ou des soustractions sur des entiers.

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 :

(Pi.x + 1, Pi.y) - On reste sur la même ordonnée en se décalant à gauche.
(Pi.x + 1, Pi.y - 1) - On monte en se décalant à gauche.

Pour cela, nous évaluons une erreur d'alignement donnée par la distance au cercle calculée par application de l'équation du cercle :

ErreurY(Pi.x + 1, Pi.y) = (Pi.x + 1)^2 + Pi.y^2 + R^2 = (Pi.x^2 + Pi.y^2 + R^2) + 2*Pi.x + 1 = ErreurY(Pi.x, Pi.y) + 2*Pi.x + 1.
ErreurY(Pi.x + 1, Pi.y - 1) = (Pi.x + 1)^2 + (Pi.y - 1)^2 + R^2 = (Pi.x^2 + Pi.y^2 + R^2) + 2*(Pi.x - Pi.y) + 2 = ErreurY(Pi.x, Pi.y) + 2*(Pi.x - Pi.y) + 2.

Donc :

ErreurY(Pi.x + 1, Pi.y) - 2*Pi.y + 1 = ErreurY(Pi.x + 1, Pi.y - 1).
ErreurY(Pi.x + 1, Pi.y) > ErreurY(Pi.x + 1, Pi.y - 1) sauf pour Pi.y==0.

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

Tant que l'erreur cumulée ne dépasse pas cette moyenne, nous choisissons le pixel (Pi.x + 1, Pi.y).
On reste sur la même ordonnée en se décalant à gauche et on cumule l'erreur.
Dès que l'erreur cumulée dépasse cette moyenne, nous choisissons le pixel (Pi.x + 1, Pi.y - 1).
On monte en se décalant à gauche et on recale l'erreur de 2*Pi.y + 1 après cumul.

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 :

Au lieu de calculer CorrectionErreurX = 2*Pi.x + 1 à chaque itération :
- CorrectionErreurX est initialisé à 1.
- CorrectionErreurX est augmenté de 2 quand X est augmenté.
Au lieu de calculer CorrectionErreurY = -2*Pi.y + 1 à chaque itération :
- CorrectionErreurY est initialisé à 1-2*R.
- CorrectionErreurY est augmenté de 2 quand Y est diminué.

Ainsi :

Dans la phase d'initialisation, nous avons que des additions, des soustractions ou des multiplications sur des entiers.
Dans la phase d'itération, nous avons que des additions ou des soustractions sur des entiers.

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 /******/


	X : Entier;

	Y : Entier;

	ErreurX : Entier;

	ErreurY : Entier;

	CorrectionErreurX : Entier;

	CorrectionErreurY : Entier;

	X1 : Entier;

	X2 : Entier;

	Longueur : Entier;




/* Portion de cercle à parcours vertical. */

ErreurX=1-Rayon;

X=Rayon;

Y=0;

CorrectionErreurX=1-2*Rayon;

CorrectionErreurY=1;

TantQue X>=Y Faire

	/* Dessin des points courants. */

	DessinerPointElementaire(C.X+X, C.Y+Y);

	DessinerPointElementaire(C.X+X, C.Y-Y);

	DessinerPointElementaire(C.X-X, C.Y+Y);

	DessinerPointElementaire(C.X-X, C.Y-Y);

	/* Progression sur le cercle. */

	ErreurX+=CorrectionErreurX;

	Si ErreurX>0 Alors
	
		X--;

		CorrectionErreurX+=2;

		ErreurX-=CorrectionErreurY;
	
	Fin Si

	Y++;

	CorrectionErreurY+=2;


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

	/* Progression sur le cercle. */

	ErreurY+=CorrectionErreurY;

	Si ErreurY>0 Alors
	
		/* Changement d'ordonnée. Vidage de la portion 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);

		X1=X;

		X2=X;

		Y--;

		CorrectionErreurY+=2;

		ErreurY-=CorrectionErreurX;
	
	Fin Si

	X++;

	CorrectionErreurX+=2;

	X2++;


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 :

Les lignes rouges correspondent à ce que tracerait l'algorithme précédent.
Les lignes noires correspondent à ce qu'il faut tracer après modification de cet algorithme.

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 /******/


	XExterieur : Entier;

	XInterieur : Entier;

	YExterieur : Entier;

	YInterieur : Entier;

	ErreurXExterieur : Entier;

	ErreurXInterieur : Entier;

	ErreurYExterieur : Entier;

	ErreurYInterieur : Entier;

	CorrectionErreurXExterieur : Entier;

	CorrectionErreurXInterieur : Entier;

	CorrectionErreurYExterieur : Entier;

	CorrectionErreurYInterieur : Entier;

	RayonExterieur : Entier;

	RayonInterieur : Entier;

	X1 : Entier;

	X2 : Entier;

	Longueur : Entier;




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

	/* Dessin des portions de cercle. */

	Longueur=XExterieur-XInterieur+1;

	DessinerLigneElementaire(C.X+XInterieur, C.Y+YExterieur, Longueur);

	DessinerLigneElementaire(C.X+XInterieur, C.Y-YExterieur, Longueur);

	DessinerLigneElementaire(C.X-XExterieur, C.Y+YExterieur, Longueur);

	DessinerLigneElementaire(C.X-XExterieur, C.Y-YExterieur, Longueur);

	/* Progression sur le cercle exterieur. */

	ErreurXExterieur+=CorrectionErreurXExterieur;

	Si ErreurXExterieur>0 Alors
	
		XExterieur--;

		CorrectionErreurXExterieur+=2;

		ErreurXExterieur-=CorrectionErreurYExterieur;
	
	Fin Si

	YExterieur++;

	CorrectionErreurYExterieur+=2;

	/* Progression sur le cercle interieur. */

	ErreurXInterieur+=CorrectionErreurXInterieur;

	Si ErreurXInterieur>0 Alors
	
		XInterieur--;

		CorrectionErreurXInterieur+=2;

		ErreurXInterieur-=CorrectionErreurYInterieur;
	
	Fin Si

	YInterieur++;

	CorrectionErreurYInterieur+=2;


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

	/* Progression sur le cercle exterieur. */

	ErreurYExterieur+=CorrectionErreurYExterieur;

	Si ErreurYExterieur>0 Alors
	
		/* Changement d'ordonnée. Vidage des portion du cercle. */

		Si YExterieur>RayonInterieur Alors
		
			Longueur=2*X2;

			DessinerPointElementaire(C.X-X2, C.Y+Y, Longueur);

			DessinerPointElementaire(C.X-X2, C.Y-Y, Longueur);
		
		Sinon
		
			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 Si

		X2=XExterieur;

		YExterieur--;

		CorrectionErreurYExterieur+=2;

		ErreurYExterieur-=CorrectionErreurXExterieur;

		Si YExterieur<=RayonInterieur Alors
		
			/* Progression sur le cercle interieur. */

			TantQue YInterieur!=YExterieur Alors
			
				ErreurYInterieur+=CorrectionErreurYInterieur;

				Si ErreurYInterieur>0 Alors
				
					YInterieur--;

					CorrectionErreurYInterieur+=2;

					ErreurYInterieur-=CorrectionErreurXInterieur;
				
				Fin Si

				XInterieur++;
			
			FinTantQue

			X1=XInterieur;

		
		Fin Si
	
	Fin Si

	XExterieur++;

	X2++;

	CorrectionErreurXExterieur+=2;


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