Zaawansowana grafika komputerowa

20.II.2002 Ćwiczenia organizacyjne.

Zadanie 1 (termin 2 tygodnie).

Treść zadania jest dość obszerna, samo zadanie powinno być dość ciekawe.
Oto najprostszy, konsolowy program rysujący tzw. zbiór Julii na płaszczyźnie.

# include <complex.h>
# include <stdio.h>

void Julia(complex<double> c)
{
    int i,j;
    double px,py;
    complex<double> x;
    unsigned char iter;

    for (j=0,py=-2.04;j<24;j++,py+=0.17)
        for (i=0,px=-2.00;i<80;i++,px+=0.05)
        {
            iter=0;
            x=complex<double>(px, py);            // [1]
            while ((abs(x)<4.0) && (iter<31))
            {
                iter++;
                x=x*x+c;
            }
            putc(63-iter, stdout);
        }
}

int main()
{
    Julia(complex<double>(0, -1));
    return 0;
}

Zbiór ten jak widać istnieje na płaszczyźnie zespolonej, w wycinku [-2,2] x [-2,2]. W celu wyznaczenia 'koloru' każdego punktu p takiego wycinka, algorytm iteruje funkcję

f(z) = z²+c

przy początkowej wartości parametru z równej p ([1]) dla jakiegoś ustalonego c. Iteracja przerywana jest w dwóch przypadkach:

osiągnięto maksymalną dopuszczalną liczbę iteracji (tu: 31)
kolejne wartości układu iteracyjnego 'uciekają' do nieskończoności (tu: |p| >= 4.0)

(zainteresowanych głębszym zrozumieniem istoty fraktalnych zbiorów Julii i Mandelbrota odsyłam np. do "Granice chaosu. Fraktale" Peitgena, Jurgensa i Saupego).
Okazuje się, że iteracja tak prostej funkcji prowadzi do zbiorów fraktalnych nie tylko w przestrzeni liczb zespolonych. Zadanie polega na napisaniu programu wizualizującego fraktalne zbiory Julii w przestrzeni kwaternionów.

Specyfikacja:

program ma umożliwiać zadanie parametru będącego wektorem 4 liczb rzeczywistych (współrzędnych liczby z przestrzeni kwaternionów),
obraz fraktala ma pojawiać się na ekranie albo ma być zapisywany do pliku w jakimś formacie graficznym (BMP, JPG)

Wskazówki:

w przestrzeni kwaternionów H istnieją 3 jednostki urojone: i j k. Każdy element może być zapisany jako:

a + bi + cj + dk
kwaterniony dodaje się w 'zwykły sposób' (jak liczby zespolone, dodawanie po osiach)
kwaterniony mnoży się korzystając z następujących reguł mnożenia jednostek urojonych:
i2 = j2 = k2 = -1
ij = -ji = k
jk = -kj = i
ki = -ik = j
mnożenie kwaternionów nie jest przemienne, na ogół xy nie jest równe yx
zbiory Julii w przestrzeni kwaternionów 'żyją' w kostce K = [-2,2] x [-2,2] x [-2,2] x [-2,2]
do obliczeń obrazu 4-wymiarowego zbioru Julii przyjmiemy, że interesuje nas przekrój tego zbioru i płaszczyzny t = 0 (czyli do obliczeń wybierzemy tylko punkty postaci (x, y, z, 0)
maksymalną ilość iteracji można dowolnie zwiększyć, zyskuje się dzięki temu większą dokładność obrazu zbioru Julii (na przykład 256 czy 512 iteracji), kolor punktu przestrzeni powinien być zależny od ilości iteracji jaką algorytm wykonał dla tego punktu (zależność może być bardzo prosta, typu RGB(iter, 255-iter, iter))
algorytm decyduje o tym, jaki jest kolor dowolnego punktu przestrzeni, jednak przyjmiemy, że istotne są tylko te punkty przestrzeni, w których algorytm wykonał maksymalną ilość iteracji (innymi słowy interesuje nas tylko wnętrze zbioru, te punkty, w których algorytm wykonuje mniej iteracji w przestrzeni 4-wymiarowej tworzyły by otoczenie zbioru Julii; wizualizacja takiego otoczenia byłaby nieinteresująca)
program powinien stworzyć 2-wymiarowy obraz stosując rzut równoległy bądź perspektywiczny i wykorzystać informację o kolorze punktów przestrzeni 3-wymiarowej do narysowania malutkich cieniowanych trójkątów pomiędzy każdymi dwoma sąsiadującymi punktami (zdecydowanie warto wykorzystać OpenGL, można dołożyć oświetlenie)
'dokładność' obliczeń (czyli gęstość próbkowania kostki K) powinna być dobrana tak, aby obliczenia trwały sensowną ilość czasu (nie więcej niż kilka minut).

Propozycje dalszego rozwijania programu:

dowolnie modyfikowana w czasie rzeczywistym pozycja obserwatora
prebuforowana animacja (tzn. z wcześniejszym obliczeniem obrazu kilkunastu / kilkudziesięciu klatek animacji i odtwarzaniu ich; animacja w czasie rzeczywistym raczej się nie uda ze względu na czas trwania obliczeń pojedynczego obrazu) powstała przez modyfikacje parametru wejściowego c algorytmu

Przykładowy obraz 4-wymiarowego zbioru Julii, wygenerowany przez program Quat 1.10, wygenerowany z dwóch różnych pozycji obserwatora tak, aby umożliwić oglądanie stereoskopowe (zezem rozbieżnym)

6.III.2002

Zadanie 2 (termin 2 tygodnie).

Należy napisać prosty engine ray-trace'ujący, który będzie w kolejnych zadaniach rozwijany.

Specyfikacja:

jako format wejściowy przyjmujemy format MGF lub POV (specyfikacja formatu MGF dostępna jest na sieci w wielu miejscach, wystarczy zapytać o to dowolną wyszukiwarkę, specyfikacja POW - tamże),
jako format wyjściowy przyjmujemy BMP, TIFF, TGA lub inny prosty format grafiki 24 bitowej,
sposób działania programu powinien zależeć od sposobu wywołania z linii poleceń. Dostępne powinny być dwa warianty:
- program pracujący w oknie konsoli, pokazujący postęp w tworzeniu obrazu za pomocą jakichś tekstowych pasków postępu,
- program tworzący okno graficzne i pokazujący postęp pracy w postaci obrazu graficznego (obsługa grafiki dowolna: Win32API, OpenGL, DirectX)
lista funkcji, które program powinien implementować:
obraz:

paleta kolorów 24 bitowa
dowolnie określane rozmiary obrazu (w rozsądnych granicach)

tworzenie obrazu:

dowolnie określona pozycja obserwatora, punkt na który obserwator patrzy i jego kierunek "góra-dół" (innymi słowy dowolny lokalny układ obserwacji)
możliwie dużo różnych klas prostych obiektów zadanych w postaci:

trójkątów i czworokątów na płaszczyźnie
funkcji uwikłanych F(x, y, z) = 0

oświetlenie, przezroczystość, odbijanie światła

możliwość definiowania dowolnie wielu źródeł światła o określonym natężeniu składowych kolorów
światła kierunkowe (dany jest tylko wektor kierunkowy)
światła punktowe (dany jest tylko punkt położenia, przyjmujemy że światło biegnie we wszystkie możliwe strony)
światła punktowe o określonym kierunku padania (dany jest punkt położenia i wektor kierunkowy) i zdefiniowanym kącie tworzącej stożka światła
model oświetlenia Phonga
możliwość dowolnego określenia stopnia przezroczystości obiektu, czyli stopnia w jakim kolor punktu na powierzchni obiektu ma zależeć od koloru obiektu, a w jakim od koloru wyznaczonego przez kontynuowanie obliczeń na tym samym promieniu
możliwość dowolnego określenia stopnia "odbijalności" promieni światła (powierzchnie lustrzane), czyli stopnia w jakim kolor punktu na powierzchni obiektu ma zależeć od koloru obiektu, a w jakim od koloru wyznaczonego przez kontynuowanie obliczeń na promieniu odbitym od powierzchni

Specyfikację należy potraktować jako pewien kierunek rozwoju engine'u, nie zaś jako listę szczegółowych wymagań.

Pomocna literatura:

[1] Nicholas Wilt, "Ray-tracing zorientowany obiektowo" + biblioteka OORT1.0 (do ściągnięcia z sieci)
10.IV.2002

Zadanie 3 (termin 17.IV.2002).

W zbudowanym w zadaniu 2 engine zaimplementować dowolny mechanizm przyspieszania obliczeń punktów przecięcia promienia z najbliższym obiektem. Dodatkowo zaimplementować możliwość tworzenia obrazów stereoskopowych.

Specyfikacja:

należy zdecydować się na co najmniej jedną z metod przyspieszania obliczeń (bryły otaczające, BSP, inne)
należy podczas prowadzenia obliczeń prowadzić statystykę czasu obliczeń związanych z wyznaczaniem przecięć
rozwiązanie zadania powinno polegać na przedstawieniu raportu z generowania przykładowych scen starym i nowym sposobem (oczywiście niedopuszczalne jest aby zoptymalizowany algorytm generował inny obraz!)
raport powinien porównywać czas potrzebny na obliczenia w obu podejściach dla co najmniej 5 różnych przykładowych scen
raport należy przedstawić w postaci znormalizowanego wykresu (to znaczy przyjąć czas generowania sceny starym sposobem jako 100 jednostek i pokazać na wykresie proporcjonalny czas generowania sceny nowym sposobem np. 76, to samo dla kolejnych scen)
podsumowanie raportu powinno pokazywać również średni znormalizowany czas generowania scen nowym sposobem (tzn. jak poprzedni w odniesieniu do 100 jednostek dla starego sposobu tworzenia sceny należy pokazać średni czas generowania scen nowym sposobem)
wykresy będziemy porównywać aby zaobserwować jak poszczególne metody wpływają na czas obliczeń (jeśli znajdą się przynajmniej dwie różnie metody) oraz jaka jest efektywność implementacji każdej z metod
dodatkowe wymaganie dotyczące obrazów stereoskopowych polega na dołożeniu funkcji, która pozwoli utworzyć dwa niezależne obrazy z dwóch różnych pozycji obserwatora, nieznacznie przesuniętych względem siebie wzdłuż osi wyznaczającej kierunek lewo-prawo obserwatora, a następnie obraz wyjściowy utworzy jako złożenie obu obrazów (sklejenie ich jeden obok drugiego). Obraz wyjściowy powinien mieć zachowane proporcje, tzn. jeśli generowany jest obraz w rozdzielczości 800x600 to obraz stereoskopowy powinien być sklejeniem dwóch obrazów 400x600).

Zadanie 4 (termin 29.V.2002).

Zbudowany engine wyposażyć w następujące metody przyspieszania obliczeń:

interpolacja (metoda adaptacyjna, subpixel)
metody Monte-Carlo
podobnie jak w poprzednim zadaniu przygotować znormalizowany wykres, będący raportem porównującym czasy oryginalnego algorytmu i czasy algorytmów przyspieszonych (w przypadku algorytmu Monte-Carlo nie musi być to przyspieszenie - tu równie ważne są efekty wizualne)