Algorithme de Bresenham

Partagez votre expérience de PureBasic avec les autres utilisateurs.
Avatar de l’utilisateur
venom
Messages : 3071
Inscription : jeu. 29/juil./2004 16:33
Localisation : Klyntar
Contact :

Algorithme de Bresenham

Message par venom »

Bonjour,

Voilà comme tout le monde en ce moment, j'ai un peu de temps pour coder. (fin pas tant que ça en faite) :lol:
Une connaissance m'a fait connaitre l'Algorithme de Bresenham. Bon je ne vais pas décrire ici dans le detail ce qu'est l'Algorithme de Bresenham. Wikipedia le fait tres bien. Ou un moteur de recherche quelconque. La toile ne manque a ce sujet et en français.
Si je dois résumé, ça permet de tracer une ligne entre 2 ponts. Du moins dans mon cas, car l'Algorithme a depuis était décliner pour toutes sortes de formes.

Je me suis donc dit : "tiens voilà un défi a essayer de relever". Forcément, si je post c'est que c'est réussi. :wink:
Même si j'en vois certain qui vont dire : "Ba il y a la fonction line() qui fait ça très bien". Tout a fait comme ci-dessous :

Code : Tout sélectionner

  If OpenWindow(0, 0, 0, 200, 200, "Line", #PB_Window_SystemMenu | #PB_Window_ScreenCentered)
    If CreateImage(0, 200, 200) And StartDrawing(ImageOutput(0))
      Box(0, 0, 200, 200, RGB(255, 255, 255))
      For Width = 1 To 180 Step 5
        Line(10, 10, Width, 180, RGB(Random(255), Random(255), Random(255)))
      Next Width
      StopDrawing() 
      ImageGadget(0, 0, 0, 200, 200, ImageID(0))
    EndIf
    
    Repeat
      Event = WaitWindowEvent()
    Until Event = #PB_Event_CloseWindow
  EndIf
Voir même LineXY() aussi.

Mais c'est avant tout pour ma culture personnelle, le plaisir de gratter un peut de code. Et aussi vous allez voir dans certain cas elle peut s’avérer utile. (même si aujourd'hui je n'en ai pas l'utilité)

Voici donc dans un premier temps, l'Algorithme de Bresenham seul qui a était réalisé:

Code : Tout sélectionner

Procedure Bresenham(x1, y1, x2, y2)

ex = Abs(x2-x1)
ey = Abs(y2-y1)
dx = 2*ex
dy = 2*ey
dxx = ex
dyy = ey
i = 0
xincr = 1
yincr = 1

  If (x1>x2)
    xincr = -1
  EndIf
 
  If (y1>y2)
    yincr = -1
  EndIf
 

;{ cas 1 Dx plus grand que Dy
  If (dxx>dyy)
   While i<=dxx
     ; on récupere les coordonnees via x1 et y1
     Debug x1
     Debug y1
    i+1
     
    x1+ xincr
    ex - dy
 
     If ex < 0
      y1+yincr
      ex+dx
     EndIf

   Wend
  EndIf
;}
 
 
;{ cas 2 Dx plus petit que Dy
  If (dxx<dyy)
   While i<=dyy
    ; on récupere les coordonnees via x1 et y1
     Debug x1
     Debug y1
    i+1
   
    y1+ yincr
    ey - dx
 
     If ey < 0
      x1+xincr
      ey+dy
     EndIf

   Wend
  EndIf
;}
 
 
;{ cas 3 Dx = Dy
  If (dxx=dyy)
   While i<=dyy
    ; on récupere les coordonnees via x1 et y1
     Debug x1
     Debug y1
    i+1
   
    y1+ yincr
    ey - dx
 
     If ey < 0
      x1+xincr
      ey+dy
     EndIf

   Wend
  EndIf
;}
EndProcedure
Juste avant je vous ai dit qu'elle pouvait s’avérer utile, car oui pour tracer une ligne PureBasic le fait très bien, mais quand il s'agit de tracer une ligne dans un tableau ? C'est plus délicat. :lol:

Voici donc un code qui montre le fonctionnement dans un tableau.
Pour utilisé le code, tout ce fait a la souris.
Le bouton gauche affiche le point de départ de la ligne. Le bouton droit affiche le point d'arrivé.

Code : Tout sélectionner

; //////////////////////////////////////////////////
; //      Autor :         Venom                   //
; //      Project name :  Algorithme de Bresenham //
; //      Version :       V 2.0                   //
; //      Compilator :    PureBasic V5.72         //
; //      Date :          29/03/2020              //
; //      OS :            Windows 10              //
; //////////////////////////////////////////////////


;- Window Constants
Enumeration
  #Window_0
EndEnumeration

;- Gadgets Constants
Enumeration
  #AffichageGrille
  #AffichagePointDepart
  #AffichagePointArriver
  #AffichagePointTracer
EndEnumeration


Global TailleCarre = 10, LargeurTotal = 600, HauteurTotal = 600
Global NbCaseLargeur = LargeurTotal/TailleCarre, NbCaseHauteur = HauteurTotal/TailleCarre

Global x1 = 0, y1 = 0, x2 = 59, y2 = 59 ; positionnement au demarrage des points de depart et arriver

Global Dim Tableau(NbCaseLargeur, NbCaseHauteur)



; initialisations
InitSprite()
InitKeyboard()
InitMouse()


; declaration des procedures
Declare AffichageGrille()
Declare PointDepart()
Declare PointArriver()
Declare PointTracer()
Declare ViderTableau()
Declare Bresenham(x1, y1, x2, y2)


;==================================================================================================
;==================================================================================================
;                                     OUVERTURE DE LA FENETRE
;==================================================================================================
;==================================================================================================
  If OpenWindow(#Window_0, 0, 0, 600, 600, "Algorithme de Bresenham", #PB_Window_SystemMenu | #PB_Window_MinimizeGadget | #PB_Window_TitleBar | #PB_Window_ScreenCentered)
   OpenWindowedScreen(WindowID(#Window_0), 0, 0, 600, 600)
    ; on charge les differents sprites
     AffichageGrille()
     PointDepart()
     PointArriver()
     PointTracer()

  EndIf 
  
  
;==================================================================================================
;==================================================================================================
;                                            BOUCLES
;==================================================================================================
;==================================================================================================
  Repeat
    Repeat
     Event = WindowEvent()
      Select Event 
       Case #PB_Event_CloseWindow
        End 
      EndSelect
    Until Event = 0
    
    ExamineMouse()
    
    ; creer et affiche le curseur de la souris
    If StartDrawing(ScreenOutput())
      DrawingMode(#PB_2DDrawing_Transparent)
      DrawText(MouseX(), MouseY(), Chr(42), RGB(255,0,255))
     StopDrawing()
    EndIf 
    
    ; on appui sur le bouton gauche de la souris qui correspond au point de depart (vert)
    If MouseButton(#PB_MouseButton_Left) <> 0
      x1 = MouseX()/TailleCarre
      y1 = MouseY()/TailleCarre
    EndIf 
    
    ; on appui sur le bouton droit de la souris qui correspond au point d'arriver (rouge)
    If MouseButton(#PB_MouseButton_Right) <> 0
      x2 = MouseX()/TailleCarre
      y2 = MouseY()/TailleCarre
    EndIf

    FlipBuffers() 
    ClearScreen(RGB(0, 0, 0))
    
    ; on affiche la grille de fond
    DisplaySprite(#AffichageGrille, 0, 0)
    
    ; on appel la procedure qui affiche le résultat du tracer
    Bresenham(x1, y1, x2, y2)
    
    ; on affiche les ponts de depart et arriver sur le tracer
    DisplaySprite(#AffichagePointDepart, x1*TailleCarre, y1*TailleCarre)
    DisplaySprite(#AffichagePointArriver, x2*TailleCarre, y2*TailleCarre)
    
    
    ExamineKeyboard()
  Until KeyboardPushed(#PB_Key_Escape)
   End 
 
 
 
 
 
;==================================================================================================
;==================================================================================================
;                                           PROCEDURES
;==================================================================================================
;==================================================================================================
Procedure AffichageGrille()
 CreateSprite(#AffichageGrille, LargeurTotal, HauteurTotal)
  If StartDrawing(SpriteOutput(#AffichageGrille))
   For x = 0 To 800 Step 0
    x+TailleCarre
    Line(x, 0, 1, 800, $303030) ; ligne verticale
    Line(0, x, 800, 1, $303030) ; ligne horizontale
   Next 
   StopDrawing()
  EndIf
EndProcedure
  

Procedure PointDepart()
 CreateSprite(#AffichagePointDepart, TailleCarre, TailleCarre)
  If StartDrawing(SpriteOutput(#AffichagePointDepart))
   Box(0, 0, TailleCarre, TailleCarre, #Green)
   StopDrawing()
  EndIf
  
  Tableau(x1, y1) = 1
EndProcedure


Procedure PointArriver()
 CreateSprite(#AffichagePointArriver, TailleCarre, TailleCarre)
  If StartDrawing(SpriteOutput(#AffichagePointArriver))
   Box(0, 0, TailleCarre, TailleCarre, #Red)
   StopDrawing()
  EndIf
 
  Tableau(x2, y2) = 2
EndProcedure


Procedure PointTracer()
 CreateSprite(#AffichagePointTracer, TailleCarre, TailleCarre)
  If StartDrawing(SpriteOutput(#AffichagePointTracer))
   Box(0, 0, TailleCarre, TailleCarre, #Yellow)
   StopDrawing()
  EndIf
EndProcedure


Procedure ViderTableau()
For tx = 0 To NbCaseLargeur-1
 For ty = 0 To  NbCaseHauteur-1
   
  Tableau(tx, ty) = 0

 Next 
Next  
EndProcedure


Procedure Bresenham(x1, y1, x2, y2)
; Debug "x1 -> " + x1
; Debug "y1 -> " + y1
; Debug "x2 -> " + x2 
; Debug "y2 -> " + y2
; Debug "ex -> " + ex 
; Debug "ey -> " + ey 
; Debug "dx -> " + dx 
; Debug "dy -> " + dy
; Debug "dxx -> " + dxx 
; Debug "dyy -> " + dyy
  
  
; on vide le tableau pour afficher le nouveau tracer  
ViderTableau()

; on commence les calculs pour le tracer
ex = Abs(x2-x1)
ey = Abs(y2-y1)
dx = 2*ex
dy = 2*ey
dxx = ex
dyy = ey
i = 0
xincr = 1
yincr = 1


  If (x1>x2)
    xincr = -1
  EndIf 
  
  If (y1>y2)
    yincr = -1 
  EndIf 
  

;{ cas 1 Dx plus grand que Dy
  If (dxx>dyy)
   While i<=dxx
      
    Tableau(x1, y1) = 3 ; on récupere les coordonnees du tracer pour les integrés au tableau ID 3
    i+1
     
    x1+ xincr
    ex - dy
  
     If ex < 0
      y1+yincr
      ex+dx 
     EndIf

   Wend 
  EndIf 
;}
  
  
;{ cas 2 Dx plus petit que Dy
  If (dxx<dyy)
   While i<=dyy
  
    Tableau(x1, y1) = 3  ; on récupere les coordonnees du tracer pour les integrés au tableau ID 3
    i+1
    
    y1+ yincr
    ey - dx
  
     If ey < 0
      x1+xincr
      ey+dy 
     EndIf 
 
   Wend 
  EndIf 
;}
  
  
;{ cas 3 Dx = Dy
  If (dxx=dyy)
   While i<=dyy
    Tableau(x1, y1) = 3  ; on récupere les coordonnees du tracer pour les integrés au tableau ID 3
    i+1
    
    y1+ yincr
    ey - dx
  
     If ey < 0
      x1+xincr
      ey+dy 
     EndIf 
 
   Wend 
  EndIf 
;}
  
   
; on affiche la grille du fond
DisplaySprite(#AffichageGrille, 0, 0)
  
  
; on affiche le tracer contenue dans le tableau ID 3
For tx = 0 To NbCaseLargeur-1
 For ty = 0 To  NbCaseHauteur-1
   
  If Tableau(tx, ty) = 3 ; tracer
   DisplaySprite(#AffichagePointTracer, tx*TailleCarre, ty*TailleCarre)
  EndIf 
 
 Next 
Next 
EndProcedure
J'ai commenté le code un minimum pour y voir un peut. J'imagine qu'il y a d'autres astuces pour arrivée a ce résultat. :wink:

Ps : vous pouvez changez la dimension de la grille via le variable TailleCarre ligne 25 :wink:
Ps² : j'ai suivi cette vidéo qui explique bien le déroulement.






@++
Dernière modification par venom le mer. 01/avr./2020 9:30, modifié 1 fois.
Windows 10 x64, PureBasic 5.73 x86 & x64
GPU : radeon HD6370M, CPU : p6200 2.13Ghz
Ollivier
Messages : 4190
Inscription : ven. 29/juin/2007 17:50
Localisation : Encore ?
Contact :

Re: Algorithme de Bresenham

Message par Ollivier »

C'est cool.

De tête, Comtois en touché un mot. Le Soldat Inconnu aussi. Sûrement G-Rom, et une bonne poignée d'autre personnes. Peut-être fig aussi. A voir.

Donc, évidemment c'est toujours utile et toujours un bon défi personnel.

Les lignes de code sont courtes donc, même sans ordinateur, je peux jeter un oeil de temps en temps...



Merci Venom
Avatar de l’utilisateur
microdevweb
Messages : 1798
Inscription : mer. 29/juin/2011 14:11
Localisation : Belgique

Re: Algorithme de Bresenham

Message par microdevweb »

Bonjour j'ai du utiliser cet algo en C pour une projet scolaire, avec une base de donnée de 500.000 record on devait créer les cartes d'identité du personnel (tout en code pas de sdl ni aucune lib) selon certains critères bien défini, c'est cool de partager cela avec pour Pb



Image
Windows 10 64 bits PB: 5.70 ; 5.72 LST
Work at Centre Spatial de Liège
Avatar de l’utilisateur
microdevweb
Messages : 1798
Inscription : mer. 29/juin/2011 14:11
Localisation : Belgique

Re: Algorithme de Bresenham

Message par microdevweb »

Juste à titre indicatif voici le code en C

Code : Tout sélectionner

/*----------------------------------------------------------
** FUNCTION NAME    : _bresenham
** PROCESS          : draw a line with a angle
** ARGUMENTS        : int x1        -> position x to start
*                     int y1        -> position y to start
*                     int x2        -> position x to end
*                     int y2        -> position y to end
*                     int color     -> color used to draw
** RETURN           : void
** NOTE             : use bresenham algorithm
-----------------------------------------------------------*/
static void _bresenham(image *img,int x1,int y1,int x2,int y2,int color)
{

    int dx = abs(x2-x1), sx = x1<x2 ? 1 : -1;
    int dy = abs(y2-y1), sy = y1<y2 ? 1 : -1;
    int err = (dx>dy ? dx : -dy)/2, e2,x = x1,y = y1;

    while(1)
    {
        set_pixel(img,x,y,color);
        if (x==x2 && y==y2)
            break;
        e2 = err;
        if (e2 >-dx)
        {
            err -= dy;
            x += sx;
        }
        if (e2 < dy)
        {
            err += dx;
            y += sy;
        }
    }
}
Windows 10 64 bits PB: 5.70 ; 5.72 LST
Work at Centre Spatial de Liège
Avatar de l’utilisateur
venom
Messages : 3071
Inscription : jeu. 29/juil./2004 16:33
Localisation : Klyntar
Contact :

Re: Algorithme de Bresenham

Message par venom »

Salut microdevweb,

Merci de ton retour et partage.






@++
Windows 10 x64, PureBasic 5.73 x86 & x64
GPU : radeon HD6370M, CPU : p6200 2.13Ghz
Ollivier
Messages : 4190
Inscription : ven. 29/juin/2007 17:50
Localisation : Encore ?
Contact :

Re: Algorithme de Bresenham

Message par Ollivier »

Une femme à barbe. C'est original.
Avatar de l’utilisateur
GallyHC
Messages : 1703
Inscription : lun. 17/déc./2007 12:44

Re: Algorithme de Bresenham

Message par GallyHC »

Bonjour tous,

@microdevweb > avec du ternaire c toujours mieux (y a quelque commande qui manque a PB) ^^

Comme aussi pour un "If", le "AndAlso", qui peut permettre de faire avec un if tout les tests en une ligne en évitant des erreurs.

en tout cas sympa comme petit défis perso (y a du bon même dans c'est moment difficile).

Cordialement,
GallyHC
Configuration : Tower: Windows 10 (Processeur: i7 "x64") (Mémoire: 16Go) (GeForce GTX 760 - 2Go) - PureBasic 5.72 (x86 et x64)
Avatar de l’utilisateur
microdevweb
Messages : 1798
Inscription : mer. 29/juin/2011 14:11
Localisation : Belgique

Re: Algorithme de Bresenham

Message par microdevweb »

@Olivier

Et voici son grand-père

Image
Windows 10 64 bits PB: 5.70 ; 5.72 LST
Work at Centre Spatial de Liège
G-Rom
Messages : 3626
Inscription : dim. 10/janv./2010 5:29

Re: Algorithme de Bresenham

Message par G-Rom »

Tu peut optimiser un peu , voici 2/3 astuces :

La première, utilise des tableaux 1D , beaucoup plus rapide que 2 ou x dimension.
pour passer de deux dimension a une :
index = x + largeur * y
et l'inverse :
x = index % largeur
y = index / largeur
Privilégie FillMemory() en place de deux boucle imbriqué pour "vidé" un tableau :
Dim Tableau.l(640,480)
FillMemory(@Tableau(),640*480,0,#PB_Long)
FillMemory est extrêmement rapide.
Avatar de l’utilisateur
venom
Messages : 3071
Inscription : jeu. 29/juil./2004 16:33
Localisation : Klyntar
Contact :

Re: Algorithme de Bresenham

Message par venom »

Salut G-Rom.

Merci pour tes remarques, je ne connais pas FillMemory() je vais y jeter un œil :wink: même si a mon niveau je trouve le code déjà rapide :lol:






@++
Windows 10 x64, PureBasic 5.73 x86 & x64
GPU : radeon HD6370M, CPU : p6200 2.13Ghz
Ollivier
Messages : 4190
Inscription : ven. 29/juin/2007 17:50
Localisation : Encore ?
Contact :

Re: Algorithme de Bresenham

Message par Ollivier »

@G-Rom
G-Rom a écrit :La première, utilise des tableaux 1D , beaucoup plus rapide que 2 ou x dimension.
Je suis étonné que ce soit plus rapide, "fait maison" plutôt que natif.Dim pix(x, y)(sans le débogueur). C'est vraiment plus rapide en 1D ?
G-Rom
Messages : 3626
Inscription : dim. 10/janv./2010 5:29

Re: Algorithme de Bresenham

Message par G-Rom »

Ollivier a écrit :@G-Rom
G-Rom a écrit :La première, utilise des tableaux 1D , beaucoup plus rapide que 2 ou x dimension.
Je suis étonné que ce soit plus rapide, "fait maison" plutôt que natif.Dim pix(x, y)(sans le débogueur). C'est vraiment plus rapide en 1D ?
Oui, l'utilisation d'un tableau 1D à toujours été plus rapide, je l'ai aussi constaté dans plusieurs langage différents, qu'ils soient compilés ou interprétés.

Code : Tout sélectionner



Dim SCREEN_2D.l(1024,768)

Dim SCREEN_1D.l( 1024 * 768 )

*BUFFER = AllocateMemory(1024 * 768 * 4)

Delay(100)

A1 = ElapsedMilliseconds()
For i = 0 To 59
  For y = 0 To 767
    For x = 0 To 1023
      SCREEN_2D(x,y) = Random($FFFFFF)
    Next
  Next
Next 
A2 = ElapsedMilliseconds()

Delay(100)

B1 = ElapsedMilliseconds()
For i = 0 To 59
  For y = 0 To 767
    For x = 0 To 1023
      INDEX = x + 1024 * y
      SCREEN_1D(INDEX) = Random($FFFFFF)
    Next
  Next
Next 
B2 = ElapsedMilliseconds()

Delay(100)

C1 = ElapsedMilliseconds()
For i = 0 To 59
  For y = 0 To (767*4) Step 4
    For x = 0 To (1023*4) Step 4
      PokeL(*BUFFER + x + 1024 * y,Random($FFFFFF))       
    Next
  Next
Next 
C2 = ElapsedMilliseconds()




MessageRequester("","2D = " + Str(A2-A1) + "ms 1D = " + Str(B2-B1) + "ms Poke = " + Str(C2-C1)) 

Ollivier
Messages : 4190
Inscription : ven. 29/juin/2007 17:50
Localisation : Encore ?
Contact :

Re: Algorithme de Bresenham

Message par Ollivier »

Effectivement : carrément plus rapide, même avec un tableau statique en structure...

Code : Tout sélectionner

n = p\i[x]\j[y]
. Donc 1D c'est plus rapide.
Répondre