Triceraprog
La programmation depuis le Crétacé

Articles avec le tag « VG5000 ».

  • VG5000µ, simplification du tracé du cercle ()

    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

  • Après la ligne, le cercle ()

    Après avoir tracé des segments de droite à l'écran grâce au BASIC du VG5000µ, passons au cercle.

    Si vous avez fait un peu de trigonométrie à l'école, vous devez savoir que, pour un angle α allant de 0 à , tracer des points aux coordonnées (cos(α), sin(α)). Ces coordonnées sont multipliées par le rayon et déplacées au centre du cercle. Et c'est comme cela qu'il peut sembler de prime abord intéressant de tracer un cercle.

    Cela ressemble à quelque chose comme ça.

    • initialiser cx et cy avec les coordonnées du centre du cercle, r avec son rayon
    • initialiser a à 0
    • tant que \(a < 2\pi\)
      • \(x = cx + r.cos(a)\)
      • \(y = cy + r.sin(a)\)
      • tracer un point en (x, y)
      • augmenter a
    • fin


    Super simple.

    Mais trop simple.

    Dans l'algorithme ci-dessus, la ligne qui indique augmenter a n'indique pas de combien il faudrait augmenter a.

    Lorsque l'on trace un cercle avec un crayon sur une feuille, on prend quelques points de références bien choisi, puis on interpole entre ces points pour tracer la courbe. Si on utilise un compas, c'est encore plus simple, il suffit de deux points de référence : le centre et un point du rayon.

    Nous avons ici le même problème que lorsque l'on cherchait à tracer un segment de droite : l'espace de tracé des points à l'écran n'est pas continu. Il s'agit dans notre cas d'allumer des pixels de manière à provoquer l'illusion de la continuité.

    S'ils sont trop tassés, c'est moche. S'ils sont trop espacés, ça fait des trous.

    Prenons un exemple avec cx = 6, cy = 5 et r = 5. Augmentons a d'un dixième de π à chaque fois. Voilà ce que cela donne :

    a 0.pi/101.pi/102.pi/103.pi/104.pi/105.pi/106.pi/10 7.pi/108.pi/109.pi/10
    x 1111109864321
    y 5789101010987
    a 10.pi/1011.pi/1012.pi/1013.pi/10 14.pi/1015.pi/1016.pi/1017.pi/1018.pi/1019.pi/10
    x 112346891011
    y 5321000123

    Traçons cela sur une grille.

    Cercle 1

    Tout comme avec le segment de droite au début, il y a des trous. Et si le rayon augmente, il y aura encore plus de trous. On peut se dire alors qu'on augmente a par de plus petites valeurs. Mais on voit sur le dessin qu'à certains endroits, les pixels sont adjacents. Cela signifierait qu'il faudrait, suivant les endroits, augmenter a différemment.

    Arrêtons-nous là pour deux raisons : la première est que l'on sent bien que cela va nous amener vers des choses vraiment complexes. La seconde est que calculer le cosinus et le sinus sur une machine ancienne de ce type, c'est lent, très lent. Certes, notre affichage de pixel est lent lui aussi, n'ajoutons pas du lent au lent.

    Mais alors que faire ?

    Changer de stratégie, et surtout, d'équation de départ. L'équation d'un cercle est aussi celle-ci : \(x^2 + y^2 - r^2 = 0\). Où r est le rayon. Un tel cercle est centré sur les coordonnées (0, 0) mais il suffit d'y ajouter les coordonnées du centre du cercle voulu pour le déplacer dans l'espace.

    Équation sur le cercle

    La deuxième chose que l'on va faire est, comme avant pour le segment de droite, de simplifier le problème en utilisant des octants, c'est-à-dire une division en huit secteurs. Ces secteurs sont choisis pour leurs axes de symétries sur le cercle de manière à ce que, pour un octant donnée, nous puissions nous occuper d'un cas très simple.

    Je vous invite à aller voir l'image plus bas pour repérer les axes de symétries utilisés.

    Une méthode

    En commençant par le point le plus haut du cercle et sur l'octant en haut à droite, on peut réduire le problème à une courbe qui part dans la direction générale entre la droite et la diagonale droite-bas. Dans ce secteur, un pixel aura pour voisin suivant soit le pixel juste à sa droite, soit le pixel juste au-dessous celui à sa droite.

    Si on trouve comment tracer ce petit morceau de courbe, il suffit de tracer les huit courbes symétriques sur le cercle pour obtenir la forme complète.

    Comment choisir si le pixel suivant le pixel courant doit être celui à sa droite ou celui en diagonal ? En utilisant la partie gauche de la formule ci-dessus pour évaluer la position du cercle parfait par raport à un point situé entre les deux points éligibles.

    Si le résultat est inférieur à 0, alors c'est que le point médian est à l'intérieur du cercle. On choisi alors le pixel à droite comme coordonnée suivante.

    Si le résultat est supérieur à 0, alors c'est que le point médian est à l'extérieur du cercle. On choisi alors le pixel en bas à droite comme coordonnée suivante.

    Et ainsi de suite jusqu'à ce que la coordonnée x soit supérieure à la coordonnée y, ce qui signal la fin de l'octant, puisque nous aurons alors atteint la diagonale.

    Reprenons :

    • 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

    Voyons ce que cela donne avec les même entrées que précédemment :

    x 6789
    y 1010109
    m -3.75
    (suivant à droite)
    -0.75
    (suivant à droite)
    4.25
    (suivant en bas à droite)
    3.25

    Le cercle n'a plus de trous, les pixels sont voisins et forment une illusion de continuité. Ce qui donne sur du papier quadrillé, avec en noir les coordonnées ci-dessus et en gris les différents symétriques.

    Cercle 2

    Note : cet algorithme n'est pas le seul possible et nous verrons lors de son implémentation qu'il peut être simplifié au niveau de ses calculs. Mais ceci est une autre histoire.

    Note 2 : le second algorithme présenté est l'algorithme de tracé de cercle de Bresenham, du nom de son auteur.


  • VG5000µ, tracer une ligne en BASIC ()

    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
    

    Résultat de tracé de segments


  • Récréation 3D ()

    Aujourd'hui, j'ai préparé quelques illustrations sous forme d'évocations de machines connues. Voici une première image, qui j'espère évoque assez bien la machine dont j'ai parlé jusqu'à maintenant sur ce site.

    VG5000µ en 3D


  • Après le point, la ligne ()

    Après avoir vu le point, si nous passions à la ligne ? Ou plus exactement, au segment de droite.

    Sur une feuille de papier, tracer un segment de droite entre deux points est une chose simple : un crayon, un règle, on positionne la règle sur les deux points et l'on trace un trait en tenant fermement cette dernière.

    Le trait a alors une allure continue ; du moment que l'on n'utilise pas un microscope pour en détailler la composition. Et c'est une représentation suffisante, dans la plupart des cas, de l'objet mathématique sous-jacent.

    Sur un écran d'ordinateur, c'est un tout autre problème. En effet, un écran traditionnel est constitué d'une matrice de petits carreaux, les pixels. Les pixels des écrans récents sont très petits et malgré cela, tracer un beau segment de droite n'est pas si simple. Alors imaginez avec les gros carreaux formant les affichages d'anciens ordinateurs ?

    Plutôt que de l'imaginer, vous pouvez même faire une expérience.

    Prenez une feuille à petits carreaux, choisissez un point de départ que vous coloriez en noir, un point d'arrivée que vous coloriez en noir. L'exercice consiste alors à colorier les carreaux intermédiaires afin de tracer un segment de droite.

    Si la réalisation est très simple pour des segments de droite horizontaux, vertiaux ou diagonaux, les droites plus quelconques, elles, demandent un peu plus d'attention afin d'obtenir un beau tracé, équilibré.

    Lignes à carreaux

    Une stratégie peut être de prendre une règle, de tracer un trait fin entre les milieux des deux cases d'extrémités et de colorier ensuite les cases traversées par le trait.

    Lignes à problèmes

    Il y a de l'idée, mais la droite, avec certaines orientations, est épaisse par endroit. Avec des gros pixels, cela ne va pas bien rendre.

    Une autre idée est d'utiliser la forme mathématique d'une droite : \(y = ax + b\). En ajustant correctement a et b et faisant varier x sur les coordonnées de l'écran, on devrait trouver y.

    Coordonnées

    x0123456
    y11,522,533,544,5

    La solution fonctionne bien... jusqu'à ce que a soit supérieur à 1. Au-delà de 1, le tracé du segment à l'écran n'est plus continu, mais comporte des trous !

    Des trous

    Et c'est sans parler du cas où l'on voudrait tracer un segment vertical. En effet, avec l'idée de faire varier les x, pour un segment vertical, x ne prend qu'une valeur. Et donc y une seule valeure aussi. Ce qui donne... un beau point. C'est normal puisqu'à une valeur de x on associe une et une seule valeur de y.

    Cette manière de tracer des segments de droite semble ne pas fonctionner, et pourtant, c'est première idée n'est pas si mauvaise. Elle nécessite juste un petit ajustement.

    Puisque la méthode de balayage des x fonctionne sur les segments de droites allant d'une pente nulle, l'horizontale, à une pente de 1, la diagonale, peut-être faut-il changer un peu d'angle pour les segments de droite allant de la diagonale à la verticale ?

    Pour cette partie-là, est-ce qu'il ne suffirait pas de poser : \(x = a'y + b'\) ? C'est-à-dire balayer les y pour obtenir les x, avec des coefficients ajustés en conséquence.

    Coordonnées

    y0123456
    x22 + 1/32 + 2/333 + 1/33 + 2/34

    Plus de trous

    Ça fonctionne plutôt bien.

    Par un jeu de symétries, le problème peut être résolu en séparant l'espace autour du point de départ en huit espaces qui induiront l'utilisation d'un balayage des x ou des y. Ces secteurs étant au nombre de huit, on les appelle des octants.

    Pour simplifier le problème, on peut limiter les cas à deux d'entres eux en prenant pour extrémité de départ le point le plus à gauche sur l'axe des x, par exemple. Il reste alors à considérer dans lequel des quatre octants à la droite de ce point le segment va être tracé, et choisir entre le balayage des x ou le balayage des y.

    Octants

    Pour décider de la méthode à appliquer, on peut commencer par calculer la pente de la droite. Si les deux points sont (x, y) et (x', y'), alors la pente de la droite est \(\frac{(y' - y)}{(x' - x)}\), le a dans \(y = ax + b\).

    Cependant, en cas de droite verticale, on se retrouve avec une division par 0 (x' étant égal à x). Si la droite est presque verticale, on peut aussi se retrouver avec des valeurs assez grandes et des problèmes de capacités de calcul de la machine.

    En fait, il n'est pas nécessaire de calculer la pente, car ce que l'on cherche à savoir où se situe la droite portant le segment par rapport à une horizontale, une verticale et une diagonale.

    Et pour cela, il suffit d'une part de comparer les valeurs absolues de \((y' - y)\) et de \((x' - x)\). Si dans le cas d'un balayage des y, on part du point le plus bas (tout comme on part du point le plus à gauche pour le balayage des x), alors les secteurs sont utilisés de cette manière :

    Décision


    Un premier algorithme

    J'obtiens donc une première idée d'algorithme qui ressemble grossièrement à ça :

    • 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'')


    Voici un algorithme de tracé de segment de droite qui fonctionne. Mais qui est aussi extrêmement lent. Dans un prochain article, nous verrons comment rendre ça sur le VG5000 en BASIC.


« Page 2 / 5 »