Dotaz: Detekce objektu ze samostatných hran

[Nosense]

Přílohy:

• pred.png (15171 bytů)
• po.png (18909 bytů)

Dobrý den

Řeším problém jak z množiny samostatných křivek určit objekty které jsou jimy definovány. Vstupem je množina uzavřených křivek, kde každá z křivek je tvořena posloupností úseček. Křivky se neprotínají. Pořadí vstupních křivek ani směr jejich definice (po/proti směru hodin) není definován. Výstupem by pro každou křivku měla být informace "vpravo (po směru definice) je objekt, vlevo je prázdný prostor", respektive naopak a úroveň vnoření (viz přiložené obrázky).

Budu rád za jakékoliv naznačení správného algoritmu.

Odpovědi

[Marv-CZ]

Chceš akorát provést graficky to vyplnění ploch jako na obrázku po.png nebo získat informaci, které křivky spolu tvoří vyplněný objekt?

To první je jednodušší. Hledej „paritní řádkové vyplňování“ nebo „vyplňování rozkladovými řádky“.

[Nosense]

Obrázky jsem zadal jen pro ilustraci. O uvedených metodách grafického vyplňování vím, ale potřebuji přesně ty informace co jsem napsal (tj. hodnota "vpravo"/"vlevo" a číslo úrovně vnoření), nikoliv grafickou reprezentaci. Vstupní data mi vypadnou z (pseudo)CAD programu a cílem je nakonec vygenerovat data pro CNC frézu. Potřebuji pro každou křivku vyřešit 2 problémy – 1. kompenzace průměru frézy: je potřeba určit po které straně řezat; 2. pořadí řezání: není možné vyříznout nejdřív vnější křivku a potom vnitřní, protože by daná část už nedržela.

[Šangala]

Pošlete to do kooperace na laser nebo vodu. (Sorry nedalo mi to )

[Nosense]

Nevím jestli jsem to správně pochopil, ale jakékoliv odesílání někam nic nevyřeší, protože se mi cílový stroj válí doma v dílně. A u laseru i vody je třeba řešit stejné problémy – vodní ani laserový paprsek není možné zaostřit do nekonečně úzkého paprsku.

[Šangala]

To nelze (s pohledu frézy ano ), ale software dodávaný k těmto zařízením to má již vyřešené.
Což Vám samozřejmě nepomůže, pokud to chcete dělat doma a neřeší to dotazovaný problém.
Mně to nedalo jen proto, že efektivita řezaní laserem (pokud se jedná o plech do cca. 3mm) je výrazně vyšší než mechanické dělení (frézování) - u vody je to obdobné. Frézování je efektivnější jen tehdy pokud je možné položit více plechů na sebe a řezat jich více současně a dělá se to ve větších dávkách po tabulích. Ale pak je třeba řešit některé další věci jako správné broušení nástroje, dořezávání můstků apod.

[Nosense]

Protože se jedná v podstatě výlučně jen o řezání dřeva (překližky) je fréza nejvhodnější nástroj. Vodní paprsek nemá smysl pro dřevo řešit. U laseru je problém opálení řezaných hran, protože na nich lepidlo drží podstatně hůře než na frézovaných hranách. A co jsem se doposud setkal s laserem řezanými díly (ze dvou různých strojů) byla oproti frézování kupodivu mizerná přesnost. Nejednalo se sice o hi-tech, ale jen poloprofesionální stroje za řádově stovky tisíc, nicméně od operátorů obou strojů jsem slyšel stížnosti na to, že laser je v podstatě nemožné přesně zaostřit, protože z laserové hlavy vychází mírně kuželový paprsek. Na dílech co jsem měl v ruce dělala odchylka až 2 desetiny milimetru.

[Šangala]

Tak to laser není dobrý nástroj, zde by uspěla voda (no dřevo lze řezat vodou , pokud mu to nevadí ), která ovšem podřezání (rozptyl) má větší než laser (laser u tenkých plechů ten rozptyl má zanedbatelný, ale je zbytečné to rozebírat ). Co se týče přesnosti při dobrém seřízení a nastavení je ta přesnost ve 2D rozhodně pod 0.1mm.
Zaručenou přesnost vyšší 0.2 milimetrů na překližce a obecném 2D tvaru bych se neodvážil garantovat ani kdyby mě mučili .

[Marv-CZ]

Příloha:

• poradi.png (24465 bytů)

Pořadí řezání:

1. zjistit ohraničující okna
2. ohodnotit do kolika větších oken, okno spadá
3. řezat od těch s nejvyšší hodnotou

Snad to bude pochopitelnější z přiloženého obrázku.

Pro určení strany, po které řezat, by snad šlo nějak využít modifikaci toho vyplňovací algoritmu - řeže se po „nevyplněných“ stranách.

[Nosense]

U těch oken by mohl být problém s překrýváním. Tvary mohou být i konkávní, takže jejich křivky se sice neprotínají, ale jejich vnější okna se překrýt mohou. Napadla mě ale modifikace řádkového vyplňování, která by mohla vyřešit oba problémy. Teď bohužel musím běžet, ale do večera to ještě promyslím a ozvu se.

[Marv-CZ]

Ty konkávní tvary jsem bral v úvahu a mělo by to fungovat i tak. Hodnota se zvyšuje jen v případě, že okno je celé uvnitř jiného, překrývající se v úvahu neberou.

Pokud něco zajímavého vymyslíš tak se pak určitě poděl.

[Nosense]

v podstatě mě napadlo, že pokud bych uměl zjistit jestli konkrétní bod leží vně nebo uvnitř křivky, mohl bych zajistit pořadí řezání následovně: pro každou křivku bych otestoval jestli libovolný bod, každé z dalších křivek (a tím i celá křivka) leží uvnitř nebo vně testované křivky. Pro každou, křivku která leží uvnitř bych inkrementoval čítač úrovně. Tedy v pseudokodu nejak takto:
MnozinaKrivek K
Krivka i,j

for i in K:
    for j in (K-i):
        if (j.bod uvnitr i) then j.level++
Tím bych pro každou křivku dostal úroveň stejně jako na druhém obrázku z úvodního příspěvku. Vyřezávání pak probíhá od nejvyšší úrovně. Úroveň kromě pořadí řezání značí i stranu – každá sudá úroveň značí vnější hranu a lichá vnitřní. Tento celý postup je ovšem založen na tom, že umíme určit jestli bod leží uvnitř nebo vně křivky. Tady přichází na řadu modifikovaný postup řádkového vyplňování, ale možná by přesnější termín byl ray casting. V podstatě jde o to vrhnout z testovaného bodu paprsek (libovolným směrem) a zkontrolovat jestli je počet průsečíků s křivkou lichý (bod je uvniř) nebo sudý (bod je vně). Je potřeba ještě promyslet speciální případy, např. paprsek procházející vrcholem, ale to se řeší právě v řádkovém vyplňování, takže vyhrabu pár poznámek ze školy a nejspíš to tam najdu.

[Marv-CZ]

Příloha:

• prus.png (4288 bytů)

Ještě musíš vzít v úvahu, že u nekonvexních křivek ti to může jednu křivku protnout vícekrát. A další problém je, kam vlastně paprsek vrhat - podívej se na příklad v příloze.

A ještě mám takový dotaz víceméně nesouvisející s postupem co řešíme. Co se vlastně bude dít s tím materiálem, který jde pryč. Jen se odřízne podle obrysů nebo se postupně celý odfrézuje?

[Nosense]

No především se při hledání jestli bod leží uvnitř nebo vně křivky bere v úvahu pouze jedna uzavřená křivka a ostatní se ignorují. Nekonvexní tvary řeší právě sudý/lichý počet průsečíků. Předpokládejme bod uvnitř a z něj paprsek vedený libovolným směrem (v reálu se bude používat rovnoběžný s jednou z os). Tento paprsek musí konečnou uzavřenou křivku opustit ať chce nebo ne = 1 průsečík. U nekonvexního tvaru může do křivky znovu vstoupit, ale musí také znovu vystoupit, takže se počet průsečíku může dále zvyšovat pouze po dvou. Tím tedy zůstane zachován lichý počet průsečíků u paprsku, který začínal uvnitř. Pokud paprsek začíná vně křivky, buď křivku neprotne = 0 průsečíků, nebo do ní vstoupí, ale také vystoupí = 2 průsečíky, což se může opakovat, ale lichý počet průsečíků zůstane.

Řežou se pouze obrysy. To znamená, že materiál mezi díly zůstává.

[Šangala]

Pokud by tvar byl konvexní stačí spočítat kolmý vektor do daného bodu ke všem úsečkám(vektorům) dané seřazené a CW nebo CCW křivky (kteroužto seřazenou mít musíte pro generovaní dráhy) a pokud kolmice směřují na stejnou stranu (+/-) tak je bod uvnitř. - jen nápad, mně tyto věci, ale většinou moc nejdou…
Ale jinak co tak něco skoro-hotové. (Ať přispěji něčím lepším, než v předchozím podvlákně)

[Nosense]

Ano to je přesně co jsem hledal a nakonec vymyslel :), konkrétně jednodušší verzi s jednou křivkou (http://en.wikipedia.org/wiki/Point_in_polygon), která mi umožní krom orientace hran (vnitřní nebo vnější) určit také pořadí řezání, jak popisuji o něco výše.

[Šangala]

Jaký máte stroj, má svůj řídící systém? Ptám se proto jestli kompenzaci nástroje (dráhovou korekci ) řeší systém nebo vy. Pokud Vy tak je před Váma další problém „jak objet vnější rohy“.
Máte v zásadě tři zákadní možnosti:

1. Objet je ekvidistantními úsečkami protaženými do průniku, ale to při velmi ostrém úhlu může znamenat  „zajet si do sousedního města“, při úhlu kolem 90° to zas způsobí rázy - kinetická energie a náhlá změna směru je sfiňa (to Vám asi nebude vadit)
2. Obtočit roh po kružnici kde poloměr se rovná kompenzaci (R nástroje), což může při pomalém chodu spálit povrch výsledného výrobku a „svalíte“ roh (zde je otázka jestli rychlost řídíte dle středu nástroje nebo dle dotyku s materiálem, jenže v tomto případě by musela být rychlost, tak vysoká že se tom ani fotonu nesnilo, bo objíždíte bod ).
3. Provést elegantní smyčky, které zajistí ostrý roh, nejedou „moc“ navíc a mají klidný chod, ale kdo se s tím má počítat, že .

No a proč to píšu, protože mě to baví a protože krom možnosti dva, máte nové polygony a to i nekonvexní nebo samy sebe protínající se, a které musí mít všudypřítomnou vzdálenost mezi sousedními dvěma minimálně ø nástroje.

No a pokud to řeší stroj, (definujete stranu - dráhovou korekci a průměr nástroje), tak zas musíte vědět jak to systém řeší, nebo lze-li to definovat, jinak vám budou vznikat „obloučky“ (zafrézování) na vnitřních stranách dílů, které jste nechtěl

[Nosense]

No je to takový "na koleně" spíchnutý stroj z toho co dům dal. Řízené je to pomocí EMC2 (http://www.linuxcnc.org/), který má poměrně pokročilý systém plánování trajektorie a komponezace nátrojů (popsáno např zde: http://www.linuxcnc.org/docview/html/gcode_tool_compensation.html). Mně tedy vlastně stačí nadefinovat si parametry nástrojů v tabulce nástrojů EMC2 a potom na začátku programu v g-code vybrat nástroj a před každou křivkou určit řez po pravé nebo levé straně následující dráhy. Software by měl vyřešit ostatní.

[Šangala]

Díval jsem se a je to taková „ISO“ klasika (G40/G41/G42), a výpočet se standardně obtočí kolem rohu po kružnici.
Takže pokud se pojede stejnou rychlostí může u dřeva dojít k připálení rohu (celou dobu realizace kruhového oblouku řeže nástroj obvod dílu na stejném místě) a obecně ke zaoblení rohu (dle nastavení G61/G64 a schopnosti pohonů).

a před každou křivkou určit řez po pravé nebo levé straně
Poznámka: Odečtení kompenzace (posun nástroje na ekvidistantní dráhu) je (obvykle, kde jinde ) provedeno v bloku (řádku), ve kterém je řazena funkce (G40/G41/G42), takže blok (řádek) předem by jste měl být ve vzdálenosti větší než R nástroje od řezané kontury. A ideální je aby pohyb v bloku kde je kompenzace řazena byl v rovině XY (předpokládám tuto rovinu) větší než R nástroje, pak je pohyb stroje „čistý“
Co to všechno znamená? No jen to, že bude třeba řešit nájezd na „konturu“ a automaticky může být obtížné toto vyřešit (laser a voda to má jednoduché, kompenzace je obvykle menší, než minimální možná vzdálenost kontur od sebe.)

No a když je obsluha pako a nechá vám zařezání na tvaru, tak je to vidět, a je to jedno jestli je to na laseru/vodě či frézce.
Nejen proto, ale i proto existují NC programátoři .

[Šangala]

Nekonvexní obrazce se převedou na více konvexních a pro takovouto skupinu musí platit to co pro jeden objekt.