Maintenant que nous avons un algorithme pour tracer un cercle ainsi que le moyen d'afficher un gros pixel à l'écran, nous voilà prêts pour traduire tout cela en BASIC, comme cela a été fait auparavant avec le segment de droite.
Pour rappel, voici l'implémentation en BASIC d'affichage d'un point à l'écran.
100 REM AFFICHE UN POINT DANS L'ESPACE SEMI-GRAPHIQUE
110 REM X CONTIENT L'ABSCISSE ENTRE 0 et 79
120 REM Y CONTIENT L'ABSCISSE ENTRE 0 et 74
130 ZX=INT(X/2):ZY=INT(Y/3)
140 RX=X-ZX*2:RY=Y-ZY*3
150 CH=2^(RY*2+RX)
160 DI=&"4000"+ZY*80+ZX*2
170 AT=PEEK(DI+1)
200 OL=64:IF (AT AND 128) = 128 THEN OL=PEEK(DI)
220 IF (OL AND 128) = 128 THEN OL=64
230 POKE DI,OL OR CH
240 POKE DI+1,224
250 RETURN
L'implémentation du tracé de ligne utilisait les lignes 300 à 600. Je vais placer l'implémentation du cercle suivant l'algorithme de Bresenham à partir de la ligne 800.
Cela permettra d'avoir l'implémentation du tracé de segments de droite et de cercles dans le même programme.
Passons maintenant à l'implémentation de l'algorithme que je rappelle ici :
- initialiser cx et cy avec les coordonnées du centre du cercle, r avec son rayon
- initialiser (x, y) à (0, r), c'est à dire le point au sommet du cercle.
- initialiser M à $5 - r$
- tant que x ≤ y
- tracer le pixel(x + cx, y + cy) et ses sept symétries.
- calculer $m = (x+1)^2 + (y-0.5)^2 - r^2$
- si m ≥ 0 alors $y \leftarrow y - 1$, $M \leftarrow M - 8y_{i+1}$
- $x \leftarrow x + 1$, $M \leftarrow M + 8x_{i+1} + 4$
- fin
Implémentation
L'algorithme prend en entrée les coordonnées x et y du centre du cercle ainsi que son rayon. Nous aurons besoin d'utiliser les variables X et Y pour appeler l'affichage d'un point et pour rappel, cette routine utilise aussi les variables temporaires ZX, ZY, RX, RY, CH, DI, AT et OL.
Je choisi d'utiliser les variables CX et CY pour les coordonnées du centre du cercle, et R pour son rayon. Je documente ça dans des remarques directement dans le programme en BASIC.
800 REM AFFICHE UN CERCLE (BRESENHAM)
810 REM CX ET CY CONTIENNENT LES COORDONNEES DU CENTRE
820 REM R CONTIENT LE RAYON
J'ai besoin ensuite de variables pour les coordonnées courantes du point à afficher et qui vont évoluer avec l'algorithme. Je choisi XX et YY. Pour la valeur de m, je choisi la variable MM. J'initialise tout cela.
830 XX=0:YY=R:MM=5-4*R
Vient ensuite la répétition du bloc d'instruction exécutées tant que x ≤ y. Il n'y a pas d'instruction tant que en BASIC VG5000µ. Mais c'est facile à implémenter avec les moyens du bord. Un tant que c'est une condition qui si elle n'est pas valide sort, via un GOTO hors de la boucle et qui sinon exécute une suite d'instructions se terminant par un GOTO vers la condition.
Aparté GOTO : il est possible, si vous avez déjà programmé, que vous ayez entendu de l'utilisation de l'instruction GOTO comme de quelque chose à bannir. C'est en partie vraie et pourra être le sujet d'un futur billet. Ici, dans un BASIC aussi simpliste, on se permet de l'utiliser, c'est le plus évident.
Voici la structure du tant que :
840 IF XX>YY THEN GOTO 970
[ des instructions ]
960 GOTO 840
970 RETURN
En ligne 970, le RETURN indique la fin de la routine d'affichage du cercle, qui sera donc appelée via l'instruction GOSUB, comme dans le cas des segments de droite.
Quant aux instructions, elles consistent tout d'abord à affiche le pixel et ses symétries :
850 X=CX+XX:Y=CY+YY:GOSUB 100
860 X=CX+YY:Y=CY+XX:GOSUB 100
870 X=CX-XX:Y=CY+YY:GOSUB 100
880 X=CX-YY:Y=CY+XX:GOSUB 100
890 X=CX+XX:Y=CY-YY:GOSUB 100
900 X=CX+YY:Y=CY-XX:GOSUB 100
910 X=CX-XX:Y=CY-YY:GOSUB 100
920 X=CX-YY:Y=CY-XX:GOSUB 100
Puis la sélection du prochain pixel est effectuée en fonction de la valeur de MM, qui est ajustée, ainsi que les coordonnées XX et YY.
930 IF MM > 0 THEN YY=YY-1:MM=MM-8*YY
940 XX=XX+1
950 MM=MM+8*XX+4
Ce qui donne au final :
800 REM AFFICHE UN CERCLE (BRESENHAM)
810 REM CX ET CY CONTIENNENT LES COORDONNEES DU CENTRE
820 REM R CONTIENT LE RAYON
830 XX=0:YY=R:MM=5-4*R
840 IF XX>YY THEN GOTO 970
850 X=CX+XX:Y=CY+YY:GOSUB 100
860 X=CX+YY:Y=CY+XX:GOSUB 100
870 X=CX-XX:Y=CY+YY:GOSUB 100
880 X=CX-YY:Y=CY+XX:GOSUB 100
890 X=CX+XX:Y=CY-YY:GOSUB 100
900 X=CX+YY:Y=CY-XX:GOSUB 100
910 X=CX-XX:Y=CY-YY:GOSUB 100
920 X=CX-YY:Y=CY-XX:GOSUB 100
930 IF MM > 0 THEN YY=YY-1:MM=MM-8*YY
940 XX=XX+1
950 MM=MM+8*XX+4
960 GOTO 840
970 RETURN
C'est une implémentation très simple, d'un algorithme, une fois travaillé, très simple. À vrai dire, le tracé du pixel en lui même est plus complexe que le tracé du cercle. S'il vous manque la signification de certaines instructions, retournez voir l'implémentation du segment de droite, qui les détail.
Le résultat
Pour appeler la routine de tracé de cercle et afficher quelque chose, j'ajoute :
10 GOTO 1000
1000 INIT
1010 CX=30:CY=20:R=10:GOSUB 800:DISPLAY
1020 CX=40:CY=40:R=25:GOSUB 800:DISPLAY
1060 END
Tout d'abord un saut vers la ligne 1000, qui efface l'écran avec INIT puis appelle l'affichage de deux cercles. Cela donne l'image en début de cette article, avec les deux cercles.
Mais c'est toujours très lent !
Étant donné que l'algorithme se repose sur une implémentation d'affichage de pixel très lente, l'affichage du cercle est lui-même très lent. Il aura fallu plusieurs minutes avant de voir l'image de la fin de l'article, et définie par l'utilisation suivante :
10 GOTO 1500
1500 INIT
1510 CX=40:CY=30
1520 FOR R=25 TO 30
1530 GOSUB 600
1540 NEXT R
1550 CX=50:CY=20
1560 FOR R=1 TO 4
1570 GOSUB 600
1580 NEXT R
1590 CX=30:CY=20
1600 FOR R=1 TO 4
1610 GOSUB 600
1620 NEXT R
Le moment d'optimiser tout ça arrive, mais il reste quelques explorations en BASIC à faire avant.
