Lex Systemy, wydajne generowanie L-Systemów

[danilo2]

Hej ho, ho hej!

 

Chciałbym Wam zaprezentować rezultaty mojej pracy nad pewnym zagadnieniem związanym z grafiką komputerową.

Na samym początku postaram się zarysować do czego ta technologia może być wykorzystana. Zagadnienie dosyć mocno zahacza o L-Systemy.

 

L-Systemy swoją nazwę zawdzięczają węgierskiemu biologowi Aristidowi Lindenmayerowi, który w 1968 roku opracował specyfikację tego języka formalnego. Miał on z założenia służyć do opisu prostych struktur wielokomórkowych i ich podziałów. Okazało się jednak, że nadaje się doskonale do opisu figur fraktalnych (których mniejsze części podobne są do kształtu całej figury), roślin i całych systemów biologicznych. Język L-systemów ewoluował przez lata i obecnie stanowi najdoskonalsze znane narzędzie pozwalające na tworzenie cyfrowych roślin, systemów biologicznych i fraktali.

W matematyce mówi się, że L-Systemy są językiem pozwalającym na generowanie słów i zdań nad pewnym językiem, czyli po prostu potrafią wygenerować ciąg dowolnych znaków na podstawie zadanych reguł. Następnie znaki te interpretowane są graficznie (np. F interpretowane jest jako kreska, + jako zgięcie itp).

 

L-Systemy wykorzystuje się przy tworzeniu cyfrowych roślin i efektów specjalnych, np. w Avatarze większość roślin generowana była przy pomocy L-Systemów, stworzenie własnych kształtów błyskawic modelu płuc, mózgu, sieci neuronów, ... w L-Systemach jest bajecznie proste. Dodatkowo dają one niesamowitą proceduralną kontrolę nad praktycznie ka żdym aspektem generowanej geometrii, więc można bardzo łatwo zrobić np. animację rosnącego pnącza, albo przygotować jedno drzewo i na jego podstawie wygenerować setki innych, przy czym każde będzie różniło się od pozostałych.

L-Systemy wykorzystywane są również jako baza dla wielu pluginów, takich jak X-frog oraz Tree-generator, przy czym same dają o wiele większą kontrole, niż w tych pluginach.

 

Więcej o L-Systemach można przeczytać w darmowej książce "The Algorithmic Beauty of Plants", w internecie, albo posłuchać jak o nich opowiadałem podczas cyklu szkoleń pierwszego Artbuzza (wiedo jest na youtubie).

 

-------------------------------------------

 

Przechodząc do sedna sprawy, rok temu napisałem pracę inżynierską pod tytułem:

"Lex Systemy - opracowanie wysokopoziomowego języka przetwarzającego znaki."

 

Planowałem, że rezultaty zapostuję tutaj po kilku miesiącach od zakończenia pracy, aby mieć czas na postawienie jakiegoś bloga lub własnej strony. Rzeczywistość jednak okazała się okrutna i przez ilość pracy zawodowej oraz czasu wkładanego w projekty które prowadzę, nie znalazłem do teraz chwili na zajęcie się tą stroną i pewnie nieprędko znajdę ;)

 

Tak więc rezultaty, które tu pokazuję mają rok, ale i tak robią dobre wrażenie, tak mi się przynajmniej wydaje :)

 

 

Formalnie mówiąc, Lex Systemy są wyspecjalizowanym, wysokopoziomowym językiem przeznaczonym do przetwarzania znaków i definiowania reguł proceduralnej generacji słów nad pewnym językiem. Pozwalają one na generowanie słów dowolnego języka należącego do gramatyk klasy wyższej lub równej 1 w hierarchii Chomsky'ego.

 

 

Mówiąc po ludzku - Lex Systemy pozwalają na wydajne przetwarzanie znaków, a co za tym idzie, pozwalają między innymi na generowanie L-Systemów.

Obecnie na rynku istnieje kilka komercyjnych rozwiązań pozwalających na tworzenie L-Systemów (w tym jeden z najlepszych generatorów dostępny jest w pakiecie Sidefx Houdini i dlatego też z nim porównuję w dalszej części swoje rozwiązanie).

Warto zauważyć, że Lex Systemy pozwalają na generowanie L-Systemów niezależnie od aplikacji!

 

Pozwalają również na wiele innych rzeczy, nawet na pisanie złożonych algorytmów i tworzenie samodzielnych aplikacji. Jedną z najważniejszych cech Lex Systemów jest ich składnia. Przez długi czas projektowałem ten język tak, aby był prosty w użyciu, przejrzysty a zarazem bardzo funkcjonalny. W rezultacie otrzymałem język pozwalający na opis złożonych systemów (również L-Systemów) w sposób przejrzystszy i dający więcej możliwości niż wszystkie znane mi generatory L-Systemów, w tym ten wbudowany w Houdiniego. Szczególną uwagę położyłem na wyeliminowanie wszystkich niedogodności i błędów w architekturach znanych języków L-Systemów (więcej w tym temacie opowiadałem podczas moich wykładów na pierwszym ArtBuzzie, VideoDay, etc. - ze względu na to, że nie chcę tutaj się rozpisywać, jeżeli będzie taka potrzeba, zagłębię się w ten temat). Ponadto wszystkie opisy L-Systemów można łatwo przenosić do Lex Systemów.

 

Pozwolę sobie na wtrącenie jednej technicznej uwagi - Lex Systemy pozwalają na tworzenie L-Systemów klasy szerszej niż tylko pospolite L-Systemy kontekstowe. Pozwalają one na to, by kontekst w L-Systemach był wieloznakowy, a nawet aby był on wyrażeniem regularnym!

 

Napisałem również w C wydajny kompilator tego języka. Po przeprowadzeniu testów okazało się, że jest on ... NAPRAWDĘ wydajny :D Jest dużo szybszy niż generatory L-Systemów w Houdinim (pomiędzy testowanymi wersjami 9, 10, 11, 12 i 12.1 nie odnotowano większych różnic).

Wynikowy program działał z dużo niższą obliczeniową złożonością, niż ten w Houdinim :)

 

Testy były przeprowadzane wielokrotnie na nieobciążonej maszynie. Polegały one na obliczaniu pewnej generacji przez mój program i zapisywaniu wyniku na dysku. Analogiczne testy przeprowadziłem w Houdinim (używając Houdiniego w trybie batch (bez interfejsu graficznego) oraz Houdiniego Master (teraz FX) nie wyświetlając w viewporcie rezultatów, a jedynie każąc nodom na obliczenie się).

Wiele ludzi, w tym mój recenzent, promotor, doktorzy i koledzy miło zaskoczeni moimi rezultatami sprawdzili wraz ze mną, czy wyniki naprawdę są ok. Testowaliśmy czy wynikowa geometria jest taka sama w obu przypadkach. Była :)

 

 

Ok a teraz kilka faktów:

 

 

Testy czasowe były przeprowadzone na stacji roboczej Dell Precision T7400 (2*3.2 GHz Xeon, 64 Gb RAM) i wynosiły:

 

aksjomat: FFFA

reguły:

A -> !"////////B

B -> &FFFA

 

 

Dla pierwszych 14 generacji, wyniki czasowe są podobne. Dopiero dalej zaczynamy zabawę:

 

 

generacja 17 - houdini: 0.84s, Lex-Systemy: 0.29s

generacja 18 - houdini: 10.65s, Lex-Systemy: 0.53s

generacja 19 - houdini: 24.25s, Lex-Systemy: 0.87s

generacja 20 - houdini: 144.61s, Lex-Systemy: 1.58s

generacja 17 - houdini: 345.49s, Lex-Systemy: 2.58s

generacja 21 - houdini: 2,013.52s, Lex-Systemy: 4.76s

generacja 22 - houdini: 3,887.33s, Lex-Systemy: 7.28s

generacja 23 - houdini: crash, Lex-Systemy: 14.28s

 

Warto zauważyć, że obliczenie generacji 22 zajęło Houdiniemu ponad godzinę, w momencie gdy Lex-Systemy obliczyły ją w zaledwie 7 sekund.

 

 

inny przykład:

 

aksjomat: F+F+F+F

reguły:

F -> F-F+F+F-F+F-F-F+F

 

 

generacja 3 - houdini: ~2*10^(−3)s, Lex-Systemy ~2*10^(-3)s

generacja 4 - houdini: 2.7*10^(−2)s, Lex-Systemy 4*10^(-3)s

generacja 5 - houdini: 1.01s, Lex-Systemy 2.4*10^(-2)s

generacja 6 - houdini: 371.5s, Lex-Systemy 0.2s

generacja 7 - houdini: po upływie 7 godzin uzyskaliśmy 80% procesu generacji, Lex-Systemy: 1.76s

generacja 8 - houdini: niemożliwe, Lex-Systemy: 15.97s

generacja 9 - houdini: niemożliwe, Lex-Systemy: 145.77s

 

Tutaj różnica jest jeszcze większa!

 

-------------------------------------------

 

 

Dodatkowo napisałem 2 narzędzia - konwerter L-Systemy -> Lex-Systemy (zajmujący mniej niż 100 linijek w Pythonie, bo jak już wspomniałem, dla reguł L-Systemów języki te posiadają podobną składnię) oraz plugin do Houdiniego pozwalający na generowanie L-Systemów przy pomocy reguł standardowych oraz tych w Lex-Systemach.

Wszystkie moje poprzednie prace na L-Systemach działały z nowym pluginem i pozwalały na odtwarzanie płynnie animacji parametrów L-Systemów, przy czym z oryginalnym generatorem L-Systemów z Houdiniego otrzymywałem 2-3 FPS :)

 

 

Ze względu na pewne obostrzenia na uczelni, nie mogę udostępnić mojej pracy inżynierskiej, ale postaram się jakoś to załatwić - tu znowu pojawia się ból z czasem, więc jak na razie, aby nie czekać kolejnego roku, publikuję wyniki.

Możliwe jednak, że dostanę pozwolenie na opublikowanie działającego programu za darmo, ale tego nie mogę obiecać.

 

Zostałem poproszony o napisanie pracy naukowej na ten temat, więc jeżeli znajdę na to czas i ją napiszę, na pewno ją zapostuję.

 

 

Na chwilę obecną, jeżeli ktoś posiada jakieś pytania lub uwagi będę szczęsliwy na nie odpowiedzieć! :D

Edytowane 9 Wrzesień 2012 przez danilo2