Fraktale

W zadaniu będziemy zajmować się jedną z metod rysowania fraktali, polegającą na iterowaniu układu afinicznych przekształceń płaszczyzny. Dla danego układu k afinicznych przekształceń płaszczyzny:

x' := ai x + bi y + ci ,

y' := di x + ei y + fi ,

gdzie i = 0, 1, ..., k - 1, algorytm rysowania jest następujący:

• wybieramy punkt startowy o współrzędnych (x, y);
• wykonujemy n następujących iteracji:
  • wybieramy losowo jedno z przekształceń;
  • wyznaczamy obraz (x', y') punktu (x, y) w tym przekształceniu;
  • przypisujemy x := x', y := y';
  • rysujemy punkt (x, y).

Należy napisać w asemblerze NASM funkcję fractal tworzącą w pamięci obraz zbioru punktów powstających w wyniku wykonania powyższego algorytmu. Pamięć obrazu zorganizowana jest jako dwuwymiarowa tablica pikseli, a dokładniej jako tablica linii obrazu, gdzie każda linia jest tablicą pikseli. Linie są umieszczane w kolejności od góry do dołu, a piksele w linii od lewej do prawej. Każdy piksel zajmuje 4 bajty (True Color). Należy wymyślić i zaimplementować jakiś algorytm, który automatycznie dobiera kolory. W skrajnym przypadku obraz może być monochromatyczny. Funkcja fractal ma być wywoływana z języka C i ma mieć następujący prototyp:

void fractal(void* pixels, int bpl, int w, int h, int n, int k, TRANSFORMATION t[], POINT p[]);

gdzie:

	pixels	-	adres początku pamięci obrazu,
	bpl	-	liczba bajtów zajmowanych przez jedną linię obrazu,
	w	-	szerokość obrazu w pikselach (liczba pikseli w linii),
	h	-	wysokość obrazu w pikselach (liczba linii w obrazie),
	n	-	liczba iteracji,
	k	-	liczba przekształceń (maksymalnie 64),
	t	-	adres k-elementowej tablicy opisującej przekształcenia,
	p	-	adres 3-elementowej tablicy: p[0] to współrzędne punktu startowego iteracji, p[1] to współrzędne lewego dolnego rogu obrazu, p[2] to współrzędne prawego górnego rogu obrazu.

Struktury TRANSFORMATION, POINT są zdefiniowane następująco:

typedef struct {
FLOAT a, b, c, d, e, f;
} TRANSFORMATION;

typedef struct {
FLOAT x, y;
} POINT;

Jako typ bazowy FLOAT można przyjąć typ float lub double do wyboru.

Kod źródłowy należy dostarczyć w pliku fractal.asm. Nie wolno korzystać z żadnych bibliotek. Jeżeli funkcja fractal ma korzystać z jakichś innych funkcji lub procedur (np. generator liczb pseudolosowych), to powinny być one też napisane w asemblerze i umieszczone razem w tym samym pliku.

Działanie funkcji fractal można przetestować za pomocą programu testującego i przykładowych danych. Program testujący korzysta z biblioteki SDL. Program ten wczytuje ze standardowego wejścia kolejno parametry w, h, n, k, a następnie tablice t, p. Aby móc uruchomić program testujący na maszynie students z domu, należy użyć ssh z opcją -Y.

Na ocenę będą mieć wpływ szybkość wykonywania obliczeń, łącznie z czasem generowania losowości oraz wrażenia artystyczne, polegające na doborze kolorystyki obrazu. Na ogół szybkość będzie testowana na maszynie students. Zatem być może warto zajrzeć np. do dokumentu Software Optimization Guide for AMD64 Processors, Chapter 9 Optimizing with SIMD Instructions (łatwo go znaleźć w Internecie). Na jakość wygenerowanego obrazu bardzo duży wpływ ma losowość wyboru kolejnych przekształceń. Warto więc też popracować nad szybkim i posiadającym dobre własności statystyczne generatorem liczb pseudolosowych. Materiały dotyczące generatorów liczb pseudolosowych zostaną udostępnione na zajęciach. Do inicjalizacji generatora liczb pseudolosowych można użyć np. instrukcji rdtsc.