Zajęcia są we wtorki. Grupa nr 1 zaczyna zajęcia o 16:15, sala G-1-07. Grupa nr 2 o 18:00, sala G-1-10. Zapraszam również na konsultacje (pokój C-2-29 lub online, terminy w USOSwebie).
W trakcie semestru można mieć co najwyżej dwie nieusprawiedliwione nieobecności. Przekroczenie tego limitu oznacza brak zaliczenia.
Zaliczenia ćwiczeń wystawiane będą głównie w oparciu o projekty. Wstępnie planowane są trzy, zobaczymy w jakim tempie będziecie je Państwo realizować. Oprócz projektów będę uwzględniał również aktywność i wiedzę wykazywaną na zajęciach.
W tym roku grupy są zbyt duże, aby w trakcie zajęć dało się ze wszystkimi studentami podyskutować o ich projektach. Podzielone są więc na półgrupy. W niektóre tygodnie będą zajęcia tylko dla pierwszej półgrupy, w inne tylko dla drugiej, a niekiedy będzie musiała przyjść cała grupa.
Harmonogram ćwiczeń:
Terminy oddawania projektów:
Nazwa „gramatyki kształtu” (ang. shape grammars) przywodzi na myśl gramatyki formalne, które są wykorzystywane do definiowania składni języków programowania. I rzeczywiście, gramatyki kształtu zaadaptowały na swoje potrzeby ideę reguły (nazywanej też produkcją), wywodu, itd. Zasadniczą różnicą jest to, że gramatyki formalne przekształcają ciągi znaków, a gramatyki kształtu — rysunki (w oryginalnym artykule nazywane kształtami, co moim zdaniem jest trochę mylące).
Tak jak są różne rodzaje gramatyk ciągowych, tak też można wymyślić i korzystać z różnych rodzajów gramatyk kształtu. W poniższym opisie będę starał się zaznaczać miejsca, w których można wybrać jedno z kilku alternatywnych podejść.
Regułę gramatyki kształtu definiuje się podając dwa rysunki, zwane lewą i prawą stroną reguły. Między nimi zwyczajowo umieszcza się strzałkę.
Regułę można zastosować (zaaplikować) do rysunku, jeśli jest w nim fragment pasujący do lewej strony reguły. Usuwa się wtedy dopasowany fragment i na jego miejsce wstawia kopię prawej strony reguły.
Niekiedy wymaga się, aby lewa strona zawierała się w prawej. Z punktu widzenia użytkownika zastosowanie takiej reguły niczego nie usuwa, dodaje tylko do rysunku nowe elementy.
Gramatykę definiuje się podając zbiór reguł oraz rysunek początkowy (startowy). Spotyka się też podejście, w którym rysunek początkowy zawsze jest pusty, a za to w zbiorze reguł jest co najmniej jedna z pustą lewą stroną i tylko takie reguły z pustą lewą stroną pasują do pustego rysunku.
Gramatyka generuje rysunki poprzez kolejne przekształcenia rysunku roboczego, który początkowo jest kopią rysunku startowego. Wybiera się regułę, dla której lewej strony istnieje dopasowanie, aplikuje ją i w ten sposób przekształca roboczy rysunek, a potem znów wybiera regułę itd. Ten proces nazywany jest „prowadzeniem wywodu w gramatyce”, a o otrzymywanych w kolejnych krokach rysunkach mówi się, że „zostały wywiedzione z rysunku początkowego”. Jeśli dla żadnej z reguł gramatyki nie można znaleźć dopasowania, to proces wywodu musi się zatrzymać.
Możliwe jest, że dla danego rysunku roboczego i danej reguły będzie istnieć kilka możliwych dopasowań (np. lewa strona to kwadrat, a na rysunku jest pięć takich kwadratów). Możliwe też, że dopasowania będzie miało kilka reguł. W takiej sytuacji można albo losowo wybrać regułę i jej dopasowanie, albo poprosić o decyzję użytkownika nadzorującego proces wywodu. Użytkownikowi można też pozwolić na zakończenie wywodu mimo istnienia dopasowań.
To, w jaki sposób znajduje się dopasowanie lewej strony musi zostać precyzyjnie określone, bo drobne różnice w definicji dopasowania mają daleko idące konsekwencje.
Dopasowanie przez przesunięcie (translację). Metaforycznie można powiedzieć, że przesuwamy rysunek lewej strony bez przechylania go na boki i staramy się nałożyć wszystkie jego linie na linie rysunku roboczego.
Translacja z ewentualnym skalowaniem. Jeśli lewa strona jest trójkątem równobocznym o wysokości 5 jednostek, to dopasuje się ona do trójkąta równobocznego o wysokości 2 jednostek o ile oba są tak samo zorientowane, np. oba mają jeden bok równoległy do osi X.
Podobieństwo geometryczne, czyli dowolne złożenie translacji, skalowania (formalnie: jednokładności), obrotu i odbicia lustrzanego. Uwaga, jeśli lewa strona jest okręgiem, to przy takiej definicji będzie ona miała nieskończenie wiele dopasowań do każdego okręgu występującego na rysunku.
Wiele innych możliwości, np. zawężone podobieństwo bez odbić lustrzanych albo translacja, skalowanie i obroty o wielokrotność 45°.
Struktury danych reprezentujące rysunki i strony reguł oraz operujące na nich algorytmy znajdowania dopasowań nie są banalne, zwłaszcza gdy przez dopasowanie rozumie się podobieństwo. Trzeba w nich uwzględnić możliwość pojawienia się figur emergentnych (przecięcie dwóch nakładających się figur geometrycznych też jest jakąś figurą; stykające się figury tworzą nową, większą figurę). Nie warto aplikować reguły, jeśli w wyniku jej zastosowania rysunek w oczach użytkownika się nie zmieni (np. reguła z kwadratem po lewej stronie, po prawej ten sam kwadrat z okręgiem w środku — jeśli rysunek zawiera kwadrat z już wcześniej wpisanym okręgiem, to nie warto tej reguły tam dopasowywać).
Dla uproszczenia problemu można użyć markerów. Można o nich myśleć jako o figurach mających unikalny kształt — marker w lewej stronie reguły można dopasować tylko do znajdującego się na rysunku markera tego samego typu. Służą do jawnego wskazywania tych miejsc rysunku, w których chcemy aplikować reguły. W najprostszym przypadku wszystkie reguły gramatyki będą miały po lewej stronie pojedynczy marker, po prawej rysunek i nowe markery w tych punktach, w których chcemy kontynuować wywód.
Oryginalny artykuł o gramatykach kształtu zakładał, że wygenerowane rysunki będą potem dodatkowo kolorowane. Pozwolę sobie pominąć milczeniem to, jak definiowano zasady kolorowania.
Projekt sprawdza, czy umiecie Państwo przełożyć teorię z wykładu na praktykę. Musicie zaimplementować interaktywną aplikację, która pozwala śledzić proces generowania rysunku przy pomocy gramatyki kształtu. Będziecie musieli przy tym podjąć dwie ważne decyzje.
Pierwsza decyzja: jak ma działać „silnik” aplikacji, czyli część kodu odpowiedzialna za stosowanie reguł transformacyjnych. Musicie zdecydować, z jakich prymitywów geometrycznych budowane są rysunki, czy będą wykrywane kształty emergentne, co może być po lewej stronie reguły i jak zdefiniowane jest dopasowanie. Od tego zależy stopień skomplikowania algorytmów, które będziecie musieli opracować. Osobiście radziłbym zrezygnować z kształtów emergentnych, bo one bardzo wszystko utrudniają.
Druga decyzja: jak ma wyglądać GUI aplikacji. Absolutne minimum to okno wyświetlające aktualny stan rysunku roboczego, po kliknięciu w nie myszką (czy też naciśnięciu spacji) wykonuje się losowo wybrana reguła i zawartość okna się uaktualnia. To oczywiście nie pozwala użytkownikowi wybierać, co ma być zrobione jeśli dla danego stanu rysunku jest wiele dopasowań, mam więc nadzieję że opracujecie Państwo bardziej zaawansowane GUI.
W aplikacji nie trzeba implementować edytora gramatyk — to zajęłoby dużo czasu i niczego ciekawego Państwa nie nauczyło. Gramatyki, według których generowane są rysunki proszę zdefiniować „na sztywno” w kodzie źródłowym (dobrze byłoby, aby były co najmniej trzy). GUI powinno umożliwiać wybranie jednej z dostępnych gramatyk i rozpoczęcie wywodu od jej rysunku początkowego.
Projekt oceniany będzie z uwagi na trzy kryteria:
Możliwości silnika reguł (ignorowanie kształtów emergentnych nie obniży oceny projektu).
Jakość GUI, czyli możliwość kontroli wywodu oraz wyraźne pokazywanie użytkownikowi, co reguły robią z rysunkiem.
Poprawność i czytelność kodu źródłowego. Będziecie Państwo musieli mi go pokazać i objaśnić jak działa, a ja będę musiał go zrozumieć.
Na przykład, jeśli aplikacja potrafi dopasowywać tylko poprzez translację i tylko trójkąty (a więc tylko one mogą być po lewej stronie reguł), to piątki nie dostaniecie. Możecie dostać czwórkę, jeśli ma przyzwoite GUI i poprawny kod. Jeśli miałaby wybitne GUI, to może nawet plus czwórkę.
Po przedyskutowaniu ze mną kodu aplikacji trzeba go spakować do archiwum ZIP i wrzucić na Pegaza. Projekt uznaję za zaliczony dopiero wtedy, gdy otrzymam jego kod (i ten kod daje się uruchomić, co powinno być oczywiste ale na wszelki wypadek lepiej to czarno na białym napisać).
Możecie napisać albo tradycyjną aplikację desktopową (np. w Javie, C++ lub Pythonie), albo aplikację działającą w środowisku przeglądarki WWW. Jeśli zdecydujecie się na to drugie, to spróbujcie zrobić to tak, aby można ją było uruchomić po prostu otwierając plik HTML z pendrive’a.
Możecie korzystać z bibliotek do tworzenia rysunków, reprezentowania figur, znajdowania podobieństw geometrycznych itd. Ale jeśli udałoby się Wam znaleźć bibliotekę z procedurami do aplikowania reguł gramatyk kształtu, to z niej nie wolno korzystać — te algorytmy musicie opracować i zaimplementować sami.