Lignes

Cette fiche présente la méthode de dessin des lignes 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'une ligne 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, les multiplications et les divisions.

Modèle de l'image

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

Une image est 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 de la ligne

Soit la ligne à tracer du point P1 de coordonnées (P1.x, P1.y) au point P2 de coordonnées (P2.x, P2.y). Nous supposons que :

Quitte à faire une translation de (P1.x, P1.y), l'équation de la droite est a*X + b*Y = 0.

Cela revient donc, après translation, à tracer la ligne du point de coordonnées (0, 0) au point de coordonnées (P2.x - P1.x, P2.y - P1.y). Nous prenons :

Nous constatons que :

Ligne à parcours horizontal

Une ligne est dite à parcours horizontal si sa pente est inférieure ou égale à un. Elle s'étend donc plus en largeur qu'en hauteur i.e. DeltaX>DeltaY.

Pour la dessiner, les pixels sont parcourus de l'abscisse P1.x à P2.x. L'ordonnée du premier pixel commence à P1.y.

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 à la ligne calculée par application de l'équation de la droite :

Donc :

L'erreur moyenne est donc de -b/2 en valeur absolue. Le principe est alors :

L'erreur initiale est initialisée à l'opposée de l'erreur moyenne, b/2. Elle est négative et elle augmente à chaque itération. Le test de dépassement devient Erreur >= 0.

Ligne à parcours vertical

Une ligne est dite à parcours vertical si sa pente est supérieure ou égale à un. Elle s'étend donc plus en hauteur qu'en largeur i.e. DeltaX<DeltaY.

Pour la dessiner, les pixels sont parcourus de l'ordonnée P1.y à P2.y. L'abscisse du premier pixel commence à P1.x.

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 à la ligne calculée par application de l'équation de la droite :

Donc :

L'erreur moyenne est donc de a/2 en valeur absolue. Le principe est alors :

L'erreur initiale est initialisée à l'opposée de l'erreur moyenne -a/2. Elle est négative et elle augmente à chaque itération. Le test de dépassement devient Erreur >= 0.

Algorithme du dessin d'une ligne sur une image Bitmap

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

Procedure DessinerLigne(P1 : Nul Ou Point, P2 : Nul Ou Point)
/***********************************************************/
Variable
/******/


/* Calcul de DeltaY i.e. a. */
DeltaY=P2.Y-P1.Y;
Si DeltaY>0 Alors Sinon Fin Si

/* Calcul de DeltaX i.e. b. */
DeltaX=P2.X-P1.X;
Si DeltaX>0 Alors Sinon Fin Si

Si DeltaY==0 Alors
/* Cas trivial de la ligne horizontale. */
Fin Si

Si Delta==0 Alors
/* Cas trivial de la ligne verticale. */
Fin Si

Si DeltaX>DeltaY Alors
/* Ligne a parcours horizontal. */
Sinon
/* Ligne a parcours vertical. */
Fin Si
Fin Procedure

Gestion de l'épaisseur d'une ligne sur une image Bitmap

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

Voici un exemple de quatre lignes épaissent de quatre pixels :

L'épaisseur Epaisseur est répartie de part et d'autre de la ligne sur son orthogonale. Par convention, en cas d'un nombre pair de pixels, il y a une épaisseur de pixels de plus au dessous ou à gauche qu'au dessus ou à droite.

Nous supposons toujours que :

Calcul des épaisseurs

La ligne est dessinée par épaisseur de lignes élémentaires de pixels. Chaque épaisseur est définie par deux abscisse X1 et X2 pour une ordonnée Y.

Chaque point à dessiner de l'algorithme DessinerLigne devient un ensemble d'épaisseurs à dessiner. Ces dernières se décalent de façon orthogonale au mouvement du curseur au point (X, Y) de la ligne. Ainsi, il y a un changement d'épaisseur quand il y a une variation de X.

Dans un premier temps, les épaisseurs de référence EpaisseursReference sont calculées à partir du principe de l'algorithme DessinerLigne à partir du point fictif (0, 0).

Le nombre d'épaisseurs est calculé avec la relation de Pythagore, à savoir X^2 + Y^2 = EpaisseurLigne^2.

En pratique, du fait des nombres entiers, nous minimisons |X^2 + Y^2 - EpaisseurLigne^2|. Le test d'arrêt est l'atteinte de ce minimum.

Ainsi, EpaisseursReference et EpaisseursADessiner sont des tableaux de taille au plus Epaisseur éléments.

Le tableau EpaisseursADessiner est exploité par rotation de l'index Index. Une place est libérée en traçant la plus veille épaisseur avant de mémoriser la plus récente.

Second algorithme du dessin d'une ligne sur une image Bitmap

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

Type Epaisseur Defaut
/*******************/

Fin Type

Procedure DessinerLigne(P1 : Nul Ou Point, P2 : Nul Ou Point, EpaisseurLigne : Entier=1)
/**************************************************************************************/
Variable
/******/
/* Calcul de DeltaY i.e. de a. */
DeltaY=P2.Y-P1.Y;
Si DeltaY>0 Alors Sinon Fin Si

/* Calcul de DeltaX i.e. de b. */
DeltaX=P2.X-P1.X;
Si DeltaX>0 Alors Sinon Fin Si

Si DeltaY==0 Alors
/* Cas trivial de la ligne horizontale. */
Fin Si

Si Delta==0 Alors
/* Cas trivial de la ligne verticale. */
Fin Si

EpaisseursReference=Tableau(Epaisseur, EpaisseurLigne, Epaisseur());
EpaisseursADessiner=Tableau(Epaisseur, EpaisseurLigne, Epaisseur());
EpaisseurCarre=EpaisseurLigne*EpaisseurLigne;
/* Calcul des references des epaisseurs. */
X=0;
Y=0;
DistancePrecedente=EpaisseurCarre;
Si DeltaX>DeltaY Alors
/* Ligne a parcours horizontal. */
Sinon
/* Ligne a parcours vertical. */
Fin Si

/* Repartition des epaisseurs de part et d'autre de la ligne. */
Si NbReferences%2 Alors Sinon Fin Si
DecalageX=(EpaisseursReference[Index].X1+EpaisseursReference[Index].X2)/2;
DecalageY=EpaisseursReference[Index].Y/2;
Pour Index=0 JusquA NbReferences Pas 1 Faire Fin Pour

/* Parcours de la ligne. */
Si DeltaX>DeltaY Alors
/* Ligne a parcours horizontal. */
Sinon
/* Ligne a parcours vertical. */
Fin Si

/* Vidage des epaisseurs residuelles. */
Pour I=0 JusquA NbReferences Pas 1 Faire Fin Pour
Fin Procedure