Bezier

Cette fiche présente la méthode de dessin des courbe de Bézier utilisées 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 courbe de Bézier sur une image Bitmap

L'objectif est de tracer une courbe de Bézier 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, les multiplications et les divisions.

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.

Caractéristiques de la courbe de Bézier

Soit la courbe de Bézier à tracer définies par un tableau de points P de coordonnées (P[i].x, P[i].y) pour i variant de 0 à P.NbElements - 1.

Par définition, les points P[0] et P[P.NbElements - 1] sont sur la courbe alors que les autres sont en dehors.

Nous supposons que la courbe comporte au moins trois points :

Une courbe à un point est ce point.
Une courbe à deux points est une droite.

L'équation caractéristique de la courbe de Bézier est :

Pour le réel t variable dans l'intervalle [0.0, 1.0].

Echantillonner cette équation pour différentes valeurs de t est trop gourmand en temps de calcul. Et cela est imprécis.

Nous utilisons une des propriétés des courbes de Bézier qui transforme une courbe P de N points en une courbe Q de N+1 points :

Q[0].X=P[0].X et Q[0].Y=P[0].Y.
Q[i].X=(P[i-1].X + P[i].X)/2 et Q[i].Y=(P[i-1].Y + P[i-1].Y)/2 pour i variant de 1 à NbPoints-1.
Q[NbPoints].X=P[NbPoints-1].X et Q[NbPoints].Y=P[NbPoints-1].Y.

Les points de Q obtenus sont plus proches de la courbe que ceux de P. Il y a donc convergence.

Nous appliquons ce principe de division tant que deux points successifs diffèrent de plus de Precision pixels en abscisse ou en ordonnée.

Algorithme du dessin d'une courbe de Bézier sur une image Bitmap

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

Procedure DessinerBezier(P : Nul Ou TableauDe Nul Ou Point, Precision : Entier) /*****************************************************************************/ Variable /******/


	QPrecedent : Nul Ou TableauDe Nul Ou Point;

	Q : Nul Ou TableauDe Nul Ou Point;

	NbPoints : Entier;

	I : Entier;

	PrecisionAtteinte : Booleen;

	X : Entier;

	Y : Entier;

	XPrecedent : Entier;

	YPrecedent : Entier;




NbPoints=P.NbElements;

Si NbPoints==1 Alors

/* Cas trivial d'un point. */


	DessinerPoint(P[0]);

	Retourner;

Fin Si

Si NbPoints==2 Alors

/* Cas trivial de deux points. */


	DessinerLigne(P[0], P[1]);

	Retourner;

Fin Si



/* Ajout d'un point tant que la precision n'est pas atteinte. */

PrecisionAtteinte=Faux;

QPrecedent=P;

TantQue Vrai Faire

	PrecisionAtteinte=Vrai;

	Q=Tableau(Point, NbPoints+1, Nul);

	/* Premier point. */

	Q[0]=QPrecedent[0];

	/* Points du milieu. */

	Pour I=1 JusquA NbPoints-1 Pas 1 Faire
	
		X=(QPrecedent[I-1].X + QPrecedent[I].X)/2;

		Y=(QPrecedent[I-1].Y + QPrecedent[I].Y)/2;

		Q[I]=Point(X, Y);

		Si X<0 Alors
		
			X=-X;
		
		Fin Si

		Si Y<0 Alors
		
			Y=-Y;
		
		Fin Si

		Si (X>=Precision) Ou (Y>=Precision) Alors
		
			PrecisionAtteinte=Faux;
		
		Fin Si
	
	Fin Pour

	/* Dernier point. */

	Q[NbPoints]=QPrecedent[NbPoints-1];

	

	Si PrecisionAtteinte Alors
	
		Arreter;
	
	Fin Si

	

	/* Passage au suivant. */

	QPrecedent=Nul;

	QPrecedent=Q;

	NbPoints++;

Fin TantQue


	
/* Trace de la courbe. */

Q=QPrecedent;

XPrecedent=Q[0].X;

YPrecedent=Q[0].Y;

Pour I=1 JusquA NbPoints-1 Pas 1 Faire

	X=Q[I].X;

	Y=Q[I].Y;

	DessinerLigne(Point(XPrecedent, YPrecedent), Point(X-XPrecedent, Y-YPrecedent));

	

	/* Passage au suivant. */

	XPrecedent=X;

	YPrecedent=Y;

Fin Pour

Fin Procedure

Gestion de l'épaisseur d'une courbe de Bézier sur une image Bitmap

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

Il est toutefois très aisémement modifiable puisque nous traçons la courbe par portion de lignes.

Second algorithme du dessin d'une courbe de Bézier sur une image Bitmap

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

Procedure DessinerBezier(P : Nul Ou TableauDe Nul Ou Point, Precision : Entier, EpaisseurCourbe : Entier=1) /*********************************************************************************************************/ Variable /******/


	QPrecedent : Nul Ou TableauDe Nul Ou Point;

	Q : Nul Ou TableauDe Nul Ou Point;

	NbPoints : Entier;

	I : Entier;

	PrecisionAtteinte : Booleen;

	X : Entier;

	Y : Entier;

	XPrecedent : Entier;

	YPrecedent : Entier;




NbPoints=P.NbElements;

Si NbPoints==1 Alors

/* Cas trivial d'un point. */


	DessinerPoint(P[0]);

	Retourner;

Fin Si

Si NbPoints==2 Alors

/* Cas trivial de deux points. */


	DessinerLigne(P[0], P[1], EpaisseurCourbe);

	Retourner;

Fin Si



/* Ajout d'un point tant que la precision n'est pas atteinte. */

PrecisionAtteinte=Faux;

QPrecedent=P;

TantQue Vrai Faire

	PrecisionAtteinte=Vrai;

	Q=Tableau(Point, NbPoints+1, Nul);

	/* Premier point. */

	Q[0]=QPrecedent[0];

	/* Points du milieu. */

	Pour I=1 JusquA NbPoints-1 Pas 1 Faire
	
		X=(QPrecedent[I-1].X + QPrecedent[I].X)/2;

		Y=(QPrecedent[I-1].Y + QPrecedent[I].Y)/2;

		Q[I]=Point(X, Y);

		Si X<0 Alors
		
			X=-X;
		
		Fin Si

		Si Y<0 Alors
		
			Y=-Y;
		
		Fin Si

		Si (X>=Precision) Ou (Y>=Precision) Alors
		
			PrecisionAtteinte=Faux;
		
		Fin Si
	
	Fin Pour

	/* Dernier point. */

	Q[NbPoints]=QPrecedent[NbPoints-1];

	

	Si PrecisionAtteinte Alors
	
		Arreter;
	
	Fin Si

	

	/* Passage au suivant. */

	QPrecedent=Nul;

	QPrecedent=Q;

	NbPoints++;

Fin TantQue


	
/* Trace de la courbe. */

Q=QPrecedent;

XPrecedent=Q[0].X;

YPrecedent=Q[0].Y;

Pour I=1 JusquA NbPoints-1 Pas 1 Faire

	X=Q[I].X;

	Y=Q[I].Y;

	DessinerLigne(Point(XPrecedent, YPrecedent), Point(X-XPrecedent, Y-YPrecedent), EpaisseurCourbe);

	

	/* Passage au suivant. */

	XPrecedent=X;

	YPrecedent=Y;

Fin Pour

Fin Procedure