Hlavní navigace

Fraktály v počítačové grafice XII

Pavel Tišnovský

V dnešním pokračování seriálu o fraktálech používaných v počítačové grafice si podrobně popíšeme historii, základní princip a postupy použité při vykreslování patrně nejznámějšího fraktálu v komplexní rovině - Mandelbrotovy množiny. V navazujících částech bude také popsán postup při vytváření zajímavých animací (průletu) obrázkem tohoto fraktálu.

Obsah

1. Stručná historie Mandelbrotovy množiny
2. Kdo první vykreslil Mandelbrotovu množinu?
3. Mandelbrotova množina jako dynamický systém
4. Test na divergenci orbitu
5. Výpočet bodů ležících v Mandelbrotově množině
6. Obsah dalšího pokračování tohoto seriálu

1. Stručná historie Mandelbrotovy množiny

„[I have] had the privilege to enrich Fatou-Julia's theory by adding a new part, by suggesting what Douady and Hubbard (1982) have called "Mandelbrot set or M-set“ … I have proceeded in a way loathed by theoreticians… I have wandered, contemplated, dissected, with the astonishing equivalent of a microscope that the computer is… Unforgettable images, even with the primitive tools of 1980… I did this work in 1979–1980…"
Benoit B. Mandelbrot

Mandelbrotova množina byla, podobně jako Juliovy množiny, objevena při analýze některých zdánlivě jednoduchých dynamických systémů se zpětnou vazbou. Analýza dynamických systémů se zabývá otázkou budoucího stavu systému, pokud iterativně provádíme výpočet s tou samou funkcí (resp. skupinou funkcí). Některé výsledky z analytického i numerického výzkumu těchto systémů byly publikovány již počátkem minulého století (samozřejmě, že se bez pomoci počítačů jednalo o poměrně nezáživné matematické stati). Těmito dynamickými systémy se zabývali především matematikové Gaston Julia (1893–1978) a Pierre Fatou (1878–1929), o kterých jsme si pověděli v předcházejících dílech tohoto seriálu. Na jejich práce, které souvisely především s Juliovými množinami (tak však byly nazvány až o více než půlstoletí později) navázal v sedmdesátých letech minulého století matematik Benoit B. Mandelbrot.

Jako součást své výzkumné práce využil Benoit Mandelbrot možností tehdy dostupné počítačové grafiky – to ovšem bylo na matematika dosti nezvyklé. V tomto období byly v pracovní skupině Mandelbrota a prakticky ve stejném čase i dvojicí Brookse a Matelskiho vytvořeny první obrazy fraktálu dnes nazývaného Mandelbrotova množina. První rastrové obrázky byly, vzhledem k dané době a omezeným možnostem použité výpočetní techniky, pouze černobílé, vzbudily však velký zájem jak mezi odbornou, tak i laickou veřejností. Z matematického pohledu jsou samozřejmě korektní pouze černobílé (resp. monochromatické) obrázky, protože se rozlišují pouze dvě možnosti: divergence či konvergence posloupnosti hodnot zn. V počítačové grafice se posléze došlo k barevnému „vylepšování“ obrázků, při kterém jsou barvy pixelům přiřazovány například podle počtu iterací, vzdálenosti čísla zn od počátku atd.

fractals12_1

Obrázek 1: Tímto způsobem zobrazovalo Mandelbrotovu množinu mnoho starších aplikací pro DOS a grafickou kartu VGA

2. Kdo první vykreslil Mandelbrotovu množinu?

The resulting revival makes the properties of iterations essential for the theory of fractals. The fact that the Fatou-Julia findings did not develop to become the source of this theory suggests that even classical analysis needs intuition to develop, and can be helped by the computer.
Benoit B. Mandelbrot

Na tuto zdánlivě jednoduchou otázku existuje překvapivě několik odpovědí. Mandelbrot vytvořil první obrázky Mandelbrotovy množiny v roce 1979. V roce 1981 byl na matematické konferenci prezentován článek od Brookse a Matelskiho, který také obsahoval obrázky množiny později pojmenované po Mandelbrotovi. Problém je, že tento článek i se všemi ilustracemi byl vytvořen již v roce 1978, tj. „těsně“ před Mandelbrotem, takže v tomto případě prvenství jasně připadá Brooksovi a Matelskimu.

Na druhou stranu je jasné, že Mandelbrot „svoji“ množinu studoval a také popsal (v přesné kanonické podobě, jako iteraci komplexního polynomu) mnohem důkladněji než pánové Brooks a Matelski, což také vedlo Johna Hubbarda k tomu, že v roce 1982 tuto množinu pojmenoval po Mandelbrotovi – ve skutečnosti dokonce Hubbard pravděpodobně o málo známé práci Brookse a Matelskiho nevěděl. Jak je z této příhody vidět, historie se již několikrát opakovala v tom, že jeden objev v prakticky stejnou dobu udělá více lidí. V tomto případě se sešlo více skutečností: hlubší zájem o iterativní procesy a také prudký rozvoj počítačů a počítačové grafiky.

Další verze o vzniku Mandelbrotovy množiny říká, že první obrázek byl vytvořen počítačovým odborníkem, který byl přítelem jak Mandelbrota, tak i Brookse a Matelskiho – to je do jisté míry pravděpodobné, protože v té době bylo počítačových odborníků poměrně málo a veškeré práce se prováděly na sálových počítačích dávkovým způsobem. Mandelbrot přitom v té době pracoval pro IBM a ta zase poskytovala výpočetní prostředky mnoha univerzitám, takže mezi počítačovými odborníky od IBM a vědci vznikaly poměrně rozsáhlé „družby“.

Aby se historie Mandelbrotovy množiny ještě více zamotala, byla poměrně nedávno objevena starodávná práce v dnešní době prakticky už neznámého všestranného umělce a vědce jménem Udo von Aachen. Tento nedoceněný vědec, který je v celoevropském měřítku srovnatelný snad pouze s Járou Cimrmanem, počítal konvergenci či divergenci bodů v Mandelbrotově množině ručně, pouze za pomoci papíru a husího brku. Takto prováděné výpočty samozřejmě trvaly několik let a „rozlišení“ vytvořeného obrazu Mandelbrotovy množiny bylo velmi nízké. Jak bylo ve středověku zvykem, nesměly se některé práce odporující tehdy platné doktríně přímo zveřejňovat, proto byl obrázek Mandelbrotovy množiny zakomponován do rozsáhlejší rytiny jako její nenápadná součást. Toto důležité poselství z minulosti rozluštili vědci až dnes s využitím moderní výpočetní techniky. Bližší informace o tomto důležitém objevu jsou uvedeny na stránce: http://www.ra­ygirvan.co.uk/a­poth/udo.htm.

fractals12_2

Obrázek 2: Detail Mandelbrotovy množiny

3. Mandelbrotova množina jako dynamický systém

Mandelbrotova množina je vytvořena pomocí jednoduchého dynamického systému, který je založen na iteraci funkce komplexní paraboly:

zn+1=zn2+c

kde proměnné z a c leží v komplexní rovině.

fractals12_3

Obrázek 3: Iterační výpočet bodů ležících v Mandelbrotově množině

V průběhu výpočtu se hodnota z postupně mění, zatímco hodnota c zůstává konstantní – tato se mění pouze při přesunu výpočtu na nový bod. Celý iterační proces začíná s určitou startovní hodnotou z0, takže systém postupně generuje sekvenci hodnot zk, které nazýváme orbit. Postup si ukážeme na prvních čtyřech iteracích:

z1=(z0)2+c
z2=((z0)2+c)+c
z3=(((z0)2+c)­2+c)2+c
z4=((((z0)2+c­)2+c)2+c)2+c
 

Při práci se systémem popsaným v předchozím textu nás zajímá, zda pro danou startovní hodnotu z0 a konstantu c posloupnost zk konverguje či diverguje. Ukazuje se, že pro některé počáteční hodnoty nastává také oscilace – hodnoty zk se opakují s určitou periodou, to znamená, že platí rovnost zk=zk+i, kde i je perioda oscilace. Bližším studiem vlivu počátečních podmínek na budoucí stav systému se zabýval právě Benoit B. Mandelbrot a před ním i Fatou.

Mandelbrot se omezil na případ, kdy počáteční hodnota z0 je nulová a pro každý počítaný bod se mění pouze konstanta c. Iterativním výpočtem vzniknou pouze orbity nuly. Orbity nuly lze podle jejich vlastností rozdělit do dvou kategorií:

  1. Pro některé hodnoty c je orbit konečný, tzn. všechny hodnoty zk jsou konečné. Do této kategorie spadají také hodnoty, které oscilují.
  2. Pro další hodnoty c je orbit nekonečný, tzn. po určité době rostou hodnoty zk nade všechny meze.

Mandelbrotova množina je poté definována jako množina všech komplexních čísel c, které produkují konečný orbit nuly, tedy:

fractals12_4

kde Pcn(0) znamená hodnotu zn pro danou konstantu c a z0=0. Na dalším obrázku je ukázán příklad pro dvě počáteční hodnoty c (resp. z0, protože po první iteraci je c rovno z0). První orbit je konečný, zatímco hodnoty druhého orbitu po několika prvních iteracích rostou nade všechny meze.

fractals12_5

Obrázek 5: Konvergence a divergence dvou různých hodnot z0

Pro porovnání definice Mandelbrotovy množiny a Juliových množin uvádím ještě definici Juliových množin (ta již byla vysvětlena v desátém pokračování tohoto seriálu):

fractals12_6

4. Test na divergenci orbitu

Abychom mohli úspěšně vykreslit hrubý obrázek Mandelbrotovy množiny, musíme zjistit, které body do této množiny zcela jistě nepatří. Jak již víme z předchozího textu, jedná se o ty body, jejichž orbit míří na Riemanově sféře (což je, zjednodušeně řečeno, komplexní rovina pouze s jedním nekonečnem) k nekonečnu. Je však možné jednoduše zjistit, že nějaký orbit míří k nekonečnu v konečném čase, resp. v konečném počtu kroků? Ukazuje se, že pro některé body je možné vytvořit jednoduchý test, jehož princip je ukázán na následujících řádcích.

Při testu na nekonečnost orbitu použijeme důkazu, že pro |c|<=|z| a |z|>2 posloupnost diverguje. Využije se přitom trojúhelníkové nerovnosti pro komplexní čísla:

|a+b| >= |a|-|b|,

kde za obecnou hodnotu a dosadíme z×z a za obecnou hodnotu b komplexní konstantu c:

|z×z+c| >= |z×z|-|c| = (|z|)2-|c|

Je nutné najít minimální hodnotu |z|, při jejímž překročení je |z×z+c|>|z|. Nazvěme tuto hodnotu r. Potom r×r-|c|=r resp. r×r-r-|c|=0 a dále z řešení kvadratické rovnice vyplývá:

r=(1+(1+4|c|)­1/2)/2.

Známe tedy hodnotu r. Jestliže je velikost |z| větší než r, systém diverguje. Pokud iterace začíná s hodnotou z=0, je po první iteraci z=c. V předchozích vzorcích můžeme r nahradit |c| a dostaneme vztah:

|c|×|c|-2|c| = 0 tedy |c|=2 resp. |z|=2 protože z=c

Posloupnost tedy pro |z|>2 skutečně diverguje. V průběhu iteračního výpočtu tedy stačí testovat, zda je velikost |zk|>2. Podmínka pro divergenci posloupnosti mimo jiné také znamená, že všechny body Mandelbrotovy množiny leží v komplexní rovině uvnitř kružnice o poloměru 2. Je to dáno tím, že pro |c|>2 je po první iteraci také |z|>2 a z podmínek uvedených výše vyplývá, že posloupnost diverguje.

fractals12_7

Obrázek 7: Další detail Mandelbrotovy množiny

5. Výpočet bodů ležících v Mandelbrotově množině

Z předchozího textu vyplývá, že všechny body Mandelbrotovy množiny mají absolutní hodnotu menší než 2. Také víme, že jestliže v průběhu iteračního procesu absolutní hodnota z překročí 2, posloupnost diverguje a počítaný bod tudíž neleží v Mandelbrotově množině. Opačný test, tj. test na konvergenci posloupnosti, nelze přímo provést. Používá se proto metoda, při které se zvolí dostatečně velký počet iterací, přičemž v každém kroku je testováno, zda absolutní hodnota z nepřekročí 2. Pokud tato možnost nastane, bod uvnitř Mandelbrotovy množiny zcela jistě neleží. Pokud proběhne výpočet všech iterací, aniž by absolutní hodnota z překročila 2, je počítaný bod prohlášen za prvek Mandelbrotovy množiny. Tato metoda je sice nepřesná, ale lze ji v podstatě libovolně zpřesňovat zvyšováním maximálního počtu iterací. Hodnota 2 použitá v testu se v literatuře nazývá bailout.

Postup při výpočtu bodů ležících v Mandelbrotově množině lze zapsat pomocí jednoduchého algoritmu. Vstupem algoritmu je komplexní číslo c a konstanta určující maximální počet iterací MaxIter:

  1. nastav iter:=0
  2. nastav z:=0
  3. pokud iter<MaxIter prováděj smyčku:
  4.     nastav z:=z2+c
  5.     jestliže |z|>2 bod neleží v Mandelbrotově množině; konec
  6.     nastav iter:=iter+1
  7. konec smyčky
  8. bod leží uvnitř Mandelbrotovy množiny; konec

Tento algoritmus lze velmi jednoduše implementovat s tím, že proměnné z a c jsou komplexní čísla, tj. nabývají komplexních hodnot. Protože ve většině programovacích jazyků nejsou komplexní čísla zavedena jako základní datové typy, pomůžeme si tím, že každé komplexní číslo reprezentujeme jeho reálnou a imaginární složkou – prakticky stejným způsobem jsme ostatně postupovali při vykreslování Mandelbrotovy množiny. Proto například původní komplexní proměnná z bude reprezentována dvojicí reálných proměnných zx a zy a komplexní proměnná c bude reprezentována dvojicí cx a cy.

Absolutní hodnotu |z| lze rozepsat jako sqrt(zxzx+zyzy), kde sqrt() je matematická funkce provádějící druhou odmocninu. V reálných programech není použit přímo výpočet absolutní hodnoty, protože vyčíslení odmocniny je časově velmi náročné. Poměrně složitou podmínku ve tvaru sqrt(zxzx+zyzy)>2 lze na obou stranách umocnit (obě strany jsou vždy kladné) a použít novou podmínku, kde není zapotřebí provádět časově náročný výpočet odmocnin. Výsledný tvar podmínky má tvar: zxzx+zyzy>4. Výraz z:=z2+c, jenž je zapsán pomocí dvou komplexních proměnných z a c, lze rozepsat na jeho reálnou a imaginární část:

zx'=zxzx-zyzy+cx
zy'=2zxzy+cy 

Kde zx, zy, cx, cy, zx' a zy' jsou proměnné nabývající reálných hodnot. Aby nebylo nutné používat dvou nových proměnných zx' a zy', použijí se již předpočítané mocniny reálné a imaginární složky z (podle reakcí čtenářů pod předchozími díly tohoto seriálu se však ukazuje, že se v některých případech nemusí jednat o ideální řešení). Také je vhodné prohodit oba výrazy, aby nebylo nutné zavádět nové pomocné proměnné:

zx2=zxzx
zy2=zy
zy
zy=2zxzy+cy
zx=zx2-zy2+cx 

Hodnoty v proměnných zx2 a zy2 budou použity při testu zx2+zy2>4. Nyní již můžeme celý algoritmus pro výpočet bodů Mandelbrotovy množiny přepsat do konkrétního programovacího jazyka. Jako příklad je uveden zápis v programovacím jazyce C:

/*
 * Parametrem této funkce je komplexní číslo C, pro které
 * probíhá test.
 */
int MandelbrotTest(double cx, double cy)
{
    double      zx,zy,zx2,zy2,cx,cy;    // komplexní proměnná Z
    int         iter;                   // počet iterací

    zx=0;                               // vynulovat komplexní proměnnou C
    zy=0;

    iter=0;                             // nastavit počitadlo iterací

    do {                                // iterační smyčka
        zx2=zx*zx;                      // zx^2
        zy2=zy*zy;                      // zy^2
        zy=2.0*zx*zy+cy;
        zx=zx2-zy2+cx;                  // z:=z^2+c
        iter++;                         // zvýšit hodnotu počitadla iterací
    } while (iter<maxiter && (zx2+zy2)<4.0);// test na počet iterací a bailout

    if (iter==maxiter)                  // bod leží uvnitř Mandelbrotovy množiny
        return LEZI_UVNITR;
    else                                // bod leží vně Mandelbrotovy množiny
        return LEZI_VNE;
} 

Výše uvedený algoritmus lze přímo použít pro vykreslení Mandelbrotovy množiny. Výsledek je vidět na přiloženém obrázku. Bílé pixely reprezentují body v komplexní rovině, jež neleží v Mandelbrotově množině, černé pixely naopak reprezentují body v Mandelbrotově množině ležící. Symetrie Mandelbrotovy množiny okolo reálné osy je způsobena tím, že změna znaménka cy způsobí pouze změnu znaménka proměnné zy, nikoliv zx. Na výpočet absolutní hodnoty |z| nemají znaménka reálné a imaginární složky žádný vliv. Funkce MandelbrotTest() je volaná pro každý počítaný (resp. zobrazovaný) pixel. Při větších velikostech pixelů může dojít ke znatelnému prodloužení výpočtu z důvodu častého volání této funkce. Proto je výhodnější vložit tělo funkce MandelbrotTest() přímo do hlavní výpočetní smyčky programu, kde se provádí nastavení jednotlivých pixelů.

fractals12_8

Obrázek 8: Celkový pohled na Mandelbrotovu množinu

6. Obsah dalšího pokračování tohoto seriálu

V dalším pokračování tohoto seriálu si ukážeme demonstrační příklady pro vykreslování Mandelbrotovy množiny. Také si řekneme, jakým způsobem je možné generovat animaci „průletu“ tímto fraktálem.

Našli jste v článku chybu?

11. 1. 2006 13:42

Sorry, chybka pri rucnim prevodu do HTML :-) Samozrejme, oscilace nastava pri rovnosti tech hodnot, pricitani prirozeneho cisla ke komplexni hodnote z_k nema smysl.

15. 9. 2006 14:59

BOby (neregistrovaný)
Je mandelbrot symetrický (po ose x)?

Jo a v Xaosovi a kfract se osa y zvyšuje směrem dolů. Je to chyba, nebo je to schválně?

Vitalia.cz: 7 originálních adventních kalendářů pro mlsné

7 originálních adventních kalendářů pro mlsné

Root.cz: Nová třída SD karet A1 s vysokým výkonem

Nová třída SD karet A1 s vysokým výkonem

DigiZone.cz: SES zajistí HD pro M7 Group

SES zajistí HD pro M7 Group

120na80.cz: Rovnátka, která nejsou vidět

Rovnátka, která nejsou vidět

DigiZone.cz: R2B2 a Hybrid uzavřely partnerství

R2B2 a Hybrid uzavřely partnerství

Lupa.cz: Insolvenční řízení kvůli cookies? Vítejte v ČR

Insolvenční řízení kvůli cookies? Vítejte v ČR

Podnikatel.cz: K EET. Štamgast už peníze na stole nenechá

K EET. Štamgast už peníze na stole nenechá

Podnikatel.cz: Vládu obejde, kvůli EET rovnou do sněmovny

Vládu obejde, kvůli EET rovnou do sněmovny

Podnikatel.cz: Chtějte údaje k dani z nemovitostí do mailu

Chtějte údaje k dani z nemovitostí do mailu

Lupa.cz: Co se dá měřit přes Internet věcí

Co se dá měřit přes Internet věcí

Vitalia.cz: Test na HIV je zdarma i za pět set

Test na HIV je zdarma i za pět set

DigiZone.cz: Ohrozí Freedom TV přechodové sítě?

Ohrozí Freedom TV přechodové sítě?

Vitalia.cz: Nejlepší obranou při nachlazení je útok

Nejlepší obranou při nachlazení je útok

Lupa.cz: Kdo pochopí vtip, může jít do ČT vyvíjet weby

Kdo pochopí vtip, může jít do ČT vyvíjet weby

120na80.cz: Co všechno ovlivňuje ženskou plodnost?

Co všechno ovlivňuje ženskou plodnost?

120na80.cz: 5 nejčastějších mýtů o kondomech

5 nejčastějších mýtů o kondomech

DigiZone.cz: Česká televize mění schéma ČT :D

Česká televize mění schéma ČT :D

Měšec.cz: Exekuční poradna: ptejte se online

Exekuční poradna: ptejte se online

Podnikatel.cz: E-Ježíšek si zařádí: nákupy od 2 do 5 tisíc

E-Ježíšek si zařádí: nákupy od 2 do 5 tisíc

Vitalia.cz: Pamlsková vyhláška bude platit jen na základkách

Pamlsková vyhláška bude platit jen na základkách