Hlavní navigace

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

Pavel Tišnovský 18. 1. 2006

V dnešním pokračování seriálu o fraktálech používaných (nejenom) v počítačové grafice si ukážeme několik demonstračních příkladů sloužících pro vykreslení známé Mandelbrotovy množiny. Také si řekneme, jakým způsobem je možné zobrazit detaily Mandelbrotovy množiny.

Obsah

1. Zobrazení celé Mandelbrotovy množiny
2. Obarvení Mandelbrotovy množiny
3. Ortodoxní pohled na Mandelbrotovu množinu
4. Vykreslení detailů Mandelbrotovy množiny
5. Literatura a odkazy na Internetu
6. Obsah dalšího pokračování tohoto seriálu

1. Zobrazení celé Mandelbrotovy množiny

Mandelbrotovu množinu lze vykreslit velmi jednoduše pomocí vztahů uvedených v předchozí části tohoto seriálu. Stačí provést výpočet mapování pozice pixelu zobrazeného na obrazovce na hodnotu komplexní konstanty c (tato hodnota je však konstantní jen v době výpočtu jednoho pixelu, při změně pozice pixelu je samozřejmě c nastaveno na odlišnou hodnotu). Pro každý pixel se tedy vypočte, zda jemu příslušející konstanta c způsobí růst orbitu nuly nade všechny meze, tj. zda limita |zn| diverguje. Pokud tomu tak je, pixel neleží uvnitř Mandelbrotovy množiny, v opačném případě v ní leží. V nejjednodušším případě se pixely ležící uvnitř Mandelbrotovy množiny vybarví jednou barvou a pixely ležící vně barvou odlišnou. Tento způsob obarvování pixelů je ukázán i na demonstračním příkladu 13.1. Pixely, které se nachází vně Mandelbrotovy množiny, jsou obarveny černě (je jim ponechána původní hodnota původně černé pixmapy) a pixely, které se nachází uvnitř Mandelbrotovy množiny, jsou obarveny barvou bílou. Zdrojový kód prvního demonstračního příkladu je uložen zde, k dispozici je i verze se zvýrazněním syntaxe. Mapování pixelů je nastaveno tak, aby se do rastrové mřížky o rozměrech 512×512 pixelů mapovala část komplexní roviny ležící mezi rohovými body -2–2i, -2+2i, 2–2i a 2+2i. Ovládání demonstračního příkladu 13.1:

Klávesa Význam
, snížení počtu iterací o jednotku
. zvýšení počtu iterací o jednotku
< snížení počtu iterací o deset jednotek
> zvýšení počtu iterací o deset jednotek
S uložení rastrového obrázku s fraktálem do externího souboru typu TGA
Q ukončení tohoto demonstračního příkladu
Esc má stejný význam jako klávesa Q
fractals13_1

Obrázek 1: Screenshot prvního demonstračního příkladu se zobrazenou Mandelbrotovou množinou

Funkce, která provádí výpočet bodů ležících uvnitř Mandelbrotovy množiny, má v demonstračním příkladu 13.1 tvar:

//-----------------------------------------------------------------------------
// Překreslení Mandelbrotovy množiny.
// Funkce použitá v demonstračním příkladu 13.1
//-----------------------------------------------------------------------------
void recalcMandelbrot1(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 cx0, cy0;
    double cx, cy;                              // složky komplexní konstanty C
    int    x, y;                                // počitadlo sloupců a řádků v pixmapě
    int    iter;                                // počitadlo iterací
    unsigned char color;                        // barva pixelu

    cy0=MINY;
    for (y=0; y<pix->height; y++) {             // pro všechny řádky v pixmapě
        cx0=MINX;
        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;                          // bude se počítat orbit nuly
            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;
            }
            color=(iter==maxiter) ? 255 : 0;    // vypočítat barvu pixelu
            putpixel(pix, x, y, color, color, color); // vybarvit pixel
            cx0+=(MAXX-MINX)/pix->width;        // posun na další bod na řádku
        }
        cy0+=(MAXY-MINY)/pix->height;           // posun na další řádek
    }
} 

2. Obarvení Mandelbrotovy množiny

Na první pohled poměrně nezajímavý černobílý obrázek Mandelbrotovy množiny je možné upravit postupem, který je popsán v tomto odstavci. Pokud bod odpovídající vykreslovanému pixelu neleží uvnitř Mandelbrotovy množiny, je možné ho obarvit v závislosti na počtu iterací, které proběhnou do chvíle, kdy absolutní hodnota komplexní proměnné zn, tj. hodnota |zn| nepřekročí hodnotu 2, tj. do doby, kdy je na základě podmínky ukončena vnitřní iterační smyčka. V komplexní rovině tak vzniknou izoplochy, tj. souvislé jednobarevné plochy zobrazitelné v rastrovém obrázku, jejichž barva odpovídá počtu iterací nutných pro zjištění, že pixel neleží uvnitř Mandelbrotovy množiny. Poměrně složitým důkazem, který si zde nebudeme uvádět, je možné dokázat, že jakékoli dva body odpovídající určitému počtu iterací, je možné zahrnout do jedné izoplochy, která je souvislá.

Celý postup vykreslování obarvené Mandelbrotovy množiny je ukázán na druhém demonstračním příkladu, ve kterém se opět počítají body Mandelbrotovy množiny ležící v obdélníku zadaném čtyřmi krajními body v komplexní rovině: -2–2i, -2+2i, 2–2i a 2+2i. Program nejdříve ohodnotí každý pixel dle toho, zda leží uvnitř či vně Mandelbrotovy množiny, popřípadě pixel obarví podle počtu iterací nutných k rozhodnutí testu. Zdrojový text programu je dostupný zde, popř. i jako HTML soubor s obarvením syntaxe. Na druhém obrázku je zobrazen grafický výstup tohoto programu. Ovládání tohoto demonstračního příkladu je shodné s příkladem předchozím. Za zmínku stojí způsob obarvení jednotlivých pixelů, při kterém je simulována standardní šestnáctibarevná paleta grafické karty VGA. Změnou pole ve funkci vgaPutpixel() je možné dosáhnout jiného barevného podání celého obrázku.

Klávesa Význam
, snížení počtu iterací o jednotku
. zvýšení počtu iterací o jednotku
< snížení počtu iterací o deset jednotek
> zvýšení počtu iterací o deset jednotek
S uložení rastrového obrázku s fraktálem do externího souboru typu TGA
Q ukončení tohoto demonstračního příkladu
Esc má stejný význam jako klávesa Q
fractals13_2

Obrázek 2: Screenshot druhého demonstračního příkladu se zobrazenou Mandelbrotovou množinou

Funkce pro výpočet pixelů v Mandelbrotově množině v demonstračním příkladu 13.2 vypadá následovně:

//-----------------------------------------------------------------------------
// Překreslení Mandelbrotovy množiny.
// Funkce použitá v demonstračním příkladu 13.2
//-----------------------------------------------------------------------------
void recalcMandelbrot2(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 cx0, cy0;
    double cx, cy;                              // složky komplexní konstanty C
    int    x, y;                                // počitadlo sloupců a řádků v pixmapě
    int    iter;                                // počitadlo iterací

    cy0=MINY;
    for (y=0; y<pix->height; y++) {             // pro všechny řádky v pixmapě
        cx0=MINX;
        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;                          // bude se počítat orbit nuly
            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;
            }
            vgaPutpixel(pix, x, y, iter);       // výpočet barvy pixelu a jeho vykreslení
            cx0+=(MAXX-MINX)/pix->width;        // posun na další bod na řádku
        }
        cy0+=(MAXY-MINY)/pix->height;           // posun na další řádek
    }
} 

Funkce recalcMandelbrot2() využívá pro výpočet barvy a následné vykreslení pixelů funkci vgaPutpixel(). Uvnitř této funkce je umístěné pole obsahující pro každý index trojici barvových složek RGB (červená, zelená, modrá). Velikost pole i jeho obsah je samozřejmě možné měnit, se změnou velikosti však souvisí i změna výrazu i%=16, který zabezpečuje, aby docházelo k cyklickému opakování barev. Funkce vgaPutpixel() má tento tvar:

//-----------------------------------------------------------------------------
// Vykreslení jednoho pixelu na souřadnice [x, y] se simulací standardní
// šestnáctibarevné palety grafické karty VGA.
//-----------------------------------------------------------------------------
void vgaPutpixel(pixmap *pix, int x, int y, int i)
{
    static unsigned char pal[16][3]={           // barvová paleta VGA
        {  0,  0,  0},                          // černá barva
        {  0,  0,170},                          // tmavě modrá barva
        {  0,170,  0},                          // tmavě zelená barva
        {  0,170,170},                          // tmavě azurová barva
        {170,  0,  0},                          // tmavě červená barva
        {170,  0,170},                          // fialová barva
        {170, 85,  0},                          // hnědá barva
        {170,170,170},                          // světle šedá
        { 85, 85, 85},                          // tmavě šedá
        { 85, 85,255},                          // světle modrá barva
        { 85,255, 85},                          // světle zelená barva
        { 85,255,255},                          // světle azurová barva
        {255, 85, 85},                          // světle červená barva
        {255, 85,255},                          // růžová barva
        {255,255, 85},                          // žlutá barva
        {255,255,255},                          // bílá barva
    };
    i%=16;                                      // výraz zajišťující
                                                // opakování barev
    putpixel(pix, x, y, pal[i][0], pal[i][1], pal[i][2]); // vykreslení pixelu
} 

3. Ortodoxní pohled na Mandelbrotovu množinu

V demonstračních příkladech 13.1 a 13.2 je při vykreslování Mandelbrotovy množiny použita část komplexní roviny omezená obdélníkem s rohy -2–2i, -2+2i, 2–2i a 2+2i. Na druhém obrázku jsou hranice tohoto obdélníka dále zvýrazněny díky kruhu se středem v počátku komplexní roviny a poloměrem rovným dvěma. Tento kruh je výsledkem podmínky |zn|<2 – tato podmínka je totiž pro body ležící mimo kruh splněna již při první iteraci. Vzhledem k tomu, že obrazovky většiny počítačů nemají čtvercový tvar, ale tvar obdélníku s poměrem stran 4:3, byl těmto podmínkám přizpůsoben i „ortodoxní“ pohled na Mandelbrotovu množinu. Zde se používá výřez z komplexní roviny, který je omezen krajními body -2,5–1,5i, -2,5+1,5i, 1,5–1,5i a 1,5+1,5i. O dodržení poměru 4:3 se lze přesvědčit jednoduše: reálná osa 1,5-(-2,5)=4 a imaginární osa 1,5-(-1,5)=3. Ortodoxní pohled na Mandelbrotovu množinu je použit i v demonstračním příkladu 13.3, jehož zdrojový kód je uložen zde, popř. zde je HTML verze s obarvením syntaxe.

fractals13_3

Obrázek 3: Zobrazení Mandelbrotovy množiny v okně s poměrem stran 4:3

4. Vykreslení detailů Mandelbrotovy množiny

Mandelbrotova množina patří mezi jeden z nejkomplexnějších fraktálů, alespoň co se týče její vnitřní geometrické struktury. Topologická dimenze hranice Mandelbrotovy množiny má hodnotu 1, zatímco její Hausdorffova dimenze má hodnotu rovnou dvěma. Z toho vyplývá, že Mandelbrotova množina je jedním z nejsložitějších útvarů, které je možné v rovině vůbec zobrazit. Jestliže chceme podrobněji vykreslit detaily z Mandelbrotovy množiny, stačí vhodně nastavit dva krajní body (například levý horní a pravý dolní roh) v komplexní rovině, které ohraničují obrazec, který bude vykreslen. Další možností, která je pro uživatele názornější, je zvolit střed vykreslování a měřítko zvětšení popř. zmenšení pohledu (výřezu) oproti celé množině. Mandelbrotova množina je většinou vykreslována jako množina bodů ležících v obdélníku s krajními body -2–1.5i, -2+1.5i, 2–1.5i a 2+1.5i – to již ostatně víme z předchozí kapitoly. Funkce pro přepočet krajních bodů při zadání středu zobrazení a měřítka může vypadat například následovně:

//-----------------------------------------------------------------------------
// Funkce pro výpočet pozice rohů vykreslovaného obrázku ze zadaného středu
// a měřítka
//-----------------------------------------------------------------------------
void CalcCorner(double xpos, double ypos, double scale,
                double *xmin,  double *ymin,  double *xmax, double *ymax)
{
    *xmin=xpos-2.0*scale;
    *ymin=ypos-1.5*scale;
    *xmax=xpos+2.0*scale;
    *ymax=ypos+1.5*scale;
} 

Parametry xpos a ypos určují, jaké souřadnice v komplexní rovině bude mít střed vykreslovaného obrázku. Parametr scale určuje měřítko vykreslení. Pokud bude hodnota měřítka větší než 1, výsledný obrazec bude oproti původnímu obrázku zmenšený, protože se zvětší vzdálenost mezi souřadnicemi okrajových bodů v komplexní rovině. Pokud bude naopak parametr scale menší než 1, dojde k přiblížení výsledného obrazce. Výsledkem výpočtu jsou hodnoty v proměnných x1, x2, y1, y2, jež určují hranici obdélníku v komplexní rovině, ve které se nachází počítaný obrazec. Změna pohledu na Mandelbrotovu množinu je aplikována i v demonstračním příkladu 13.4, jehož zdrojový kód je uložen zde, popř. zde jako HTML soubor se zvýrazněnou syntaxí.

fractals13_4

Obrázek 4: Detail Mandelbrotovy množiny vykreslený v demonstračním příkladu 13.4 – všimněte si malé kopie původního tvaru

Klávesa Význam
, snížení počtu iterací o jednotku
. zvýšení počtu iterací o jednotku
< snížení počtu iterací o deset jednotek
> zvýšení počtu iterací o deset jednotek
šipky posun obrazce ve směru šipek (o cca pět procent)
Page Up změna měřítka (zvětšení výřezu o deset procent)
Page Down změna měřítka (zmenšení výřezu o deset procent)
S uložení rastrového obrázku s fraktálem do externího souboru typu TGA
Q ukončení tohoto demonstračního příkladu
Esc má stejný význam jako klávesa Q

Tento demonstrační příklad využívá při změně pohledu na Mandelbrotovu množinu hrubou sílu, tj. neustále jsou přepočítávány a následně vykresleny všechny pixely v obrázku. Proto je vhodné při hledání vhodného pohledu snížit počet iterací (například na 50 nebo i méně) a původní hodnotu obnovit až po nalezení vhodného obrázku. Mnohem propracovanější metodu používá známý program XaoS Honzy Hubičky, který při změně pohledu vypočítá vektory posunu všech již dříve vypočtených pixelů a posléze dopočítá pouze pixely nové. Díky faktu, že nových pixelů může být velmi málo (typicky méně než deset procent), je posun i „zoomování“ v obrázku mnohem rychlejší než v našem demonstračním příkladu.

fractals13_5

Obrázek 5: Detail Mandelbrotovy množiny vykreslený v demonstračním příkladu 13.4

fractals13_6

Obrázek 6: Detail Mandelbrotovy množiny vykreslený v demonstračním příkladu 13.4

fractals13_7

Obrázek 7: Detail Mandelbrotovy množiny vykreslený v demonstračním příkladu 13.4

fractals13_8

Obrázek 8: Detail Mandelbrotovy množiny vykreslený v demonstračním příkladu 13.4

5. Literatura a odkazy na Internetu

  1. Devaney Robert L.: „A First Course In Chaotic Dynamical Systems“,
    Addison-Wesley, Reading, MA, 1992
  2. Lauwerier Hans: „Fractals“,
    Princeton University Press, 1991
  3. Peitgen Heinz-Otto, Richter Peter: „The Beauty of Fractals“,
    Springer-Verlag, New York, 1986, ISBN 0–387–15851–0
  4. Peitgen Heinz-Otto, Jurgens Hartmut, Saupe Dietmar: „Fractals For The Classroom“,
    Springer-Verlag, New York, 1988
  5. Tišnovský Pavel: „Výpočet plochy Mandelbrotovy množiny metodou součtu pixelů“,
    Elektrorevue, 2001
  6. Tišnovský Pavel: „Fraktály: dynamické systémy v komplexní rovině“,
    Elektrorevue, 2001
  7. Wegner Timothy, Peterson Mark: „Fractal Creations, First Edition“,
    The Waite Group Press, 1991
  8. Wegner Timothy, Tyler Bert: „Fractal Creations, Second Edition“,
    The Waite Group Press, 1993
  9. Wegner Timothy, Tyler Bert, Peterson Mark, Branderhorst Pierer: „Fractals for Windows“,
    The Waite Group Press, 1992
  10. Žára J., Beneš B., Felkel P.: „Moderní počítačová grafika“,
    Computer Press, Praha, 1998, ISBN 80–7226–049–9
  11. Žára J., Limpouch A., Beneš B., Werner T.: „Počítačová grafika – principy a algoritmy“,
    Grada, 1992
  12. Douady, A., Hubbard, J.: „Itération des polynomes quadratiques complexes“
    C. R. Acad. Sci., Paris 1982
  13. Ewing, J. H., Schober, G.: „The area of the Mandelbrot Set“
    Numer. Math. 1992

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

V dalším pokračování tohoto seriálu si ukážeme vylepšené techniky vykreslování a obarvování Mandelbrotovy množiny. Také si řekneme, jaký je vztah mezi Mandelbrotovou množinou a množinami Juliovými a jak je možné tento vztah využít při interaktivní změně počátečních podmínek Juliovy množiny.

Našli jste v článku chybu?

20. 1. 2006 9:10

Jde vam spise o co nejrychlejsi implementaci s mensi presnosti, nebo naopak o co nejvetsi presnost (a rozsah) hodnot?

Ta zminovana knihovna pro arbitrary precision z FractIntu je urcena pro "deep zooming", tj. pro velke zvetseni fraktalu, pri kterych by v pripade pouziti floatu, doublu (i extended) dochazelo k velkym chybam pri iterativnim vypoctu - pekne je to videt napriklad pri zoomovani v programu XaoS.

Podobnou funkcionalitu nabizi i knihovna GMP, ktera je sirena pod licenci GNU…



19. 1. 2006 16:25

Pod Linuxem se (samozrejme) preklada pomoci gcc, ale musite mit nainstalovane i develop verze OpenGL a GLUTu. U OpenGL v tomto pripade staci SW implementace.

Pod MS Windows jsem preklad zkousel na gcc (MinGW, gcc verze 3.2) na Borland C++ 5.5 (to je ta verze Borlandskeho prekladace zadarmo). Nicmene by to melo fungovat i s MS Visual C, ale to nemam kde odzkouset.

Ja si vsak myslim, ze nemoznost prekladu nebude ani tak zpusobena zdrojakem, prece jen je to standardni cecko 99 (a to jen kvuli jed…



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

Rakovina oka. Jak ji poznáte?

Lupa.cz: Google měl výpadek, nejel Gmail ani YouTube

Google měl výpadek, nejel Gmail ani YouTube

120na80.cz: Bojíte se encefalitidy?

Bojíte se encefalitidy?

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

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

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

Přehledná titulka, průvodci, responzivita

Lupa.cz: UX přestává pro firmy být magie

UX přestává pro firmy být magie

DigiZone.cz: Sony KD-55XD8005 s Android 6.0

Sony KD-55XD8005 s Android 6.0

Měšec.cz: Finančním poradcům hrozí vracení provizí

Finančním poradcům hrozí vracení provizí

DigiZone.cz: ČT má dalšího zástupce v EBU

ČT má dalšího zástupce v EBU

Podnikatel.cz: Víme první výsledky doby odezvy #EET

Víme první výsledky doby odezvy #EET

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

120na80.cz: Jak oddálit Alzheimera?

Jak oddálit Alzheimera?

Podnikatel.cz: EET: Totálně nezvládli metodologii projektu

EET: Totálně nezvládli metodologii projektu

Měšec.cz: U levneELEKTRO.cz už reklamaci nevyřídíte

U levneELEKTRO.cz už reklamaci nevyřídíte

Vitalia.cz: Chtějí si léčit kvasinky. Lék je jen v Německu

Chtějí si léčit kvasinky. Lék je jen v Německu

DigiZone.cz: NG natáčí v Praze seriál o Einsteinovi

NG natáčí v Praze seriál o Einsteinovi

Vitalia.cz: Jsou čajové sáčky toxické?

Jsou čajové sáčky toxické?

120na80.cz: Pánové, pečujte o svoje přirození a prostatu

Pánové, pečujte o svoje přirození a prostatu

Lupa.cz: Babiš: E-shopů se EET možná nebude týkat

Babiš: E-shopů se EET možná nebude týkat

Vitalia.cz: Paštiky plné masa ho zatím neuživí

Paštiky plné masa ho zatím neuživí