Triceraprog
La programmation depuis le Crétacé

• VG5000µ, haute résolution (2017-06-01)

  Dans les articles précédents sur l'affichage du VG5000µ, je travaillais dans une résolution que je nomme « gros pixels », basée sur des caractères semi-graphiques. Grâce à l'implémentation d'une routine d'affichage de pixel, j'avais pu programmer un affichage de ligne et un affichage de cercle.

  Avec ce mode d'affichage, on obtient une résolution de 80 pixels horizontalement par 75 pixels verticalement. Ce qui donne un total de 6000 pixels. Cependant, le manuel d'utilisation de la machine indique une définition d'image de 80 000 points. Plus de 13 fois plus. Existe-t-il une façon d'afficher des pixels plus petits et d'atteindre une haute (toute proportion gardée) définition ?

  Petit rappel : je ne m'occupe pour le moment que des capacités du VG5000µ offertes par le BASIC, et se mettant à la place d'une utilisation à l'époque, avec juste le manuel de base.

  Plus fin

  Pour atteindre une définition plus fine depuis le BASIC, il faut utiliser les informations du Chapitre 16, sur les jeux de caractères définissables par l'utilisateur.

  Comme on l'a vu avec les caractères semi-graphique, l'écran du VG5000µ est organisé suivant une grille de 40 colonnes et 25 lignes, avec chaque emplacement pouvant afficher un caractère. Ce caractère peut être un chiffre, une lettre, de la ponctuation, ou bien un caractère semi-graphique. Mais il existe aussi des caractères laissés libres dont il est possible de définir le contenu.

  C'est un peu comme si l'on pouvait définir une nouvelle police de caractères. Et la manière dont est configuré le VG5000µ laisse deux plages de 96 de ces caractères. Une plage pour le mode texte et une plage pour le mode graphique. Ce qui, si l'on met de côté les restrictions d'attributs d'affichage qui sont différents en texte (mode TX) et en graphique (mode GR), donne 192 caractères programmables.

  Ces caractères, comme les autres prédéfinis, sont des blocs de 8 pixels de large par 10 pixels de haut. Ce qui donne donc un total théorique de 15360 pixels qui peuvent être simultanément affichés en haute définition à l'écran. Avec des contraintes sur les couleurs, sur les emplacements et les enchaînements des modes TX et GR.

  Cela donne une théorie d'un peu moins de 20% de l'écran qui peut être en haute définition.

  Par la réutilisation de caractères identiques à plusieurs emplacements et le mélange de ces caractères avec les caractères de bases texte et semi-graphique, il est possible de pousser la théorie. Au prix d'un effort considérable. Dessiner de belles images directement sur la machine est long et complexe.

  Définition des caractères

  L'objectif de cet article est d'obtenir sur le VG5000µ une image en haute définition affichée depuis le BASIC. Voyons donc déjà le principe de la programmation de ces caractères, qui est similaire à celui que l'on trouve sur d'autres machines, comme le CPC6128.

  Chaque caractère est composé de 10 lignes de 8 pixels, chacun des pixels pouvant avoir deux états : allumé et éteints, ou plutôt, couleur d'encre et couleur de fond.

  8 pixels avec deux états, c'est parfait pour tenir dans un octet de 8 bits. Un caractère sera donc défini par une série de 10 octets.

  La manière de créer un caractère est de prendre du papier quadrillé, de colorier des cases, puis de transformer ces cases coloriées en 1, celles qui ne le sont pas en 0 pour obtenir les valeurs d'encodage du caractère.

  Voici par exemple ce qui pourrait être une sorte de vaisseau pour un jeu.

  

  Ce qui, donne l'encodage suivant.

  									Codage en base 10
  0	0	0	0	0	0	0	0	->	0
  0	0	0	0	0	0	0	0	->	0
  0	0	0	1	1	0	0	0	->	24
  0	1	1	1	1	1	1	0	->	126
  1	0	1	0	0	1	0	1	->	165
  0	1	1	1	1	1	1	0	->	126
  0	0	0	1	1	0	0	0	->	24
  0	0	0	0	0	0	0	0	->	0
  0	0	0	0	0	0	0	0	->	0
  0	0	0	0	0	0	0	0	->	0

  La commande VG5000µ pour programmer les caractères demande de transformer cette série de nombre sous une écriture hexadécimal, puis, par d'écrire le tout sous une forme de chaîne de caractères.

  Hexadécimal : cette notation sort du cadre de l'article. Rapidement, il s'agit de compter dans une base de 16 chiffres, plutôt que les 10 habituels. Les 6 chiffres après le 9 sont notés A, B, C, D, E et F.

  Dans notre exemple, la série de nombres (en base 10) de haut en bas 0, 0, 24, 126, 165, 126, 24, 0, 0, 0 se transforme en série de nombres (en base 16) 0, 0, 18, 7E, A5, 7E, 18, 0, 0, 0. Comme un nombre hexadécimal de 0 à 255 ne prendra jamais plus de deux caractères, la commande demande à mettre tous les nombres sur deux caractères et assembler le tout. Cela donne au final : 0000187EA57E18000000.

  Exemple plus poussé

  Calculer une grille pour chaque caractère voulu est fastidieux. Très fastidieux. C'est pourquoi pour essayer ce mode, je me suis servi d'un programme annexe, sur une machine moderne, afin de transformer une image en série de caractères définis.

  Par simplicité, je me suis limité à la palette graphique étendue, et donc à 96 caractères maximum. J'ai pris l'image de la maison que j'avais tracée dans l'article sur le tramage, je l'ai redimensionnée puis je l'ai passé à ma moulinette.

  

  Le programme BASIC en sorti est constitué de trois parties.

  5 INIT 6:EG0,6
  10 FOR Y=0 TO 12
  20 FOR X=0 TO 9
  30 READ I
  40 CURSORX X+14:CURSORY Y+4
  50 PRINT CHR$(I);
  60 NEXT X
  70 NEXT Y
  

  La première partie efface l'écran et pioche dans une liste de données les numéros de caractères à afficher à l'écran. Pour cela, deux boucles FOR imbriquées font parcourir au curseur la zone à afficher.

  À noter ligne 50 le point-virgule à la fin du PRINT, qui empêche l'instruction d'afficher le caractère de retour chariot, pas nécessaire car ce n'est pas un caractère affichable dans ce mode, mais qui évite certains calculs au BASIC.

  L'instruction READ prend une à une les valeurs fournies par l'instruction DATA de la troisième partie du programme.

  La seconde partie est une liste des définitions de tous les caractères.

  100 SETEG 115,"5CE854B4D868AAB855DB"
  110 SETEG 55,"FAAFDA77DDB6ED77ADFB"
  120 SETEG 93,"94224885284214429449"
  ...
  ...
  ...
  1020 SETEG 103,"44922449924491249249"
  1030 SETEG 119,"08020000000000000000"
  1040 SETEG 39,"00000000000000010103"
  

  Enfin, la troisième partie indique les caractères à afficher, lus par la première partie.

  1050 DATA 32,32,32,32,33,34,32,32,32,32,32,32,32,35,36,37
  1060 DATA 38,32,32,32,32,32,39,40,41,42,43,44,32,32,32,45
  1070 DATA 46,47,48,49,50,51,52,32,32,53,54,55,56,57,58,59
  1080 DATA 60,32,61,62,63,64,65,66,67,68,69,70,71,72,73,74
  1090 DATA 75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90
  1100 DATA 91,92,93,94,95,96,97,98,99,100,32,101,102,103,104,105
  1110 DATA 106,107,108,109,32,110,111,112,113,114,115,116,117,118,32,32
  1120 DATA 119,120,121,122,123,124,32,32,32,32,32,32,125,126,32,32
  1130 DATA 32,32
  

  On y remarque la répétition du caractère 32, qui est un caractère entièrement de la couleur du fond (et qui, avec un peu plus de travail, aurait pu être ignoré, afin de gagner un caractère programmable).

  Le fait d'afficher d'abord les caractères puis de les définir offre au passage un petit effet intéressant d'affichage progressif.

  Ça consomme !

  Cette manière d'afficher permet du détail, mais, surtout en BASIC, elle consomme beaucoup de place en mémoire. Le programme pour afficher l'image en fin d'article prend un peu moins de 4 ko, ce qui est énorme considérant les capacités de la machine. On pourrait stocker 3 images comme celle-ci pour la configuration mémoire sans extension, et puis c'est tout.

  Le fait d'utiliser les commandes BASIC pour cela est en parti le problème. La place nécessaire à ces données est plutôt de l'ordre de 1 ko, et le programme qui décode l'image peut-être plus léger. J'y reviendrai plus tard.

  Le résultat

  Voilà un exemple d'affichage en haute définition depuis le BASIC du VG5000µ. Cela conclue la série d'article d'exploration des capacités graphiques du VG5000µ en n'utilisant que les instructions décrites par le manuel d'utilisation. La prochaine fois que je reviendrai sur l'affichage, cela sera pour aller au-delà des limitations du BASIC.

  

  ---

• Récréation 3D, Atari STe (2017-05-25)

  Après les machines précédemment évoquées en synthèse, toutes basées sur des processeurs 8 bits, voici ma première recréation de l'époque 16 bits, un Atari STe. Dans ma chronologie de programmeur, le 512 STe (gonflé en mémoire) a remplacé l'Amstrad CPC 6128. Un plutôt gros changement.

  Côté musique, l'Atari était relié à un synthétiseur et j'ai pu découvrir les joies de la programmation MIDI et écrire un petit séquenceur à usage personnel (et très limité).

  

  ---

• Tracé d'un cercle en BASIC sur VG5000µ (2017-05-17)

  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.

  

  ---

• VG5000µ, simplification du tracé du cercle (2017-05-14)

  Avec de passer à l'implémentation en BASIC du cercle décrit dans un article précédent, passons un peu par une phase de simplification. Cet article va contenir quelques lignes de mathématiques.

  L'outil mathématique le plus complexe utilisé est celui des factorisations et développements de carrés. Les identités remarquables seront d'un grand secours. Niveau de fin de collège je crois.

  Pour rappel, voici l'algorithme de tracé de cercle de Bresenham :

  • 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.
  • 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 $x \leftarrow x + 1$ et $y \leftarrow y - 1$
    • sinon $x \leftarrow x + 1$
  • fin

  On pourrait l'implémenter tel quel. Mais je veux d'abord attirer votre attention sur un détail assez simple. Dans les deux cas de la condition, que m soit ou non supérieur à zéro, x est augmenté de 1. En effet, si vous vous souvenez, quoi qu'il arrive, on trace les pixels en prenant toujours le suivant sur la colonne à sa droite.

  On pourrait donc réécrire :

  • 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.
  • 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$
    • $x \leftarrow x + 1$
  • fin

  Cela aura le même résultat, et un peu moins d'instructions.

  Une petite pause ici : avec des langages compilés et des outils de compilation récents, il est très probable que ce genre de simplification soit fait automatiquement par le compilateur. Ce qui n'empêche pas d'écrire un code plus simple, mais sans aller jusqu'à simplifier au point que le lecteur humain ne comprenne plus rien. Ici, dans le monde BASIC interprété des années 1980, c'est une simplification intéressante que l'on doit faire à la main.

  Cette simplification fait partie des optimisations. Avec moins d'instructions, le programme ira probablement plus vite. Dans notre cas ici, le routine d'affichage de pixel est tellement lente que l'effet est négligeable. Mais tout de même.

  Simplifions encore

  Un autre type d'optimisation peut venir d'une simplification des calculs à effectuer. Le BASIC du VG5000µ n'est pas très rapide en calculs et on demande ici dans la boucle de tracé sept opérations dont trois multiplications. Et les multiplications générique, c'est lent.

  Plutôt que de calculer m complètement à chaque fois, il est possible d'en calculer la valeur à partir de la valeur précédente. Attention, un peu de mathématiques.

  Disons que $m_i$ est la valeur de m à l'itération i. Et $m_{i+1}$ la valeur à l'itération suivante. Avec la même notation pour x et y à chaque itération (le rayon r ne bouge pas), on peut poser : $m_i = (x_i+1)^2 + (y_i-0.5)^2 - r^2$.

  Et pour le calcul de m à l'itération suivante : $m_{i+1} = (x_{i+1}+1)^2 + (y_{i+1}-0.5)^2 - r^2$

  Il y a deux cas dans l'algorithme, d'abord celui où l'on sélectionne le pixel de droite. Dans ce cas là, x est augmenté de 1, et y ne change pas. Cela donne ces deux égalités : $x_{i+1} = x_i + 1$ et $y_{i+1} = y_i$.

  Avec l'objectif de calculer $m_{i+1}$ à partir de $m_i$, remplaçons dans l'équation :

  • $m_{i+1} = (x_{i+1}+1)^2 + (y_{i+1}-0.5)^2 - r^2$
  • $m_{i+1} = (x_{i+1}+1+1)^2 + (y_{i}-0.5)^2 - r^2$, (par substitution des termes à l'itération précédente)
  • $m_{i+1} = (x_i^2 + 4x_i + 4) + (y_{i}-0.5)^2 - r^2$, (par développement du premier carré)
  • $m_{i+1} = ((x_i^2 + 2x_i + 1) + (y_{i}-0.5)^2 - r^2) + 2x_i + 3$, (par commutativité et associativité)
  • $m_{i+1} = ((x_i + 1)^2 + (y_{i}-0.5)^2 - r^2) + 2x_i + 3$, (par factorisation)
  • $m_{i+1} = m_i + 2x_i + 3$, (par substitution du premier groupe qui est la définition de $m_i$)

  Ou bien, si l'on préfère calculer $m_{i+1}$ par rapport aux coordonnées à la même itération :

  • $m_{i+1} = m_i + 2(x_{i+1} - 1) + 3$, (par substitution)
  • $m_{i+1} = m_i + 2x_{i+1} - 2 + 3$, (par développement)
  • $m_{i+1} = m_i + 2x_{i+1} + 1$, (par simplification)

  Dans le deuxième cas où l'on prend le pixel en diagonal, on a x toujours augmenté de 1, mais aussi y qui est réduit de 1. Cela donne ces deux égalités : $x_{i+1} = x_i + 1$ $y_{i+1} = y_i - 1$.

  Remplaçons dans l'équation suivant le même principe :

  • $m_{i+1} = (x_{i+1}+1)^2 + (y_{i+1}-0.5)^2 - r^2$
  • $m_{i+1} = (x_{i}+1+1)^2 + (y_{i}-1-0.5)^2 - r^2$, (par substitution des termes à l'itération précédente)
  • $m_{i+1} = (x_{i}+2)^2 + (y_{i}-\frac{3}{2})^2 - r^2$, (par simplification)
  • $m_{i+1} = (x_{i}^2+4x_{i}+4) + (y_{i}^2-3y_{i}+(\frac{3}{2})^2) - r^2$, (par développement des deux carrés)
  • $m_{i+1} = ((x_{i}^2+2x_{i}+1) + (y_{i}^2-y_{i}+(\frac{1}{2})^2) - r^2) + 2x_{i} + 3 - 2y_{i} + \frac{8}{4}$, (par commutativité et associativité)
  • $m_{i+1} = m_i + 2x_{i} + 3 - 2y_{i} + \frac{8}{4}$, (par substitution du premier groupe qui est la définition de $m_i$)
  • $m_{i+1} = m_i + 2x_{i} + 3 - 2y_{i} + 2$, (par simplification, mais pas trop, pour garder la forme du premier cas visible dans l'équation)

  Ou bien, si l'on préfère calculer $m_{i+1}$ par rapport aux coordonnées à la même itération :

  • $m_{i+1} = m_i + 2(x_{i+1}-1) + 3 - 2(y_{i+1}+1) + 2$, (par substitution)
  • $m_{i+1} = m_i + 2x_{i+1} - 2 + 3 - 2y_{i+1} - 2 + 2$, (par développement)
  • $m_{i+1} = m_i + 2x_{i+1} + 1 - 2y_{i+1}$, (par simplification, mais pas trop, pour garder la forme du premier cas visible dans l'équation)

  Dans les deux cas, il s'agit donc d'ajouter à l'ancienne valeur de m un calcul qui dépend des nouvelles coordonnées. La multiplication est une multiplication par 2, ce qui est beaucoup plus rapide pour un ordinateur qu'une multiplication générale. Bon, pas en BASIC VG5000µ, mais je vous assure que dans le future, nous serons heureux d'avoir cette simplification.

  Une autre étape intéressante peut-être de relier les deux équations, en cherchant à exprimer le résultat du choix du pixel en diagonal par le résultat lorsque le choix est celui du pixel à droite.

  Voilà la raison de ne pas trop simplifier les équations à la fin des calculs. Le calcul final est :

  • $m_{i+1} = m_i + 2x_{i+1} + 1 - D$, (D pour diagonale)
  • $D = 0$ si l'on choisi le point de droite,
  • $D = 2y_{i_+1}$ si l'on choisi le point en diagonale.

  Point de départ

  Maintenant que l'on sait compter la valeur de m à une itération donnée par rapport à sa valeur précédente, il nous faut bien un point de départ. Le tout premier m, que l'on note $m_0$ est la valeur pour le premier pixel tracé. Pour rappel, dans l'algorithme, le premier pixel est celui en haut du cercle, c'est-à-dire aux coordonnées x = 0 et y = r.

  Il suffit de remplacer ces valeurs dans l'équation qui nous donne la valeur de m :

  • $m = (x+1)^2 + (y-0.5)^2 - r^2$
  • $m = (0+1)^2 + (r-0.5)^2 - r^2$, (par substitution)
  • $m = 1^2 + r^2-r+(\frac{1}{4})^2 - r^2$, (par développement)
  • $m = \frac{5}{4} - r$, (par simplification)

  Aïe, une fraction. Une fraction, c'est très bien tant qu'on est dans le calcul. Par contre, une fois que l'on doit passer à l'implémentation, cela se corse. Mieux vaut garder des calculs sur des entiers, surtout sur des machines de cette époque.

  Heureusement, tout ce qui nous intéresse dans m pour choisir le pixel suivant est son signe. Est-ce un nombre positif ou négatif ? Cette information restera valide même si la valeur de m est multipliée par un nombre positif.

  L'astuce ici sera donc, à l'implémentation, de ne pas calculer m, mais 4m, c'est-à-dire quatre fois la valeur de m. L'algorithme reste valide, et l'on se débarrasse de la fraction. En gardant des multiplications par multiples de 2, on garde la facilité à multiplier des entiers rapidement.

  • $4m_0 = 5 - r$

  Conclusion

  Cet article est un passage presque entièrement dédié à des mathématiques. Celles-ci nous ont aidé à réduire les calculs nécessaires à la résolution d'un algorithme.

  Transformer un problème en un équivalent plus simple est une des bases de l'optimisation. Cela fait parfois appel aux mathématiques, parfois à la connaissance de la machine utilisée, parfois au langage de programmation en lui-même.

  Au final, voici le nouvel algorithme, qui sera transformé en BASIC dans l'article suivant.

  • 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

  ---

• Récréation 3D, Amstrad CPC 6128 (2017-04-29)

  L'ordinateur 8 bits que j'ai le plus décortiqué, sur lequel j'ai le plus programmé en son temps, est un CPC 6128. J'y ai débuté le Pascal et abordé légèrement le C. J'y ai aussi fait mes premiers essais en assembleur.

  Un ordinateur élégant, sobre, avec un clavier très agréable, qui pouvait servir dans de nombreux domaines. Son principal et historique défaut reste son format de disquettes, particulier, rare et cher.

  

  ---

« (précédent) Page 18 / 22 (suivant) »