Triceraprog
La programmation depuis le Crétacé

Après avoir décrit un algorithme de tracé de segment de droite de manière générique, voyons un peu comment traduire ça en BASIC sur le VG5000µ. Pour ce premier article, il s'agira d'une implémentation simpliste, qui servira de base.

Pour rappel, voici l'algorithme générique :

• En entrée, on a deux points de coordonnées (x, y) et (x', y')
• Si x' est plus petit que x, échanger les valeurs de x et x' ainsi que de y et y'
• Choix de l'octant en fonction de |y' - y| et de |x' - x|
• Si on fait un balayage des x, alors
  • Calculer la pente $a = \frac{(y' - y)}{(x' - x)}$
  • Calculer $b = \frac{x'y - xy'}{x'-x}$
  • Pour tous les x'' de x à x', calculer $y'' = ax'' + b$.
  • Tracer un pixel en (x'', y'').
• Si on fait un balayage des y, alors
  • Si y' est plus petit que y, échanger les valeurs de x et x' ainsi que de y et y'
  • Calculer la pente $a = \frac{(x' - x)}{(y' - y)}$
  • Calculer $b = \frac{y'x - yx'}{y'-y}$
  • Pour tous les y'' de y à y', calculer $x'' = ay'' + b$
  • Tracer un pixel en (x'', y'')

Il s'agit à présent de transformer ces instructions en instructions BASIC. Je me base sur l'implémentation de tracé de point publié précédemment, implémenté entre les lignes 100 à 250.

C'est quelque chose de classique en BASIC de l'époque, les routines, c'est-à-dire des sous-programmes dédiés à une tâche, sont implémentées à des lignes précises. Dans le cas de mon tracé de point, la routine est re-logeable, il est possible de changer les numéros de ligne sans problème.

Cette routine utilise les variables X et Y en entrée. Elle utilise aussi en interne les variables ZX, ZY, RX, RY, CH, DI, AT et OL. Cela signifie que ces variables, si elles sont utilisées ailleurs dans le programme, verront leur contenu changer à l'appel de la routine.

C'est, j'en ai déjà parlé, une limitation gigantesque des BASIC de cet époque. Même si, ALGOL, un langage antérieur, avait introduit la portée lexicale des variables, la compartimentation des différentes parties d'un programme n'est pas un acquis lors de la création du BASIC et les versions disponibles sur les ordinateurs familiaux, par soucis d'accessibilité très certainement, ont gardé cette limitation.

Veillons donc juste à être prudent avec le nom des variables utilisées.

Préambule

Je vais implémenter la routine de segment de droite à partir de la ligne 300, soit après l'implémentation du point. Il y a une raison pour cela que j'expliquerai sûrement plus tard.

La routine commence par une petite documentation du fonctionnement. Ces commentaires sont complètement optionnels mais bien utiles pour les utilisateurs futurs. Voire pour moi, me rappeler plus tard ce que j'avais décidé.

300 REM AFFICHE UN SEGMENT DE DROITE DANS L'ESPACE SEMI-GRAPHIQUE
310 REM X1 ET Y1 CONTIENNENT LES COORDONNEES DE DEPART
320 REM X2 ET Y2 CONTIENNENT LES COORDONNEES D'ARRIVEE

Puis vient l'échange des coordonnées. Comme le BASIC du VG5000µ n'a pas de commande pour inverser le contenu de deux variables (c'est une instruction plutôt rare), il me faut passer par une variable intermédiaire que je nomme TT. On reconnaîtra bien là les pâtés caractéristique des programmes BASIC de l'époque. Plein de lettres et de signes collés.

330 IF X2<X1 THEN TT=X1:X1=X2:X2=TT:TT=Y1:Y1=Y2:Y2=TT

Il faut ensuite, pour décider de l'octant et donc du balayage, savoir si on est plus de la verticale que de l'horizontale. Pour cela, on peut calculer la valeur absolue de la différence des X (abscisses) et des Y (ordonnées).

340 AX=ABS(X2-X1):AY=ABS(Y2-Y1)

Vient ensuite la sélection de la sous-routine à utiliser, en fonction de balayage utilisé. L'instruction conditionnelle IF du BASIC du VG5000µ n'a pas de clause ELSE comme sur beaucoup d'autres BASIC. Une solution (il y en a d'autres) est d'écrire les deux choix explicitement.

Si la condition indiquée après le IF est vérifiée, alors le programme continuera à la ligne indiquée après l'instruction GOSUB. Lorsque l'interpréteur BASIC rencontrera l'instruction RETURN, le déroulement reprendra après le GOSUB.

350 IF AX >= AY THEN GOSUB 400
360 IF AX < AY THEN GOSUB 500
370 RETURN

Balayages

Reste à écrire les deux balayages différents. Commençons par les X.

400 A=(Y2-Y1)/(X2-X1)
410 FOR X=X1 TO X2
420 Y=INT(0.5+Y1+A*(X-X1))
430 GOSUB 100
440 NEXT X
450 RETURN

Il n'y a pas de fonction d'arrondi disponible. La fonction est émulée en prenant la partie entière, c'est-à-dire sans les chiffres après la virgule, du nombre augmenté de 0.5. La fonction pour obtenir la partie entière est INT.

La ligne 420 est une simplification du calcul de b dans l'équation de la droite, valide pour les valeurs de x du segment de droite. Je vous laisse faire le calcul.

Pour le balayage des Y, il faut commencer par échanger les coordonnées si nécessaire.

500 IF Y2<Y1 THEN TT=X1:X1=X2:X2=TT:TT=Y1:Y1=Y2:Y2=TT

Puis le balayage en lui-même est effectué.

510 A=(X2-X1)/(Y2-Y1)
520 FOR Y=Y1 TO Y2
530 X=INT(0.5+X1+A*(Y-Y1))
540 GOSUB 100
550 NEXT Y
560 RETURN

La ligne 530 comme la 420 est une simplification des calculs.

Et voilà. Une routine de tracé de segment de droite avec les moyens du bord, en BASIC VG5000µ.

Petite modification avant le récapitulatif, les lignes 500 et 330 font toutes les deux l'échange des coordonnées. Se répéter en programmation est mauvais signe dans une grande partie des cas. Déplaçons cette partie dans une sous-routine.

330 IF X2<X1 THEN GOSUB 270

500 IF Y2<Y1 THEN GOSUB 270

270 TT=X1:X1=X2:X2=TT:TT=Y1:Y1=Y2:Y2=TT
280 RETURN

Récapitulatif

300 REM AFFICHE UN SEGMENT DE DROITE DANS L'ESPACE SEMI-GRAPHIQUE
310 REM X1 ET Y1 CONTIENNENT LES COORDONNEES DE DEPART
320 REM X2 ET Y2 CONTIENNENT LES COORDONNEES D'ARRIVEE

330 IF X2<X1 THEN GOSUB 380

340 AX=ABS(X2-X1):AY=ABS(Y2-Y1)
350 IF AX >= AY THEN GOSUB 400
360 IF AX < AY THEN GOSUB 500
370 RETURN

380 TT=X1:X1=X2:X2=TT:TT=Y1:Y1=Y2:Y2=TT
390 RETURN

400 A=(Y2-Y1)/(X2-X1)
410 FOR X=X1 TO X2
420 Y=INT(0.5+Y1+A*(X-X1))
430 GOSUB 100
440 NEXT X
450 RETURN

500 IF Y2<Y1 THEN GOSUB 380
510 A=(X2-X1)/(Y2-Y1)
520 FOR Y=Y1 TO Y2
530 X=INT(0.5+X1+A*(Y-Y1))
540 GOSUB 100
550 NEXT Y
560 RETURN

Utilisation

Voici par exemple une utilisation du programme pour tracé un dessin. Sur chacune des lignes, les coordonnées des lignes sont mentionnées puis la sous-routine est appelée. La commande DISPLAY exécutée ensuite sert à forcer le rafraîchissement de l'écran après chaque ligne.

Comme indiqué précédemment, c'est long, très long. Il faut environ 17 secondes sur la machine pour contempler le résultat. Le VG5000µ nous laisse peu d'options en restant dans le BASIC pour améliorer cela. Nous essaierons cependant une prochaine fois.

10 GOTO 1000

1000 INIT
1010 X1=10:Y1=15:X2=35:Y2=5:GOSUB 300:DISPLAY
1020 X1=60:Y1=15:X2=35:Y2=5:GOSUB 300:DISPLAY
1030 X1=10:Y1=15:X2=35:Y2=60:GOSUB 300:DISPLAY
1040 X1=60:Y1=15:X2=35:Y2=60:GOSUB 300:DISPLAY
1050 X1=60:Y1=15:X2=10:Y2=15:GOSUB 300:DISPLAY
1060 END