Obsah
Rozmisteni min
Prvnik krokem bylo naprogramovani nejakeho modelu na rozmisteni min (bodu podel kterych se bude urcovat, ze je nutna reinicializace). Naprogramovany jsou 3 ruzne ucinne metody:
Zminene problemy resim zatim tim, ze k reinicializaci je nutne vybuchnuti vetsiho poctu bodu, cimz se eliminuji ty spatne umistene. Snad to bude fungovat (vyzkouseno zatim nic z nizeji popsaneho duvodu). Nejlepe se mi zatim jevi metoda 2 - opet ta nejjednodusi.
V textech me dostupnych se nikdo blize nerozepisuje, jak miny volit, jen p. Sethian rika "nekde u hrany." Nekdy dokonce primo hranu. To se mi nejak nezda, ale expert je on. :-) Obrazky na miny jsem bohuzel smazal a uz se mi chce docela spat, takze je sem doplnim pozdeji.
Uprava reinicializacniho schematu
Puvodne jsme reinicializovali podle schematu - zjisti body, ktere jsou bliz ke krivce nez stanovena mez, a kdyz jejich pocet prekroci urcite procento vsech, reinicializuj. Tento zpusob ucinne odmaze vliv prekryvu a hranic mezi procesy, ale na zaklade prvnich pokusu je nutno dodat, ze reinicializuje az prilis casto. Proto jsme zmenili zpusob na "kdyz zmeni znamenko" - dame je dale od kraje nez v predchozim pripade... Jsou tam urcite problemy, jak tyto body volit, jak nastavit, aby zaroven odmazal ty prechody mezi procesy a zaroven se zachovala dobra schopnost reinicializace.
Dalsim zjistenim byla pomerne slba funkcnost min polozenych jako metoda 2, tedy do rohu pokryvacich oblasti. Problem je v tom, ze k rohum se krivka dostane vzdy az mnohem pozdeji, nez je potreba reinicializovat. Bylo by potreba detekovat rohy vznikle prekryvy techto oblasti - neni problem, ale vznika problem, ktery je smer "dvonitr" z techto bodu. Tato metoda se stava historickou...
Rekonstrukce krivky
Dale je potreba nejak rekonstruovat tu krivku aka nulovou uroven. Hledal jsem, jak to dela p. Sethian a metoda se jmenuje Marching Cubes. Je z roku 1987 a z poctu clanku, ktere tuto metodu vyuzivaji jsem odvodil, ze je to nejak dost proflakla klasika. Bohuzel se mi podarilo najit jen asi 2 clanky, ktere metodu velice hrube popisuji - jde z nich pochopit hlavni myslenka (15 zakladnich typu ve 3D...), ale nejak jsem to moc nechytil. Originalni clanek je snad nesehnatelny. :-( Tato metoda pry ukazuje svoji silu hlavne ve 3D, ve 2D se Sethian jeste zminuje o metode Contour Plotter - vedecke vyhledavace mlci, google vyhazuje spoustu reklam na plottery. Pravdepodobne pujde o sledovani hranice nejakym intuitivnim zpusobem.
Ja jsem se zkusil vydat opet velice jednoduchou cestou, na ktere jsme se domluvili. Myslenkou bylo to, ze najdu nejaky bod na krivce a z nej potom postupne pomoci trojuhelnicku odvodim celou spojitou krivku. Bojoval jsem s tim cely den a vysledek je zhruba ten, ze metoda "sledovani" je az neuveritelne citliva na presnost a je velmi tezke ji zrekonstruovat. Zkusil jsem jen napocitat vzdalenosti a okamzite ji rekonstruovat a moc mu to neslo. Opustil jsem tento zpusob a presel jsem na brutalni silu metodou testu na vsechny body: prochazim radky/sloupce a kdyz najdu rozdilne znamenko na dvou sousedicich bodech, tak pomoci Vaseho postupu dopocitam bod na trojuhelniku. Asi neco delam spatne, protoze to neuveritelne dlouho trva a asi by to chtelo neco lepsiho. Uz ted se objevuji problemy v bodech kolmych na smer prohledavani - rekonstruuje podstatne nepresne. Dalsim problemem je, ze jsem si uvedomil, ze k pokryti krivky potrebuji body mit v rozumnem poradi a to tento zpusob nesplnuje.
Jeden maly obrazecek na rozliseni 0.01*1e-9 pri e^2=e-20 v case 0.02. Stale se to lisi zhruba o dva body. :-(
Rozmisteni min
Prvnik krokem bylo naprogramovani nejakeho modelu na rozmisteni min (bodu podel kterych se bude urcovat, ze je nutna reinicializace). Naprogramovany jsou 3 ruzne ucinne metody:
- Hrany. Program se snazi detekovat hrany narrowbandu a kousek od kraju vytvori miny. Problem: Sledovat hranu pri prekryvajicich se oblastech (blocich) neni az tak jednoduche, jak se mi na prvni pohled zdalo. Stadium: funguje, ale myslenka ma hodne omezeni. Kdyz se prekryji vice nez dva pokryvajici bloky, tak tam vznikaji blbiny. Toto by jeste slo nejak opravit (asi docela slozite), ale v kazdem pripade zustanou chyby na oblastech prekryvu s jinym procesem. Tam krivka naprosto korektne opousti oblast (je osetreno), ale z duvodu pomalych presunu dat uz se mi tam nechce davat zadne posilani dat s okolnimi procesy. Vysledek: Hezky se hodi na hodne hladke krivky bez ostrych hran. (#define 2)
- Rohy. Projdu pokryvajici bloky a kosek od rohu tam fouknu minu. Opet vynechavam hodne rizikove oblasti kolem prekryvu procesu. Min je pak velice malo a kazdy spatne umisteny muze byt velmi nebezpecny. (#define 1)
- Trasovani po radcich/sloupcich. Jdu po radku a az narazim na zmenu v dist fci (mezi nepocitanym okolim a narrowbandem), tak oznacim minu. Funguje podobne jako metoda jedna, ale je podstatne pomalejsi. Navic opet velice trpi zminenymi prekryvy. (#define 0)
- Mina je bod, ktery ma ve svem ctvercovem okoli o urcite velikost bod
s hodnotou INIT_DIST (tzn. mimo narrow band). Elegantni reseni, ale pomerne
narocny algoritmus.
| Metoda 1 |
Metoda 2 |
Metoda 3 |
Metoda 4 |
|
|
|
|
Zminene problemy resim zatim tim, ze k reinicializaci je nutne vybuchnuti vetsiho poctu bodu, cimz se eliminuji ty spatne umistene. Snad to bude fungovat (vyzkouseno zatim nic z nizeji popsaneho duvodu). Nejlepe se mi zatim jevi metoda 2 - opet ta nejjednodusi.
V textech me dostupnych se nikdo blize nerozepisuje, jak miny volit, jen p. Sethian rika "nekde u hrany." Nekdy dokonce primo hranu. To se mi nejak nezda, ale expert je on. :-) Obrazky na miny jsem bohuzel smazal a uz se mi chce docela spat, takze je sem doplnim pozdeji.
Uprava reinicializacniho schematu
Puvodne jsme reinicializovali podle schematu - zjisti body, ktere jsou bliz ke krivce nez stanovena mez, a kdyz jejich pocet prekroci urcite procento vsech, reinicializuj. Tento zpusob ucinne odmaze vliv prekryvu a hranic mezi procesy, ale na zaklade prvnich pokusu je nutno dodat, ze reinicializuje az prilis casto. Proto jsme zmenili zpusob na "kdyz zmeni znamenko" - dame je dale od kraje nez v predchozim pripade... Jsou tam urcite problemy, jak tyto body volit, jak nastavit, aby zaroven odmazal ty prechody mezi procesy a zaroven se zachovala dobra schopnost reinicializace.
Dalsim zjistenim byla pomerne slba funkcnost min polozenych jako metoda 2, tedy do rohu pokryvacich oblasti. Problem je v tom, ze k rohum se krivka dostane vzdy az mnohem pozdeji, nez je potreba reinicializovat. Bylo by potreba detekovat rohy vznikle prekryvy techto oblasti - neni problem, ale vznika problem, ktery je smer "dvonitr" z techto bodu. Tato metoda se stava historickou...
Rekonstrukce krivky
Dale je potreba nejak rekonstruovat tu krivku aka nulovou uroven. Hledal jsem, jak to dela p. Sethian a metoda se jmenuje Marching Cubes. Je z roku 1987 a z poctu clanku, ktere tuto metodu vyuzivaji jsem odvodil, ze je to nejak dost proflakla klasika. Bohuzel se mi podarilo najit jen asi 2 clanky, ktere metodu velice hrube popisuji - jde z nich pochopit hlavni myslenka (15 zakladnich typu ve 3D...), ale nejak jsem to moc nechytil. Originalni clanek je snad nesehnatelny. :-( Tato metoda pry ukazuje svoji silu hlavne ve 3D, ve 2D se Sethian jeste zminuje o metode Contour Plotter - vedecke vyhledavace mlci, google vyhazuje spoustu reklam na plottery. Pravdepodobne pujde o sledovani hranice nejakym intuitivnim zpusobem.
Ja jsem se zkusil vydat opet velice jednoduchou cestou, na ktere jsme se domluvili. Myslenkou bylo to, ze najdu nejaky bod na krivce a z nej potom postupne pomoci trojuhelnicku odvodim celou spojitou krivku. Bojoval jsem s tim cely den a vysledek je zhruba ten, ze metoda "sledovani" je az neuveritelne citliva na presnost a je velmi tezke ji zrekonstruovat. Zkusil jsem jen napocitat vzdalenosti a okamzite ji rekonstruovat a moc mu to neslo. Opustil jsem tento zpusob a presel jsem na brutalni silu metodou testu na vsechny body: prochazim radky/sloupce a kdyz najdu rozdilne znamenko na dvou sousedicich bodech, tak pomoci Vaseho postupu dopocitam bod na trojuhelniku. Asi neco delam spatne, protoze to neuveritelne dlouho trva a asi by to chtelo neco lepsiho. Uz ted se objevuji problemy v bodech kolmych na smer prohledavani - rekonstruuje podstatne nepresne. Dalsim problemem je, ze jsem si uvedomil, ze k pokryti krivky potrebuji body mit v rozumnem poradi a to tento zpusob nesplnuje.
- Hruba sila - probereme vsechny body a metodou trojuhelnicku napocitame krivku.
- Jdeme po krivce metodou trojuhelnicku - rekurzivne.
- To same ale v nerekurzivni verzi - nepozna treba rozvetveni krivky.
| Metoda |
1 |
2 |
3 |
| Cas |
0.025 s |
0.004 s |
0.003 s |
| Chyba |
9e-6
pri prostorovem kroku 3e-3 |
||
Jeden maly obrazecek na rozliseni 0.01*1e-9 pri e^2=e-20 v case 0.02. Stale se to lisi zhruba o dva body. :-(
Celkova reinicializace
Puvodne jsem se naivne domnival, ze cela reinicializace se bude skladat s testu, zda-li je nutna (na zaklade min), a pak uz jen nalezeni krivky, jeji znovupokryti, znovunapocitani vzdalenosti a pokracovani ve vypoctu. Problemy, ktere se vyskytly:
Bod 5 z predchoziho vypisu nakonec vyresen nasledovne:
Ackoli se zpocatku zdalo, ze to funguje vyborne, je tu maly problem. Kazdy proces zna jako vzdy jen svoji malou cast krivky. Pri nastavovani znamenek pri novem pokryti se tam objevi uz oblast, kde krivka neni - nezname tam hranizi a znamenka jsou nastavena spatne. Reseni je jako vzdy si nechat poslat pokracovani krivky od nasledujiciho procesu - opet zpomaleni. :-(( Bohuzel, ani toto se neukazalo jako dostatecne silne - nekdy se objevi male trhlinky... Mozna bug. Hezke je, ze staci posilat jen jeden konec, druhy se spravi sam zpusobem noveho rozdeleni krivky dle bodu (2).
Puvodne jsem se naivne domnival, ze cela reinicializace se bude skladat s testu, zda-li je nutna (na zaklade min), a pak uz jen nalezeni krivky, jeji znovupokryti, znovunapocitani vzdalenosti a pokracovani ve vypoctu. Problemy, ktere se vyskytly:
- Prvni problem je v pokladani min, kdy je nutno navic zvazit, ze na nekterych hranach je temer nulova vzdalenost normalni - tam, kde se prekryvame s jinym procesem. Trochu nesikovne reseni se naslo - miny prilis blizko uz pri pokladani proste nepolozime.
- Jestlize kazdy proces zrekonstruuje krivku, tak je tam cast, ktera se opet prekryva vice procesy - je tam jakoby dvakrat. Pri znovupokryvani je to nutno zohlednit, protoze jinak se nam bude zvetsovat uzemi pokryvane vice procesy a nastane problem se synchronizaci.
- Potrebujeme body krivky v poradi, aby slo nasim zpusobem pokryt. Opet jsem to musel prepsat, protoze metoda sice posklada body, ale je nutno mu zadat prvni bod.
- Dlouho jsem premyslel, jak to udelat, aby v pripade nutne reinicializace se akce provedla jen na jednom procesu. Uz jsem se do toho pustil, ale pak jsem si uvedomil, ze vsechny ostatni procesy na nej stejne musi kvuli synchronizaci pockat - navic je pravdepodobne, ze kdyz potrebuje jeden, tak bude potrebovat i druhy - budeme cekat znovu. Reseni: vzdy se reinicializuji vsechny procesy. Zpomaleni oproti jednomu je v optimalnim pripade nulove.
- Body 1 - 4 jsou vyreseny, momentalne je problem v zjisteni, jak je to s urcenim, co je uvnitr a co je vne. Zatim nemam napad, jak to hezky udelat - snad jen zapamatovat si pozice nekterych bodu a jejich znamenko a potom to lavinove rozsirit...
Bod 5 z predchoziho vypisu nakonec vyresen nasledovne:
- Pri rekonstrukci krivky si ulozim "trojuhelniky", z kterych byly jednotlive body krivky napocitany. Znamenka v techto bodech se po reinicializaci nezmeni (jinak je nekde bota).
- Po vytvoreni noveho narrow bandu a napocitani vzdalenosti (bez znamenka), nastavime znamenka v bodech ziskanych z rekonstrukce krivky (bod 1).
- Z kazdeho bodu "trojuhelniku" v podstate nastartuju vyplnovani souvisle oblasti, kde hranici jsou body z bodu 2.
| Prvni iterace |
Po prvni reinicializaci |
Po druhe reinicializaci |
|
|
|
Ackoli se zpocatku zdalo, ze to funguje vyborne, je tu maly problem. Kazdy proces zna jako vzdy jen svoji malou cast krivky. Pri nastavovani znamenek pri novem pokryti se tam objevi uz oblast, kde krivka neni - nezname tam hranizi a znamenka jsou nastavena spatne. Reseni je jako vzdy si nechat poslat pokracovani krivky od nasledujiciho procesu - opet zpomaleni. :-(( Bohuzel, ani toto se neukazalo jako dostatecne silne - nekdy se objevi male trhlinky... Mozna bug. Hezke je, ze staci posilat jen jeden konec, druhy se spravi sam zpusobem noveho rozdeleni krivky dle bodu (2).
