Ellipses

Cette fiche présente la méthode de dessin des ellipses 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'une ellipse sur une image Bitmap

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

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.

Soit l'ellipse à tracer de centre P de coordonnées (P.x, P.y) et de rayon Rx en abscisse et Ry en ordonnée.

Quitte à faire une translation de (P.x, P.y), l'équation de l'ellipse est (X/Rx)^2 + (Y/Ry)^2 = 1 soit Ry^2*X^2 + Rx^2*Y^2 = Rx^2*Ry^2.

Cela revient donc, après translation, à tracer l'ellipse du point de coordonnées (0, 0) et de rayon Rx en abscisse et Ry en ordonnée.

L'ellipse est tracée par un algorithme similaire à celui employé pour les lignes. Selon la portion d'ellipse, 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 l'ellipse à 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 (Rx, 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 à l'ellipse calculée par application de l'équation du cercle :

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

Donc :

ErreurX(Pi.x, Pi.y + 1) - (2*Pi.x - 1)*Ry^2 = 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 ((2*Pi.x - 1)*Ry^2)/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)*Ry^2 après cumul.

L'erreur initiale est initialisée à l'opposée de l'erreur moyenne, -((2*P1.x - 1)*Ry^2)/2 = -((2*Rx - 1)*Ry^2)/2 approximée par -Rx*Ry^2. 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 l'ellipse d'après son équation, nous avons : d(Ry^2*X^2 + Rx^2*Y^2) = d(Rx^2*Ry^2) soit 2*Ry^2*X*dX + 2*Rx^2*Y*dY = 0 soit dY/dX = -(Ry^2*X)/(Rx^2*Y).

Comme dX<=0 et dY>=0, on obtient (Ry^2*X)/(Rx^2*Y) <= 1 soit Rx^2*Y >= Ry^2*X.

Le point d'arrêt est P3.

Optimisation

Une optimisation supplémentaire est possible :

Au lieu de calculer CorrectionErreurX = -(2*Pi.x - 1)*Ry^2 à chaque itération :
- CorrectionErreurX est initialisé à (1 - 2*Rx)*Ry^2.
- CorrectionErreurX est augmenté de 2*Ry^2 quand X est diminué.
Au lieu de calculer CorrectionErreurY = (2*Pi.y + 1)*Rx^2 à chaque itération :
- CorrectionErreurY est initialisé à Rx^2.
- CorrectionErreurY est augmenté de 2*Rx^2 quand Y est augmenté.
Au lieu de calculer BorneX = Ry^2*X à chaque itération :
- BorneX est initialisé à Ry^2*Rx.
- BorneX est diminué de Ry^2 quand X est diminué.
Au lieu de calculer BorneY = Rx^2*Y à chaque itération :
- BorneY est initialisé à 0.
- BorneY est augmenté de Rx^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 d'ellipse à 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 P2 de coordonnées (0, Ry) 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) = Ry^2*(Pi.x + 1)^2 + Rx^2*Pi.y^2 + Rx^2*Ry^2 = (Ry^2*Pi.x^2 + Rx^2*Pi.y^2 + Rx^2*Ry^2) + (2*Pi.x + 1)*Ry^2 = ErreurY(Pi.x, Pi.y) + (2*Pi.x + 1)*Ry^2.
ErreurY(Pi.x + 1, Pi.y - 1) = Ry^2*(Pi.x + 1)^2 + Rx^2*(Pi.y - 1)^2 + Rx^2*Ry^2 = (Ry^2*Pi.x^2 + Rx^2*Pi.y^2 + Rx^2*Ry^2) + 2*(Pi.x + 1)*Ry^2 - (2*Pi.y - 1)*Rx^2 = ErreurY(Pi.x, Pi.y) + (2*Pi.x + 1)*Ry^2 - (2*Pi.y - 1)*Rx^2.

Donc :

ErreurY(Pi.x + 1, Pi.y) - (2*Pi.y - 1)*Rx^2 = 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 ((2*Pi.y - 1)*Rx^2)/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)*Rx^2 après cumul.

L'erreur initiale est initialisée à l'opposée de l'erreur moyenne, -((2*P2.y - 1)*Rx^2)/2 = -((2*Ry - 1)*Rx^2)/2 approximée par -Ry*Rx^2. Elle est négative et elle augmente à chaque itération. Le test de dépassement devient ErreurX >= 0.

Terminaison du parcours

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

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

Comme dX>=0 et dY<=0, on obtient (Rx^2*Y)/(Ry^2*X) <= 1 soit Ry^2*X >= Rx^2*Y.

Le point d'arrêt est P3.

Optimisation

Une optimisation supplémentaire est possible :

Au lieu de calculer CorrectionErreurX = (2*Pi.x + 1)*Ry^2 à chaque itération :
- CorrectionErreurX est initialisé à Ry^2.
- CorrectionErreurX est augmenté de 2*Ry^2 quand X est augmenté.
Au lieu de calculer CorrectionErreurY = -(2*Pi.y - 1)*Rx^2 à chaque itération :
- CorrectionErreurY est initialisé à (1 - 2*Ry)*Rx^2.
- CorrectionErreurY est augmenté de 2*Rx^2 quand Y est diminué.
Au lieu de calculer BorneX = Ry^2*X à chaque itération :
- BorneX est initialisé à 0.
- BorneX est augmenté de Ry^2 quand X est augmenté.
Au lieu de calculer BorneY = Rx^2*Y à chaque itération :
- BorneY est initialisé à Rx^2*Ry.
- BorneY est diminué de Rx^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'une ellipse sur une image Bitmap

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

Procedure DessinerEllipse(C : Nul Ou Point, RayonX : Entier, RayonY : Entier) /***************************************************************************/ Variable /******/


	RayonXCarre : Entier;

	RayonXCarre2 : Entier;

	RayonYCarre : Entier;

	RayonYCarre2 : Entier;

	X : Entier;

	Y : Entier;

	ErreurX : Entier;

	ErreurY : Entier;

	CorrectionErreurX : Entier;

	CorrectionErreurY : Entier;

	BorneX : Entier;

	BorneY : Entier;

	X1 : Entier;

	X2 : Entier;

	Longueur : Entier;




RayonXCarre=RayonX*RayonX;

RayonXCarre2=2*RayonXCarre;

RayonYCarre=RayonY*RayonY;

RayonYCarre2=2*RayonYCarre;



/* Portion d'ellipse à parcours vertical. */

ErreurX=-RayonX*RayonYCarre;

X=RayonX;

Y=0;

CorrectionErreurX=(1-2*RayonX)*RayonYCarre;

CorrectionErreurY=RayonXCarre;

BorneX=RayonYCarre*RayonX;

BorneY=0;

TantQue BorneX>=BorneY 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 l'ellipse. */

	ErreurX+=CorrectionErreurX;

	Si ErreurX>0 Alors
	
		X--;

		CorrectionErreurX+=RayonYCarre2;

		ErreurX-=CorrectionErreurY;

		BorneX-=RayonYCarre;
	
	Fin Si

	Y++;

	CorrectionErreurY+=RayonXCarre2;

	BorneY+=RayonXCarre;

Fin TantQue
 


/* Portion d'ellipse à parcours horizontal. */

ErreurY=-RayonY*RayonXCarre;

X=0;

Y=RayonY;

CorrectionErreurX=RayonYCarre;

CorrectionErreurY=(1-2*RayonY)*RayonXCarre;

BorneX=0;

BorneY=RayonXCarre*RayonY;

X1=0;

X2=0;

TantQue BorneX<=BorneY Faire

	/* Progression sur l'ellipse. */

	ErreurY+=CorrectionErreurY;

	Si ErreurY>0 Alors
	
		/* Changement d'ordonnée. Vidage de la portion de l'ellipse. */

		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+=RayonXCarre2;

		ErreurY-=CorrectionErreurX;

		BorneY-=RayonXCarre;
	
	Sinon
	
		X2++;
	
	Fin Si

	X++;

	CorrectionErreurX+=RayonYCarre2;

	BorneX+=RayonYCarre;


Fin TantQue
 
/* Vidage du résidu de l'ellipse. */

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'une ellipse sur une image Bitmap

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

Voici un exemple d'une ellipse épaisse 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 de l'ellipse 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 ellipses intérieures et extérieures sont parcourues en parallèle et des lignes horizontales de pixels sont tracées.

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

Algorithme du dessin d'une ellipse sur une image Bitmap

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

Procedure DessinerEllipse(C : Nul Ou Point, RayonX : Entier, RayonY : Entier, EpaisseurEllipse : Entier=1) /********************************************************************************************************/ Variable /******/


	RayonXCarreExterieur : Entier;

	RayonXCarreInterieur : Entier;

	RayonXCarre2Exterieur : Entier;

	RayonXCarre2Interieur : Entier;

	RayonYCarreExterieur : Entier;

	RayonYCarreInterieur : Entier;

	RayonYCarre2Exterieur : Entier;

	RayonYCarre2Interieur : Entier;

	XExterieur : Entier;

	XInterieur : Entier;

	YExterieur : Entier;

	YInterieur : Entier;

	ErreurXExterieur : Entier;

	ErreurXInterieur : Entier;

	ErreurYExterieur : Entier;

	ErreurYInterieur : Entier;

	CorrectionErreurXExterieur : Entier;

	CorrectionErreurXInterieur : Entier;

	CorrectionErreurYExterieur : Entier;

	CorrectionErreurYInterieur : Entier;

	BorneX : Entier;

	BorneY : Entier;

	RayonXExterieur : Entier;

	RayonXInterieur : Entier;

	RayonYExterieur : Entier;

	RayonYInterieur : Entier;

	X1 : Entier;

	X2 : Entier;

	Longueur : Entier;




RayonXExterieur=RayonX+EpaisseurEllipse/2;

RayonYExterieur=RayonY+EpaisseurEllipse/2;

RayonXInterieur=RayonXExterieur-EpaisseurEllipse;

RayonYInterieur=RayonYExterieur-EpaisseurEllipse;



RayonXCarreExterieur=RayonXExterieur*RayonXExterieur;

RayonXCarreInterieur=RayonXInterieur*RayonXInterieur;

RayonXCarreExterieur2=2*RayonXCarreExterieur;

RayonXCarreInterieur2=2*RayonXCarreInterieur;

RayonYCarreExterieur=RayonYExterieur*RayonYExterieur;

RayonYCarreInterieur=RayonYInterieur*RayonYInterieur;

RayonYCarre2Exterieur=2*RayonYCarreExterieur;

RayonYCarre2Interieur=2*RayonYCarreInterieur;



/* Portion d'ellipse à parcours vertical. */

ErreurXExterieur=-RayonXExterieur*RayonYCarreExterieur;

ErreurXInterieur=-RayonXInterieur*RayonYCarreInterieur;

XExterieur=RayonXExterieur;

XInterieur=RayonXInterieur;

YExterieur=0;

YInterieur=0;

CorrectionErreurXExterieur=(1-2*RayonXExterieur)*RayonYCarreExterieur;

CorrectionErreurXInterieur=(1-2*RayonXInterieur)*RayonYCarreInterieur;

CorrectionErreurYExterieur=RayonXCarreExterieur;

CorrectionErreurYInterieur=RayonXCarreInterieur;

BorneX=RayonYCarreExterieur*RayonXExterieur;

BorneY=0;

TantQue BorneX>=BorneY Faire

	/* Dessin des portions d'ellipse. */

	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 l'ellipse extérieure. */

	ErreurXExterieur+=CorrectionErreurXExterieur;

	Si ErreurXExterieur>0 Alors
	
		XExterieur--;

		CorrectionErreurXExterieur+=RayonYCarre2Exterieur;

		ErreurXExterieur-=CorrectionErreurYExterieur;

		BorneX-=RayonYCarreExterieur;
	
	Fin Si

	YExterieur++;

	CorrectionErreurYExterieur+=RayonXCarre2Exterieur;

	BorneY+=RayonXCarreExterieur;

	/* Progression sur l'ellipse intérieure. */

	ErreurXInterieur+=CorrectionErreurXInterieur;

	Si ErreurXInterieur>0 Alors
	
		XInterieur--;

		CorrectionErreurXInterieur+=RayonYCarre2Interieur;

		ErreurXInterieur-=CorrectionErreurYInterieur;

	
	Fin Si

	YInterieur++;

	CorrectionErreurYInterieur+=RayonXCarre2Interieur;


Fin TantQue
 


/* Portion d'ellipse à parcours horizontal. */

ErreurYExterieur=-RayonYExterieur*RayonXCarreExterieur;

ErreurYInterieur=-RayonYInterieur*RayonXCarreInterieur;

XExterieur=0;

XInterieur=0;

YExterieur=RayonYExterieur;

YInterieur=RayonYInterieur;

CorrectionErreurXExterieur=RayonYCarreExterieur;

CorrectionErreurXInterieur=RayonYCarreInterieur;

CorrectionErreurYExterieur=(1-2*RayonYExterieur)*RayonXCarreExterieur;

CorrectionErreurYInterieur=(1-2*RayonYInterieur)*RayonXCarreInterieur;

BorneX=0;

BorneY=RayonXCarreExterieur*RayonYExterieur;

X1=0;

X2=0;

TantQue BorneX<=BorneY Faire

	/* Progression sur l'ellipse extérieure. */

	ErreurYExterieur+=CorrectionErreurYExterieur;

	Si ErreurYExterieur>0 Alors
	
		/* Changement d'ordonnée. Vidage de la portion de l'ellipse. */

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

		X2=XExterieur;

		YExterieur--;

		CorrectionErreurYExterieur+=RayonXCarre2Exterieur;

		ErreurYExterieur-=CorrectionErreurXExterieur;

		BorneY-=RayonXCarreExterieur;

		Si YExterieur<=RayonYInterieur Alors
		
			/* Progression sur l'ellipse intérieure. */

			TantQue YInterieur!=YExterieur Alors
			
				ErreurYInterieur+=CorrectionErreurYInterieur;

				Si ErreurYInterieur>0 Alors
				
					YInterieur--;

					CorrectionErreurYInterieur+=RayonXCarre2Interieur;

					ErreurYInterieur-=CorrectionErreurXInterieur;

				
				Fin Si

				XInterieur++;
			
			FinTantQue

			X1=XInterieur;

		
		Sinon
		
			XInterieur=0;
		
		Fin Si
	
	Fin Si

	XExterieur++;

	X2++;

	CorrectionErreurXExterieur+=RayonYCarre2Exterieur;

	BorneX+=RayonYCarreExterieur;


Fin TantQue
 
/* Vidage du résidu de l'ellipse. */

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