Hlavní navigace

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

Pavel Tišnovský 25. 1. 2006

V dnešním pokračování seriálu o fraktálech používaných (nejenom) v počítačové grafice si řekneme, jaký existuje vztah mezi Mandelbrotovou množinou a Juliovými množinami. Relaci mezi těmito dvěma typy fraktálů si ukážeme i na demonstračním příkladě. Také si popíšeme některé vylepšené techniky vykreslování a obarvování Mandelbrotovy množiny.

Obsah

1. Vztah mezi Mandelbrotovou množinou a Juliovými množinami
2. Interaktivní změna parametrů Juliovy množiny
3. Výpočet barvy vnitřních pixelů na základě zadané funkce
4. Způsoby obarvování bodů ležících uvnitř Mandelbrotovy množiny
5. Obarvení vnitřních bodů na základě velikosti koncové hodnoty orbitu
6. Obarvení vnitřních bodů na základě podílu reálné a imaginární složky orbitu
7. Obarvení vnitřních bodů na základě úhlu koncové hodnoty orbitu
8. Literatura a odkazy na internetu
9. Obsah dalšího pokračování tohoto seriálu

1. Vztah mezi Mandelbrotovou množinou a Juliovými množinami

Jak jsme si již několikrát řekli v předchozích částech tohoto seriálu ([X], [XI], [XII], [XIII]), existuje pouze jedna Mandelbrotova množina, jelikož při jejím výpočtu je hodnota z0 vždy nastavena na (komplexní) nulu a mění se pouze hodnota c v závislosti na souřadnicích počítaného bodu v komplexní rovině. Juliových množin však existuje nekonečné množství, protože při jejich výpočtu je možné libovolně měnit hodnotu komplexní proměnné c. Každé hodnotě c přitom odpovídá určitá Juliova množina. Pozici (souřadnicím) počítaného body v komplexní rovině zde odpovídá hodnota z0. Také jsme si již řekli, že Juliovy množiny je možné rozdělit do třech kategorií podle toho, zda jejich vnitřní body tvoří (nenulovou) plochu, spojitou oblast s nulovým povrchem či zda se jedná o izolované body, tj. o Fatouův či Cantorův prach.

Při výpočtu bodů ležících uvnitř Juliových množin se využívá stejná podmínka pro divergenci posloupnosti z0…zn jako při výpočtu bodů ležících vně Mandelbrotovy množiny, tedy: |c|<=|zi| a současně |zi|>2. Z toho také vyplývá, že má smysl volit pouze takové hodnoty c, jejichž velikost je menší než 2. Jak bude ukázáno na dalších obrázcích, jsou Juliovy množiny středově symetrické (vzhledem k počátku komplexní roviny, tj. k hodnotě 0+0i), zatímco Mandelbrotova množina je symetrická okolo horizontální (reálné) osy komplexní roviny. Rozdílná symetričnost, kterou některé programy pro generování fraktálů s výhodou využívají k urychlení svého běhu, je způsobena odlišnými počátečními podmínkami při výpočtu – symetričnost je mimochodem zajištěna již při první iteraci.

Již Gaston Julia na počátku minulého století zjistil, že fakt, zda bude nějaká Juliova množina spojitá či nikoli, je možné zjistit iterací jejího kritického bodu, kterým je v tomto případě komplexní nula (tzv. orbit nuly). Avšak Mandelbrotova množina není ve své podstatě nic jiného než množina bodů, pro něž orbit nuly nediverguje. Z toho také vyplývá, že Mandelbrotova množina vlastně tvoří mapu všech Juliových množin – souřadnice bodů, které leží v Mandelbrotově množině, vedou při jejich dosazení do hodnoty c k vytvoření spojité Juliovy množiny. To však není zdaleka vše. Také je možné jednoduchým pokusem zjistit, že tvar takto vytvořené Juliovy množiny do značné míry odpovídá tvaru okraje Mandelbrotovy množiny v okolí bodu c. Kupodivu platí i částečně opačné tvrzení. Pokud si zobrazíme nějakou Juliovu množinu ve větším zvětšení (například stonásobném), bude Mandelbrotova množina v okolí bodu c a při stejném zvětšení obsahovat „kopii“ dané Juliovy množiny – to však platí pouze pro ty hodnoty c, které leží na hranici Mandelbrotovy množiny, v opačném případě je výsledkem jednobarevná plocha.

2. Interaktivní změna parametrů Juliovy množiny

Výše uvedené tvrzení, že Mandelbrotova množina je mapou tvarů všech Juliových množin, využijeme i v dnešním prvním demonstračním příkladu (zde je uložen zdrojový kód a HTML verze se zvýrazněnou syntaxí). Po spuštění tohoto příkladu se v levé polovině okna aplikace zobrazí Mandelbrotova množina, přičemž zobrazená plocha odpovídá v komplexní rovině čtverci s vrcholy -2–2i, -2+2i, 2–2i a 2+2i. V pravé polovině okna je zobrazena Juliova množina pokrývající stejnou část komplexní roviny. Počáteční parametry zobrazené Juliovy množiny, tj. komplexní hodnotu c, je možné měnit pohybem myši po obrazu Mandelbrotovy množiny. Po stlačení levého tlačítka myši se provede přepočet ze souřadnic kurzoru myši v okně na souřadnice bodu ležícího v komplexní rovině. Tyto souřadnice jsou následně použity jako komplexní hodnota c při překreslení Juliovy množiny. Všimněte si, že pokud je kurzor myši umístěn uvnitř Mandelbrotovy množiny (v černé oblasti), je příslušná Juliova množina souvislá, pokud je kurzor naopak vně Mandelbrotovy množiny, rozpadá se Juliova množina na Cantorův prach. Nejzajímavější tvary Juliových množin vznikají pro c ležící na hranici Mandelbrotovy množiny. Všechny tři varianty jsou zobrazeny na přiložených screenshotech (na obrázcích je kromě aktuální hodnoty c zobrazen i kurzor myši, který dané hodnotě odpovídá).

fractals14_1

Obrázek 1: Screenshot prvního demonstračního příkladu s hodnotou c nastavenou na 0+0i

Na pomalejších počítačích (< PII 450MHz) je vhodné zmenšit počet iterací, aby překreslování při (stále) stlačeném levém tlačítku myši bylo okamžité. Naopak na hodně rychlých počítačích může být vhodné změnou čtyř konstant na začátku programu zvětšit velikosti obou pixmap, například na hodnotu 512×512 pixelů. Při překladu je samozřejmě vhodné povolit maximum dostupných optimalizačních metod. Na následujících výpisech kódu si všimněte rozdílů ve způsobu výpočtu Mandelbrotovy a Juliovy množiny – samotná iterační smyčka je naprosto stejná, liší se pouze způsob nastavování komplexní hodnoty c a z0.

fractals14_2
Obrázek 2: Screenshot prvního demonstračního příkladu s hodnotou c nastavenou na 0+1i

Funkce provádějící výpočet a překreslení Mandelbrotovy množiny

//-----------------------------------------------------------------------------
// Funkce provádějící výpočet a překreslení Mandelbrotovy množiny
//-----------------------------------------------------------------------------
void recalcMandelbrot(pixmap *pix,              // pixmapa pro vykreslování
                      int    maxiter)           // maximální počet iterací
{
    double zx, zy, zx2, zy2;                    // složky komplexní proměnné Z a Z^2
    double cx, cy;                              // složky komplexní konstanty C
    double cx0, cy0;

    int    x, y;                                // počitadla sloupců a řádků v pixmapě
    int    iter;                                // počitadlo iterací
    unsigned char r, g, b;                      // barvové složky pixelu

    cy0=-2.0;
    for (y=0; y<pix->height; y++) {             // pro všechny řádky v pixmapě
        cx0=-2.0;
        for (x=0; x<pix->width; x++) {          // pro všechny pixely na řádku
            cx=cx0;                             // nastavit počáteční hodnotu Z(0)
            cy=cy0;
            zx=zy=0.0;                          // nastavení nulového orbitu
            for (iter=0; iter<maxiter; iter++) {// iterační smyčka
                zx2=zx*zx;                      // zkrácený výpočet druhé mocniny složek Z
                zy2=zy*zy;
                if (zx2+zy2>4.0) break;         // kontrola překročení meze divergence
                zy=2.0*zx*zy+cy;                // výpočet Z(n+1)
                zx=zx2-zy2+cx;
            }
            r=127+127.0*sin(iter/30.0);         // výpočet barvy pixelu
            g=iter*30;
            b=127-127.0*sin(iter/30.0);
            if (iter==maxiter)
                putpixel(pix, x, y, 0, 0, 0);   // body uvnitř množiny jsou černé
            else
                putpixel(pix, x, y, r, g, b);
            cx0+=(4.0)/pix->width;              // posun na další bod na řádku
        }
        cy0+=(4.0)/pix->height;                 // posun na další řádek
    }
} 

fractals14_3
Obrázek 3: Screenshot prvního demonstračního příkladu s hodnotou c nastavenou na -2+0i

Funkce provádějící výpočet a překreslení Juliovy množiny

//-----------------------------------------------------------------------------
// Funkce provádějící výpočet a překreslení Juliovy množiny
//-----------------------------------------------------------------------------
void recalcJulia(pixmap  *pix,                  // pixmapa pro vykreslování
                      int    maxiter)           // maximální počet iterací
                  double cx,                    // hodnota komplexní konstanty C
                  double cy)
{
    double zx, zy, zx2, zy2;                    // složky komplexní proměnné Z a Z^2
    double zx0, zy0;

    int    x, y;                                // počitadla sloupců a řádků v pixmapě
    int    iter;                                // počitadlo iterací
    unsigned char r, g, b;                      // barvové složky pixelu

    zy0=-2.0;
    for (y=0; y<pix->height; y++) {             // pro všechny řádky v pixmapě
        zx0=-2.0;
        for (x=0; x<pix->width; x++) {          // pro všechny pixely na řádku
            zx=zx0;                             // nastavit počáteční hodnotu Z(0)
            zy=zy0;
            for (iter=0; iter<maxiter; iter++) {// iterační smyčka
                zx2=zx*zx;                      // zkrácený výpočet druhé mocniny složek Z
                zy2=zy*zy;
                if (zx2+zy2>4.0) break;         // kontrola překročení meze divergence
                zy=2.0*zx*zy+cy;                // výpočet Z(n+1)
                zx=zx2-zy2+cx;
            }
            r=127+127.0*sin(iter/30.0);         // výpočet barvy pixelu
            g=iter*30;
            b=127-127.0*sin(iter/30.0);
            if (iter==maxiter)
                putpixel(pix, x, y, 0, 0, 0);   // body uvnitř množiny jsou černé
            else
                putpixel(pix, x, y, r, g, b);
            zx0+=(4.0)/pix->width;              // posun na další bod na řádku
        }
        zy0+=(4.0)/pix->height;                 // posun na další řádek
    }
} 

fractals14_4
Obrázek 4: Screenshot prvního demonstračního příkladu s hodnotou c nastavenou na 0,344+0,078i

fractals14_5
Obrázek 5: Screenshot prvního demonstračního příkladu s hodnotou c nastavenou na -0,609–0,531i

3. Výpočet barvy vnitřních pixelů na základě zadané funkce

V předchozím pokračování tohoto seriálu jsme si ukázali, že výpočet barvy pixelu ležícího vně Mandelbrotovy či Juliovy množiny je možné provést na základě mapování počtu iterací na barvovou paletu. Tradičně měla tato paleta rozsah 16 nebo 256 barev, což souviselo s technologií použitých grafických karet (EGA či VGA). V dnešní době grafických karet schopných zobrazit až 16 milionů barev (samozřejmě, že ne současně) však může mít barvová paleta prakticky libovolný rozsah. Dokonce je možné tradičně pojatou barvovou paletu (tj. ve skutečnosti vyhledávací tabulku) nahradit spojitou či nespojitou funkcí, pro každou barvovou složku je možné zvolit odlišnou funkci. Tato možnost je ukázána na dnešním druhém demonstračním příkladu (zde je zdrojový tvar tohoto příkladu, popř. zde HTML verze se zvýrazněnou syntaxí). Po překladu a spuštění tohoto příkladu je možné pomocí kláves [0][9] měnit funkce pro výpočet barev pixelů na základě dosažené iterace. Dále je možné klávesami [R], [G] a [B] povolovat či zakazovat jednotlivé barvové kanály. Další ovládání této demonstrační aplikace (například posun fraktálu pomocí kurzorových šipek a změna měřítka klávesami [PageUp] a [PageDown]) jsou stejné, jako v příkladech uvedených v předchozí části tohoto seriálu.

fractals14_6
Obrázek 6: Screenshot druhého demonstračního příkladu

Část kódu, který provádí výpočet barev jednotlivých pixelů, vypadá následovně:

    switch (palette) {                  // vykresleni pixelu s vybranou barvovou paletou
        case 0:
            r=iter<<1;
            g=iter<<1;
            b=iter<<1;
            break;
        case 1:
            r=iter*10.0;
            g=127+127.0*sin(iter/30.0);
            b=127+127.0*sin(iter/10.0);
            break;
        case 2:
            r=127+127.0*sin(iter/30.0);
            g=iter*10;
            b=127+127.0*sin(iter/10.0);
            break;
        case 3:
            r=127+127.0*sin(iter/30.0);
            g=127+127.0*sin(iter/10.0);
            b=iter*10.0;
            break;
        case 4:
            r=127+127.0*sin(iter/30.0);
            g=iter*20;
            b=127+127.0*sin(iter/10.0);
            break;
        case 5:
            r=iter*5;
            g=255-iter*7;
            b=iter*9;
            break;
        case 6:
            r=127+127.0*sin(iter/30.0);
            g=iter*20;
            b=127-127.0*sin(iter/30.0);
            break;
        case 7:
            r=127-127.0*sin(iter/30.0);
            g=iter*10;
            b=127+127.0*sin(iter/10.0);
            break;
        case 8:
            r=127+127.0*sin(iter/30.0);
            g=127-127.0*sin(iter/10.0);
            b=iter*10;
            break;
        case 9:
            r=127-127.0*sin(iter/10.0);
            g=iter*20;
            b=127+127.0*sin(iter/20.0);
            break;
    } 

fractals14_7
Obrázek 7: Další screenshot druhého demonstračního příkladu

4. Způsoby obarvování bodů ležících uvnitř Mandelbrotovy množiny

Ve všech předchozích příkladech byly body (resp. pixely), které ležely uvnitř Mandelbrotovy množiny, obarveny stejnou barvou. Výsledkem však byla poměrně nudná jednobarevná plocha uprostřed zobrazeného celkového pohledu na množinu. S využitím dále uvedených funkcí je možné i uvnitř Mandelbrotovy množiny zobrazit struktury, protože po provedených iteracích je možné vzít do úvahy aktuální polohu výsledného orbitu. Vzhledem k tomu, že hodnota orbitu je komplexní číslo (zn), je možné s tímto číslem provádět mnoho operací, přičemž výsledky těchto operací mohou sloužit k výpočtu barev pixelů ležících uvnitř Mandelbrotovy množiny.

5. Obarvení vnitřních bodů na základě velikosti koncové hodnoty orbitu

Po dosažení maximálního počtu iterací je právě zpracovávaný bod považován za součást Mandelbrotovy množiny. Pokud zjistíme velikost poslední vypočtené hodnoty zn, tj. vypočteme |zn|, je možné tuto hodnotu použít pro výpočet barvy daného pixelu. Zde popisovanou metodu je vhodné použít zejména při prohlížení některého z „kruhů“, které přiléhají k hlavnímu kardioidu. Celý výpočet, který se samozřejmě provádí až po všech průchodech iterační smyčkou, může vypadat například následovně:

if (iter==maxiter)                      // bod leží uvnitř množiny
    r=g=b=200.0*sqrt(zx*zx+zy*zy);
else {                                  // bod leží mimo množinu
    ...
} 

fra
Obrázek 8: Fraktál s obarvenými vnitřními body na základě velikosti koncové hodnoty orbitu

6. Obarvení vnitřních bodů na základě podílu reálné a imaginární složky orbitu

Pokud se po dokončení všech iterací vypočítá podíl reálné a imaginární složky hodnoty zn, vynikne vnitřní struktura Mandelbrotovy množiny zejména na jejích okrajích. Způsob výpočtu je patrný z následujícího úryvku kódu, fraktál vypočtený touto metodou je zobrazen na devátém obrázku.

if (iter==maxiter) {                    // bod leží uvnitř množiny
    if (zy==0) zy=1.0;                  // zabránit dělení nulou
    r=35.0*(zx/zy);
    g=25.0*(zx/zy);
    b=10.0*(zx/zy);
}
else {                                  // bod leží mimo množinu
    ...
} 

fractals14_9
Obrázek 9: Fraktál s obarvenými vnitřními body na základě podílu reálné a imaginární složky orbitu

7. Obarvení vnitřních bodů na základě úhlu koncové hodnoty orbitu

Třetí možností, jak využít známou hodnotu orbitu zn, je výpočet úhlu tohoto komplexního čísla. V dále uvedeném kódu je použita céčkovská funkce atan2(), která akceptuje dva parametry, přičemž je zajištěno, že nedojde k dělení nulou. Fraktál vypočtený touto metodou je zobrazen na desátém obrázku.

if (iter==maxiter) {                    // bod leží uvnitř množiny
    r=g=b=atan2(zx,zy)*64;
else {                                  // bod leží mimo množinu
    ...
} 

fractals14_a
Obrázek 10: Fraktál s obarvenými vnitřními body na základě úhlu koncové hodnoty orbitu

8. Literatura a odkazy na internetu

Literatura:

  1. Stevens Roger: „Fractal Programming in C“,
    M&T Publishing, 1989, ISBN 1–55851–038–9
  2. Peigen, H.O., Richter, P.H.: „The Beauty of Fractals“,
    Springer-Verlag, 1985
  3. Kettler Neal: „What are fractals?“

Odkazy na internetu

  1. Oficiální stránky programu FractInt:
    http://www.frac­tint.org/
  2. Stránky programu XaoS:
    http://xaos.sou­rceforge.net/en­glish.php
  3. Starší (a IMHO hezčí) verze stránek programu XaoS:
    http://xaos.sou­rceforge.net/blac­k/index.php
  4. Mandelbrot Explorer (internetový prohlížeč Mandelbrotovy množiny):
    http://www.sof­tlab.ece.ntua­.gr/miscellane­ous/mandel/man­del.html
  5. The Mandelbrot Set (Javovský applet):
    http://www.min­dspring.com/~chro­ma/mandelbrot­.html
  6. Sustainability through the Dynamics of Strategic Dilemmas (článek):
    http://laetusin­praesens.org/doc­s00s/cardrep.php
  7. Interior Sketchbook Diary (článek):
    http://www.li­nas.org/art-gallery/mandel/man­del.html

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

V dalším pokračování tohoto seriálu si řekneme, jakým způsobem je možné obarvit body (pixely), které leží vně Mandelbrotovy množiny. Prozatím jsme si ukázali pouze techniku obarvení na základě počtu proběhlých iterací, možné jsou však i jiné způsoby.

Našli jste v článku chybu?

14. 2. 2006 8:16

To je dobry napad, melo me to napadnout samotneho :-(. O kousek nize v diskusi jsou ty odkazy uvedeny. Jsou primo brany z RedSysu, proto ty divne identifikatory pripojene za puvodni nazev :-) Vsechny prilohy (ze vsech clanku, nejenom o fraktalech) jsou totiz ulozeny na jednom miste, takze neexistuje hierarchicke pojmenovani...

14. 2. 2006 8:12

Odkazy na zdrojové kódy demonstračních příkazů nebyly v původním článku uvedeny (resp. zmizely při převodu do redakčního systému :-), proto jsou odkazy uvedeny zde:

Zdrojový kód prvního demonstračního příkladu:
http://i.iinfo.cz/urs-att/fractals14_1-113776941386523.c

Zdrojový kód prvního demonstračního příkladu převedený do HTML se zvýrazněním syntaxe:
http://i.iinfo.cz/urs-att/fractals14_1-113776944763247.html

Zdrojový kód druhého demonstračního příkladu:
Vitalia.cz: Mondelez stahuje rizikovou čokoládu Milka

Mondelez stahuje rizikovou čokoládu Milka

Vitalia.cz: Manželka je bio, ale na sex moc není

Manželka je bio, ale na sex moc není

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Podnikatel.cz: Hledáte investora? Neunáhlete se

Hledáte investora? Neunáhlete se

Podnikatel.cz: Alza.cz má StreetShop. Mall.cz více výdejních míst

Alza.cz má StreetShop. Mall.cz více výdejních míst

DigiZone.cz: Rádio Šlágr má licenci pro digi vysílání

Rádio Šlágr má licenci pro digi vysílání

Lupa.cz: Avast po spojení s AVG propustí 700 lidí

Avast po spojení s AVG propustí 700 lidí

Vitalia.cz: Dáte si jahody s plísní?

Dáte si jahody s plísní?

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

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

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

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

Vitalia.cz: Baletky propagují zdravotní superpostel

Baletky propagují zdravotní superpostel

120na80.cz: Boreliózu nelze žádným testem prokázat

Boreliózu nelze žádným testem prokázat

Podnikatel.cz: Babiše přesvědčila 89letá podnikatelka?!

Babiše přesvědčila 89letá podnikatelka?!

Měšec.cz: Zdravotní a sociální pojištění 2017: Připlatíte

Zdravotní a sociální pojištění 2017: Připlatíte

Lupa.cz: Proč firmy málo chrání data? Chovají se logicky

Proč firmy málo chrání data? Chovají se logicky

Podnikatel.cz: Podnikatelům dorazí varování od BSA

Podnikatelům dorazí varování od BSA

120na80.cz: Horní cesty dýchací. Zkuste fytofarmaka

Horní cesty dýchací. Zkuste fytofarmaka

120na80.cz: Rakovina oka. Jak ji poznáte?

Rakovina oka. Jak ji poznáte?

Lupa.cz: Teletext je „internetem hipsterů“

Teletext je „internetem hipsterů“

Podnikatel.cz: Na poslední chvíli šokuje vyjímkami v EET

Na poslední chvíli šokuje vyjímkami v EET