G-Code optimaliseren

[Douwe]

Beste CNCers,

Bij het maken van printplaten met eagle en pcb-gcode heb ik gemerkt dat er heel inefficiente toolpaths worden geproduceerd door pcb-gcode. Verder heb ik dit ook regelmatig met andere programma's (je moet dan precies in de goede volgorde alles aanklikken).

Nu dacht ik hier moet een oplossing op te bedenken zijn. En zo ben ik begonnen een simpel stukje software te schrijven waarin je een bestaande g-code kunt laden en die vervolgens optimaliseren.
Dit wil ik doen door de code in stukken te hakken op de G00 commandos en ze opnieuw op een efficientere manier terug te plaatsen, zodat de totale beweging boven het werkstuk zo kort mogelijk is. Ik ben niet van plan het daadwerkelijke frezen aan te gaan passen!

Mijn eerste opzetje ziet er als volgt uit:

Een stukje software waarin de g-code geladen wordt (in dit geval drill.nc).
De software laat onderin het toolpath zien (alleen de rapid movements.. dus G00). Ook wordt er weergegeven hoeveel units (in dit geval millimeters) rapid movement er nodig zijn voor de total g-code.



In bovenstaande afbeelding kun je heel mooi zien hoe onhandig de freesbeweging is. Met name de blauwe tool kan veel beter horizontale sprongen maken...

Vervolgens kun je door "optimize" te klikken de code optimaliseren.
De g-code ziet er dan als volt uit:



Nu is het vinden van een goed algoritme nogal een gedoe...
Wat ik nu heb gedaan is simpelweg telkens het dichtsbijzijnde punt kiezen om naartoe te bewegen. Maar dit hoeft niet per sé in totaal de kortste route te zijn, want soms gebeurt het dat je in een hoek eindigt en alsnog het halve werkstuk moet oversteken.

Nu ben ik benieuwd of er hier mensen zijn die nog slimme ideen hebben om dit verder te verbeteren!

Groeten,
Douwe

[hugo stoutjesdijk]

Is dat niet het beroemde vertegenwoordigers probleem ? Wat nog niet opgelost schijnt te zijn.
Maar het is altijd bij automatisch gegenereerde routes dat je je ergert aan de oplossing. Dus weglopen en wachten tot ie klaar is ( en bij TomTom, gewoon negeren )
Maar misschien is het een idee om het hele oppervlak te verdelen in een aantal 'tegels' en er wel voor te zorgen dat je steeds alle startpunten binnen 1 tegel afmaakt (wel optimaliseren). Dan is de irritatie-faktor misschien al een stuk minder. Alleen is de uitdaging dan ook nog de optimale tegelmaat te verzinnen.
Eigenlijk meer een puzzel voor de wintermaanden

[audiomanics]

Met de huidige rekenkracht kun je misschien een array maken van alle punten (x en y) Dat was je al gelukt, anders had je de eerste tekening niet eens kunnen maken.
Verder geef je ieder punt een flag of dat punt al gebruikt is of niet.
Vanaf de positie waar je "nu" staat kun je van ieder punt de afstand berekenen als het nog niet gebruikt is.. Degene met de kortste afstand ga je heen.
Een paar for-next lussen en een snelle eenrichting sorteerroutine (for pointer = 0 to Npunten, if Afstandb<afstanda then a=b; xpointer ypointer= kortste afstand, next) en uiteindelijk is je array gevuld met de kortste route.

Is volgens mij alleen maar nuttig als je een paar honderd van die printen wil boren..
(of als je fastmove iets van 50mm/min is... )

Kees

[DaBit]

Da's is inderdaad het 'travelling salesman' probleem. Daar zijn wel algoritmes voor om dat met brute kracht te berekenen.

[Douwe]

@DaBit, Ik ken het Travelling salesman probleem (of de chinese postman variant). Het verschil is dat het hier gaat om een aantal (zeg N) beginpunten en evenveel eindpunten. Je wilt nu de beste combinatie van begin- en eindpunten vinden (dat wil zeggen, opgeteld moeten alle afstanden eind-begin zo laag mogelijk zijn). Het zijn dus eigenlijk heel veel afzonderlijke lijnstukjes.

@Kees, Volgens mij is dat precies wat ik heb gedaan op het moment. Telkens het dichtstbijzijnde punt berekenen. Dit is aardig efficient, maar soms gaat het dus fout. Zie bijvoorbeeld in het tweede plaatje de verticale blauwe lijn. Hier had beter eerst beneden begonnen kunnen worden en dan in horizontale strepen steeds verder naar boven gewerkt...

Naar mijn idee scheelt het toch aanzienlijk. In bovenstaand voorbeeld gaat het namelijk om het boren van gaatjes. Het boren kost nauwelijks tijd, de tijd gaat vooral in de verplaatsing in de x en y richting zitten. In het voorbeeld is te zien dat de frees eerst een horizontale afstand van 5 meter moet afleggen en na optimalisatie nog maar 2 meter. Als je een frees hebt die niet zo snel is, dan is dat een aanzienlijk verschil.

[theorieken]

De computers van tegenwoordig hebben er heel weinig moeite mee om enkele paden honderden keren opnieuw te berekenen om de kortste te vinden.
Het ingewikkeldste hier lijkt me dat de meeste blokken (buiten cirkels waarschijnlijk) een verschillend start als eindpunt hebben.
Wordt dit momenteel ook al volledig meegenomen?
(Want als je enkel filtert op de G00's zul je enkel de startpunten van de blokken krijgen lijkt me)

[audiomanics]

Hier had beter eerst beneden begonnen kunnen worden en dan in horizontale strepen steeds verder naar boven gewerkt...

Dan had je eerst naar beneden moeten gaan en dat is ook weer 3 cm ? Je haalt met deze methode misschien niet 100% effectiviteit maar 95% haal je toch wel..
Je kunt eventueel de afstandberekening een beetje tweaken: 2 * (x1-x2) ^2 + (y1-y2)^2. Zo geef je de voorkeur aan X.. (worteltrekken hoeft niet, zo blijft de afstand een soort van integer.. rekent een stuk sneller)

Kees

[DaBit]

Het verschil is dat het hier gaat om een aantal (zeg N) beginpunten en evenveel eindpunten. Je wilt nu de beste combinatie van begin- en eindpunten vinden

Ja, dat verandert het TSP in eentje met 2x zoveel punten en een aantal vaste routes ertussen. Maar als ik er zo over nadenk heb je al gauw teveel punten om er een brute-force TSP op los te laten; dat kost je meer tijd dan gewoon 3 meter extra ijlgang met acceleratie/deceleratie.

Ik heb er niet heel erg hard over nagedacht, maar ik denk dat een cost-based algoritme in een aantal iteraties een aardig resultaat moet kunnen geven. Niet optimaal, maar da's ook helemaal niet spannend meer als je 10-30% van het theoretische optimum af zit.

De computers van tegenwoordig hebben er heel weinig moeite mee om enkele paden honderden keren opnieuw te berekenen om de kortste te vinden.

Mjaaah, dat denk je maar. Een exponentieel in complexiteit toenemend probleem word toch lastig als je een paarduizend blokken hebt. Ook op een hele snelle PC.

[tatanka]

Douwe,

Na het genereren van de G-code met de ULP in Eagle gebruik ik altijd opti_qt.exe .
Die doet de G-code aardig optimaliseren.

Google eens hiervoor.
In cnczone.com is deze beschreven.

Jos

[Douwe]

opti_qt.exe: Die doet de G-code aardig optimaliseren.

Ik heb hem zojuist even uitgeprobeerd. Er is zeker een flinke verbetering te zien (en nog heel snel ook!).
Er is echter wel een probleem, sommige gaten in de nieuwe g-code worden met andere tools geboord dan in de originele g-code. Heb jij dit probleem ook?

Verder heb ik de maker van het door jou genoemde programma gelijk een pb-tje gestuurd, want ik ben wel benieuwd wat voor algoritme hij gebruikt

[ruudpg]

Wil je serieus optimaliseren, zal je niet alleen naar beginpunten van lijnen moeten kijken maar ook naar eindpunten, en desnoods die code ook even moeten laten omdraaien indien noodzakelijk zodat de gegenereerde eindpunten als de weg korter is ook als beginpunt gebruikt kunnen worden waardoor het beginpunt dan weer als eindpunt aangemerkt moet worden, al met al heb je behoorlijk wat vergelijkingen nodig en mogelijke oplossingen die je eerst moet doorrekenen om tot de meest optimale bewerkingsvolgorde te komen.

[tatanka]

Er is echter wel een probleem, sommige gaten in de nieuwe g-code worden met andere tools geboord dan in de originele g-code. Heb jij dit probleem ook?

Nee, ik heb nog geen gaten geboord met dit programma.

Ik heb hier een printboormachine en boor de gaten daarmee.
Op mijn Basic 540 moet ik nog een stuk MDF vlakfrezen en dan eens boren.

Maar ik ben met zoveel dingen tegelijk bezig. Pff.

Jos

[KaRaMBa]

Als ik het goed heb, wil je eindpunten aan een volgende begin punt toewijzen, zodat de totale afstand die je steeds moet 'verspringen' minimaal is. Als je niet perse wil eindigen op je startpunt, is het een toewijzings probleem, en niet het TSP.

Nu is mijn graaftheorie is wat weggezagt, maar als je een bipartite graaf maakt van eindpunten en beginpunten, en de verbindingen daartussen weeg je met de afstand die moet worden afgelegd, is een perfecte matching volgens mij een optimale oplossing? Dat is, bijvoorbeeld met de hongaarse methode, in polynomiale tijd op te lossen...

[Douwe]

@KaRaMBa, Het Hongaarse algoritme lijkt inderdaad heel geschikt voor het oplossen van dit probleem.
Nu heb ik inmiddels het algoritme geimplementeerd, maar ik vrees dat ik tegen een probleem aan ga lopen.

Kan het nu niet voor komen dat je, als je het weer als één lang toolpad gaat bekijken, verschillende eilandjes krijgt in plaats van één doorlopend pad?
Het algoritme houdt er namelijk volgens mij geen rekening mee dat ieder eindpunt een volgend beginpunt bepaald... Of vergis ik me?