www.mikrocontroller.net

Forum: PC-Programmierung Bresenham-Kreis: Verschobener Start ?


Autor: Ja mann (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Tach zusammen,

ich habe mir eine kleine CNC Steuerung geschaffen, die nun mittels des 
Algoritmus von Bresenham auch Kreise fräsen kann. Mein Problem ist nun 
Folgendes: Der momentane Algorithmus kann nur Kreise ziehen, deren 
Startpunkttangenten parallel zur x- oder y-Achse liegen. Dafür werden ja 
diese drei Variablen wie folgt initialisiert:
d = 1 - r
dx = 3
dxy = -2 * r + 5

Es müsste doch nun eine Möglichkeit geben diese Startwerte für einen 
beliebigen Startpunkt zu berechnen, aber ich komm' nicht drauf.
Ausgegangen werden soll von folgenden Daten (wie vom G-Code bekannt):
- Startpunkt X1, Y1
- Endpunkt X2, Y2
- Radius r

z.B.: Kreisbogen X1 = 0, Y1 = 0, X2 = 10, Y2 = 10, r = 20

Schönen Gruß & Danke fürs Lesen

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Der Algoritmus von Bresenham zeichnet ja im Prinzip keinen Kreis,
sondern nur ein Achtel. Durch z.B. mehrmaliges Wiederholen kann dann
ein ganzer Kreis gezeichnet werden.
Wenn du nun das erste Achtel nimmst, so ist die Starttangente immer
Achsenparallel (ergibt sich ja aus der Bresenham-Konstruktion). Um das
zu ändern, kannst du einfach eine Achsentransformation vornehmen wobei
eine Achse dann die Tangente, die andere die Senkrechte ist. Die
Skalierung muss aber so gewählt werden, dass möglichst keine
Rechengenauigkeit flöten geht.

Gruss

Jörg


P.S. warum brauchst du andere Tangenten als die Achsenparallelen?

Autor: Ja mann (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>warum brauchst du andere Tangenten als die Achsenparallelen?
Das fängt z.B. schon mal mit den jeweils "ungeraden" Kreisachteln an: 
Das erste Segment geht von 0° bis 45°, das zweite von 45° bis 90°. Beim 
zweiten ist also schonmal die Starttangente auf 45°. Hat man eine 
SetPixel Funktion, ist das nicht schwer, weil man die 8 Segmente 
gleichzeitig z.B. mit x0-x und x0-x etc. zeichnen kann. Bei einer Fräse 
möchte man aber natürlich die 8 Segmente nacheinander fahren.
Des weiteren gibt es den Fall dass man ein Kreisviertel fahren möchte, 
selbigen aber z.B. um 30° gedreht zu einer Achse haben möchte (also von 
30° bis 120°).
Meine Geometriekenntnisse sind leider etwas eingerostet, werde aber mal 
nach "Achstransformation suchen".

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ach ja, das Stichwort CNC hätte ja schon meine Frage beantwortet, habe
aber nur an Bildschirmausgabe gedacht. Deine Frage bezog sich also nur
auf Tangenten von 45 Grad, wiel du ja alle Achtel hintereinander fahren
möchtest.

Dann kannst du folgendes machen: Zeichne ganz normal das erste Achtel,
ausgehend von (r,0) als Startpunkt. Dann kommt das zweite Achtel mit
45-Grad-Tangente. Die Achstransformation ist jetzt (1,1) für die neue
X-Achse und (-1,1) für die neue Y-Achse, der Radius ist jetzt
r2 = r/sqrt(2). Jetzt einfach so tun, als hätte man ein neues erstes
Achtel mit neuem r2. Das dritte Achtel ist wieder wie das erste, nur mit
X-/Y-Achse vertauscht usw. Zeichne einfach mal die ersten zwei Achtel
auf Karopapier und mach dir die Skalierungen 1/sqrt(2) und die
Achstransformation klar.


Gruss

Jörg

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Habe ich noch vergessen zu erwähnen: Die Skalierung mit 1/sqrt(2)
setzt natürlich voraus, dass deine Rechengenauigkeit hoch genug ist,
z.B. bei grösseren Kreuztisch mindestens 32-Bit, um die Übergänge
bei den Achteln "unsichtbar" zu halten.

Gruss
Jörg

Autor: Ja mann (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>der Radius ist jetzt r2 = r/sqrt(2).

Das ist Klasse! Ich hatte mir bisher so geholfen, dass ich die 
"Laufvariablen" dx und dxy nach einem Kreisachtel nicht zurücksetze, 
sondern im 2. Oktanten subtrahiere, anstatt zu addieren. Z.B. für den 
Fall das man gerade im Kreis ist mache ich im 2. Oktanten nicht

dx+=2; dxy+=2;

sondern

dx-=2; dxy-=2;

Nach dem jeweils 2. Oktanten initialisiere ich dann dx und dxy neu. 
Werde das aber auf Deinen Vorschlag umbauen, gefällt mir besser.

Dann nochmal zurück zum Kreisabschnittsproblem: Ich habe also 2 Punkte, 
zwischen denen ein Kreisbogen mit Radius r gefahren werden soll. Ich 
könnte damit den Mittelpunkt bestimmen, und den Bresenham zunächst 
"leer" laufen lassen bis der erste Punkt erreicht ist. Müsste von der 
Theorie her klappen, habe aber gerade bemerkt dass sich da leider noch 
mehr Lücken in der Mathematik auftun:

http://de.wikipedia.org/wiki/Kreissegment

Ich habe durch meine 2 Punkte also die Sehne s gegeben. Um nun den 
Mittelpunkt bestimmen zu können, muss ich ein Mittellot von meiner Sehne 
mit der Länge sqrt(r² - (s/2)²) fällen, dort befindet sich mein 
Mittelpunkt.
So die Theorie, aber wie komme ich "numerisch" ausgehend von x0, y0, x1, 
y1 (Sehne) an xm und ym ?

Mit deprimierten Grüßen
Ja mann

Autor: Detlef _a (detlef_a)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Gibt zu einer Sehne/Radius zwei Mittelpunkte und die liegen da, wo das 
angehängte jpg sagt ;-)

Math rulez !
Cheers
Detlef

PS: Ja, das ist ein Verstoß gegen gültige Bildanhängeregeln.

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Also den Kreismittelpunkt bekommst du z.B. mit der Lotkonstruktion:

  0. Sehne (sx,sy) := (x1-x0,y1-y0)
  1. Sehnenmittelpunkt (xms,yms) := 0.5*(x0+x1,y0+y1)
  2. Senkrechte (tx,ty) := (-sy,sx)     (oder auch (sy,-sx) !!!!)
  3. (xm,ym) := (xms,yms) - faktor1*(tx,ty)
     mit faktor1 := sqrt(0.5*(sx^2+sy^2)/(tx^2+ty^2))
  4. Zenitpunkt (xz,yz) := (xm,ym) + faktor2*(tx,ty)
     mit faktor2 := sqrt(r^2/(tx^2+ty^2))

Dann kannst du ausgehend vom Zenitpunkt in beide Richtungen jeweils
solange per Achsentransformation + Bresenham-Ansatz die Fräsbahn
berechnen, bis die Punkte (x0,y0) bzw. (x1,y1) überschritten werden.
Achtung: u.U. müssen in beiden Richtungen jeweils zwei Achtel
"gezeichnet" werden.

Bem: es sind zu zwei Punkten und einem Radius zwei Kreisbögen möglich!

Gruss

Jörg

Autor: Ja mann (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>PS: Ja, das ist ein Verstoß gegen gültige Bildanhängeregeln.
Nicht nur das, das ist eindeutig schwere Körperverletzung!

Jörg:
Super, vielen Dank einstweilen, werde mich da etwas tiefer reindenken;

>u.U. müssen in beiden Richtungen jeweils zwei Achtel
>"gezeichnet" werden.

Hm, eigentlich können es bis zu 4 Oktanten sein (es ist ja bis zu einem 
Halbkreis möglich)

>Bem: es sind zu zwei Punkten und einem Radius zwei Kreisbögen möglich!
Danke, das ist klar, deswegen gibt es in der CNC Sprache (G-Code) auch 
zwei verschiedene Kommandos, eines für linksrum und eins für rechtsrum.

Bis dann,

Ja mann

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Ja mann,

ja klar, können insgesamt 4 Achtel sein; bin von der Graphik auf
Wikipedia ausgegangen, also (x0,y0) links, (x1,y1) rechts, (xm,ym)
unten und den Zenitpunkt oben (hmm, schreibt man jetzt unten/oben/links
usw. klein oder GROSS??). Eine einfache Version testet z.B. für jeden
Punkt, ob die Schenkel (links,rechts) schon erreicht sind, eine bessere
fragt erst bei den beiden inneren Achteln nach, ob sie innerhalb der
beiden Schenkel liegen.

Gruss

Jörg


P.S. worauf läuft G-Code, auf PC oder auf spezieller Hardware?

Autor: Ja mann (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>P.S. worauf läuft G-Code, auf PC oder auf spezieller Hardware?
Überall :-) Es gibt CNC-Achssteuerungen für den PC, welche direkt 
mittels G-Code am Parallelport ein paar Schrittmotoren steuern. Selbiger 
Code wird auch von vielen X-Y-Tisch gebilden etc. verstanden. Ich möchte 
nun mit einem µC + LCD + MMC den G-Code auf der Maschine abspielen.
Der Hammer wäre natürlich wenn man einfach XML Daten (SVG) z.B. aus 
Inkscape fräsen könnte, aber das ist dann wohl doch ein paar Hausnummern 
zu groß...

Autor: Ja mann (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
hmmm, habe mir das ganze mal etwas durchgerechnet, aber bei Nr.3 blieb 
ich stecken:

>3. (xm,ym) := (xms,yms) - faktor1*(tx,ty)
>     mit faktor1 := sqrt(0.5*(sx^2+sy^2)/(tx^2+ty^2))

xm und ym sollen vermutlich den Kreismittelpunkt darstellen. Allerdings 
geht hier an keiner Stelle der Radius mit ein, was ja nicht sein kann ?

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sorry, war bei meiner Ableitung bzw. "in die Mail kopieren" in die
Falsche Zeile geraten. Du musst ja bei der Konstruktion vom
Sehnenmittelpunkt soweit  "runter gehen", bis der Abstand von z.B.
(x0,y0) zum Kreismittelpunkt (xm,ym) genau Radius r ist. Da
die Vektoren (sx,sy) und (tx,ty) nicht normiert sind, muss noch
skaliert werden. Aus der Konstruktion ergibt sich mittels a^2+b^2=c^2
im rechtwinkligen Dreiecken

  factor1 := sqrt[(r^2-0.25*(sx^2+sy^2)) / (tx^2+ty^2)]

glaube jetzt stimmt's (zeichne es einfach mal auf ein Blatt Papier
und rechne es nach).

Gruss

Jörg

Autor: Ja mann (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Jau!

Hab's eben nochmal anhand eines Beispieles durchgerechnet und 
gezeichnet. Passt astrein! Also herzlichsten Dank nochmal für Deine 
Mühen.
Nun muss ich den ganzen Spaß nur noch meinem µC beibringen, aber die 
Theorie dafür ist ja nun klar.

Gruß
Ja mann

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
.. was ich aber nicht verstehe: wieso rechnet Mathematika oder Mapple
wie im obigen Beitrag so einen Mist ?? Lehre daraus: versuchs immer zu
verstehen als blind einem Tool zu vertrauen.

Jörg

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Meine Einlassung weiter oben war nicht als Körperverletzung gedacht.Es 
ergeben sich sehr einfache (naja) Formeln, zB für die Koordinate ym des 
Kreismittelpunkts:

ym= -dy/2+y0 +/- sqrt(dy^2*sq^3*(dy^2-sq)*(sq-4rq))/(2*dy*sq^2)

mit rq als Quadrat des Radius, sq als Quadrat der Sehnenlänge und dy als 
(y0-y1). xm gibts analog wenn man die y durch x ersetzt.

Das ganze läßt sich also relativ elegant analytisch lösen, ohne 
irgendwelche anschaulichen 'Konstruktionen' heranziehen zu müssen.

Ja.
Cheers
Detlef

Edit:
@Jörg: Das Mathematica Ergebnis ist mathematisch korrekt. Schön und 
einfach wird das Ergebnis erst durch Einführung von sq, rq und dy.

>>Lehre daraus: versuchs immer zu verstehen als blind einem Tool zu vertrauen.

Das sehe ich genauso, aber wie gesagt, das Mathematice Ergebnis ist 
richtig. Ich würde mich nicht mit der Suche nach einfachen Formeln für 
xm/ym aufhalten, wenn ich Zeit und Rechenpower habe sondern mir von 
Maple/Mathematica das Ergebnis produzieren lassen und direkt in die 
C-Source kopieren. BTW, der Optimierer wird die gemeinsamen Terme schon 
finden.

Autor: Pieter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
moin moin,

bei mir läuft auf einem 8051 ein solcher G-Code Interpreter.
Da für die Fräserradienkorrektur auch der Winkel Start/Stop notwendig 
war, konnte darüber auch der Quadrant berechnet werden. Von da aus lasse 
ich einfach eine Schleife laufen, wird die Startposition erreich, wird 
die Motorsteuerung freigegeben. Beim Erreichen der Stopposition wird die 
Schleife abgebrochen.

Mit Gruß
Pieter

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Detlef _a,

ich habe nicht die Korrektheit bezweifelt, du hast ja die zu lösende
Gleichung korrekt formuliert. Mathematika weiss aber nicht, wie du's
gerne hättest und bietet dir eine, oft aber keine schöne Lösung.
Für die Formulierung solcher Probleme und deren graphische Ausgabe
aber schon ein schönes Tool.

Gruss und schönes Wochenende,

Jörg

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.