Oskar za Level Sets (kompjuterska grafika)

[paculla]

Ove godine, pored nekoliko drugih grupa Oskara za tehnicka dostignuca ide Ron Fedkiw-u, Nick Rasmussen-u i Frank Losasso Petterson-u, za oblast kompijuterske grafike. Osnovna metoda koju ova tri naucnika koriste su Level Sets (zaista ne umem da prevedem), nastali tokom 90ih za simulaciju dinamike fluida (ne graficku nego "fizicku"). U poslednjih 10ak godina, Level Sets su se uvukli u razne oblasti, od grafike, preko obrade slike, planiranje putanja kroz grafove, computational geometry....Evo link na pricu u kojim filmovima se koristila metoda Fedkiwa. Evo i par njihovih simulacija. Imala sam priliku da gledam prezentacije i Fedkiwa i Sorenssena i rezultati koje su pokazivali su bili fantasticni. Sto se tice simulacije fluida, za koju su dobili Oskara, animacije izgledaju realisticnije nego pomocu drugih metoda, posto se zasnivaju na pravim fizickim zakonima. Posto sam ja vec godinama odusevljenja konceptom Level Sets i neverovatnim opsegom aplikacija koje su za kratko vreme osvojili, evo kratka prica o Level Sets, bez jednacina (ako uspem). Ako nekoga interesuje, mozemo i da prosirimo.Jednostavno receno, Level Sets (LS) su metod za proracunavanje propagacije povrsina (bilo kakvih n dimenzionalnih povrsina). Kada je Sethian, tata LS, poceo da se bavi LS, radio je to za dinamiku fluida. Na primer, imamo dve vrste fluida koji se krecu i imaju neki zajednicku povrsinu, sto se u ovom slucaju moze razumeti kao sve tacke u kojima se fluidi dodiruju. Sethian se bavio numerickim simulacijama kretanja tog interfejsa izmedju fluida.Da bih objasnila kocept LS, moram napisati samo reci o predstavljanju povrsina. Povrsina se moze predstaviti analiticki, npr jednacinom, povrsina se moze predstaviti tackama (lista svih tacaka na povrsini u diskretizovanom prostoru), povrsina se moze prestaviti parametrizovano... Svi ovi metodi su eksplicitni, mozemo reci i direktni.LS koristi implicitnu predstavu. Umesto da 'zapisemo' gde su sve tacke povrsine, mi u svaku tacku prostora 'zapisujemo' najkracu udaljenost tacke od povrsine. Dodatno, pamtimo da li smo unutar (-) ili van (+) povrsine.Npr, umesto da predstavljamo nasu konturu sa slike (2d povrsina) tackama ili parametrizovano, mi pamtimo ovakvu mapu. Cemu ovo sluzi? Em trosimo memoriju do besvesti (umesto malog broja koordinata, mi pamtimo udaljenost od celog prostora), em konturu moramo da izracunavamo, umesto da je eksplicitno imamo. Prilican overkill.Kada bi ova povrsina uvek mirovala, ovo bi zaista bio overkill. Medjutim, ako nasa povrsina krene da se krece, kao u primeru sa fluidima, pocinjemo da shvatamo zasto ima smisla koristiti ovu implicitnu predstavu. Da uprostim, recimo da se sve tacke povrsine krecu istom brzinom (primer sa slike: brzina je 1 jedinica/sekundi a pravac 'na napolje'). Onda ova overkill predstava odjednom ima mnogo vise informacija nego eksplicitna, zato sto svaka vrednost u mapi znaci: za koliko sekundi ce povrsina stici u tu tacku (ako je +) ili pre koliko sekundi je povrsina bila ovde. Slicno rezonovanje vazi i za proizvoljne brzine, ali to ne umem da objasnim bez jednacina. Poenta je da celu propagaciju mozemo spakovati u jednu funkcijukoja ima n+1 dimenzija (n dimenzionalna povrsina + vreme).Glavna prednost je sto ovakva predstava dozvoljava simulacije jako kompleksnih sistema. Sa tackastom ili parametrizovanom povrsinom, razdvajanje i spajanje povrsina je velika glavobolja. Koja tacka ide u koju, kako se preklapaju.... Kod LS, spajanje dve povrsine se resava sabiranjem razdaljina (jedan plus). Zato je mnogo jednostavnije koristiti prave fizicke zakone. Kao sto rekoh, LS se u medjuvremenu koristi za mnoge probleme sa povrsinama koje se krecu. U obradi slike, LS se koriste za rekonstrukciju oblika, gde se za pokretanje povrsine koriste karakteristike slike, slicno kao sto se za simulaciju fluida koriste fizicki zakoni.

[Al-Khwarizmi]

Zanimljiva tema. Nisam baš neki sagovornik za istu, pošto skrušeno moram priznati da o LS ništa nisam čitao, ali ova pričica mi je zagolicala maštu. Jesi li imala prilike da sama primenjuješ LS, ili da bar praviš jednostavne primere? Ako si rada da malo proširiš priču, ja ću sa zadovoljstvom pratiti temu. Molim te i da preporučiš linkove koji će biti od koristi kada ugrabim malo vremena da se LS detaljnije posvetim i van foruma.edit: nepismen

Edited February 1, 2008 by Al-Khwarizmi

[paculla]

radim vec godinama sa ls, najvise za obradu slike, statistiku oblika i planiranje putanja. za pocetak, pogledaj sethianovu stranicu (link iz prvog posta). tekst za american scientist (http://math.berkeley.edu/~sethian/2006/Papers/sethian.amersci.pdf) je skracena verzija knjige. kad ugrabim vremena, dacu malo detaljnije objasnjenje za propagaciju razlicitim brzinama.

Edited February 1, 2008 by paculla