Afiniczne dywany

Poznaliśmy już dywany na ustalonej powierzchni, w których algorytm za pomocą dwóch pętli pracowicie zamalowuje jakiś kawałek ekranu, i dywany nieograniczone - gdzie punkt wędruje w niekiedy bardzo rozległej przestrzeni matematycznej i pozostawia po sobie barwny ślad. Dywany afiniczne należą do kategorii dywanów nieograniczonych.

Poznaliśmy już dywany na ustalonej powierzchni, w których algorytm za pomocą dwóch pętli pracowicie zamalowuje jakiś kawałek ekranu, i dywany nieograniczone - gdzie punkt wędruje w niekiedy bardzo rozległej przestrzeni matematycznej i pozostawia po sobie barwny ślad. Dywany afiniczne należą do kategorii dywanów nieograniczonych.

Rysunek 1. Ta zagadkowa grafika, zwana trójkątem Sierpińskiego, jest efektem pracy trzech zestawów przekształceń afinicznych. Bieżące przekształcenie jest wybierane za pomocą prostego losowania, ale mimo obecności czynnika losowego cała grafika wykazuje zadziwiająco regularną strukturę.

Rysunek 1. Ta zagadkowa grafika, zwana trójkątem Sierpińskiego, jest efektem pracy trzech zestawów przekształceń afinicznych. Bieżące przekształcenie jest wybierane za pomocą prostego losowania, ale mimo obecności czynnika losowego cała grafika wykazuje zadziwiająco regularną strukturę.

Niech zmienne x i y oznaczają współrzędne punktu. Punkt ten, oczywiście, potrafimy wykreślić na ekranie. Zatem zmieńmy początkowe wartości jego współrzędnych, wykreślmy go na ekranie, znów zmieńmy współrzędne, ponownie wykreślmy i tak dalej - powiedzmy milion razy... Co zobaczymy na ekranie? Ścieżkę, ślad pozostawiony przez wędrujący punkt:

x = 0, y = 1;

for( i = 0; i < 1000000; ++i)

{

x = f( x, y);

y = g( x, y);

putpixel( x, y, RED);

}

Ten prosty szkic algorytmu ilustruje tak zwany proces iteracji (wielokrotnego przekształcania) położenia punktu. Samym przekształcaniem zajmują się ledwie zarysowane tutaj funkcje f() i g() - to w nich tkwi tajemnica piękna lub brzydoty uzyskiwanej grafiki. Zanim napiszemy jakiś konkretny program, przyjrzyjmy się kilku bardzo istotnym szczegółom technicznym tego algorytmu.

Po pierwsze, spodziewamy się, że nasze programy będą dość powolne - żeby grafika była dostatecznie soczysta, powinna składać się z wielu punktów, zatem główna pętla iterująca musi się długo obracać. Podany tutaj czynnik 1000000 wcale nie jest przesadzony.

Po drugie, brakuje tu skalowania, czyli dopasowania rozmiarów grafiki do rozmiarów ekranu. To nieprzyjemne zagadnienie jest szczególnie ważne przy wykreślaniu dywanów iterowanych - nigdy nie mamy pewności, w jakim obszarze przestrzeni matematycznej będzie poruszał się punkt. Trajektoria stale przesuwanego punktu zależy od jego położenia początkowego (w naszym szkicu były to współrzędne (0,1)) i oczywiście od konkretnej postaci funkcji f() i g(). Z łatwością zgadniemy funkcje, które przesuwają punkt w obszarze, powiedzmy, od -1 do +1 (choćby trygonometryczna funkcja sin()) albo wyprowadzają go do nieskończoności (choćby funkcja polegająca na podnoszeniu do kwadratu). Ponadto dysponując dobrym skalowaniem, za jednym zamachem będziemy mogli pozycjonować grafikę na ekranie, eksponować wybrane jej fragmenty, brać pod mikroskop szczególnie udane wycinki. Z tych wszystkich powodów w naszych programach od razu powinniśmy zaimplementować porządne skalowanie współrzędnych punktu i wykonywać je zawsze tuż przed wykreśleniem na ekranie obrazu.

Rysunek 2. Skoro trójkąt Sierpińskiego jest generowany przez rodzinę trzech przekształceń afinicznych, niech każde przekształcenie będzie skojarzone z jakimś kolorem. Kolory te możemy zawczasu przygotować w odpowiedniej tablicy, równolicznej z rodziną przekształceń.

Rysunek 2. Skoro trójkąt Sierpińskiego jest generowany przez rodzinę trzech przekształceń afinicznych, niech każde przekształcenie będzie skojarzone z jakimś kolorem. Kolory te możemy zawczasu przygotować w odpowiedniej tablicy, równolicznej z rodziną przekształceń.

Po trzecie - nawet w tym ogólnym szkicu jest subtelny błąd. Funkcja f() modyfikuje współrzędną x, ale już w następnym wierszu dostępu do tej współrzędnej domaga się druga funkcja g(). Zmienna x została za szybko zmodyfikowana...

Oto ten sam szkic, ale już z uwzględnieniem trzech powyższych uwag. Cztery stałe RMinX, ... RMaxY oznaczają eksponowany wycinek przestrzeni matematycznej, który ma być wyświetlony w ekranowym obszarze, opisanym czterema stałymi EMinX, ... EMaxY. Na podstawie tych parametrów wyli-czymy tak zwane współczynniki skalowania A, ... D. Ponadto tymczasowa zmienna xx jest odpowiedzią na trzecią, przed chwilą zgłoszoną uwagę:

const int EMinX = 0, EMaxX = 640

EMinY = 0, EMaxY = 480;

const double RMinX = -1, RMaxX = 1

RMinY = -1, RMaxY = 1;

//współczynniki skalowania

double A, B, C, D;

//współrzędne matematyczne punktu...

double x, y, xx;

//...i ich odpowiedniki ekranowe

int xe, ye;

int i; //licznik obrotów pętli

A = (EMaxX - EMinX) / (RMaxX - RMinX);

B = EMinX - A * RMinX;

C = (EMaxY - EMinY) / (RMinY - RMaxY);

D = EMinY - C * RMaxY;

x = y = 0.3; //początkowa pozycja punktu

for( i = 0; i < 1000000; ++i)

{

xe = A * x + B; //przeskalowanie punktu...

ye = C * y + D;

//... i jego ślad na ekranie

putpixel( xe, ye, BLUE);

xx = f( x, y); //jeszcze nie zmieniamy x...

y = g( x, y);

x = xx; //...a dopiero teraz.

}

Rysunek 3. Ta grafika, zwana paprocią Barnsleya, jest generowana rodziną czterech przekształceń. Ponieważ każdemu przekształceniu przypisaliśmy inny kolor, widzimy wyraźnie, że obszar czerwonej łodyżki jest znacznie mniejszy niż zielonego liścia. Sprawiedliwe losowanie numeru przekształcenia jest ewidentnym marnowaniem pikseli czerwonych, które zapewne już wielokrotnie pokryły czerwoną łodygę, za to wyraźnie przydałyby się w innych miejscach liścia. Musimy znaleźć taki algorytm losowania numeru przekształcenia, który częściej będzie dostarczał jednych wartości, rzadziej innych.

Rysunek 3. Ta grafika, zwana paprocią Barnsleya, jest generowana rodziną czterech przekształceń. Ponieważ każdemu przekształceniu przypisaliśmy inny kolor, widzimy wyraźnie, że obszar czerwonej łodyżki jest znacznie mniejszy niż zielonego liścia. Sprawiedliwe losowanie numeru przekształcenia jest ewidentnym marnowaniem pikseli czerwonych, które zapewne już wielokrotnie pokryły czerwoną łodygę, za to wyraźnie przydałyby się w innych miejscach liścia. Musimy znaleźć taki algorytm losowania numeru przekształcenia, który częściej będzie dostarczał jednych wartości, rzadziej innych.

Najwięcej kłopotu mamy z przeskalowaniem obszaru matematycznego (tutaj o rozpiętości dwóch jednostek w pionie i w poziomie) w ekran (tutaj o archaicznej rozpiętości dawnego trybu VGA). Nie ma wyjścia - kiedyś trzeba to zrobić... Za to potem jest już łatwo - zauważmy tylko, że w pętli iteracyjnej oszczędzamy współrzędną x do czasu wyliczenia zarówno nowej wartości x, jak i y.

Rysunek 4. Dzięki niesprawiedliwemu losowaniu numeru przekształcenia ten sam liść paproci jest znacznie soczystszy - gęstość pikseli w każdym kolorze jest mniej więcej taka sama. Porządne rozwiązanie tego problemu wymaga oszacowania proporcji między wielkościami pól, obsługiwanych przez poszczególne przekształcenia afiniczne.

Rysunek 4. Dzięki niesprawiedliwemu losowaniu numeru przekształcenia ten sam liść paproci jest znacznie soczystszy - gęstość pikseli w każdym kolorze jest mniej więcej taka sama. Porządne rozwiązanie tego problemu wymaga oszacowania proporcji między wielkościami pól, obsługiwanych przez poszczególne przekształcenia afiniczne.

Tyle na temat szkicu algorytmu dywanu iterowanego. Teraz przyjrzymy się pewnej szczególnie prostej postaci funkcji f() i g(), zwanej bardziej tajemniczo przekształceniem afinicznym, a pospoliciej przekształceniem liniowym:

...

xx = M1 * x + M2 * y + T1;

y = M3 * x + M4 * y + T2;

...

W powyższych równaniach pod symbolami M i T kryją się zwykłe, niewielkie liczby. Mówiąc krótko - nowe x, a także nowe y powstają w wyniku przemnożenia dotychczasowych współrzędnych przez jakieś parametry, zsumowania ich i jeszcze dodania pewnej stałej wartości. Naprawdę trudno o prostszą postać funkcji f() i g(). Zauważmy też z radością, że ta prosta forma dobrze rokuje szybkości naszych programów - wszak mnożyć i dodawać to dzisiejsze procesory naprawdę potrafią!

Do zrobienia pozostał dosłownie jeszcze jeden krok - otóż jedno przekształcenie liniowe nigdy nie wygeneruje ciekawego obrazu. Musimy wprowadzić do gry kilka przekształceń (tzn. kilka przed chwilą przytoczonych funkcji), ale o różnych wartościach współczynników M i T. Takie alternatywne przekształcenia - a konkretniej rodziny ich współczynników - najwygodniej będzie zebrać w odpowiednich tablicach. Ponadto rodzinę, która akurat przekształca punkt, będziemy po prostu losować. Oto algorytm ostatecznego programu (rysunek 1):

// Trójkąt Sierpińskiego

const int EMinX = 0, EMaxX = ClientWidth

EMinY = 0, EMaxY = ClientHeight;

const double RMinX = -0.2, RMaxX = 4.2

RMinY = -0.2, RMaxY = 4.2;

double A, B, C, D;

double x, y, xx;

int xe, ye;

int i;

//trzy rodziny przekształceń

double M1[ 3] = {0.5, 0.5, 0.5};

double M2[ 3] = {0.0, 0.0, 0.0};

double M3[ 3] = {0.0, 0.0, 0.0};

double M4[ 3] = {0.5, 0.5, 0.5};

double T1[ 3] = {0.0, 2.0, 1.0};

double T2[ 3] = {0.0, 0.0, 1.73};

int nr; //numer bieżącego przekształcenia

A = (EMaxX - EMinX) / (RMaxX - RMinX);

B = EMinX - A * RMinX;

C = (EMaxY - EMinY) / (RMinY - RMaxY);

D = EMinY - C * RMaxY;

x = y = 0.0; //początkowa pozycja punktu

for( i = 0; i < 1000000; ++i)

{

//które przekształcenie pracuje?

nr = random(3);

xx = M1[ nr] * x + M2[ nr] * y + T1[ nr];

y = M3[ nr] * x + M4[ nr] * y + T2[ nr];

x = xx;

xe = A * x + B; //przeskalowanie punktu

ye = C * y + D;

putpixel( xe, ye, BLUE);

}

Dywan afiniczny powstaje w wyniku wielokrotnego przesuwania punktu na płaszczyźnie za pomocą szczególnie prostego przekształcenia, zwanego przekształceniem afinicznym. Po każdym wyliczeniu nowych współrzędnych punkt wykreślamy na ekranie. Dywan jest ekranowym śladem po takim wędrującym punkcie. Nie sposób przewidzieć jego wyglądu, dopóki się go nie zobaczy... Niektóre dywany zaliczają się do najbardziej zagadkowych zjawisk matematycznych, a ich obrazy często są niezwykłe.


Zobacz również