2007.06_Piękno fraktali_[Programowanie].pdf

dla programistów

Programowanie C++/KDE/QT

Piękno fraktali

Marek Sawerwain

Czym tak naprawdę są fraktale? Dziś w sposób jednoznaczny jeszcze nikt nie potrai odpowiedzieć.

Można je przedstawiać jako obiekty o ułamkowym wymiarze, bowiem jeśli punkt czy linia jest obiektem

jednowymiarowym a płaszczyzna obiektem dwuwymiarowym, to fraktale są obiektami o wymiarze

np. 1.7. O fraktalach mówi się także jak o obiektach samopodobnych.

tego rodzaju obiekty, gdyż ich rysowanie przy

pomocy ołówka i kartki papieru jest niezwykle

trudne ze względu na bardzo dużą ilość obli-

czeń, jakie należy przeprowadzić. Dynamiczny rozwój tej

nauki stał się możliwy dzięki postępowi w technice kom-

puterowej. Coraz szybsze komputery pozwalają na prze-

prowadzanie wielu skomplikowanych obliczeń, które

są niezbędne, aby uzyskać graiczne reprezentacje fraktali.

Jednak z drugiej strony napisanie programu, który bę-

dzie zdolny do rysowania fraktali, nie jest zadaniem bar-

dzo trudnym. Uzyskanie najsłynniejszych fraktali (jak

zbiór Mandelbrota i Julii) wymaga nieco cierpliwości i kil-

ku wolnych godzin. W tym artykule postaram się poka-

zać, w jaki sposób można opracować program do tworze-

nia fraktali w języku C++ przy wykorzystaniu programu

KDevelop. Co oznacza, że opracowany przez nas program

będzie funkcjonował w ramach środowiska KDE.

gramu KDevelop . Opracujemy tylko podstawowe funkcje,

ale nie odmówimy sobie wykorzystania możliwości gra-

icznego projektowania interfejsu, choć sam interfejs na-

turalnie nie będzie zbyt skomplikowany. Wystarczy nam

tylko jedno okno dialogowe oraz przycisk oznaczający ry-

sowanie fraktala. Dodamy także kontrolkę QComboBox ,

w której wybierzemy typ zbioru Mandelbrot bądź Julia oraz

kilka pól edycyjnych. Do tych pól będziemy mogli wpisy-

wać współrzędne obszaru, w których będzie rysowany

fraktal. Sam rysunek fraktala zostanie narysowany we-

wnątrz widgetu QFrame .

Tego typu interfejs za pomocą KDevelopa zaprojektuje-

my w dosłownie chwilę, ale bardzo ważny jest numer wer-

sji programu KDevelop . Powinna to być wersja przynajm-

O autorze

Autor zajmuje się tworzeniem oprogramowania dla

WIN32 i Linuksa. Zainteresowania: teoria języków pro-

gramowania oraz dobra literatura. Kontakt z autorem:

autorzy@linux.com.pl

Plan aplikacji

We wstępie już zdradziłem, że program rysujący fraktale

będzie opracowany w środowisku KDE przy użyciu pro-

czerwiec 2007

T rudno w jednoznaczny sposób wyobrazić sobie

dla programistów

Programowanie C++/KDE/QT

Najwięcej problemów będzie sprawia-

ło samo narysowanie fraktala i to jest nasz

główny problem. Dlatego w klasie o nazwie

Fractal dokonamy implementacji wszyst-

kich pomocniczych funkcji do wykonania

tego zadania. Podczas rysowania obiektu

fraktalnego bardzo często korzysta się z liczb

zespolonych, nie inaczej jest w naszym przy-

padku. Jednakże nie będziemy tworzyć włas-

nej klasy do obsługi liczb zespolonych, wy-

korzystamy standardową deinicję complex

dostępną w bibliotece standardowej języka

C++. W ten sposób zyskamy na czasie oraz

będziemy mogli tworzyć bardziej skompli-

kowane formuły. Oszczędzimy sobie tak-

że posługiwania się nieco bardziej skompli-

kowaną matematyką, bowiem wyznaczanie

pierwiastka czy funkcji wykładniczej dla ar-

gumentów zespolonych jest już nieco trud-

niejsze niż dla wartości rzeczywistych.

Rysunek 1. Schemat najważniejszych zdarzeń w programie

Podstawowa technika

rysowania fraktali

Typ fraktali, jaki chcemy rysować, a mia-

nowicie zbiór Mandelbrota oraz Julii, okre-

śla technikę tworzenia tego typu rysunku.

Ogólnie polega to na tym, że fraktal rysu-

jemy w ramach zwykłego układu współ-

rzędnych. Oczywiście należy dobrać odpo-

wiednie współrzędne, np. zbiór Mandelbro-

ta warto na początek rysować w następują-

cym obszarze: poszczególne wartości dla osi

liczbowej X przyjmują wartości w zakresie

od -1.5 do 1.5, a dla osi Y odpowiednio od -

0.5 do 0.5. Podane współrzędne określają pe-

wien prostokątny obszar.

Naszym zadaniem jest poruszanie się

po poszczególnych punktach tego obszaru.

Odstęp pomiędzy poszczególnymi piksela-

mi, czyli tzw. krok, jest właściwie dowolny.

Przy czym mniejsza wartość kroku powodu-

niej 3.3.5. Znacznie starsze wersje tego pro-

gramu nie są zintegrowane z programem

QTDesigner , który umożliwia wygodne pro-

jektowanie interfejsu za pomocą myszki,

a proces ten jest w pełni zintegrowany ze

środowiskiem KDevelop . Projekt znajdujący

się na płycie DVD został utworzony z typu

Simple Designer based KDE Application . Pro-

gram, w którym występuje tylko kilka okien

dialogowych najlepiej tworzyć za pomocą

tej opcji.

Spoglądając na nasz program w sposób

bardzo ogólny, widać, iż nie będzie to skom-

plikowana aplikacja. Potwierdza to schemat

zaprezentowany na Rysunku 1. W progra-

mie niewątpliwie głównym zadaniem jest

rysowanie zbioru Mandelbrota bądź Julii,

ale oprócz tego dodamy zapis otrzymane-

go rysunku do pliku. Wprowadzimy tak-

że podwójne buforowanie, aby narysowany

fraktal nie znikał w momencie przesunięcia

okna.

W naszym projekcie kod źródłowy został

podzielony na kilka plików. Pliki fractal.cpp

i fractal.h zawierają implementację klasy Frac-

tal , która bezpośrednio jest odpowiedzialna

za narysowanie zbioru fraktalnego. Następ-

ne dwa pliki – fracappwidget.cpp oraz fra-

cappwidget.h – implementują obiekt fracAp-

pWidget, który odpowiada oknu dialogowe-

mu tworzonemu w naszym programie. To

w tej klasie znajdują się metody wywoływa-

ne, gdy klikniemy na przycisk Draw Fractal

albo OK. W projekcie znajdują się też pliki

main.cpp oraz fracapp.cpp i fracapp.h waż-

ne z punktu widzenia aplikacji KDE, ale z ra-

cji ograniczonej objętości artykułu nie będę

przedstawiał ich roli.

Rysunek 2. Zależności między układami współrzędnych

www.lpmagazine.org

dla programistów

Programowanie C++/KDE/QT

Listing 1. Metoda odpowiedzialna za narysowanie zbioru Mandelbrota

Jak widać argumentem jest kontrolka Image-

Area, inalny rysunek zostanie narysowany

właśnie za pomocą tej kontrolki, a dokładniej

mówiąc – na niej. Następny krok to odczy-

tanie informacji o współrzędnych obszaru,

w którym będziemy rysować. Potrzebna jest

także liczba iteracji:

void Fractal :: DrawMandelbrot ( int type ) {

int xx , yy ;

int r , g , b ;

double dx , dy ;

QPainter dd ( pixmap );

for ( xx = 0 ; xx < SCR_MAX_X ; xx ++ ) {

for ( yy = 0 ; yy < SCR_MAX_Y ; yy ++) {

dx = ( a_max - a_min ) / SCR_MAX_X * xx + a_min ;

dy = ( b_max - b_min ) / SCR_MAX_Y * yy + b_min ;

switch ( type ) {

case 0 : ColorCalc ( fncMandel2 ( dx , dy ) , & r , & g , & b ); break ;

case 1 : ColorCalc ( fncMandel3 ( dx , dy ) , & r , & g , & b ); break ;

case 2 : ColorCalc ( fncMandel4 ( dx , dy ) , & r , & g , & b ); break ;

}

dd . setPen ( QColor ( r , b , g ) );

dd . drawPoint ( xx , yy );

_painter -> setPen ( QColor ( r , b , g ) );

_painter -> drawPoint ( xx , yy );

}

xmin=XMin_EDT->

text().toDouble();

i=Iterations->value();

Mając te informacje, tworzymy obiekt klasy

Fractal:

Fractal *m = NULL;

m = new Fractal();

Odczytane przed chwilą informacje przeka-

zujemy do obiektu i, jak widać, obiekt paint

również jest przekazywany do klasy rysują-

cej fraktal:

je otrzymanie dokładniejszego obrazu. W na-

szym przypadku będzie on zależał od wiel-

kości okna, w którym rysujemy fraktal i bę-

dzie obliczany samodzielnie przez nasz pro-

gram.

Poruszając się po poszczególnych punk-

tach, będziemy w odpowiedni sposób je ko-

lorować. Kolor będzie zależał od tzw. czasu

ucieczki, bowiem dla każdych współrzędnych

będziemy sprawdzać, czy punkt należy do

zbioru Mandelbrota bądź Julii, przeliczając go

w odpowiedni sposób. Najczęściej w pętli bę-

dziemy sprawdzać, czy punkt ten mieści się

w pewnym obszarze. W zależności od tego jak

szybko punkt ucieknie nam z rozpatrywanego

obszaru, będziemy stosować odpowiedni ko-

lor. I właśnie sposób kolorowania jest najważ-

niejszy w przypadku tych dwóch fraktali.

Opisany sposób wydaje się dość prosty,

ale wymaga przeprowadzania wielu opera-

cji. Posługiwać się będziemy dwoma różny-

mi układami współrzędnych: ekranowymi i

rzeczywistymi (zostało to pokazane również

na Rysunku 2.). Ogólnie przedstawia się to w

następujący sposób: odczytujemy współrzęd-

ne ekranowe związane z określonym widge-

tem KDE (w naszym przypadku będzie to

kontrolka QFrame). Zaczynamy od górnego

lewego rogu, czyli od punktu (0,0). Konwer-

tujemy te współrzędne do układu kartezjań-

skiego, czyli typowego układu współrzęd-

nych (w naszym konkretnym przypadku bę-

dą to współrzędne (-1.5, -0,5)), z jakimi każdy

się spotyka choćby w szkole, następnie stosu-

jemy odpowiednią formułę matematyczną

do obliczenia tzw. czasu ucieczki. W zależno-

ści od wartości tego czasu stawiamy piksel w

odpowiednim kolorze.

m->SetDrawDevice( &paint );

m->SetIter( i );

m->SetArea

( xmin, xmax, ymin, ymax);

m->SetScrMaxVal

( ImageArea->width(),

ImageArea->height());

W programie korzystamy jeszcze z kontro-

lki QComboBox o nazwie FractalType, aby

sprawdzić czy użytkownik chce rysować

fraktal Mandelbrota czy zbiór Julii. W pierw-

szym przypadku rysowanie za pomocą meto-

dy m->DrawMandelbrot(0);, gdzie zero ozna-

cza podstawowy typ zbioru Mandelbrota,

a dla Julii rozpoczęcie procesu rysowania, jest

inicjowane linią: m->DrawJulia(0, -1.25, 0);.

Listing 3. Obliczanie czasu ucieczki

Listing 2. Obliczanie czasu ucieczki

int Fractal :: fncJulia2 (

double _a , double _b ,

double _c , double _d )

{

int i ;

std :: complex < double > z , t , c ;

z . real () = _a ; z . imag () = _b ;

c . real () = _c ; c . imag () = _d ;

for ( i = 0 ; i < max_iter ; ++ i ) {

t = z * z ;

z = t + c ;

if ( std :: norm ( z ) > 4 ) break ;

}

return i ;

}

int Fractal :: fncMandel2 (

double _a , double _b ) {

int i ;

std :: complex < double > z , t , c ;

z . real () = 0 ; z . imag () = 0 ;

c . real () = _a ; c . imag () = _b ;

for ( i = 0 ; i < max_iter ; ++ i ) {

t = z * z ;

z = t + c ;

if ( std :: norm ( z ) > 4 ) break ;

}

return i ;

}

Zbiór Mandelbrota

Po tym dość długim wstępie teoretycznym

czas na praktyczne pokazanie, w jaki sposób

rysujemy zbiór Mandelbrota. Proces ten w ca-

łości jest wykonywany przez metodę Draw-

Mandelbrot z klasy Fractal, jednak nim ją

omówimy, niestety musimy zajrzeć do ob-

sługi przycisku Draw Fractal, bowiem trze-

ba wykonać kilka niezbędnych czynności.

Pierwsza to utworzenie obiektu o nazwie pa-

int pomocnego w procesie rysowania frak-

tala:

QPainter paint( ImageArea );

czerwiec 2007

dla programistów

Programowanie C++/KDE/QT

Pierwszy argument oznacza różne odmiany

zbioru Julii, natomiast dwie następne wiel-

kości to wartość początkowa, która ma duży

wpływ na wygląd zbioru. Warto poekspery-

mentować i wpisać inne wartości, aby zoba-

czyć, jaki to ma wpływ na fraktal.

W tym momencie można już analizo-

wać kod z Listing 1., bowiem to on jest odpo-

wiedzialny za rysowanie graiki. Jednak my

sprawdzimy, co się dzieje po narysowaniu

graiki. Dwie poniższe linie usuwają bufor,

jeśli został utworzony wcześniej, a następnie

tworzą nowy bufor o wymiarach zgodnych

z obiektem ImageArea.

do przeskalowania aktualnej wartości współ-

rzędnych ekranowych, czyli zmiennej xx, a

następnie otrzymaną wielkość dodajemy do

a_min. Ponieważ wartości xx zwiększają się

do szerokości ekranu (zapisana w zmiennej

SCR_MAX_X ), to będziemy z każdym zwięk-

szeniem wartości xx zbliżać się do wartości

a_max. W analogiczny sposób postępujemy

w przypadku wartości osi Y.

Inaczej mówiąc, po tych obliczeniach

w zmiennych dx i dy znajdują się wartości

rzeczywiste, teraz w zależności od wartości

argumentu type wywołujemy odpowiednią

metodę, której zadaniem jest na podstawie

współrzędnych obliczyć, ile iteracji potrzeba,

aby punkt „uciekł” z odpowiedniego obsza-

ru. Funkcji do wyznaczania czasu ucieczki

jest kilka: fncMandel2, fncMandel3 i podobnie

dla zbioru Julii. W dość łatwy sposób można

skonstruować własną lecz o tym opowiem

za chwilę.

Obliczony numer iteracji jest argumen-

tem dla drugiej metody o nazwie Color-

Calc, która zgodnie z nazwą wyznaczy ko-

lor w standardzie RGB. Dysponując kolo-

rem, możemy już postawić punkt na ekranie

pod współrzędnymi xx oraz yy. Korzystając z

klasy QPainter jest to bardzo łatwe do zreali-

zowania, bowiem za pomocą metody setPen

określamy kolor, a metodą drawPoint stawia-

my punkt na ekranie: dd.setPen ( QColor

(r,b,g) ); dd.drawPoint(xx,yy).

Przy czym stawiamy dwa punkty – jeden

do wewnętrznego bufora o nazwie pixmap,

a drugi do kontrolki QFrame za pośrednic-

twem obiektu o nazwie _painter . W ten spo-

sób na ekranie możemy śledzić, w jaki sposób

oraz jak szybko rysowany jest fraktal.

Tajemnice metod fncMandel2

i ColorCalc

Jak widać, najważniejsze czynności wykonuje

się w tych dwóch metodach. Listing 2. przed-

stawia metodę fncMandel2 . Do jej dwóch ar-

gumentów przekazujemy współrzędne punk-

tu, dla którego będziemy wyznaczać liczbę

iteracji po której „ucieknie”z odpowiednie-

go obszaru. Do sprawdzenia czy tak się sta-

ło potrzebne są nam liczby zespolone, któ-

re wbrew pozorom ułatwiają realizację tego

zadania. Niestety nie będziemy w tym miej-

scu tłumaczyć, czym są liczby zespolone,

warto zajrzeć do odpowiednich książek od

matematyki bądź poszukać kilku podstawo-

wych informacji w internecie. Jak się zaraz

okaże, my będziemy traktować te liczby bar-

dzo normalnie (wbrew innej nazwie, bowiem

o liczbie zespolonej mówi się też jako o licz-

bie urojonej), będziemy podnosić je do kwa-

dratu, dodawać etc. Możemy także policzyć

pierwiastek z liczby zespolonej, co więcej,

liczby zespolone umożliwiają też policzenie

pierwiastka z ujemnej liczby rzeczywistej.

Mówiąc krótko – liczby zespolone pozwalają

na nieco więcej niż liczby naturalne czy rze-

czywiste.

Deklarujemy trzy zmienne reprezentują-

ce liczby zespolone: z , t oraz c . Na początek

do zmiennej z wpisujemy zero, czyli do części

rzeczywistej i urojonej wpisujemy zera. Na-

tomiast do zmiennej c wpisujemy współrzęd-

ne punktu. Za pomocą zwykłej pętli for pod-

if ( pix_buf != NULL )

delete pix_buf;

pix_buf = new Qpixmap

( ImageArea->width(),

ImageArea->height() );

W tym buforze będzie się znajdował nasz

fraktal. Bufor jest potrzebny, ponieważ w mo-

mencie odrysowania okna dialogowego na-

szego programu narysowany fraktal zo-

stanie usunięty i naszym zadaniem będzie

przywrócenie graiki. Dlatego należy wyko-

nać kopię graiki do nowo utworzonego bu-

fora i tym zajmuje się metoda DrawInto kla-

sy Fractal.

QPainter add_painter

( pix_buf );

m->DrawInto

( &add_painter );

Rysowanie

zbioru Mandelbrota

Listing 1. zawiera kod metody DrawMandel-

brot . Jak widać główną rolę odgrywają pę-

tle for. Za ich pomocą przemieszczamy się

po kontrolce QFrame od zera do maksymal-

nej wartości na każdej z osi. Jak wcześniej

wspomniałem, musimy zamienić współrzę-

dne ekranowe na współrzędne rzeczywiste

dopasowane do obszaru, w jakim rysuje-

my nasz fraktal. Wykonują to dwie linie ko-

du – jedna dla współrzędnej X, druga dla

współrzędnej Y:

dx = ( a_max – a_min)

/ SCR_MAX_X * xx + a_min;

dy = ( b_max – b_min)

/ SCR_MAX_Y * yy + b_min;

Idea tych wyrażeń jest bardzo prosta, np. dla

wartości na osi X dzielimy szerokość prze-

działu rzeczywistego przez szerokość prze-

działu ekranowego, otrzymana wartość służy

Rysunek 3. Projektowanie interfejsu naszej aplikacji

czerwiec 2007

dla programistów

Programowanie C++/KDE/QT

nosimy wartość liczby z do kwadratu i sumu-

jemy z wynikiem otrzymanym z poprzedniej

iteracji. Następnie sprawdzamy, czy norma

z tej liczby przekroczyła czwórkę. Norma ozna-

cza, że traktujemy liczbę zespoloną jako wektor

i sprawdzamy, jak daleko oddaliła się od punk-

tu (0,0). Jeśli tak się stało, przerywamy działa-

nie pętli, a wartość zmiennej i zwracamy jako

wynik. Oczywiście może się zdarzyć, iż nigdy

nie uda się nam przekroczyć czwórki, ale wte-

dy zadziała ograniczenie na liczbę iteracji w pę-

tli for. Inaczej mówiąc, sprawdzamy, czy kolej-

ne sumy kwadratów nie przekraczają okręgu o

zadanym promieniu. I to wszystko, co wyko-

nuje funkcja fncMandel2 .

Dwie pozostałe funkcje jak fncMandel3

oraz fncMandel4 podnoszą wartość z do trze-

ciej potęgi lub do czwartej potęgi:

Jeśli tak się nie stało, dla poszczególnych skła-

dowych mnożymy liczbę iteracji przez pewną

stałą w zależności od naszych potrzeb. W przy-

kładzie powyżej na kolor największy wpływ

ma składowa zielona. Stosujemy także opera-

cję modulo 256, aby ostatecznie wartość każdej

składowej przyjęła wielkość z zakresu od 0 do

255. Świetne efekty da także następujący spo-

sób obliczania koloru:

ika jest zupełnie inna niż w przypadku zbio-

ru Mandelbrota . Decyduje o tym naturalnie

funkcja obliczająca czas ucieczki, treść tej

funkcji jest przedstawiona na Listingu 3.

Zmienna z na początku przyjmuje wartość

odpowiadającą współrzędnym rzeczywistym,

ale w czasie iteracji oprócz policzenia kwa-

dratu dodajemy także wartość c i to ona decy-

duje o tym, jak przedstawia się końcowy

obraz.

Sposób kolorowania nadal pozostaje taki

sam jak w poprzednim przypadku. Podob-

nie jak zmiany w formule obliczania cza-

su ucieczki. W przypadku funkcji fncJulia3

zmienna z jest obliczana w następujący spo-

sób:

r = ( (double)i / (double)max_iter);

*rc = (int)roundf(r * 256);

*gc = (int)roundf(r * 256);

*bc = (int)roundf(r * 256);

Sam fraktal będzie czarno-biały, ale te frag-

menty, dla których czas ucieczki jest najwięk-

szy, tzn. uciekały stosunkowo najwolniej z ok-

ręgu o zadanej wielkości, będą jasne. Co osta-

tecznie daje dość nieoczekiwany efekt.

t = z * z * z ;

z = t + c;

t = z * z * z;

Dla funkcji fncJulia4 formuła jest następująca:

Zbiór Julii

Wiemy już, w jaki sposób powstaje zbiór Man-

delbrota , zatem teraz czas na przedstawienie

sposobu, w jaki rysujemy zbiór Julii. Ogólny

sposób rysowania jest podobny jak w przy-

padku Mandelbrota , dlatego metoda DrawJu-

lia jest właściwie identyczna z metodą Draw-

Mandelbrot z Listingu 1. Przyjmuje ona dwa

dodatkowe argumenty, co potwierdza poniż-

sza linia kodu:

albo

t = z * z * z * z;

z = t + c;

t = z * z * z * z;

z = t + c;

I podobnie jak w pierwszej wersji tej funkcji

sprawdzamy, czy norma ze zmiennej z nadal

jest mniejsza niż cztery. Warto zmieniać to og-

raniczenie, aby sprawdzić jak to wpływa na

wygląd naszego fraktala. Można też próbować

tworzyć inne przekształcenia np. t = cos(z * z) .

Kolorowanie odbywa się za pomocą meto-

dy ColorCalc przyjmującej cztery argumenty:

Możemy naturalnie zmieniać też sposób do-

dawania zmiennej c .

Zapis pliku do widgetu

ImageArea i jego odświeżanie

Wbrew pozorom opisane powyżej czynności

są wystarczające do narysowania zbioru frak-

talnego, czasem warto też zapisać uzyska-

ny obraz do pliku. Dzięki API biblioteki QT

jest to bardzo łatwe do wykonania. Na począ-

tek upewniamy się, czy na pewno dysponu-

m->DrawJulia(0, -1.25, 0);

ColorCalc(int i, int *rc, int *gc,

int *bc);

Dwa dodatkowe argumenty oraz sposób ich

wykorzystania powodują, że otrzymana gra-

Pierwszy to numer iteracji, a trzy pozostałe to

wskaźniki na pozostałe składowe obliczane-

go koloru. Zakładamy, że funkcja będzie ge-

nerować wartości składowych w zakresie od

0 do 255. Sam proces kolorowania jest reali-

zowany za pomocą poniższej trywialnej in-

strukcji warunkowej:

if( i >= max_iter) {

*rc = 0; *gc = 0; *bc = 0;

}

else {

*rc = ( i * 128 ) % 256;

*gc = ( i * 64 ) % 256;

*bc = ( i * 32 ) % 256;

}

Jeśli zmienna i przekroczyła maksymalną licz-

bę iteracji, to przyjmujemy, że kolor będzie

czarny (może to być również kolor biały, czyli

poszczególne składowe przyjmą wartość 255).

Rysunek 4. KDevelop i uruchomiony program opisywany w artykule

www.lpmagazine.org

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: