Bresenham Kreisbewegung 2. Oktant

[Keine A. (karabennemsi)]

Ich nutze jetzt zur Ansteuerung von zwei Schrittmotoren um einen Kreis 
zu fahren den Bresenham Algorithmus.

Der Psudocode für den ersten Oktankt sieht folgendermaßen aus (von 
Wikipedia kopiert):

x = r
y = 0
fehler = r

WHILE y < x
   REM Schritt in schnelle Richtung
   dy = y*2+1 : REM bei Assembler-Implementierung *2 per Shift
   y = y+1
   fehler = fehler-dy
   IF fehler<0 THEN
      REM Schritt in langsame Richtung (hier negative x-Richtung)
      dx = 1-x*2 : REM bei Assembler-Implementierung *2 per Shift
      x = x-1
      fehler = fehler-dx
   END IF

Ich habe mir jetzt gedacht und auch so umgesetzt, dass ich ja den 
zweiten Oktanten gleich weiterberechnen kann (muss da ja auch keine 
Bewegungsrichtung ändern), bis x <= 0 ist. Ich habe für diesen 2. 
Oktanten den Algorithmus etwas angepasst. Ich habe noch nicht geprüft, 
wie genau der Kreis ist.

Ist mein Algorithmus für den 2. Oktant so korrekt?

WHILE x > 0
   REM Schritt in schnelle Richtung
   x = x-1 : Hier muss erst x-1 vor dx berechnet werden, sonst wird ein Schritt zu viel gemacht
   dx = 1-x*2
   fehler = fehler-dx

   IF fehler>0 THEN
      REM Schritt in langsame Richtung
      dy = y*2+1 
      y = y+1
      fehler = fehler-dy
   END IF

[Xanthippos (xanthippos)]

Ist dir https://github.com/grbl/grbl aufgefallen?

Die zerlegen das Problem in 3 Teile. Zuerst setzen die alle Arten von 
Bögen aus kleinen Geraden zusammen. Dann berechnen sie aus den 
Steigungen die maximalen Geschwindigkeiten und Beschleunigungen. Zum 
Schluss benutzen sie nur mehr den Bresenham Algorithmus für Geraden.

Alles in einem Schritt  berechnen dürfte wohl zu komplex werden.

[Hannes J. (Firma: _⌨_) (pnuebergang)]

Keine A. schrieb:
> Der Psudocode für den ersten Oktankt

Quadrant, da du offensichtlich in 2D rechnest, nicht 3D.

> Ist mein Algorithmus für den 2. Oktant so korrekt?

Weiß ich nicht, keine Lust mir den anzusehen. Aber ich kann dir sagen 
wie man das schon vor ewigen Zeiten gemacht hat: Mit einer 
entsprechenden Koordinatentransformation der Ergebnisse des 
Bresenham-Algrotithmus.

II. Quadrant: x' = -x; y' = y
III. Quadrant: x' = -x; y' = -y
IV. Quadrant: x' = x; y' = -y

und der triviale Fall:

I. Quadrant: x' = x; y' = y

[Mario M. (thelonging)]

Er meint schon Oktant, weil die sich innerhalb eines Quadranten 
spiegelbildlich verhalten.

[Hannes J. (Firma: _⌨_) (pnuebergang)]

Xanthippos schrieb:
> Alles in einem Schritt  berechnen dürfte wohl zu komplex werden.

Ähm, nein. Bresenhams Algorithmus wird seit ewigen Zeiten (80 Jahre) für 
das Zeichnen (ursprünglich Plotten) von Linien und Kreisen verwendete. 
Im Prinzip hat der TS den schon hin geschrieben. Es fehlt nur noch die 
Koordinatentransformation.

[Keine A. (karabennemsi)]

Hannes J. schrieb:
> Ähm, nein. Bresenhams Algorithmus wird seit ewigen Zeiten (80 Jahre) für
> das Zeichnen (ursprünglich Plotten) von Linien und Kreisen verwendete.
> Im Prinzip hat der TS den schon hin geschrieben. Es fehlt nur noch die
> Koordinatentransformation.

Ich zeichne aber nicht, sondern bewege Schrittmotoren. Und da benötige 
ich eine kontinuierliche Kreisbewegung.

Und wie ich mit der Koordinatentransformation diese Kreisbewegung 
geschlossen forsetzen kann sehe ich nicht, da die 
Koordinatentransformation z.B. beim 2. Oktant aus entgegengesetzer 
Richtung kommt.

[Uwe D. (monkye)]

Also ich hatte das Grundprinzip so verstanden, dass beim Wechsel des 
Oktanten, so wie im Beitrag 
Beitrag "Re: Bresenham Kreisbewegung 2. Oktant" von Hannes 
angemerkt, das Vorzeichen zu beachten ist und dazu tauschen X und Y 
die Rollen, weil sich dann X (negativ) schneller bewegt als Y.

[Keine A. (karabennemsi)]

Uwe D. schrieb:
> Also ich hatte das Grundprinzip so verstanden, dass beim Wechsel des
> Oktanten, so wie im Beitrag
> Beitrag "Re: Bresenham Kreisbewegung 2. Oktant" von Hannes
> angemerkt, das Vorzeichen zu beachten ist und dazu tauschen X und Y
> die Rollen, weil sich dann X (negativ) schneller bewegt als Y.

Wenn du eine Kreisbewegung mit zwei Schrittmotoren machst und in den 2. 
Oktanten wechselst, kannst du den Algorithmus nicht einfach nochmal 
durchlaufen.

Du müsstest den Algorithmus rückwärts laufen lassen. Oder eben 
fortführen, was ich mache.

[Xanthippos (xanthippos)]

> Ich zeichne aber nicht, sondern bewege Schrittmotoren. Und da benötige
> ich eine kontinuierliche Kreisbewegung.

Das ist nicht so einfach. Du musst rechtzeitig mit dem Abbremsen 
beginnen. Bevor die Stelle erreicht ist, an der einer der Motoren still 
steht. Und bei Übergängen zwischen Kreissegmenten und Geraden willst du 
nicht abbremsen.

Du benötigst keine kontinuierliche Kreisbewegung du benötigst zwei 
kontinuierliche, jitterfreie Beschleunigungen.

[Christoph db1uq K. (christoph_kessler)]

Beitrag "Re: Darstellung kreis oder kurve auf GLCD"
Da habe ich 2006 meinen Bresenham in AVR-Assembler gepostet.
Auch in Achtelkreise aufgeteilt.

[Abdul K. (ehydra)]

Es gibt den Bresenham auch erweitert für Ellipsen. Der Kreis ist davon 
ein Sonderfall. Leider kann ich dir keinen Code geben, ist bei mir schon 
30 Jahre her. Findet man bestimmt irgendwo.

[Christoph db1uq K. (christoph_kessler)]

Die Achtelkreise reichten jedenfalls für ein Smith-Diagramm

;*************************************************************************
;* Unterprogramm zur Ausgabe von einem bis acht Achtelkreissegmentpixeln
;* Übergabevariable X_Circ,Y_Circ,X_Cent,Y_Cent,Segmt  
;* Zählweise Segmente - Koordinaten(X/Y):
;* (239/127)  I~~~~~~~~~~~~~~~I (0/127)
;*            I   2 1         I
;*            I  3   0        I
;*            I  4   7        I
;*            I   5 6         I
;* (239/0)    I_______________I (0/0)
;*************************************************************************
Segm0:  
  sbrs  Segmt,0    ; Achtel 0 zeichnen ?
  rjmp  Segm1
  mov  X_Pix,X_Cent  ; Kreismittelpunkt X_Cent
  sub  X_Pix,Y_Circ  ; minus Y-Koordinate Y_Circ
  mov  Y_Pix,Y_Cent  ; Kreismittelpunkt Y_Cent
  add  Y_Pix,X_Circ  ; plus X-Koordinate X_Circ
  rcall  PutPix    ; Bildpunkt auf Display ausgeben
Segm1:  
u.s.w.