3D- Algorithmus- Idee gesucht
-
Hi CNC-Freak,
mein Code IST der Flaschenhals, aber ich kann daran nichts ernsthaft optimieren.
An 2) bleibt der Algorithmus hängen, der Findung des Punktes, durch den eine sinnvolle Interpolationsgerade gelegt werden kann.
Soll ich wirklich nach Kriging 10'000 Einträge durch 'ne Matrizeninversion jagen und damit Rechenzeit sparen?
Ich habe übrigens nur 1 MB RAM, was eh schon üppig für 'nen Controller ist. Nöh, am PC geht's ja schon so, nur beim Downsizen wird's knifflig ... :xmas2:
-
pointercrash() schrieb:
mein Code IST der Flaschenhals, aber ich kann daran nichts ernsthaft optimieren.
An 2) bleibt der Algorithmus hängen, der Findung des Punktes, durch den eine sinnvolle Interpolationsgerade gelegt werden kann.sag niemals nie. vielleicht kann man doch noch was rausholen. benutzt du floats und hast keinen rechenknecht eingebaut? ein muktitasking-os oder viele interrupts, die rechenzeit abzwacken? machst du vielleicht zu aufwendige berechnungen in schleifen, die man auch vorher machen könnte? schon mal den generierten asm-code angeschaut? compilereinstellung auf 'optimize for speed'?. all das kannste mal checken. und schliesslich, vielleicht gibt es 'nen besseren algo für sowas. da musste mal googlen oder vielleicht meldet sich noch ein 3-d spielecoder hier (die müssten sowas eigentlich gut auf'm schirm haben).
-
Hi Opti,
oh ja, float ist mit drin, weil ich damit den Radius über die Wurzelfunktion (nach Pythagoras) ermittle, eine FPU hat die Kiste nicht. Mittels des Kreis- Bresenhams ermittle ich dann die Außenkontur im Raster, dann zerfällt alles zum Koordinatenvergleich in INT.
Das war bislang die flotteste Methode, alle Versuche, daran zu drehen voll nixi
Ich mache mir eigentlich einen Kopf wg. des grundlegenden Algorithmus, und da wären wohl wirklich die Spieleprogr gefragt.Tja ... und dann?
-
pointercrash() schrieb:
oh ja, float ist mit drin, weil ich damit den Radius über die Wurzelfunktion (nach Pythagoras) ermittle, eine FPU hat die Kiste nicht.
au weia, das ist echt übel. du ahnst vielleicht nicht, wie viele taktzyklen eine einfache, allerdings emulierte float-operation verschlingen kann. geschweige denn von sqrt() und sowas. vielleicht solltest du darüber nachdenken, alles mit fixkomma bzw. int (geht fast immer) zu machen oder dem device eine FPU zu spendieren.
pointercrash() schrieb:
Ich mache mir eigentlich einen Kopf wg. des grundlegenden Algorithmus...
ja, würde ich auch. der richtige algorithmus schlägt alle optimierungen. das ist ein 'naturgesetz'.
-
integer-freak schrieb:
ja, würde ich auch. der richtige algorithmus schlägt alle optimierungen. das ist ein 'naturgesetz'.
Ja, genau! Mit brute force geht dem Rechner die Puste aus, deswegen mein Hilferuf.
Um's nochmal anschaulicher zu machen: Nehmt einen dreibeinigen Tisch, kürzt ein Bein des Tisches und hobelt in dessen Mitte eine Kuhle raus. Das ist das Werkstück. In den Tisch muß "I :xmas1: You" geschnitzt werden. Eine zweite Zeile gibt es auch noch, und eine dritte, sonst wär's langweilig.
Der Motivschnitzer ist ein Automat, der die Außenkonturen aller Buchstaben und Motive abfährt, und damit über den Fehlstand des Tisches und die Kuhle theoretisch Bescheid weiß und er muß seine Schnitzbefehle entsprechend anpassen.
Aber unser Schnitzer ist kein 4,6 GHZ QuadCore- PC, sondern ein 24 MHz- Controller, also Paralympics- Klasse.
Meine Idee war, vom Punkt des Schnitzkommandos den nächstliegenden Punkt der Vermessung zu finden und dann einen geeigneten Punkt, um eine Gerade auszurechnen, um unserem Schnitzer mitzuteilen, inwieweit er tiefer oder höher schnitzen muß.
Alle Klarheiten beseitigt?
-
Wie wäre es die Berechnungen einfach von einem modernen Rechner durchführen zu lassen und dann nur noch das fertige Ergebnis an den alten 386er Controller zu übermitteln?
-
HighEndMachineFan schrieb:
Wie wäre es die Berechnungen einfach von einem modernen Rechner durchführen zu lassen und dann nur noch das fertige Ergebnis an den alten 386er Controller zu übermitteln?
Weil die Datenübertragung dann zum Flaschenhals wird. Einmal hin, einmal her mit 115 kBaud, mehr geht leider nicht wirklich, ob da die Kiste an den eigenen Daten nuckelt oder das Zeug zweimal verschoben wird, richtig zulegen wird das Konzept so nicht.
-
so wie ich das sehe hast du zwei optionen:
1. einen besseren algo finden.
2. den bisherigen code zu optimieren
ich behaupte mal ganz frech, dass bei punkt 2 noch eine menge möglich ist d.h. dass du die grenzen deines bisherigen algos nicht ausgegelotet hast (das zeigen deine bisherigen antworten. läuft dein x86-target etwa im real-mode? benutzt dein device ein OS?) der unterschied von 24Mhz zu 4.6Ghz beträgt etwa faktor 190. ich kenne deinen code nicht, aber es könnten bremsen drin sein (floats ohne FPU z.b.), deren beseitigung diesen faktor verkleinern könnten, so dass es passt.
-
du honk, dafür hat er doch den thread aufgemacht
-
pointercrash() schrieb:
Weil die Datenübertragung dann zum Flaschenhals wird. Einmal hin, einmal her mit 115 kBaud, mehr geht leider nicht wirklich, ob da die Kiste an den eigenen Daten nuckelt oder das Zeug zweimal verschoben wird, richtig zulegen wird das Konzept so nicht.
Hat der Controller keine andere Anschlußmöglichkeiten?
Z.B. nen ISA Bus, dann würden schon 8 MBit/s durchpassen?Vielleicht sind auf der Platine Kontaktstellen, die nur nicht
mit ner Buchse/Stecker etc. belegt sind?
-
wenn ich das richtig verstanden habe, fährt der fräskopf nur in zwei dimensionen und die z-achse dient lediglich dazu, um die frästiefe festzustellen?
durch die geringe anzahl der scanpunkte im vergleich zu den positionen, die der fräskopf anfahren kann, würde ich das zielgebiet wahrscheinlich in quadrate aufteilen. im "schlimmsten" fall spannt jeder scanpunkt ein quadrat auf. für speed up können beliebig viele adjazente punkte zu einem gemittelten quadrat zusammengefasst werden.
was zu jedem dieser quadrat a priori berechnet wird, ist der korrekturgradient, der auf die fräspositionen angwendet werden muss, um die korrekte position zu erreichen.
der vorteil dieser methode ist, dass zur bestimmung des korrekturpunktes dann "nur noch" das quadrat bestimmt werden muss, in dem er liegt. wenn man die quadrate dann beispielsweise in einer octree ähnlichen struktur speichert, kann man sie sehr schnell bestimmen.
-
problemlöser-freak schrieb:
so wie ich das sehe hast du zwei optionen:
1. einen besseren algo finden.
2. den bisherigen code zu optimieren
ich behaupte mal ganz frech, dass bei punkt 2 noch eine menge möglich ist d.h. dass du die grenzen deines bisherigen algos nicht ausgegelotet hast (das zeigen deine bisherigen antworten. läuft dein x86-target etwa im real-mode? benutzt dein device ein OS?) der unterschied von 24Mhz zu 4.6Ghz beträgt etwa faktor 190. ich kenne deinen code nicht, aber es könnten bremsen drin sein (floats ohne FPU z.b.), deren beseitigung diesen faktor verkleinern könnten, so dass es passt.
Hi, erstmal zur Technik:
Es ist ein M16C62 "nackt", also ohne OS mit 1 MB RAM und SDCard- Port, den ich mit einer FAT32- Library ansteuere. Zwar könnte ich die Files schneller transferieren, aber halt nur seriell mit einem 1- Byte- Buffer und da gibt's noch zwei weitere Schnittstellen, die in einem bestimmten Timing bedient werden MÜSSEN. Das System ist so, da kann ich nichts dran ändern, es gibt auch keine FPU.Optimierung:
Ich habe den Radius rausgeschmissen und suche jetzt nur noch Punkte, die in x oder y eine bestimmte, jedoch maximale Entfernung haben. Das hat doch etliche Vergleiche weniger bedeutet und Float weitgehend geschmissen. So etwa 20% schneller jetzt, aber noch nicht der Hit.
Die Berechnung der Geraden könnte ich auch noch auf INT umstellen, aber das ist nachrangig, die meiste Zeit bleibt bei der Suche nach den Punkten über. Ich habe eher den Verdacht, daß mein Algorithmus Blödsinn ist.Algorithmus:
Der erste Punkt ist derjenige, der dem Werkzeugpunkt in x und y am nächsten ist. Das kostet mit brute force schon Zeit, die Suche nach dem zweiten geeigneten Punkt ist dann die Performance- Katastrophe. Ist zwar schon hundert Jahre her, aber da muß man wohl datenbankmäßig herangehen und die Punkte geeignet indizieren. Heißt, ich schnappe mir mal meine alten dBase- Mappen und gehe damit in Klausur.
-
cnc-noob schrieb:
... für speed up können beliebig viele adjazente punkte zu einem gemittelten quadrat zusammengefasst werden.
was zu jedem dieser quadrat a priori berechnet wird, ist der korrekturgradient, der auf die fräspositionen angwendet werden muss, um die korrekte position zu erreichen.
der vorteil dieser methode ist, dass zur bestimmung des korrekturpunktes dann "nur noch" das quadrat bestimmt werden muss, in dem er liegt. wenn man die quadrate dann beispielsweise in einer octree ähnlichen struktur speichert, kann man sie sehr schnell bestimmen.
Ha ja, das klingt gut ... hast Du mir ein paar Links dazu?
-
Es ist ein M16C62 "nackt"
war nicht gestern von einem 368DX die rede?
-
x86-fan schrieb:
Es ist ein M16C62 "nackt"
war nicht gestern von einem 368DX die rede?
ich glaube es war ein 386DX, DX ohne FPU
emm.. und wie passen eigentlich
P(x,y,z)... 10'000 Punkte ...1'000'000 Punkte
in 1MB? wie kommen die daten ueberhaupt auf den controller? (ich bin kein cnc freak dass ich das voellig nachvollziehen koennte).
Weil die Datenübertragung dann zum Flaschenhals wird. Einmal hin, einmal her mit 115 kBaud
irgendwoher muessen die daten kommen, ich waere auch der meinung dass ein schnellerer rechner die daten vorverarbeiten koennte.
was mich zu der naechsten fragen fuehrt:
Ein PC (A64-3000) hat mittlerweile so eine Power, daß mein Primitiv- Algorithmus hinhaut, aber der Controller (~386DX40), auf dem es eigentlich laufen soll, geht damit völlig in die Knie.
ueber welche zeitdimensionen sprechen wir hier eigentlich?
und wie schnell ist der speicher auf dem PIC ? koennte es sein dass der das limitierende bei dem ganzen ist?und noch ne dumme frage (wie gesagt, bin kein cnc-freak):
waere es nicht moeglich die 3d aufgabe in viele kleine 2d aufgaben aufzuteilen? sodass du schichtenweise arbeiten wuerdest? oder muss das ganze irgendwie am stueck gemacht sein?btw. ein bild von so ner fraesearbeit waere nett um uns mal neidisch zu machen
:xmas1:
-
das mit den 1 mio. punkten hat mich jetzt auch gerade stutzig gemacht ^^ die passen ja nie und nimmer in 1 MB ram, also müssen die entweder sequentiell durchlaufen werden oder - das wäre die spaßbremse schlechthin - werden für jede suche vom massenspeicher nachgeladen.
nochmal zu den vorgaben:
- die ideelle fräsfläche ist planar (tischplatte)
- unebenheiten und fehlstellungen führen zu korrekturen in allen drei achsendie fräsfläche wird als rechteck angenommen. jeweils vier scanpunkte werden zu einem rechteck zusammengefasst (das macht bei 10.000 gleich verteilten scanpunkten maximal 99*99 rechtecke). die vier eckpunkte eines solchen rechtecks bestimmen direkt den korrekturgradienten ( = neigung der fläche). d.h. der gradient kann sehr günstig bestimmt werden und im schnitt muss auf 100 reale positionen nur ein gradient berechnet werden.
soll jetzt ein neuer punkt angefahren werden, wird bestimmt, in welchem rechteck er liegt. dazu wird im grunde divide & conquer angewendet. d.h. es werden nicht alle rechtecke durchsucht, sondern zunächst die suche auf eine hälfte der fräsfläche beschränkt, dann auf eine hälfte der bestimmten hälfte usw. bis die gewünschte granularität erreicht ist.
die rechtecke werden dazu "indiziert", wobei nur die x und y komponente eines rechtecks als index dient.
es kann also durch maximal ld(99*99) prüfungen das rechteck bestimmt werden.durch den gradienten kann jetzt die korrektur nicht nur der z-achse, sondern auch der x/y-komponente bestimmt werden. sollte nur die z-achse wichtig sein, reduziert sich die berechnung des gradienten sogar lediglich auf die berechnung eines mittelwerts (der eckpunkte) und eines summanden. d.h. die korrektur ist eine kostengünstige addition.
-
cnc-noob schrieb:
das mit den 1 mio. punkten hat mich jetzt auch gerade stutzig gemacht ^^ die passen ja nie und nimmer in 1 MB ram, also müssen die entweder sequentiell durchlaufen werden oder - das wäre die spaßbremse schlechthin - werden für jede suche vom massenspeicher nachgeladen.
Eben nicht, nur die Korrekturdaten, also die gemessene Punktwolke bleibt im RAM. Das läuft so ab:
- Ich lasse mir die Bahndaten der Außenkonturen berechnen und fahre die aber ohne z- Bewegung, sondern mit einem Distanzmesser nur in x und y ab, was zu der Punktwolke führt.
- Dann kriege ich die echten Fräsdaten, die ich erstmal auf die SD- Karte schaufle. Die enthält natürlich viel mehr Information, Vorgabe war, bis zu einer Mio Punkten dort halten zu können. Momentan habe ich 1 GB drin, aber das Filesystem kann auch 16GB- Karten korrekt verwalten.
- Dann die Fräsdatei Befehl für Befehl holen, mit den Werten aus der Punktwolke korrigieren und wieder auf SD- Karte ablegen. Die paar Mikrosekunden Lesen und Schreiben sind's nicht, die Punkte für die z-Korrektur kostet die Zeit.
- Dann erst schicke die Daten an die Achsensteuerung. Bei einer unkorrigierten Bahn habe ich keinerlei Zeitprobleme. In einer anderen Applikation erzeuge ich auf der gleichen Hardware während des Parsens der Fräsdatei etwa 30 kHz Stepperimpulse und da war noch Luft - keine Buffer- Underruns.cnc-noob schrieb:
nochmal zu den vorgaben:
- die ideelle fräsfläche ist planar (tischplatte)korrekt.
cnc-noob schrieb:
- unebenheiten und fehlstellungen führen zu korrekturen in allen drei achsen
Fast, nicht ganz. Ich habe nur ein Dreiachssystem, wobei die Fläche nahezu plan ist, aber manchmal nicht ganz. Wenn ich jetzt nicht auch noch auf die Werkzeuggeometrie achtgeben mag, lasse ich x und y und kompensiere nur in z-Richtung. Ziel ist es, Inschriften in Granit zu fräsen. Der kommt normalerweise plangeschliffen, aber wenn ein alter Stein nur restauriert und neu graviert werden soll, hat er an Stelle der alten Inschrift nach dem Ausschleifen eine Kuhle von bis zu 2,5 mm. Jetzt nimm auch noch an, daß die durchschnittliche Graviertiefe logischerweise auch so 2-3 mm beträgt und gehe von einem V-förmigen Fräsprofil des Werkzeugs aus, dann wird klar, daß die Maschine das besser wissen sollte. Zudem langt die Werkstückpositionierung auch systembedingt so +-0.5mm daneben, d.h. die gesamte Tischplatte liegt auch ein bißchen schief. Glaub's oder nicht, man sieht das dann echt am Schriftbild.
cnc-noob schrieb:
die fräsfläche wird als rechteck angenommen. jeweils vier scanpunkte werden zu einem rechteck zusammengefasst (das macht bei 10.000 gleich verteilten scanpunkten maximal 99*99 rechtecke).
Da liegt schon mal der Hase im Pfeffer. Ich verwende eine Konturbahn, die ich full Speed abfahre und scanne die z-Entfernung derweil in isochronen Abständen. Da aber die Achsen beschleunigen und verzögern, sind die Punkte nicht äquidistant und es wäre purer Zufall, wenn in dem feineren Raster der Maschine auch nur zwei x- Koordinaten identisch wären.
Da mir der Rest, wie man durch Aufteilen nach "unten" sucht, halbwegs klar ist, wie Du's wohl meinst frag' ich mal andersrum:
Ich baue mir einfach ein gröberes Raster, ab dem ersten Punkt hat das Quadrat nur eine Tiefe, bis zu zwei weitere Punkte "kippen" das Quadrat, aber ab dem vierten Punkt könnte mir das Quadrat in Dreiecke aufbrechen. Was mache ich da dann damit? Das ist das Einzige, was ich jetzt nicht verstehe.
-
rapso schrieb:
ich glaube es war ein 386DX, DX ohne FPU
Jein, es ist definitiv ein M16C62, weil den aber nicht jeder kennt: Der packt ungefähr soviel weg wie ein 386DX40 ohne FPU.
rapso schrieb:
emm.. und wie passen eigentlich
müssen sie gar nicht, siehe Klarstellung, die Erste.
rapso schrieb:
irgendwoher muessen die daten kommen, ich waere auch der meinung dass ein schnellerer rechner die daten vorverarbeiten koennte.
Die Hardware ist, wie sie ist. Hin- und Herschicken ist zwar eine Lösung, aber dann müßte ich mir Gedanken machen, wie man eine ausgefuchste, timingkritische Totmannkette überarbeitet. Lieber nicht, wenn's anders geht. Und es muß anders gehen, denn ein Mitbewerber hat nur ein olles 68'00er- Derivat auf der Karte und kann's auch. Das ist dann eine Frage des Ehrgeizes.
rapso schrieb:
ueber welche zeitdimensionen sprechen wir hier eigentlich?
und wie schnell ist der speicher auf dem PIC ? koennte es sein dass der das limitierende bei dem ganzen ist?Deswegen der Vergleich mit dem 386er - in der Dimension bewegt sich das.
Auf dem PC waren 5000 Meßpunkte mit 15'000 Bahnpunkten (das ist das übliche Verhältnis) in unter einer Minute "durch", auf dem Controller in einer halben Stunde so knapp ein Viertel bearbeitet, bevor ich das abgebrochen habe. Also etwa Faktor 130 langsamer.rapso schrieb:
waere es nicht moeglich die 3d aufgabe in viele kleine 2d aufgaben aufzuteilen?
Zerfällt denn nicht alles zuletzt in eindimensionale Bit ein/Bit aus- Aufgaben? Ich glaube einfach, daß mein übergeordneter Ansatz der Abstraktion Quatsch mit Soße war, deswegen der Thread hier.
rapso schrieb:
btw. ein bild von so ner fraesearbeit waere nett um uns mal neidisch zu machen
Meinst Du wirklich? Ich hab'ein paar freigegebene Sachen, mag aber niemanden langweilen ...
-
fuer das suchen von nahesten punkten bietet sich ein KD-tree am besten an, eigentlich.
Eine einfache optimierung fuer dein bestehendes system waere es die punkte in einem gewissen bereich in eine zweite liste aufzunehmen. in dieser koennten alle punkte in einem radius von z.b. 5% der punktwolke. da du sehr lokal suchst, haettest du in diesem 'cache' eigentlich immer die besten kandidaten. bewegst du dich mal weiter als 50% von der mitte der 'cache-wolke' zum rand, baust du eine neue auf.
so koenntest du leicht faktor 100 an speed bekommen. ist aber sehr abhaengig von den inputdaten, dem radius und der update rate.und ich waere an bildern interesiert, wir haben dafuer sogar einen thread
-
rapso schrieb:
Eine einfache optimierung fuer dein bestehendes system waere es die punkte in einem gewissen bereich in eine zweite liste aufzunehmen.
Bin gerade dabei, sowas zusammenzukrickeln und es schaut so aus, als würde das die Suche nach dem ersten Punkt schon gewaltig beschleunigen. Ich mache einen Lauf durch alle Punkte und mache eine "Bounding Area" auf, die ich immer weiter halbiere und sortiere die Punkte da hinein, danach liegen die als hierarchischer Baum da. Ich habe noch zuviele Bugs im Code, um wirklich was sagen zu können, aber ich mache in der Richtung weiter.
rapso schrieb:
in dieser koennten alle punkte in einem radius von z.b. 5% der punktwolke. da du sehr lokal suchst, haettest du in diesem 'cache' eigentlich immer die besten kandidaten.
Ja, für den ersten Punkt schon, aber ich muß in Erinnerung rufen, daß damit nur die halbe Arbeit getan ist. Ich muß ja hauptsächlich die Korrektur für x/y- Paare finden, die ich NICHT abgefahren habe, deswegen hat mir die Idee der Gradientenbildung für Flächenbereiche gefallen.
rapso schrieb:
und ich waere an bildern interesiert,
Gut, ob das zu T&L und Shading paßt, wage ich zu bezweifeln, aber da ist ein Filmchen einer anderen Anwendung der gleichen Steuerung, die es auf 17 m/min bringt und orthopädische Schuh- Einlagen fräst: Einlagen auf Krankenkasse. Dann habe ich noch Das gibt's nicht auf Krankenkasse, als am Testwerkzeug von Weiss die Schneiden kaputtgefahren wurden - nächster Versuch Mitte Januar. Man sieht am unteren Bildchen das Problem sehr deutlich, wenn die Platte nicht ganz plan ist. Ein gekauftes STL- Halbplastikmodell haben wir aus so einer Art Kunststein herausgekratzt. Ist so unscharf, weil man sonst die Werkzeugbahnen zu genau sieht. :p
