Forum: Mikrocontroller und Digitale Elektronik in einer Tabelle den bestmöglichen Wert suchen


von Andi (Gast)


Lesenswert?

Moin!

Hab da nen kleines Problem und bin grad etwas ausgepowert, irgendwie
find ich keine vernünftige Lösung. Vielleicht habt ihr ja Ideen oder
nen Lösungsansatz...

Folgendes:

Nach einer 24Bit/16Bit-Division habe ich ein Ergebnis irgendwo zwischen
256 und 5000. (Alle anderen Werte sind für mich irrelevant) In einer
Tabelle mit ca. 100 Werten möchte ich jetzt denjenigen heraussuchen,
der meinem Ergebnis am nächsten ist (beziehungsweise den Wert, der der
nächst höhere ist). Also angenommen in der Tabelle stehen die Werte:
(...)
524
502
481
461
443
(...)
und mein Divisions-Ergebnis beträgt angenommene 496, wie finde ich
jetzt am schnellsten den Wert 502 heraus?

Ich programmiere übrigens in Assembler, von C hab ich keine Ahnung...

Gruß,
Andi

von Andi (Gast)


Lesenswert?

Achso... Ich hätte noch schreiben sollen, daß ich nen Atmel AVR Mega8535
benutze...

von Oliver (Gast)


Lesenswert?

Per Pointer die gesamte Tabelle durchsuchen, bis der Vergleichswert
über- oder unterschritten wird, je nachdem, ob Du die Tabelle von unten
nach oben oder andersherum aufbaust.

von Profi (Gast)


Lesenswert?

Das ist eine Standard-Aufgabe der Informatik.
Einfachste Möglichkeit: Binäre Suche:
Du prüfst, ob der Wert kleiner oder größer als der Wert in der Mitte
der Tabelle ist, wenn kleiner, dann halbiere den unteren Teil der
Tabelle, wenn größer, dann untersuche den oberen Teil der Tabelle.
Das ganze machst Du solange, bis Du die Tabelle nicht mehr teilen
kannst.
Bei einer Tabelle mit 128 Einträgen brauchst Du 7 Vergleiche.
Geht natürlich nur, wenn die Tabelle sortiert ist.

von Hagen (Gast)


Lesenswert?

einfachste Möglichkeit ist die sequentielle linare Suche. Deine Tabelle
ist also sortiert und du gehst sie vom kleinesten zum größten Element
durch so lange der Tabellenwert kleiner dem Vergleichswert ist.

Bischen schneller (50/7= ca. 7 mal) ist es die binäre Suche zu
benutzen.

Gruß Hagen

von Detlev (Gast)


Lesenswert?

Da es darum geht den am nächsten liegenden Wert zu finden, muss man
zwei Tabellen verwenden:

Eine mit den Schwellwerten, ab denen der nächste Wert gilt
Eine mit den endgültigen Werten.

Erst wird die erste Tabelle durchlaufen solange bis der nächste
Schwellwert höher ist. Dadurch erhält man den Index für die zweite
Tabelle.

Wenn der Platz knapp ist: Man kann auch in der ersten Tabelle die
Differenzen der Schwellwerte abspeichern (da reichen wahrschinlich 8
bit) und subtrahiert diese Werte solange, bis die nächste Differenz
größer ist als der Rest.

Alternativ: Nur eine Tabelle verwenden, Betrag der Differenz ausrechnen
und mit bisherigem Minimalwert vergleichen. Ist der Wert kleiner, als
neuen Minimalwert nehmen, index erhöhen und weiter, sonst ist der beste
Wert gefunden.

von inoffizieller WM-Rahul (Gast)


Lesenswert?

>Eine mit den Schwellwerten, ab denen der nächste Wert gilt
>Eine mit den endgültigen Werten.

Was meinst du?

Man bildet einfach der Reihe nach die Differenz zwischen dem
Rechenergebnis und den Werten in der Tabelle.
Das Optimum ist dann der Wert mit der kleinsten Differenz (absolut
gesehen). Bei 100 Werten und einem Mikrocontroller sollte man die
Bubble-Sort-Methode (lineare Suche) benutzen. Alles andere hat was mit
kleinen Vögeln und grossen Projektilen zutun...

von Karl heinz B. (kbucheg)


Lesenswert?

Na ja.
Sooo aufwendig ist eine binäre Suche auch wieder nicht.
Am Index der zum Schluss übrigbleibt (mit Ausnahme des
ersten und des letzten) vergleicht man dann mit dem gefundenen
Wert bzw. mit dem Wert unmittelbar davor bzw. danach um zu
entscheiden welcher näher liegt.

Klar ist das etwas mehr Aufwand als eine lineare Suche,
aber nicht soooo viel mehr. Und letztendlich hängt es davon
ab, wie oft so eine Suche gemacht werden muss und ob man
wirklich das letzte aus dem Code rausholen muss.

von inoffizieller WM-Rahul (Gast)


Lesenswert?

Stimmt. Die binäre Suche hätte bei 100 Werten vielleicht 10 Vergleiche(?
könnte man auch ausrechnen...), und wenn man mit einem Feld un deinem
Feldindex arbeitet ist das ziemlich simpel (zwei Schleifen und ein paar
Vergleiche...)

von Karl heinz B. (kbucheg)


Lesenswert?

> 10 Vergleiche(? könnte man auch ausrechnen...)

Die Anzahl der Suchschritte ist ceil(log2(n)). Bei 100 also 7.
Verglichen mit der durschschnittlichen Anzahl der Suchschritte
bei linearem Suchen: n/2, also 50, ist das schon relativ
gut. Das Verhältnis wird mit steigendem n schnell immer
besser, zugunsten binärem Suchen. Bei 500 stehts schon 250
zu 9, bei 1000 haben wir 500 zu 10, etc. (einfach n immer
bis zur nächsten 2-er Potenz aufrunden, aus 1000 wird 1024
und 1024 ist 2 hoch 10)

von Karl heinz B. (kbucheg)


Lesenswert?

Hmm. Wenn ich mir die Werte so anschaue:

(...)
524
502
481
461
443
(...)

dann fällt mir auf:
   524 - 502    =  22
   502 - 481    =  21
   481 - 461    =  20
   461 - 443    =  18

mit Ausnahme der 18 (könnte auch ein Rundungsproblem sein)
sieht das eigentlich sehr regelmässig aus.
Daher meine Frage:
Ist das jetzt Zufall?
Vielleicht könnte man auch eine Formel finden, die die
Umrechnung macht.
Erzähl doch mal mehr über die Tabelle.

von Andi (Gast)


Lesenswert?

Moin, moin!

Erstmal tausend Dank für Eure Beiträge. Neuer Tag, neue Energie: heut'
klappt's wieder besser mit dem Überlegen als gestern Abend. ;-)

Erstmal für Diejenigen, die es interessiert, wozu ich das ganze
brauche, alle Anderen überspringen einfach den nächsten Absatz:

---
Also, meine Tabelle ist eine fertig umgerechnete "Tangens-Tabelle",
diese benötige ich zur Berechnung der resultierenden
Schrittmotorgeschwindigkeit für einen CNC-Kreuztisch. Genauer: Wenn ich
eine Diagonale fahren muß, muß die einzelne Achsgeschwindigkeit
abnehmen, damit der Gesamt-Vorschub konstant bleibt. Dabei spielt das
Verhältnis der X- zur Y-Achse eine Rolle, daraus lassen sich mit dem
ArcTan der Winkel bestimmen. (Einfache Geometrie eines
gleichschenkligen Dreiecks). Die Werte in der Tabelle sind dabei das
Ergebnis: längere Achse mal 256 duch kürzere Achse. (Daher 24Bit-Wert:
16Bit mal 256). Ist das Verhältnis 1:1, habe ich die kleinste
Geschwindigkeit auf der längeren Achse, nämlich 70,7% der
Gesamtgeschwindigkeit. Wird das Verhältnis der längeren Achse zur
kürzere Achse zu groß, spielt die kürzere Achse keine Rolle mehr, da
die Geschwindigkeit der längeren Achse nicht mehr reduziert werden
braucht. Das ist ab Ergebnis 4885 der Fall.
Anhand der Tabelle finde ich heraus, um wieviel die Geschwindigkeit der
längeren Achse herabgesetzt werden muß. Die kürzere Achse richtet
(synchronisiert) sich dabei an die längere Achse.
Ein Beispiel:
 X-Achse = 15000 Steps, Y-Achse gleich 10000 Steps.
 -> Längere Achse = X -> Verhältnis x/y = 15000/10000
 -> Berechnung auf dem uC =15000*256/10000 = 384
Meine Tabelle enthält nun 33Grad Alpha (Achswinkel) den Wert 394, und
für 34Grad den Wert379. Das bedeutet, wenn ich für mein Ergebnis von
384 in der Tabelle nachschaue, kann ich ablesen, daß der
Steigungswinkel zwischen 33 und 34 Grad liegt.

noch ein Beispiel:
 X-Achse = 2400 Steps, Y-Achse gleich 4000 Steps.
 -> Längere Achse = Y -> Verhältnis y/x = 4000/2400
 -> Berechnung auf dem uC =4000*256/2400 = 426
Die Tabelle enthält (zufällig) genau den Wert 426, dieser steht für
31Grad. Nur das diesmal nicht der Winkel Alpha sondern Betha gemeint
ist, da ja die Y-Achse die längere ist. Aber das spielt für die
Geschwindigkeit keine Rolle, denn in diesem Fall nehme ich ja die
Y-Achse zur Berechnungsgrundlage.

(
Meine fertige Tabelle später wird nicht Anhand der Gardzahlen
berechnet, sondern anhand der Vorschubgeschhwindigkeit, so daß ich
anhand der Position des Wertes in der Tabelle direkt den Vorschub
ableiten kann. Sonst müßte ich jetzt ja in einer zweiten Sinus-Tabelle
nnachsehen, wie groß der Vorschub für 33-34Grad sein muß. Die Werte
werden sich also später etwas verändern. In diesem Stadium der
Projektes möchte ich jedoch erstmal den Winkel auf einem Display
ausgeben und noch keine Motoren steuern. Also einfach: Eingabe der
X-Achse und der Y-Achse und der uC berechnet mir daraus den
(gerundeten) Achswinkel.
)
---
So, ich hoffe das hilft zur Erklärung, wofür ich das ganze brauche.


Wenn das Projekt fertig ist, kann ich direkt aus einer
HPGL-Plotterdatei, die z.B. mit Autocad erzeugt wurde, meinen
Kreuztisch steuern. Pen-Up/Pen-Down heißt dabei dann einfach Z-Achse
runter oder hoch. Man könnte auch sagen, ich bau mir einen Plotter
selber, nur das der nicht plottet sondern fräst. ;-)

Ich denke, ich werde eine Tabelle mit 128 Werten anlegen und dann die
Binary-Tree-Search-Variante nehmen, sollte unter ASM recht einfach zu
programmieren sein.

Meine Ablauf-Überlegungen:

-ein Register als Pointer für die Suche auf 64
-Schleifen-Register auf 32, je Durchgang nach rechts verschieben (/2)
-Wert aus der Tabelle lesen und mit Berechnung vergleichen
-größer->Pointer + Schleifenzähler, kleiner->Pointer - Schleifenzähler
-nächster Schleifendurchgang, solange bis Schleifenregister=0.

Somit sollte mein Pointer am Ende genau den Wert haben, an dessen
Stelle das passenste Ergebnis steht... Werd ich gleich probieren.

Weitere Vorschläge oder Ideen sind natürlich weiter willkommen. :-)

Gruß,
Andi.

von inoffizieller WM-Rahul (Gast)


Lesenswert?

Da frage ich mich gerade, ob der Bresenham-Algorithmus auch die
Vorschubgeschwindigkeit beachtet.

von Andi (Gast)


Lesenswert?

Hä? Was isn ein Bresenhalm-Algorithmus?

:-)

Gruß,
Andi

von inoffizieller WM-Rahul (Gast)


Lesenswert?

>Bresenhalm-Algorithmus

ist ein Algorithmus für bräsige Halmaspieler...

Ich meinte den hier:
http://de.wikipedia.org/wiki/Bresenham-Algorithmus

von Andi (Gast)


Lesenswert?

Hm, ganz interessant, habs mal schnell überflogen. Hab mit geometrie
sonst bisher nohc nicht viel am Hut gehabt, hab daher von dieser
bräsigen Halma-Theorie ;-) noch nichts gehört.

Genau das möchte ich wohl praktisch auf meine Fräse übertragen: die
schnellere Achse wird ausgeführt und hin und wieder, je nach Steigung,
einen Schritt in der anderen Achse ausgeführt.

Soweit ists ja auch kein Problem, nur soweit ich das sehen konnte, wird
dabei NICHT der Vorschub berücksichtigt, wozu auch: Der Computer soll
die Schräge ja so schnell wie möglich zeichnen, ich aber nicht! Im
Gegenteil, je nach zu fräsendem Material und Fräsbohrer muß ich ja eine
festgelegte Vorschub-Geschwindigkeit einhalten, und bei Schrägen sind
die einzelne Achsen (=Katheten im Dreieck) halt langsamer als die
resultierende Gesamtbewegung (=Hypotenuse). Und genau dafür brauche ich
meine Berechnung, die, so wie ich das zuminedest bisher sehen konnte, am
schnellesten und einfachsten mit einer Tabelle zu ermitteln ist.

Eine 7-Bit Auflösung (128-Werte) für die Herabsetzung der
Geschwindigkeit der längeren (=schnelleren) Achse sollte mir vollkommen
ausreichen, wenn nicht, könnte ich später noch zwischen der einzelnen
Werten interpolieren. Kommt auch noch ein wenig darauf an, wieviel
Rechenpower ich auf meinem Mega8535 später noch übrig hab.

Gruß,
Andi

von Karl heinz B. (kbucheg)


Lesenswert?

> Da frage ich mich gerade, ob der Bresenham-Algorithmus auch die
> Vorschubgeschwindigkeit beachtet.

Ja. Tut er im Prinzip.
Der Bresenham sagt dir in welche Richtung 'das nächste
Pixel' gesetzt werden muss (X oder Y) damit sich der
'Stift' möglichst wenig von der idealen Geraden entfernt.

> Hä? Was isn ein Bresenhalm-Algorithmus?

Jetzt bin ich aber enttäuscht.
Du willst einen Plotter (äh. CNC ist aber vom Prinzip
her dasselbe) bauen und kennst den Bresenham nicht?

Zu Deiner Tabelle
Du machst dir unnötige Arbeit. Der Winkel interessiert
in Wirklichkeit niemanden. Alles was du brauchst ist
die Vektorzerlegung des Vorschubvektors in die Komponente
entlang der X und Y Achse. Die ist aber trivial. Die hast
du naemlich schon. Das ist jeweils die X und die Y Komponente
des Vorschubvektors.
Alles was du noch tun musst ist, die Komponenten so zu skalieren,
dass entlang der Resultierenden (des eigentlichen Vorschubvektors)
die gewünschte Voschubgeschwindigkeit entsteht.

Sei Vx/Vy  der vorgegebene Richtungsvektor und S die einzuhaltende
Vorschubgeschwindigkeit, dann sind

   X = S / Vx
   Y = S / Vy

die geforderten Geschindigkeiten. Vx/Vy sind als Einheitsvektor
(also Vektor der Länge 1) zu sehen. Je nachdem wie du die
Vorschubrichtung bekommst ist das entweder

Richtung in Form zweier Punkte P1x/P1y, P2x/P2y gegeben:

    dx = P2x - P1x
    dy = P2y - P1y
    L = sqrt( dx * dx + dy * dy )
    Vx = dx / L
    Vy = dy / L

oder aber als Winkel a

    Vx = sin(a)
    Vy = cos(a)


Beispiel: Du sollst von 1200/800 nach 4000/2850 fahren
mit einer Geschwindigkeit von 20 Steps in der Sekunde.
Wie gross ist die Geschwindigkeit entlang der Achsen X
und Y?

    P1 = 1200 ; 800
    P2 = 4000 ; 2850

    dx = 4000 - 1200  -> 2800
    dy = 2850 - 800   -> 2050

    L = sqrt( 2800 * 2800 + 2050 * 2050 ) -> 3470,23

    Vx = 2800 / 3470 -> 0,8069
    Vy = 2050 / 3470 -> 0,5908

    Sx = 20 * 0,8069 -> 16,13
    Sy = 20 * 0,5908 -> 11,81

Wenn du also in X-Richtung 16,13 Schritte pro Sekunde machst
und in Y Richtung 11,81 Schritte pro Sekunde, dann bewegt
sich das Zentrum deines Kreuztisches mit (mehr oder weniger)
genau 20 Schritten pro Sekunde in die angegebebene Richtung
vom Punkt P1 zum Punkt P2.

(Probe: sqrt( 16,13 * 16,13 + 11,81 * 11,81 ) -> 19,991

 Die Ungenauigkeit kommt dadurch zustande, dass ich einige
 Kommastellen in der Berechnung unter den Tisch hab fallen
 lassen).


Du solltest aber wirklich den Bresenham aufsuchen. Obiges
Verfahren garantiert dir naemlich, bedingt durch die
Rechenungenauigkeit, nicht dass du tatsaechlich am gewünschten
Endpunkt rauskommst (das würde dein Verfahren im ürigen auch nicht).

von Karl heinz B. (kbucheg)


Lesenswert?

> Soweit ists ja auch kein Problem, nur soweit ich das sehen konnte,
> wird dabei NICHT der Vorschub berücksichtigt, wozu auch: Der
> Computer soll die Schräge ja so schnell wie möglich zeichnen, ich
> aber nicht!

Doch das tut er.
Der Bresenham sagt dir in welcher Richtung der nächste anzufahrende
Punkt liegt. Wie schnell du dann an diesen Punkt kommst ist
dir überlassen. Stell es dir einfach so vor, dass dir der
Bresenham eine Treppenfunktion zwischen 2 Punkten generiert.
Also eine Funktion die nur aus waagrechten bzw. senkrechten
Linien besteht. Deine Fräse fährt dann immer mit konstanter
(eingestellter) Geschwindigkeit entweder waagrecht oder
senkrecht. Nur sind halt die einzelnen Verfahrstrecken so
kurz, dass du sie nicht mehr optisch auflösen kannst.

von inoffizieller WM-Rahul (Gast)


Lesenswert?

Übrigens zeigt dieser Thread auch mal wieder, wie schön man von
eigentlichen Thema abweichen kann.

von Karl heinz B. (kbucheg)


Lesenswert?

:-)
Er zeigt vielmehr, dass man mit Nachdenken im Vorfeld
sich so manches Problem in Luft auflöst.

(Mann war das immer ein Kampf den Mathematikern beizubringen,
dass sie ihre Sinus/Cosinus/Tanges Sachen einpacken sollen
und lieber auf Vektorrechnung in der Computergraphik umsteigen
sollen: Geht schneller und die Genauigkeit leidet auch nicht
so sehr darunter).

von Hagen (Gast)


Lesenswert?

Hi Karl Heinz,

deine Erklärung trifft das Problem sehr korrekt auf mathematischer
Ebene. Aber wenn er mit seiner Tabelle + Binäre Suche auskommt dann
wird dies mit hoher Wahrscheinlichkeit weitaus schneller auf einem AVR
laufen als eine Wurzel ziehen + Sin()/Cos() + Divisonen zu berechnen.

Gruß Hagen

von inoffizieller WM-Rahul (Gast)


Lesenswert?

Es zeigt aber auch, dass es sich lohnt, mit anderen über (s)ein Problem
zu reden. Viele meinen scheinbar auch, dass Ihr Projekt extrem geheim
ist bzw. dass man ihnen etwas wegnehmen würde. Wenn dem so wäre,
bräuchten sie hier auch nichts reinschreiben...

von Karl heinz B. (kbucheg)


Lesenswert?

Du vergisst, dass er mit seiner Tabelle lediglich den
Arcus Tangens berechnet. Das ist aber noch nicht das
Ende der Fahnenstange. Seine Berechnung geht dann noch
weiter.

Ausserdem: Wer sagt, dass man die ganze obige Berechnung
nicht auch in Form von Tabellen zusammenfassen kann.

Im übrigen finde ich das ganze müssig, den ich würde
das so gar nicht machen. Was bringen mir die Werte?
Was hab ich davon, dass ich weiss wieviele Steps
pro Sekunde ich in X und Y Richtung simultan machen muss?
Das ist naemlich gar nicht so einfach, das hinzukriegen.

Viel simpler ist es sich vom Bresenham ausrechnen zu lassen
wo mein nächster Punkt liegt und diesen Punkt fahre ich
dann entweder senkrecht oder waagrecht mit immer der gleichen
Geschwindigkeit an. Und von dort gehts dann, wieder mit
der gleichen Geschwindigkeit, weiter zum nächsten Punkt:
entweder senkrecht oder waagrecht. Der Bresenham regelt also
gewissermassen die konstante Vorschubgeschwindigkeit dadurch,
dass er auf einer Diagonalen mehr anzufahrende Punkte einfügt.

von inoffizieller WM-Rahul (Gast)


Lesenswert?

Dann müsste man ja nur noch mit einem Timer die Ausgabe steuern. Damit
kann man dann ziemlich einfach die Vorschubgeschwindigkeit einstellen
(Timer-Frequenz...). Interessant wird dann die Kreisbahn-Berechnung.
Der Algorithmus dafür im Wiki ist IMHO nur für Achtelkreise geeignet.

von Karl heinz B. (kbucheg)


Lesenswert?

> Dann müsste man ja nur noch mit einem Timer die Ausgabe steuern.

Ganz genau. In jedem Timer Interrupt lässt man sich
vom Bresenham errechnen ob man einen Schritt in X oder
einen Schritt in Y machen muss, führt den Schritt durch
und wartet auf den nächsten Timer Interrupt. Fertig.

> Interessant wird dann die Kreisbahn-Berechnung.
> Der Algorithmus dafür im Wiki ist IMHO nur für Achtelkreise
> geeignet.

Ich hab jetzt im Wiki auf die Schnelle nichts gefunden,
aber auch für Kreise gibt es einen 'Bresenham'.

von inoffizieller WM-Rahul (Gast)


Lesenswert?

>aber auch für Kreise gibt es einen 'Bresenham'.

Ja, der arbeitet auch nach dem vektoriellen Prinzip, dass die
Hypotenuse des Dreiecks mit den Schenkeln X und Y gleich r ist.

In dem Beispiel, wird dann ein Vollkreis aus acht einzelnen Segmenten
zusammengesetzt. Wenn man aber mit einem Fräser unterwegs ist, dann
erfordert es ja eine bestimmte Vorschubrichtung. Mal sehen, ob ich was
dazu finde...

von Andi (Gast)


Lesenswert?

Hallo nochmal...

Erstmal danke für die Antworten. Und: Ja, ich baue sozusagen einen
Plotter und kenne den "Bresen-dingsda" nicht, jedenfalls kannte ich
das bisher nicht. ;-) Man kann ja nicht alles wissen und da ich bisher
nichts in diese Richtung zu tun hatte, hab ich mich damit halt eben
auch noch nicht beschäftigt. Wird jetzt ja vielleicht auch Zeit. Nun
gut.

Also, die o.a. Berechnungen der Geschwindigkeiten klingt ganz logisch
und ist wohl auch richtig. Was mich aber dabei stört, ist halt diese
von dir beschriebene Ungenauigkeit des Endpunktes, denn genau diesen
MUSS ich in jedem Falle einhalten. Und bei der von mir überlegten
Methode tue ich das sehr wohl, da ich für die Zweite Achse NICHT die
Geschwindigkeit berücksichtige, sondern nur die Anzahl der Steps. Die
Achse mit weniger Steps wird der anderen Achse angepaßt, macht also am
Ende EXAKT die Anzahl der Schritte, die sie auch machen soll. Ihre
Geschwindigkeit regelt sich halt nach der längeren Achse. Nur für diese
berechne ich die Geschwindigkeit, die Geschwindigkeit der anderen Achse
paßt nachher automatisch, da der letzte Step jeder Achse zur gleichen
Zeit erfolgt und ich somit alle Steps beider Achsen ausgeführt habe.
Solange also durch die Motoren und der Mechanik nichts verloren geht,
habe ich sichergestellt, daß der tatsächlich erreichte Endpunkt auch
dem geforderten entspricht.

Ich will ja NICHT, dass meine Fräse später eine Treppe abfährt, wie von
Karl Heinz so schön beschrieben. Es sollen ja X und Y Achse gleichzeitig
angesteuert werden. Durch die Trägheit der Mechanik ergibt sich später
eine mehr oder weniger flüssige Bewegung und dadurch keine Treppe
sondern tatsächliche schrägen.

Hmmm.:
---
>> L = sqrt( 2800 * 2800 + 2050 * 2050 ) -> 3470,23
---

Genau sowas will ja vermeiden... auf nem Uc solch 'komplizierten'
Rechnungen anstellen, ne Quadratwurzel ziehen.... da kann ich dann doch
lieber inner Tabelle nachsehen. Wieviel Taktzyklen würde denn ein
mega8535 allein für diese Formel brauchen? Und dann ist das ja noch
nicht alles, kommen ja noch die beiden Divisionen Vx = dx / L und Vy =
dy / L dazu, und alles feinste 16Bit-Berechnungen, oder sogar noch
mehr, schließlich sinds ja auch noch Komma-Werte...
(ich geb ja zu, vielleicht ist ja der AVR nicht der geeignetste Typ für
diese Aufgabe, aber den kenne ich halt am Besten und wollte mich nun
nicht extra für dieses Projekt in andere uC einarbeiten).
...

Wenn das so funktionieren würde, wie ich mir das vorgestellt habe, mit
meiner Methode, dann brauche ich nur eine Division (24Bit/24Bit),
hierfür benötige ich etwa (ausprobiert) 450 Zyklen. Vielleicht läßt
sich das auch noch optimieren, keine Ahnung, bin keine
ASM-Rechenkünstler. ;-) eigentlich brauche ich ja nur 24bit/16bit.

Danach brauch ich nur noch in meiner Tabelle nachsehen, hierbei bin ich
grad am programmieren. Mal sehen wie schnell das ist, ich denk aber
nicht mehr als 50Zyklen. Somit hab ich alles was ich an Daten brauche
in ca.550 Zyklen, wenn ich noch das drumrum berücksichtige. Schließlich
brauch ich dann ja auch noch etwas Rechenpower für die PWM-Ausgabe an
die Stepper, das einlesen der Positionsdaten aus dem externen SRAM
(32K) etc...

Letzten Endes soll es so aussehen, daß die komplette HPGL-Datei vom PC
über die serielle Schnittstelle an den mega8535 gesendet wird, dieser
die Koordinaten (und andere Steuerbefehle) während des Empfangens
gleich von den ASCII-Zeichen in 16-Bit-Werte umrechnet, im externen
32KByte SRam ablegt und den Plot- (bzw, Fräs-) Vorgang später alleine
ohne PC macht. Denn meine HPGL-Dateien enthalten keinerlei Radien o.ä.,
sondern nur Geraden. Ein Kreis wird also schon vom Plottertreiber im PC
in unzählige Geraden zerlegt. So braucht mein 8535 keine Kreise oder
Radien berechnen. Nur etwas mehr Speicher. Aber das ist nicht das
Problem, externes 62256-SRAM bringt genug Platz, denn selbst eine für
meine Zwecke aufwändige HPGL-Datei bringts gerade mal auf 28kB, und das
sind die ASCII-Zeichen, die ja wesentlich mehr Platz verbrauchen, als
nachher die reinen Koordinaten...

Nichts desto trotz, ich werd mir diesen Bresenham-Algo-Dingsda nochmal
genauer ansehen... Erstmal teste ich jetzt meine Tabelle :-)

Gruß,
Andi.

von Karl heinz B. (kbucheg)


Lesenswert?

> Wenn man aber mit einem Fräser unterwegs ist, dann
> erfordert es ja eine bestimmte Vorschubrichtung.

Schon richtig.
Sind aber alles nur Spiegelungen an einer Hauptachse bzw.
Diagonale. D.h. das muesste im wesentlichen auf eine Menge
geschickt verteilter Vorzeichenwechsel hinauslaufen.

Der unangenehmste Fall ist allerdings ein Kreisbogen.
Ich behaupte mal, dass Vollkreise gar nicht so häufig
vorkommen wie Bögen. Bögen sind richtig unangenehm. Die würde
ich wahrscheinlich mit n-seitigen Polygonen annähern
(dazu brauchts dann allerdings sin/cos) und den Bresenham
dann das Polygon fräsen lassen. Eine 2D-Transformation in
die Ursprungslage mit dem Anfang des Bogens auf 0 Grad und
Rückrechnung der einzelnen vom Kreis-Bresenham ausgeworfenen
Koordinaten in die gewünschte Lage ist zwar möglich, erscheint
mir allerdings hier wirklich mit Kanonen auf Spatzen.

von inoffizieller WM-Rahul (Gast)


Lesenswert?

>in unzählige Geraden zerlegt
Und dann nur 32K? Hmmm.... ;)

Wenn du sowieso nur Gerade abfährst, ist der Bresenham-Algorithmus die
erste Wahl.
Hast du in der Datei dann nur die anzufahrenden Punkte hintereinander
stehen (mit dem Zusatz der "Stifthöhe")?

>> L = sqrt( 2800 * 2800 + 2050 * 2050 ) -> 3470,23

Kann man auch dadurch vereinfachen, dass man alle Vergleichswerte für
Wurzelfunktion quadriert. Dann spart man sich die Wurzel...(Bresenham
arbeitet mit der gleichen Vereinfachung!)

von Karl heinz B. (kbucheg)


Lesenswert?

> Ich will ja NICHT, dass meine Fräse später eine Treppe abfährt,
> wie von Karl Heinz so schön beschrieben.

Das tusu du sowieso, das folgt schon daraus, dass dein
digital gesteuerter Fräser eben nicht jede Position
anfahren kann, sondern immer nur in Sprüngen arbeitet.
Solange die Sprünge aber nur fein genug sind, ist das
genau genug. Ob du die Sprünge jetzt mit deiner Methode
oder mit einem Bresenham berechnen lässt spielt keine
Rolle. Die Treppe hast du (ausser auf den Hauptachsen und
auf der Diagonale) durch das digitale Prinzip. Das ist wie
wenn du am Monitor eine Linie ziehts. Wenn du nicht in
den Hauptachsen zeichnest dann hast du Treppen im Linienzug.
Eine höhere Auflösung des Monitors verringert zwar diesen
Effekt kann ihn aber nicht eliminieren, weil er aus dem
System selbst entsteht.

von Karl heinz B. (kbucheg)


Lesenswert?

Viel Spass beim Austüfteln der Bewegung.

Es ist eine Sache, zu wissen dass bei 1280 Schritten in
X Richtung gleichzeitg 675 Schritte in Y gemacht werden
muessen. Aber das umsetzen, so dass diese Schritte dann tatsächlich
auch simultan gemacht werden ist eine ganz andere. Schliesslich
musst du im obigen Beispiel nach jedem 1,89629-ten Schritt in X
Richtung auch einen Schritt in Y Richtung machen :-)

Von wegen der Zyklen:
Das ist dein geringstes Problem. So schnell kannst du gar nicht
fräsen, wie der AVR rechnen kann. Die Rechengeschwindigkeit ist
also dein geringstes Problem.

von Andi (Gast)


Lesenswert?

@Rahul

Ja, stimmt, in meiner (bzw. die vom HP-Plotter-Treiber erzeugte)
HPGL-Datei stehen neben ein paar für mich unwichtigen Infos nur
absolute koordinaten, neben den paar "Pen-Up"/"Pen-Down" sowie
"Pen-Select" - Befehlen. Sogesehen wird also sogar der professionelle
HP-Plotter nur mit diesen absoluten Koordinaten angesprochen.
Glücklicher Weise, denn das vereinfach die Sache ungemein.

Mir ist schon klar, daß ich im Endeffekt eine Treppe abfahre, aber
dabei war ich halt der Meinung, daß das simultane ansteuern der beiden
Achsen durch die Trägheit der Antriebe eine gleichmäßigere Gerade
zustanden kommt, als wenn ich die beiden Achsen immer nur nacheinander
anfahre. Denn dann hab ich tatsächlich eine Treppe, angenommen ich hab
eine 45Grad-Schräge. In diesem Fall werden immer zur gleichen Zeit an
beiden Motoren ein Schritt ausgegeben, die erzeugte Bewegung ist also
tatsächlich auch eine Schräge. Steuere ich immer abwechselnd eine Achse
nach der anderen an, so erzeuge ich wieder eine Treppe...

Ok, agree, vermutlich wird das auch durch die Trägheit der Motoren
wieder ausgegelichen, sofern das ganze schnell genug passiert...

Egal - ich will jetzt erstmal meine Tabellentheorie testen, vielleicht
mache ich mir dann zum Vergleich immer nochmal die Arbeit, dieses
Bräsen-Halma zu probieren. ;-)

Achso, Karl-Heinz: In den meisten Fällen wirst Du wohl Recht haben, daß
meine Fräse gar nicht so schnell sein kann wie der AVR. Aber ich mach
mir trotzdem Gedanken darüber, wie schnell denn die Berechnung von
statten geht, denn da mein Kreis ja nur aus kurzen Geraden besteht,
wird der einzelne kurze Fräsabschnitt auch schnell beendet sein und bis
dahin muß ja die Berechnung der nächsten Geraden fertig sein, sonst muß
die Fräse ja auf ein und derselben stelle eine Weile (paar ms) lang
rumfräsen... :-/ Also nehme ich den worst case an und eine einzelne
Gerade beträgt nur 1/40mm ..... Leider weiß ich noch nicht, wie groß
die maximale Geschwindigkeit der Fräse sein wird, bei der Mechanik bin
ich nämlich auch noch bei. Ich warte immer noch auf diese sündhaft
teuren Linearführungen, die ich kürzlich bestellte... Und die
Vexta-Stepper sind auch noch nicht da (sollten aber jeden Moment kommen
:)

Gruß,
Andi.

von inoffizieller WM-Rahul (Gast)


Lesenswert?

>Egal - ich will jetzt erstmal meine Tabellentheorie testen,

Und wieder einer, der es lieber umständlich macht/machen will...

Übrigens wird dein System auch noch etwas vibrieren, was zur
"Verschleifung" der Treppe führt. Dass du ein rotierendes Werkzeug
benutzt, tut ein weiteres dazu.
Man sieht die Treppe nicht mal, wenn man ein Schleppmesser benutzt.
Wenn die Auflösung groß genug ist (möglichst viele Zwischenschritte von
einem Punkt zum nächsten), dann wird dir das auch nicht auffallen.
Ich werde mir die HPGL mal näher angucken...

@Karl-Heinz:
>der arbeitet auch nach dem vektoriellen Prinzip, dass die
>Hypotenuse des Dreiecks mit den Schenkeln X und Y gleich r ist.

Sollte das nicht sogar schon die Lösung für "mein" Problem mit den
Kreissgmenten sein: Bei gegebenem Kreismittelpunkt (oder Radius) und
gegebenen Start- und Endpunkten, sollte man mit der Beziehung x²+y² =
r² doch ein Kreissegment möglich sein. Den folgenden Punkt müsste man
doch durch minimieren dieser Gleichung herausfinden. Man muß x²+y² drei
mal aussrechnen, und die kleinste Abweichung zu r² herausfinden. Dann
sollte man den nächsten Punkt haben.
Ich rechne das mal durch...

von inoffizieller WM-Rahul (Gast)


Lesenswert?

Unter der Vorraussetzung, dass sich immer nur eine Achse bewegen darf,
reichen zwei Berechnungen.

von Andi (Gast)


Lesenswert?

:-))

>Und wieder einer, der es lieber umständlich macht/machen will...

Öhhh, naja, das wollte ich damit nicht sagen! Wie gesagt, ich schaue
mir diese Bresenham-Theorie nochmal an, bis ich aber soweit bin dauert
es eh ja noch nen Weilchen. Damit meinte ich ja nur, daß ich das
Problem der Tabellensuche erstmal lösen möchte. (Vor posten komm ich ja
kaum zum coden ;-) Denn darum ging es ja in diesem Threat ja eigentlich.
Das heißt nicht, daß ich das auch nachher so verwende, aber schließloch
werde ich das Binary-Tree-Verfahren wohl woanders auch noch brauchen
können, und sei es für andere spätere Projekte. Da ich mir darüber
gerade Gedanken gemacht habe und damit auch schon angefangen habe,
ziehe ich das jetzt erstmal durch, bevor ich mir weitere Gedanken um
die eigentliche cnc-Thematik mache.

Aber nur weiter so, ihr helft mir schon ganz gut weiter. ;-))

Gruß,
Andi.

von Karl heinz B. (kbucheg)


Lesenswert?

> Sollte das nicht sogar schon die Lösung für "mein" Problem mit den
> Kreissgmenten sein: Bei gegebenem Kreismittelpunkt (oder Radius) und
> gegebenen Start- und Endpunkten, sollte man mit der Beziehung x²+y²
> = r² doch ein Kreissegment möglich sein. Den folgenden Punkt müsste
> man

Das Problem das ich sehe ist folgendes:
Wenn du beim Kreis bei Alpha=0° bist, dann möchtest du lieber
y durchsteppen und ein x dazu suchen. Bei 90° ist es aber genau
umgekehrt.
Aber wenn ich mir das nochmal überlege: könnte wirklich gehen.

von Karl heinz B. (kbucheg)


Angehängte Dateien:

Lesenswert?

> Aber wenn ich mir das nochmal überlege: könnte wirklich gehen.

Zu früh auf "Submit" gedrückt.

Was ich meine ist: Auf einem Monitor möchtest du das definitiv
berücksichtigen, da du sonst Lücken in den Punkten hast.
Da da aber ein Fräser sowieso die Lücken quasi interpolierend
abfährt, hmm. Das einzige Problem das ich jetzt noch ausmachen
kann ist, dass du keine Kontrolle über die effektive Fräs-
geschwindigkeit mehr hast. Wenn der Fräser aus 0° heraus auf
die erste x/y Position fährt (wobei x sich um 1 verringert hat)
hat er einen relativ weiten Weg, im Vergleich zu dem Fall wenn
x die Mittelpunktskoordinate erreicht.

Das ist blöd zu erklären. ev. zeigt eine Zeichnung besser
was ich meine:
Wenn du rechts anfängst und zu gegebenem x ein y suchst, dann
ist der Sprung von einer y Koordinate zur nächsten (beim
nächstkleinerem x) relativ gross, während sich am oberen
Extremwert das ganze anders rum abspielt: Du kannst x
decrementieren ohne dass sich y gross ändert.
Konkret würde das dann heissen, dass der Fräser ziemlich schnell
loslegt und dann immer langsamer wird.

von inoffizieller WM-Rahul (Gast)


Lesenswert?

>Konkret würde das dann heissen, dass der Fräser ziemlich schnell
>loslegt und dann immer langsamer wird.

Nee, glaube ich nicht. Der Tisch bewegt sich ja immer nur um einen
Schritt, und das nur in eine Richtung (x ODER y).
Natürlich muß man eine Fallunterscheidung machen, welcher
Koordinaten-Anteil wie behandelt wird (relativ zum Mittelpunkt). Und
eine Abbruchbedingung ist auch nötig...
Ich werde mir mal eine Tabelle basteln...

von Andi (Gast)


Lesenswert?

Hallo!

Naja, leider paßt der ursprüngliche Betreff ja nun eigentlich nicht
mehr zum Thema. Hab ich mal abgeändert...

Ich hab mir aber gestern abend bezüglich dem Bresenham-Dingsda nochmal
Gedanken um folgenden Satz gemacht:

>Nee, glaube ich nicht. Der Tisch bewegt sich ja immer nur um einen
>Schritt, und das nur in eine Richtung (x ODER y).

Hmmmm. Das würde doch aber heißen, daß z.B. eine 45Grad-Diagonale
doppelt so lange braucht, anstelle der ~1,4 mal, wie es eigentlich sein
müßte??? 1000Steps in die y-Achse und 1000Steps in die x-Achse. Also
insgesamt werden 2000Steps ausgeführt...

Ich muß mir das gleich mal genauer Ansehen, mein Tabellenproblem, um
das es hier eigentlich ging, hab ich jedenfalls soweit gelöst. (Da mach
ich auch noch mal nen Extra-Thema auf...)

Gruß,
Andi

von inoffizieller WM-Rahul (Gast)


Lesenswert?

>Also insgesamt werden 2000Steps ausgeführt...

Das vermute ich auch.
Allerdings ist die 45°-Diagonale auch die Worst-Case-Betrachtung.
Dafür könnte man noch eine Fallunterscheidung machen (dX = dY).

von Andi (Gast)


Lesenswert?

Hallo!

Ja klar, die 45-Grad-Variante ist der worst-case, aber auch 46, 47, 60
oder sonstirgendwas paßt mit der einzuhaltenden
Vorschubsgeschwindigkeit nicht mehr überein. Also, selbst wenn man den
Bresenham-Algo nimmt, benötigt man immer noch eine Korrektur für die
Vorschubsgeschwindigkeit. Und genau hier kann meine Tabelle wieder
nützlich sein, denn daraus kann ich passend zum Achsverhätnis die
notwenidge Geschwindigkeitsanpassung ableiten.

Gruß,
Andi

von Karl heinz B. (kbucheg)


Lesenswert?

Du kannst davon ausgehen, dass alle heute benutzten
graphischen Geräte den Bresenham zum Linienzeichnen
benutzen.
Und eine 45 Grad Linie sieht auf Pixelebene immer so aus:


  *
   *
    *
     *
      *
       *

von inoffizieller WM-Rahul (Gast)


Lesenswert?

>Und eine 45 Grad Linie sieht auf Pixelebene immer so aus:

nach Bresenham würde sie IMHO aber eher so aussehen:
**
 **
  **
   **
    **
     **

von Karl heinz B. (kbucheg)


Lesenswert?

>> Nee, glaube ich nicht. Der Tisch bewegt sich ja immer nur um einen
>> Schritt, und das nur in eine Richtung (x ODER y).
> Hmmmm. Das würde doch aber heißen, daß z.B. eine 45Grad-Diagonale
> doppelt so lange braucht

Wir haben über Kreise diskutiert!
nicht über normale Linien.

Hol dir doch mal einen Bresenham, gibts wie Sand am Meer,
und experimentier mal mit konkreten Zahlen. Das Teil
ist echt genial: einfach im Aufbau, einfach in der Implementierung,
millionenfach (was red ich da: milliardenfach) bewährt und erledigt
seine Aufgabe ohne Probleme. Was will man mehr.

von Karl heinz B. (kbucheg)


Lesenswert?

> nach Bresenham würde sie IMHO aber eher so aussehen:
> **
> **
>  **
>   **
>    **
>     **

Darf ich vorschlagen, da schnappst dir eine Lupe und betrachtest
mal deinen Bildschirm genauer.

Wie gesagt: Wenn irgendwo Linien und Pixel im Spiel sind, kannst
du eine sichere Bank auf Bresenham wetten.

von inoffizieller WM-Rahul (Gast)


Lesenswert?

>paßt mit der einzuhaltenden
>Vorschubsgeschwindigkeit nicht mehr überein

Doch, du bewegst dich ja von einem Schritt zum nächsten immer mit der
gleichen Geschwindigkeit.
Bei deinem Verfahren "übergehst" du bloß du notwendigen
Zwischenschritte. Mit Schrittmotoren kann man keine Zwischenschritte
machen. Die arbeiten digital, wobei man die Auflösung sehr stark  durch
Microstepping erhöhen kann.
Wenn du wirklich die optimale Schnittgeschweindigkeit fahren willst
brauchst du noch eine weitere Achse, die dir dein Werkstück (um die
Z-Achse) dreht.

Zu langsam ist eigentlich nur ein Problem der Kühlung...

Ich werde mir son Ding auch endlich bauen/kaufen müssen.

von Karl heinz B. (kbucheg)


Lesenswert?

Dabei fällt mir auf:
Ich hab da weiter oben ganz schönen Blödsinn verzapft,
von wegen es gibt nur senkrechte und waagrechte Schritte.

Ein 'Bresenham' geht auch nur die Linie in x Richtung
durch und entscheidet ob die y Koordinate jetzt um 1
größer werden muss oder gleich bleibt.
Ja nach dem Quadrant wird die Rolle von x und y vertauscht
bzw. y wird nicht erhöht, sondern erniedrigt.
Der Bresenham ist deswegen so berühmt, weil er die für
dieses Verfahren notwendigen Floatingpoint-Operation in
den Integer-Bereich gebracht hat. Wenn du einen Tag Zeit
hast: Ich muss in meiner Bibliothek noch eine Quelle haben
in der die Herleitung des Bresenham aus einer naiven Floating-
Point Implementierung drinn ist. Da komme ich aber erst
heute abend ran.

von inoffizieller WM-Rahul (Gast)


Lesenswert?

@Karl-Heinz:
Stimmt! (manchmal ist Paint sehr praktisch...)
Wenn man das aber auf eine Fräsmaschine überträgt, die die Schritte nur
nacheinander ausführen kann, dann habe ich recht.
Die Version mit dem Monitor arbeitet nicht wie eine Fräse, sondern eher
eine Bohrmaschine (mit Kreuztisch): Sie macht einen Schritt in die eine
Richtung, dann den in die andere und dann wird der Bohrer abgesnkt (der
Punkt der Linie gesetzt).
Die Fräse arbeitet aber im Material, ohne jedes Mal den Fräskopf
anzuheben.
Verstehst du, was ich meine?
Der Fräser legt jeden Schritt zurück, den der Algorithmus braucht.

von inoffizieller WM-Rahul (Gast)


Lesenswert?


von Karl heinz B. (kbucheg)


Lesenswert?

>> paßt mit der einzuhaltenden
>> Vorschubsgeschwindigkeit nicht mehr überein
>
> Doch, du bewegst dich ja von einem Schritt zum nächsten immer mit
> der gleichen Geschwindigkeit.

Andi hat schon recht.
Das war ein Trugschluss von mir.
Ein Bresenham der eine Linie von 0/0 nach 100/100 führt
setzt auch nur 100 Pixel. Genausoviele wie wenn die Linie
von 0/0 nach 100/0 gehen würde. Die Strecke ist aber im
ersten Fall um den Faktor sqrt(2) länger.

Irgendwie haben wir da jetzt einen Wirbel hineingekriegt
und zu meiner Schande muss ich gestehen, dass ich da der
Hauptschuldige bin.

Aber die Tabelle wird jetzt trivial: Berechne das Verhältnis
von x zu y (bzw. je nach 'Quadrant' y zu x ) normiere es auf,
sagen wir mal, 16 Werte und benutze das Ergebnis als Index in
die Tabelle um daraus die Vorschubgeschwindigkeit zu erhalten.
Es gibt keinen Grund in der Tabelle eine Suche zu veranstalten
und besagte 16 verschiedene Werte sind, denke ich mal, genug
um für einen Bereich von 45° die Vorschubgeschwindigkeit
ausreichend genau zu korrigieren.

von Karl heinz B. (kbucheg)


Lesenswert?

> Wenn man das aber auf eine Fräsmaschine überträgt, die die
> Schritte nur nacheinander ausführen kann, dann habe ich recht.

Das würde ich nicht so machen.
Ich würde eher soweit gehen und sagen:
mögliche Schritte sind
  waagrecht   (nur X)
  senkrecht   (nur Y)
  diagonal    (ein Schritt in X und Y)

von inoffizieller WM-Rahul (Gast)


Lesenswert?

Eine Fallunertscheidung mehr? Warum auch nicht.

von Andi (Gast)


Lesenswert?

Moiiiiin! :-)

>Andi hat schon recht.
Hehe, danke, also doch -grinz- :-)

>Das war ein Trugschluss von mir.
>Ein Bresenham der eine Linie von 0/0 nach 100/100 führt
>setzt auch nur 100 Pixel. Genausoviele wie wenn die Linie
>von 0/0 nach 100/0 gehen würde. Die Strecke ist aber im
>ersten Fall um den Faktor sqrt(2) länger.

Nach vielem Hin und Her und wieder hin oder dann doch nicht...: Genau
dieses war mein ursprüngliches Problem, wofür ich eine Lösung suchte.
Und genau dafür wollte ich eine Tabelle verwenden. Die eigentliche
Bewegung, die ich, nachdem ihr mich auf den Bresenham gebracht habt,
wohl auch damit lösen werde, war eigentlich gar nicht das Thema dieses
Treats.

Aber macht ja nix, denn auf jeden Fall war es nützlich für mich. :-)
Den Bresenham für die Bewegung, die Geschwindigkeitskorrektur mittels
Tabelle.

>normiere es auf,
>sagen wir mal, 16 Werte und benutze das Ergebnis als Index in
>die Tabelle um daraus die Vorschubgeschwindigkeit zu erhalten.

Was genau meinst Du mit "aufnomieren"?  Vielleicht löse ich das
Problem ja wirklich etwas zu umständlich, in einer Tabelle nach meiner
Geschwindigkeitskorrektur zu suchen. Für die komplette Prozedur (siehe
anderen Treat von mir,
http://www.mikrocontroller.net/forum/read-1-405057.html ) benötige ich
etwa 250 Taktzyklen. (Wie weiter oben beschrieben hoffte ich, daß
Problem mit Roundabout 50Zyklen zu erledigen). Hinzu kommt noch die
vorherige 24Bit-Division zur Ermittlung des Achsverhältnisses
(multipliziert mit 256, damit ich ohne Komma-Werte auskomme)

Gruß,
 Andi.

von Andi (Gast)


Lesenswert?

Uiii, jetzt fällt mir noch was auf...

Auf der Website, die Rahul weiter oben verlinkt hatte, steht ja ganz
gut beschrieben, auch für nicht Mathematiker wie mich ;-), wie dieser
Algo für nen Plotter funktioniert. Und nachdem ich das Bild

http://turing.fh-landshut.de/~jamann/bresenham-Dateien/image021.jpg

gesehen habe, kam mir doch noch eine Idee: Der Plotter macht demnach ja
tatsächlich nur 2 Bewegungen: gerade oder schräg.

Wenn man jetzt annimmt, der "Plotter" macht alle 100 Zeiteinheiten
einen Step in einer geraden Richtung, muß ich doch nur noch diese
Zeiteinheit auf 141 Zeiteinheiten hinaufsetzen, sofern eine schräge
Richtung durchgeführt werden muß.

Bei gleicher Entfernung auf der x-Achse dauert damit eine Linie im
45-Grad-Winkel 1,41 mal so lange, wie eine 0-Grad-Linie, denn sie ist
ja auch 1,41mal so lang. Ist der Wert irgendwo dazwischen, werden ja
gerade sowie auch schräge "Teillinien" abgearbeitet, somit liegt also
auch die Zeitspanne irgendwo zwischen 1,00 und 1,41...

Oder was meint Ihr? Dann könnte ich meine Tabelle für die
Geschwindigkeitsberechnung doch komplett vergessen. :-) Einziger
Nachteil wäre, daß keine wirlich lineare Bewegung mehr ausgeführt wird,
die Steppermotoren werden mit Einzelschritten in unterschiedlichen
Zeitabständen angesteuert. Ob das wieder zu Vibrationen führt? Ich
denke, dazu muß ich doch erstmal die "Hardware" fertig haben und das
ganze mal ausprobieren...

Zumindest kann ich somit für Softwareversion 1.0 einiges an Code und
somit an Arbeit sparen ;-)

Also dann, Danke nochmal für den Hinweis auf Bresenham! :-))

Gruß,
Andi

von Karl H. (kbuchegg)


Lesenswert?

> Wenn man jetzt annimmt, der "Plotter" macht alle 100 Zeiteinheiten
> einen Step in einer geraden Richtung, muß ich doch nur noch diese
> Zeiteinheit auf 141 Zeiteinheiten hinaufsetzen, sofern eine schräge
> Richtung durchgeführt werden muß.

Bingo!

> Einziger Nachteil wäre, daß keine wirlich lineare Bewegung mehr
> ausgeführt wird

Hast du schon mal ausgerechnet, welche Distanz dein Kreuztisch
bei einem einzigen Stepper-Schritt machen wird?

von inoffizieller WM-Rahul (Gast)


Lesenswert?

Übrigens entstand meine "Gerade" unter der Voraussetzung, dass die
Motoren nur einen Schritt in die eine oder (xor) die andere Richtung
macht. Das wäre zwar schonender für die Stromversorgung, aber nicht
unbedingt praxistaulich/-üblich.

Wenn man sowieso nur 2 verschiedene Richtungen einschlagen kann, hat
man ja auch nur 2 verschiedene Geschwindigkeiten von einem Punkt zum
nächsten. Aber ob das überhaupt sinn macht, das noch zu unterscheiden,
weiß ich nicht. Ich würde für den Anfang zusehen, dass ich überhaupt
erst mal die Strecke zwischen zwei Punkten abfahren kann...

von Karl heinz B. (kbucheg)


Lesenswert?

Ich denke Plotter korrigieren die Geschwindigkeit tatsächlich.
Bei meinem alten Roland-Plotter (HP7475 kompatibel) ist
die Stiftgeschwindigkeit schon ziemlich konstant was ich
mich so erinnern kann. Macht auch Sinn, da mann mit Tusche
bzw. Faserstiften nicht beliebig schnell fahren kann.

von Andi (Gast)


Lesenswert?

Hallo!

>> Einziger Nachteil wäre, daß keine wirlich lineare Bewegung mehr
>> ausgeführt wird
>
>Hast du schon mal ausgerechnet, welche Distanz dein Kreuztisch
>bei einem einzigen Stepper-Schritt machen wird?

Ja, klar. Die von mir verwendeten Bauteile ergeben eine (theoretische)
Distanz von 1/100mm pro Vollschritt, ich werde allerdings für den
Anfang erstmal Halbschritte nehmen, später ganz gerne auch Microsteps,
je kleiner desto besser. Darin liegt ja aber auch nicht das Problem.

Vermutlich hast Du recht, ich werd das auch einfach so ausprobieren.
Meine Angst besteht nur darin, daß das Ding durch die ungleichmäßigen
Zeitabschnitte der einzelnen Steps anfängt zu vibrieren, oder die
Stepper gar irgendwelche Schritte verlieren bzw zu viel machen. Ich
weiß ja nicht, wie das ganze Teil nachher darauf reagiert, wenn ich
z.B. 10 Steps hintereinander mit je 1000us Zeitabstand fahre und dann
mal zwischendurch einen, der 1414us Zeitabstand hat. Schließlich spielt
die Trägheit des ganzen auch noch eine Rolle... Ich denke mal, ab einer
gewissen Geschwindigkeit könnte das zu Problemen führen, oder nicht?

Gruß,
Andi

von Karl heinz B. (kbucheg)


Lesenswert?

> Darin liegt ja aber auch nicht das Problem

Na ja.
Ohne jetzt deine Mechanik zu kennen: 1/100 mm ist schon
recht wenig. Da muss die Mechanik zwischen Motor und
Fräse schon super sein, damit du dir auf dem Weg dazwischen
nicht noch mehr Spiel aufreist.

> Ich denke mal, ab einer gewissen Geschwindigkeit könnte das zu
> Problemen führen, oder nicht?

Das kann schon sein.
Auf der anderen Seite, wenn ich mich so zurückerinnere:
Die Fräser fahren ja relativ langsam durch das Material.
Anfahren und Stoppen wirst du sowieso über eine Rampe
machen müssen (noch ein Grund für das augetüftelte
Verfahren: Du kannst die Geschwindigkeit ganz leicht
von 0 weg steigern bzw. auf 0 abbremsen)

Aber ich würde es auch so machen: Einfach probieren.
Mit der Geschwindigkeit zurückgehen kann man dann immer
noch :-)

von Andi (Gast)


Lesenswert?

Ja, ich schätze auch mal, daß ich mehr Spiel in der Mechanik haben
werde, als die theoretische mechanische Auflösung von 1/100mm pro
Vollstep = 1/200mm bei Halbstep. Meine HPGL-Dateien haben auch "nur"
eine Auflösung von 1/40mm, daß bedeutet eh, daß ich je vom PC
übertragenen Punkt 5 Steps machen muß.

In der Datei des PCs beträgt also eine 1mm lange Linie 40 Punkte (z.B.
von Koordinate 1000 zu 1040, meine Fräse muß für diese Strecke
insgesamt 200 Steps machen, also genau 5 mal so viel.

So, nun gehts aber langsam an die Arbeit, hab gestern meine Linearlager
bekommen. :-)

Gruß,
Andi

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.