Bienvenue aux nouveaux arrivants sur FantasPic !

- Pensez à lire les règles durant votre visite, il n'y en a pas beaucoup, mais encore faut-il les respecter .
- N’hésitez pas à faire des remarques et/ou suggestions sur le Forum, dans le but de l'améliorer et de rendre vos prochaines visites plus agréables.
- Vous pouvez regarder votre "panneau de l'utilisateur" afin de configurer vos préférences.
- Un passage par "l'utilisation du forum" est recommandé pour connaître les fonctionnalités du forum.

--- L’équipe FantasPic ---
Forum général sur l'Assembleur !

Modérateur : mazertoc

Algorithme de Bresenham
satinas
Expert
Expert
Messages : 1225
Enregistré en : novembre 2015

#11 Message par satinas » ven. 28 oct. 2022 09:42

Bonjour,

Le bit C en sortie de soustraction (A = A-B) ne donne pas le signe du résultat A, mais celui de de la différence A-B.
En sortie de soustraction :
- C = 0 -> (A-B) positif ou nul et A >= B
- C = 1 -> (A-B) négatif et A < B

Il y a ce même problème de calcul de signe dans les 2 codes asm.
D'autre part, dans la ligne de l'algo :
D += 2 * (x - y) + 5
Ce qui donne en plus lisible
D = D + (2 * (x - y)) + 5

Dans ton code basic :
D = D + (x - y)
D = D * 2 + 5
Ce qui revient à
D = 2 * D + (2 * (x - y)) + 5

Pour une résolution lcd ne depassant pas 128, je ne pense pas que ce soit nécessaire de passer les variables erreur et D en 16 bits. Il faut tout passer en 16 bits si on trace des arcs de cercle de très grand rayon, ou pour un lcd 320x240.

Algorithme de Bresenham
francois77
Passioné
Passioné
Messages : 307
Enregistré en : avril 2022

#12 Message par francois77 » ven. 28 oct. 2022 11:08

Bonjour Satinas,

Merci pour ton aide

Prévoir un code pour les écrans plus grands, cela devient un macro générique

A+

Francois

Algorithme de Bresenham
satinas
Expert
Expert
Messages : 1225
Enregistré en : novembre 2015

#13 Message par satinas » ven. 28 oct. 2022 11:30

Bonjour François

Oui, il faut des macros d'addition et soustraction 16 bits. On peut ainsi travailler directement avec les variables passées en argument, sans avoir à passer par des variables intermédiaires.
Après, faire du générique en assembleur pour travailler en 8 ou 16 bits, qui trop embrasse mal étreint :)
Grâce au préprocesseur on peut aiguiller vers des routines spécifiques, selon la valeur de la résolution déclarée dans des defines.

Algorithme de Bresenham
Temps-x
Avatar de l’utilisateur
Expert
Expert
Messages : 2595
Enregistré en : juillet 2016
Localisation : Terre

#14 Message par Temps-x » sam. 29 oct. 2022 02:12

Bonsoir satinas, francois77, et tout le forum,

satinas a écrit :Source du message Oui, il faut des macros d'addition et soustraction 16 bits.

il faut bien plus que ça, car comme je le précise il y a des nombres négatifs qui vont de -65535 à +65535, bref... il y a de quoi s’occuper pour un bon moment .

satinas a écrit :Source du message Pour avoir le signe de erreur, il faut tester son bit 7, il est à 1 si la variable est négative.


Le bit 0 c'est Carry, et normalement il me semble qu'il est plutôt à zéro quand c'est négatif.

Tu parles de ceci pour le code ligne

Code : Tout sélectionner


remb1                                          
      incf y
,F

      pset x
,y,0,1                       ; pset x,y,1,couleur

      movf xdist
,W
      subwf erreur
,F                      ; erreur = erreur - xdist    

                                          
; if erreur < 0 THEN
      btfsc STATUS
,C   
      goto remb2
                                  
      btfsc pas
,0   
      incf  x
,F                           ; x = x + 1
      btfss pas
,0
      decf  x
,F                           ; x = x - 1   
                                            
      movf ydist
,W
      addwf erreur
,F                      ; erreur = erreur + ydist                                   
                                          
remb2
      movf y2
,W
      xorwf y
,W
      btfss STATUS
,
      goto remb1                           
; next y

      return



Tester sous Mplab 8.92 je n'ai pas trouvé d'erreur, de plus pas d'erreur dans le traçage de ligne, voir la première vidéo en Post #1


:roll: Pour l'instant, je me demande comment on peut mémorisé un nombre négative de 16 bits, sachant qu'après plusieurs opération STATUS va changer ses valeurs.

==> A+
Modifié en dernier par Temps-x le sam. 29 oct. 2022 19:32, modifié 1 fois.
:roll: Les requins, c'est comme le langage ASM, c'est le sommet de la chaîne alimentaire. :wink:

Algorithme de Bresenham
satinas
Expert
Expert
Messages : 1225
Enregistré en : novembre 2015

#15 Message par satinas » sam. 29 oct. 2022 06:38

Bonjour à tous

Je me suis planté plus haut , en sortie de soustraction A = A-B :
C = 0 si (A-B) négatif et A < B
C = 1 si (A-B) positif ou nul et A >= B
C retourne donc l'inverse de la retenue.

Ok cela marche, alors modifie ton commentaire :)

Code : Tout sélectionner

      movf xdist,W
      subwf erreur,F                      ; erreur = erreur - xdist
     
                                          ; if (erreur-xdist) < 0 THEN
      btfsc STATUS,C   
      goto remb2

Et pourquoi -65536 et pas -32768 pour tenir dans 2 octets ?
Avec 1 octet on stocke des valeurs de -128 à +127, dont le signe est en b7.
Avec 2 octets on stocke des valeurs de -32768 à +32767, dont le signe est en b15.
https://fr.wikipedia.org/wiki/Compl%C3% ... C3%A0_deux

Algorithme de Bresenham
Claudius
Avatar de l’utilisateur
Passioné
Passioné
Messages : 260
Âge : 69
Enregistré en : septembre 2015
Localisation : ELANCOURT (78 - YVELINES)
Contact :

#16 Message par Claudius » sam. 29 oct. 2022 19:15

Bonsoir,

Cf. PIC Microcontroller Comparison Math Methods pour éviter de réinventer la roue avec en particulier la pratique appliquée à la théorie ;-)

Algorithme de Bresenham
Temps-x
Avatar de l’utilisateur
Expert
Expert
Messages : 2595
Enregistré en : juillet 2016
Localisation : Terre

#17 Message par Temps-x » dim. 30 oct. 2022 12:24

Bonsoir satinas, francois77, Claudius, et tout le forum,

satinas a écrit :Source du message Et pourquoi -65536 et pas -32768 pour tenir dans 2 octets ?

On refaisant les essais je m'aperçois qu'en n'a pas besoin de descendre aussi bas,avec 2 octets ça devrait être bon pour mode 8 bits et 16 bits(par la suite)

Dans ma deuxième méthode de l'algorithme de Bresenham on peut faire des cercles et des ronds ovalisés, c'est celle que je vais prendre. :-)

Elle fonctionne bien en basic, je la mets ci-dessous, au cas ou quelqu'un voudrais essayer de la faire en ASM,
de plus elle tient compte du format de l'écran.

satinas a écrit :Source du message Avec 1 octet on stocke des valeurs de -128 à +127, dont le signe est en b7.


Ok, c'est une bonne idée, Bigonoff on avait parlé dans le Chapitre N°1, à l'époque j'avais zappé, comme quoi qu'il faut jamais rien négligé en ASM

satinas a écrit :Source du message Je me suis planté plus haut

humour!! Voila le résultat à force de faire du C... dehors!!


Claudius a écrit :Source du message Cf. PIC Microcontroller Comparison Math Methods pour éviter de réinventer la roue avec en particulier la pratique appliquée à la théorie :-)


J'ai laissé tombé il y a bien longtemps ce site , qui est fort intéressant, mais tout en anglais, et puis.... je préfère réinventer la roue que copier une routine toute faite.

Merci pour ta participation et de vouloir aider :-)

Code en basic, qu'il faut traduire en ASM pour pic, :sifflotte: y a t'il un volontaire

Code : Tout sélectionner


   xc 
= 64: yc = 32: Rayon = 25: Couleur = 12      ' déclaration des données 

    Echelle = 128/64                               '
 longueur divisée par largeur de l'écran Oled pour avoir l’échelle
 
    x = 0
    y = Rayon

    Diametre = 2 * (1 - Rayon)

        do
            pset(xc + x, yc + y), Couleur
            
            pset(xc + x, yc - y), Couleur
              
            pset(xc - x, yc + y), Couleur
              
            pset(xc - x, yc - y), Couleur


      if ((Diametre + y) > 0) then
          y = y - 1
          Diametre = Diametre - (2 * (y * Echelle)) - 1
      end if

      if (x > Diametre) then
         x = x + 1
         Diametre = Diametre + (2 * x) + 1
      end if


    loop until y  <  0




==> A+
:roll: Les requins, c'est comme le langage ASM, c'est le sommet de la chaîne alimentaire. :wink:

Algorithme de Bresenham
Claudius
Avatar de l’utilisateur
Passioné
Passioné
Messages : 260
Âge : 69
Enregistré en : septembre 2015
Localisation : ELANCOURT (78 - YVELINES)
Contact :

#18 Message par Claudius » dim. 30 oct. 2022 20:13

Bonsoir,

Je préfère de loin l'algorithme de Bresenham tel que présenté dans l'article Algorithme de tracé d'arc de cercle de Bresenham avec notamment le tracé d'un octant (1/8 de cercle)

Code : Tout sélectionner

procédure tracerOctant (entier rayon, entier x_centre, entier y_centre)
   déclarer entier x, y, m ;
   x ← 0 ;
   y ← rayon ;                 // on se place en haut du cercle
   m ← 5 - 4*rayon ;           // initialisation
   Tant que x <= y             // tant qu'on est dans le second octant
      tracerPixel( x+x_centre, y+y_centre ) ;
      si m > 0 alors      // choix du point F
         y ← y - 1 ;
         m ← m-8*y ; // correspond au "d" des explications
      fin si ;
      x ← x+1 ;
      m ← m + 8*x+4 ;
   fin tant que ;
fin de procédure ;

... dont l'implémentation en Langage C se résume à:

Code : Tout sélectionner

#define RADIUS         40

int xc = 5;
int yc = 3;

// Algorithme de Bresenham (Wikipedia)
int x = 0;
int y = RADIUS;
int m = 5 - 4 * RADIUS;

while (x <= y) {
   tracePixel(x + xc, y + yc);   // Octant Sud-Sud-Est
   tracePixel(y + xc, x + yc);   // Octant Est-Sud-Est

   if (m > 0) {
      y = y - 1;
      m = m - 8 * y;
   }   

   x = x + 1;
   m = m + 8 * x + 4;
}
// Fin: Algorithme de Bresenham (Wikipedia)

... avec le résultat suivant sur les 2 octants Sud-Sud-Est et Est-Sud-Est (sortie sur une console "texte" )

Code : Tout sélectionner

O: Centre [5;3] Rayon [40]
X: Octant Sud-Sud-Est Y: Octant Est-Sud-Est
   x                    1                   2                   3                   4                   5
 y  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
  0 ......................................................................................................
  1 ......................................................................................................
  2 ......................................................................................................
  3 ..........0...............................................................................Y...........
  4 ..........................................................................................Y...........
  5 ..........................................................................................Y...........
  6 ..........................................................................................Y...........
  7 ..........................................................................................Y...........
  8 ..........................................................................................Y...........
  9 ..........................................................................................Y...........
 10 ........................................................................................Y.............
 11 ........................................................................................Y.............
 12 ........................................................................................Y.............
 13 ........................................................................................Y.............
 14 ......................................................................................Y...............
 15 ......................................................................................Y...............
 16 ......................................................................................Y...............
 17 ....................................................................................Y.................
 18 ....................................................................................Y.................
 19 ....................................................................................Y.................
 20 ..................................................................................Y...................
 21 ..................................................................................Y...................
 22 ................................................................................Y.....................
 23 ................................................................................Y.....................
 24 ..............................................................................Y.......................
 25 ............................................................................Y.........................
 26 ............................................................................Y.........................
 27 ..........................................................................Y...........................
 28 ........................................................................Y.............................
 29 ......................................................................Y...............................
 30 ......................................................................Y...............................
 31 ....................................................................Y.................................
 32 ..................................................................X...................................
 33 ..............................................................X.X.....................................
 34 ............................................................X.........................................
 35 ..........................................................X...........................................
 36 ......................................................X.X.............................................
 37 ....................................................X.................................................
 38 ................................................X.X...................................................
 39 ............................................X.X.......................................................
 40 ......................................X.X.X...........................................................
 41 ................................X.X.X.................................................................
 42 ........................X.X.X.X.......................................................................
 43 ..........X.X.X.X.X.X.X...............................................................................
 44 ......................................................................................................


A suivre...

Algorithme de Bresenham
Claudius
Avatar de l’utilisateur
Passioné
Passioné
Messages : 260
Âge : 69
Enregistré en : septembre 2015
Localisation : ELANCOURT (78 - YVELINES)
Contact :

#19 Message par Claudius » lun. 31 oct. 2022 18:36

Bonsoir Temps-x et tout le Forum,

S'agissant de l'algorithme présenté au post #17, sauf erreur de ma part, le loop until y < 0 est à corriger en loop until y >= 0
Malgré cette correction, cet algorithme montre, pour un cercle centré en [5;3] de rayon 40 avec Echelle = 1, une erreur au niveau du point de coordonnées [46;3] dont la distance au centre est de 41 au lieu de 40 par rapport au tracé du post #18

Pour preuve:

Code : Tout sélectionner

Centre [5;3] Rayon [40]
   x                    1                   2                   3                   4                   5
 y  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
  0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
  1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
  2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
  3 . . . . . 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . .
  4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . .
  5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . .
  6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . .
  7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . .
  8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . .
  9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . .
 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . .
 11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . .
 12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . .
 13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . .
 14 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . .
 15 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . .
 16 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . .
 17 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . .
 18 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . .
 19 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . .
 20 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . .
 21 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . .
 22 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . .
 23 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . .
 24 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . . .
 25 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . . .
 26 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . . . .
 27 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . . . . .
 28 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . . . . . .
 29 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . . . . . . .
 30 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . . . . . . . .
 31 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . . . . . . . . .
 32 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . . . . . . . . . .
 33 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . . . . . . . . . . .
 34 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X X . . . . . . . . . . . . . . . . . . .
 35 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . . . . . . . . . . . . . .
 36 . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . . . . . . . . . . . . . . .
 37 . . . . . . . . . . . . . . . . . . . . . . . . . . X X . . . . . . . . . . . . . . . . . . . . . . .
 38 . . . . . . . . . . . . . . . . . . . . . . . . X X . . . . . . . . . . . . . . . . . . . . . . . . .
 39 . . . . . . . . . . . . . . . . . . . . . . X X . . . . . . . . . . . . . . . . . . . . . . . . . . .
 40 . . . . . . . . . . . . . . . . . . . . X X . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
 41 . . . . . . . . . . . . . . . . X X X X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
 42 . . . . . . . . . . . . X X X X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
 43 . . . . . X X X X X X X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
 44 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


NB: Je conçois que tous les rayons ne sont pas égaux à 40 et même plus grands du fait de l'interpolation mais la moindre des choses est que ceux-ci soient corrects sur les abscisses et les ordonnées comme pour le point [5;43] dont la distance au centre [5;3] est bien égale à 40

Comme quoi, avant d'envisager un portage, il est impératif de valider d'une manière exhaustive l'algorithme et en général dans un langage évolué indépendamment de tout périphérique; ici un écran remplacé par une console texte permettant de vérifier au pixel près ;-)

A suivre...

Algorithme de Bresenham
Temps-x
Avatar de l’utilisateur
Expert
Expert
Messages : 2595
Enregistré en : juillet 2016
Localisation : Terre

#20 Message par Temps-x » lun. 31 oct. 2022 19:18

Bonsoir Claudius, et tout le Forum,

Claudius a écrit :Source du message sauf erreur de ma part, le loop until y < 0 est à corriger en loop until y >= 0


Il n'y a pas d'erreur, c'est bien loop until y < 0, j'ai vérifié

Je ne cherche pas à faire un cercle avec l'algorithme de Bresenham en langage PC, car je sais le faire, ce que je cherche à faire, c'est traduire le code Basic du post 17 en ASM pour Pic, et c'est loin d'être simple, Echelle 2 pour un écran Oled

:sifflotte: on se retrouve encore une fois de plus avec un code C en section ASM, j'ai rien contre le C, mais quand même ça commence à devenir ennuyeux.

Merci ! quand même pour ton esprit de participation :wink:

==> A+
:roll: Les requins, c'est comme le langage ASM, c'est le sommet de la chaîne alimentaire. :wink:


Retourner vers « Langage ASM »

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 50 invités