Des cercles a dessiner sans "circle"

[Micoute]

Bravo Ar-s c'est très réussi, j'adore et je te remercie pour le partage.

[Mesa]

Trouvés quelque part avec les algo de bresenham et d'andre.

Code : Tout sélectionner

;https://fr.wikipedia.org/wiki/Algorithme_de_trac%C3%A9_de_cercle_d%27Andres
;https://fr.wikipedia.org/wiki/Algorithme_de_trac%C3%A9_d%27arc_de_cercle_de_Bresenham

Structure XY
  X.i
  Y.i  
EndStructure
Global NewList Cercle_Bresenham.XY()
Global NewList Cercle_Andres.XY()

;algorithme de tracé de cercle de Bresenham
Procedure TracerCercleBresenham(rayon,x_centre,y_centre)
  y=rayon ;    // on se place en haut du cercle 
  m=5-4*rayon ;      // initialisation
  While x <= y;    // tant qu'on est dans le second octant
    AddElement(cercle_bresenham())
    cercle_bresenham()\x=x+x_centre:cercle_bresenham()\y=y+y_centre
    AddElement(cercle_bresenham())
    cercle_bresenham()\x=y+x_centre:cercle_bresenham()\y=x+y_centre
    AddElement(cercle_bresenham())
    cercle_bresenham()\x=-x+x_centre:cercle_bresenham()\y=y+y_centre
    AddElement(cercle_bresenham())
    cercle_bresenham()\x=-y+x_centre:cercle_bresenham()\y=x+y_centre
    AddElement(cercle_bresenham())
    cercle_bresenham()\x=x+x_centre:cercle_bresenham()\y=-y+y_centre
    AddElement(cercle_bresenham())
    cercle_bresenham()\x=y+x_centre:cercle_bresenham()\y=-x+y_centre
    AddElement(cercle_bresenham())
    cercle_bresenham()\x=-x+x_centre:cercle_bresenham()\y=-y+y_centre
    AddElement(cercle_bresenham())
    cercle_bresenham()\x=-y+x_centre:cercle_bresenham()\y=-x+y_centre
    If m > 0 ;choix du point F
      y - 1
      m=m-8*y
    EndIf
    x+1 ;
    m=m + 8*x+4 ;
  Wend
EndProcedure

;algorithme de tracé de cercle d'Andres
Procedure TracerCercleAndres(rayon,x_centre,y_centre)
  ;x=0
  y=rayon
  d=rayon - 1
  While y>=x 
    AddElement(cercle_Andres())
    Cercle_Andres()\x=x+x_centre:Cercle_Andres()\y=y+y_centre
    AddElement(Cercle_Andres())
    Cercle_Andres()\x=y+x_centre:Cercle_Andres()\y=x+y_centre
    AddElement(Cercle_Andres())
    Cercle_Andres()\x=-x+x_centre:Cercle_Andres()\y=y+y_centre
    AddElement(Cercle_Andres())
    Cercle_Andres()\x=-y+x_centre:Cercle_Andres()\y=x+y_centre
    AddElement(Cercle_Andres())
    Cercle_Andres()\x=x+x_centre:Cercle_Andres()\y=-y+y_centre
    AddElement(Cercle_Andres())
    Cercle_Andres()\x=y+x_centre:Cercle_Andres()\y=-x+y_centre
    AddElement(Cercle_Andres())
    Cercle_Andres()\x=-x+x_centre:Cercle_Andres()\y=-y+y_centre
    AddElement(Cercle_Andres())
    Cercle_Andres()\x=-y+x_centre:Cercle_Andres()\y=-x+y_centre
    If d >= 2*x
      d=d-2*x-1
      x+1
    ElseIf d < 2*(rayon-y);d <= 2*(rayon-y)
      d=d+2*y-1
      y-1   
    Else 
      d=d+2*(y-x-1)
      y-1
      x+1
    EndIf
  Wend
EndProcedure

If InitSprite() = 0 Or InitKeyboard() = 0
  MessageRequester("Error", "Sprite system can't be initialized", 0)
  End
EndIf
OpenWindow(0, 0, 0,  1024, 768, "Un écran dans une fenêtre...", #PB_Window_SystemMenu | #PB_Window_ScreenCentered)

OpenWindowedScreen(WindowID(0), 0, 0, 1024, 768)
ClearScreen(RGB(0,0,0))

;calcul 50 cercles concentriques avec les 2 méthodes, en incrémentant le rayon
For i=50 To 100
  TracerCercleAndres(i,100,160)
  TracerCercleBresenham(i,360,160)
Next i


Repeat
  ; Il est très important de traiter tous les évènements restants dans la file d'attente à chaque tour
  ;
  Repeat
    Event = WindowEvent()
    
    Select Event 
      Case #PB_Event_CloseWindow
        End 
    EndSelect
  Until Event = 0
  
  FlipBuffers() 
  StartDrawing(ScreenOutput())
  ;trace les cercles calculés avec Bresenham (en vert)
  ForEach  cercle_bresenham()
    Plot(cercle_bresenham()\x,cercle_bresenham()\y,RGB(0,255,0)) 
  Next
  ;trace les cercles calculés avec Andres (en jaune)
  ForEach  cercle_Andres()
    Plot(cercle_Andres()\x,cercle_Andres()\y,RGB(255,255,0)) 
  Next
  StopDrawing()
;   Delay(1)
  ExamineKeyboard()
Until KeyboardPushed(#PB_Key_Escape)

M.

[case]

Code : Tout sélectionner

Procedure plt(x,y,c) ; pour être sur que l'on dessine dans l'écran courant
  If x>=0 And y>=0 And x<=639 And y<=479
    Plot(x,y,c)
  EndIf
EndProcedure


Procedure rasterCircle(cx, cy, r, Color) ;  SMartin  https://www.purebasic.fr/english/viewtopic.php?f=13&t=36896
  Protected f= 1 - r
  Protected ddF_X, ddF_Y = -2 * r
  Protected x, y = r
  Plt(cx, cy + r, Color)
  Plt(cx, cy - r, Color)
  Plt(cx + r, cy, Color)
  Plt(cx - r, cy, Color)
  While x < y
    If f >= 0
      y - 1
      ddF_Y + 2
      f + ddF_Y
    EndIf
    x + 1
    ddF_X + 2
    f + ddF_X + 1
    Plt(cx + x, cy + y, Color)
    Plt(cx - x, cy + y, Color)
    Plt(cx + x, cy - y, Color)
    Plt(cx - x, cy - y, Color)
    Plt(cx + y, cy + x, Color)
    Plt(cx - y, cy + x, Color)
    Plt(cx + y, cy - x, Color)
    Plt(cx - y, cy - x, Color)
  Wend
EndProcedure
InitSprite()
InitKeyboard()
OpenScreen(640,480,32,"")
Repeat
  ExamineKeyboard()
  StartDrawing(ScreenOutput())
  rasterCircle(Random(640),Random(480),Random(80),RGB(Random(200)+55,Random(200)+55,Random(200)+55))
StopDrawing()
FlipBuffers()
Until KeyboardPushed(#PB_Key_Escape)

[Ollivier]

Case a défenestré la racine carré !

[case]

c'est pas vraiment de mon cru

[Ollivier]

Code : Tout sélectionner

.-------- --
|        |  |
|        |  |
|   b    | d|
|        |  |
.-------- --
|    c   | a|
.-------- --

Passons mes déboires pour faire un schéma : admettons ! Même si c'est moche donc...

1) << a >> c'est un carré de côté 1 et de surface 1
2) << b >> c'est un carré de côté n et de surface n * n
3) << c >> et << d >> font la même surface n * 1 et 1 * n

Mettons que b fasse 10 de côté...
Ce qui fait 10 * 10 = 100 de surface.
Comme ça c'est des chiffres ronds.

On a donc b qui fait 100 mètres carré pour être concret.

On veut savoir la surface totale (qui englobe les 4 zones).

C'est 100 + n + n + 1.
n = 10
Résultat c'est 100 + 10 + 10 + 1.
Et c'est égal à 121.

Aussi...
Comme c'est 100 + n + n + 1,
alors c'est 100 + 2n + 1 !!
C'est même 100 + (2n + 1).

Conclusion : quand on a un nombre N au pif (ici c'est 10)
et que l'on sait son carré (ici c'est 100),
alors on sait assez simplement (N + 1) au carré.

(N + 1) au carré = N au carré + (2N + 1)

N au carré nous soule ?
Pas de problème ! On commence à zéro :

0 + 2*0 + 1 = 1
1 + 2*1 + 1 = 4
4 + 2*2 + 1 = 9
9 + 2*3 + 1 = 16
16 + 2*4 + 1 = 25
etc...

On voit bien que 0, 1, 4, 9, 16, etc... sont les nombres au carré, et, si l'on exclut 2*x parce que c'est x + x, on trouve donc les carrés avec juste des additions.

C'est la méthode utilisée. C'est Pythagore avec son théorème remixé dans un hyper-plan* plutôt que dans un plan pour s'épargner un calcul de racine.

Edit : Pour hyper-plan, quand je vois la définition wiki, je me dis << Ahm merde... C'est encore aut'chose >> donc oubliez la notion d'hyper-plan que j'ai écrit : mathématiquement, plutôt que << hyper-plan >>, on parlera de << plan tordu >> . Question de concept : on ne donne pas r, mais r*r (r au carré). C'est à l'utilisateur de la fonction de calculer la racine du rayon au carré...

(note du traducteur feat Doliprane)

[Ollivier]

Les inconvénients de cette méthode :

1) On ne peut pas dessiner un arc au degré près (ou au radian près).
2) On ne peut pas... (tenez-vous à votre souris et votre kilo de Doliprane)... dessiner une ellipse autre que celle verticale et celle horizontale.

Les avantages :

1) La simplicité de calcul (additions et soustractions)
2) La rapidité en l'absence de co-processeur

[SPH]

A votre avis, comment fait fred pour dessiner point par point un cercle
Quelle est sa routine

[Ollivier]

T'as de ces questions... Au pif, je dirais qu'il utilise cet algo (fourni par case et mesa). Sauf qu'il le fait plein (disque) donc il doit "tracer" les deltas en y, c'est-à-dire pré-calculer les sauts de chaque ligne de pixels, vu que l'électronique privilégie le tracé horizontal.

Tu veux un code ?

[SPH]

Tu veux un code ?

Balance

[Ollivier]

Je pense à un truc comme ça : (ça donne quoi ?)

Code : Tout sélectionner

;**********************************************************************************************************
; (j'ai beau en rajouter des '*' ça me coupe tjr les lignes de codes...
Procedure Disc(cx,cy,r,color)
f = 1 - r
ddF_Y = -2 * r
y = r
Repeat
   If f > 0
      Box(cx - x, cy + y, 2 * x, 1, color)
      Box(cx - x, cy - y, 2 * x, 1, color)
      Box(cx - y, cy + x, 2 * y, OldX - x, color)
      Box(cx - y, cy - x, 2 * y, x - OldX, color)
      y - 1
      ddF_Y + 2
      f + ddF_Y
      oldX = x
   EndIf
   x + 1
   ddF_X + 2
   f + ddF_X + 1
Until x > y
EndProcedure

Mais tu ne feras pas de texture sans trigo. Ça je te l'assure, à moins que, comme d'hab, je me trompe...

[SPH]

Je pensais plus a un cercle évidé

[Ollivier]

Tu peux remercier case, mesa et tous les autres auteurs à l'origine de ce code. Je n'ai fait que modifier ce que case a mis à disposition, bien que je voyais le 2n+1 dans le code proposé par mesa.

Aussi tu peux faire du texturing mais c'est piégeux : c'est trop "carré", "perpendiculaire". En gros, on pourrait mettre le planisphère avec le même principe. Tu pourrais même faire tourner la surface terrestre dans le sens est-ouest plutôt rapidement. Mais impossible d'incliner alors. Impossible de toucher les subtilités autres que les angles obliques et droits.

La trigo est impossible à contourner. C'est beau la trigo : ce sont juste des vagues, des vagues parfaites en fait. Un cercle, ce sont deux vagues en quadrature, c'est-à-dire que l'une suit l'autre, comme un écho sans perte, et la distribution des deux fait un cercle...

[Ollivier]

Qu'est-ce que tu entends par << cercle évidé >> ?

Parce que tu dis que tu veux refaire un jeu ancien assez connu. Seulement, moi je suis vide de cette culture. Donc, précise, mets un lien Youtube ou un titre.

Normalement, avec ce qu'il y a au-dessus, c'est suffisant et les calculs sont là, non optimisés, spécialement pour faire les modifs. N'hésite pas aussi à demander à Fred si c'est cet algo aussi : tu demandes ici ce qu'il a fait alors qu'il est présent sur le site anglais pour sa dernière beta... T'es pas toujours réveillé là !

[SPH]

Qu'est-ce que tu entends par << cercle évidé >> ?

Parce que tu dis que tu veux refaire un jeu ancien assez connu. Seulement, moi je suis vide de cette culture. Donc, précise, mets un lien Youtube ou un titre.

Normalement, avec ce qu'il y a au-dessus, c'est suffisant et les calculs sont là, non optimisés, spécialement pour faire les modifs. N'hésite pas aussi à demander à Fred si c'est cet algo aussi : tu demandes ici ce qu'il a fait alors qu'il est présent sur le site anglais pour sa dernière beta... T'es pas toujours réveillé là !

Nan mais la, Shadow, sort de ce corps !!

Code : Tout sélectionner

DrawingMode(#PB_2DDrawing_Outlined)