Hlavní navigace

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

Pavel Tišnovský

V dnešním pokračování seriálu věnovaného fraktálům používaným (nejenom) v počítačové grafice se budeme zabývat dalšími typy rastrových obrázků s fraktální strukturou, které jsou počítány a vykreslovány v komplexní rovině. Bude se jednat o fraktály, jejichž iterační vztahy navrhl a implementoval vědec Michael Barnsley, který je mimo jiné známý i velmi důležitým objevem systémů iterovaných funkcí (IFS) a jejich praktickou aplikací při fraktální komprimaci obrázků.

Obsah

1. Princip tvorby fraktálů navržených Michaelem Barnsleym v komplexní rovině
2. Fraktál pojmenovaný Barnsley M1
3. Demonstrační příklad vykreslující fraktál Barnsley M1
4. Fraktál pojmenovaný Barnsley M2
5. Demonstrační příklad vykreslující fraktál Barnsley M2
6. Fraktál pojmenovaný Barnsley M3
7. Demonstrační příklad vykreslující fraktál Barnsley M3
8. Obsah dalšího pokračování tohoto seriálu

1. Princip tvorby fraktálů navržených Michaelem Barnsleym v komplexní rovině

Michael Barnsley je vědec, který se mimo jiné poměrně intenzívně zajímá o využití fraktálů a fraktální geometrie v praxi. Ve světě jsou proslulé především „jeho“ systémy iterovaných funkcí (IFS), kterými se v tomto seriálu samozřejmě také budeme zabývat. Kromě přímé aplikace generativní metody používající IFS systémy pro tvorbu fraktálních obrazců (koláží) je možné IFS použít v takzvané inverzní úloze – k nalezení soustavy jednoduchých lineárních funkcí (resp. lineárních transformací) popisujících nějaký rastrový obrázek. To je základní princip (obecně ztrátové) fraktální komprimace obrazů, kterou má Michael Barnsley a jeho spolupracovníci patentovanou. Patenty na tuto technologii však měly na praktické využití fraktální komprimace obrazů negativní dopad, místo ní se masivně začaly aplikovat jiné technologie využívající ztrátovou komprimaci, zejména diskrétní kosinová transformace (DCT – discrete cosinus transformation) a později také vlnková transformace (WT – wavelet transformation). Je to škoda, protože fraktální komprimace obrazů v některých případech (například pro fotky většiny přírodních objektů) nabízí lepší poměr kvalita obrazu/objem dat než DCT a WT.

V dnešní části seriálu se však ještě systémy iterovaných funkcí zabývat nebudeme. Místo toho si ukážeme tři typy fraktálních obrazců vytvářených v komplexní rovině. Tyto fraktály Barnsley popsal ve své známé knize Fractals Everywhere. Konkrétně se jedná o tři modifikace Mandelbrotových množin a k nim příslušející trojici Juliových množin. Modifikace spočívá v náhradě původního iteračního vztahu zn+1=zn2+c vztahem složitějším, ve kterém se navíc vyskytuje podmínka. Tím se původní zaoblený („organický“) tvar Mandelbrotovy množiny a Juliových množin změní takřka k nepoznání, výsledné obrazce spíše připomínají krystalické struktury. K označení všech šesti fraktálů jsem zvolil jména použitá mj. i v programu FractInt. Modifikované Mandelbrotovy množiny se nazývají M1, M2 a M3, k nim příslušející Juliovy množiny mají název J1, J2 a J3. V dnešní části seriálu budou popsány „Mandelbrotovy“ verze Barnsleyových fraktálů, příště si popíšeme „Juliovy“ verze.

2. Fraktál pojmenovaný Barnsley M1

První Mandelbrotova varianta Barnsleyovy fraktální množiny, kterou zde nazývám jednoduše M1, používá iterační vztah, ve kterém se vyskytuje podmínka (test) na aktuální hodnotu reálné složky komplexního čísla zn. Pro jednoduchost tento vztah nejprve zapíšu v pseudokódu, ve kterém nabývají proměnné z a c komplexních hodnot, přímý přepis do programovacího jazyka C je tedy poněkud složitější, neboť se musí provést rozpis všech komplexních proměnných na jejich reálnou a imaginární složku. Iterační vztah pro Barnsleyovu variantu Mandelbrotovy množiny M1 má následující podobu:

    if (real(z) >= 0)
        z(n+1)=(z-1)*c
    else
        z(n+1)=(z+1)*c 

Po rozpisu iteračního vztahu na reálnou a imaginární složku proměnných z a c již dostáváme validní a použitelný céčkovský kód:

    zx2=zx*zx;
    zy2=zy*zy;
    if (zx2+zy2>4) break;      // test na ukončení iterační smyčky
    if (zx>=0) {               // test na znaménko reálné složky Z
        zxn=zx*cx0-zy*cy0-cx0;
        zyn=zx*cy0+zy*cx0-cy0;
    }
    else {
        zxn=zx*cx0-zy*cy0+cx0;
        zyn=zx*cy0+zy*cx0+cy0;
    }
    zx=zxn;                    // přepis nových hodnot do proměnné Z
    zy=zyn; 

Všimněte si, že test na ukončení iterační smyčky zůstal stejný, jako v původní verzi Mandelbrotovy množiny. Céčkovská funkce, která s využitím výše uvedeného fragmentu kódu provádí přepočet a následné vykreslení Mandelbrotovy verze Barnsleyovy fraktální množiny M1, vypadá následovně:

//-----------------------------------------------------------------------------
// Překreslení Barnsleyovy fraktální množiny M1
//-----------------------------------------------------------------------------
void recalcBarnsleyM1(pixmap *pix,              // pixmapa pro vykreslování
                  int    maxiter,               // maximální počet iterací
                  double scale,                 // měřítko obrazce
                  double xpos,                  // posun obrazce
                  double ypos,
                  int    palette,               // barvová paleta
                  int    rf, int gf, int bf)    // příznaky barvových složek
{
    double zx, zy, zx2, zy2, zxn, zyn;          // složky komplexní proměnné Z a Z^2
    double cx0, cy0;
    double xmin, ymin, xmax, ymax;              // rohy vykreslovaného obrazce v komplexní
                                                // rovině
    int    x, y;                                // počitadla sloupců a řádků v pixmapě
    int    iter;                                // počitadlo iterací
    unsigned char r, g, b;

    calcCorner(xpos, ypos, scale, &xmin, &ymin, &xmax, &ymax);
    cy0=ymin;
    for (y=0; y<pix->height; y++) {             // pro všechny řádky v pixmapě
        cx0=xmin;
        for (x=0; x<pix->width; x++) {          // pro všechny pixely na řádku
            zx=0;                               // nastavit počáteční hodnotu Z(0)
            zy=0;
            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) break;           // test na ukončení iterační smyčky
                if (zx>=0) {                    // test na znaménko reálné složky Z
                    zxn=zx*cx0-zy*cy0-cx0;      // kladné znaménko
                    zyn=zx*cy0+zy*cx0-cy0;
                }
                else {
                    zxn=zx*cx0-zy*cy0+cx0;      // záporné znaménko
                    zyn=zx*cy0+zy*cx0+cy0;
                }
                zx=zxn;                         // přepis nových hodnot do proměnné Z
                zy=zyn;
            }
            mapPalette(palette, iter, &r, &g, &b);
            r=r*rf;                             // uživatelem řízené vynulování
            g=g*gf;                             // vybraných barvových složek
            b=b*bf;
            putpixel(pix, x, y, r, g, b);
            cx0+=(xmax-xmin)/pix->width;        // posun na další bod na řádku
        }
        cy0+=(ymax-ymin)/pix->height;           // posun na další řádek
    }
} 

Na prvním a druhém obrázku jsou vidět vybrané detaily Barnsleyova fraktálu M1. Přídavná podmínka v probíhající iterační smyčce způsobuje, že se v obrázku objevují ostré hranice mezi barevnými plochami.

fractals24_1.png

Obrázek 1: Detail Barnsleyova fraktálu M1

fractals24_2.png

Obrázek 2: Jiný detail Barnsleyova fraktálu M1

3. Demonstrační příklad vykreslující fraktál Barnsley M1

Céčkovská funkce uvedená ve druhé kapitole je použita v dnešním prvním demonstračním příkladu, pomocí kterého byl získán i třetí obrázek. Na první pohled vypadají Barnsleyovy fraktální množiny nezajímavě, avšak v následující části tohoto seriálu si ukážeme Juliovy verze Barnsleyových množin, které mají naopak velmi různorodé a elegantní tvary. Ovládání prvního demonstračního příkladu pomocí klávesnice je sepsáno v níže uvedené tabulce:

Ovládání příkladu
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 – ukončení aplikace
šipky posun obrazce ve směru šipek (o cca pět procent velikosti obrázku)
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)
0 nastavení barvové palety „Blues“ (implicitní nastavení po spuštění programu)
1 nastavení barvové palety „Gold“
2 nastavení barvové palety „Greens“
3 nastavení barvové palety „Ice“
4 nastavení barvové palety „Juteblue“
5 nastavení barvové palety „Jutemap“
6 nastavení barvové palety „Jutes“
7 nastavení barvové palety „Mandmap“ (to je použito na níže zobrazeném screenshotu)
8 nastavení barvové palety „Phong“
9 nastavení barvové palety „Rose“

fractals24_3.png

Obrázek 3: Screenshot prvního demonstračního příkladu s Barnsleyovým fraktálem M1

4. Fraktál pojmenovaný Barnsley M2

Druhá Mandelbrotova varianta Barnsleyovy fraktální množiny, kterou označuji symbolem M2, vzniká použitím složitějšího iteračního vztahu, který je možné v pseudokódu zapsat následujícím způsobem (proměnné z i c nabývají opět komplexních hodnot):

    if (real(z)*imag(c) + real(c)*imag(z) >= 0)
        z(n+1) = (z-1)*c
    else
        z(n+1) = (z+1)*c 

Po rozpisu komplexních proměnných na jejich reálné a imaginární složky již můžeme zapsat fragment céčkovského kódu, který bude následně použitý v iterační smyčce:

    zx2=zx*zx;
    zy2=zy*zy;
    if (zx2+zy2>4) break;      // test na ukončení iterační smyčky
    if (zx*cy0+zy*cx0>=0) {
        zxn=zx*cx0-zy*cy0-cx0;
        zyn=zx*cy0+zy*cx0-cy0;
    }
    else {
        zxn=zx*cx0-zy*cy0+cx0;
        zyn=zx*cy0+zy*cx0+cy0;
    }
    zx=zxn;                    // přepis nových hodnot do proměnné Z
    zy=zyn; 

Celá funkce, která bude provádět výpočet a následné překreslení Mandelbrotovy verze Barnsleyovy fraktální množiny má tvar:

//-----------------------------------------------------------------------------
// Překreslení Barnsleyovy fraktální množiny M2
//-----------------------------------------------------------------------------
void recalcBarnsleyM2(pixmap *pix,              // pixmapa pro vykreslování
                  int    maxiter,               // maximální počet iterací
                  double scale,                 // měřítko obrazce
                  double xpos,                  // posun obrazce
                  double ypos,
                  int    palette,               // barvová paleta
                  int    rf, int gf, int bf)    // příznaky barvových složek
{
    double zx, zy, zx2, zy2, zxn, zyn;          // složky komplexní proměnné Z a Z^2
    double cx0, cy0;
    double xmin, ymin, xmax, ymax;              // rohy vykreslovaného obrazce v komplexní
                                                // rovině
    int    x, y;                                // počitadla sloupců a řádků v pixmapě
    int    iter;                                // počitadlo iterací
    unsigned char r, g, b;

    calcCorner(xpos, ypos, scale, &xmin, &ymin, &xmax, &ymax);
    cy0=ymin;
    for (y=0; y<pix->height; y++) {             // pro všechny řádky v pixmapě
        cx0=xmin;
        for (x=0; x<pix->width; x++) {          // pro všechny pixely na řádku
            zx=0;                               // nastavit počáteční hodnotu Z(0)
            zy=0;
            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) break;           // test na ukončení iterační smyčky
                if (zx*cy0+zy*cx0>=0) {
                    zxn=zx*cx0-zy*cy0-cx0;
                    zyn=zx*cy0+zy*cx0-cy0;
                }
                else {
                    zxn=zx*cx0-zy*cy0+cx0;
                    zyn=zx*cy0+zy*cx0+cy0;
                }
                zx=zxn;                         // přepis nových hodnot do proměnné Z
                zy=zyn;
            }
            mapPalette(palette, iter, &r, &g, &b);
            r=r*rf;                             // uživatelem řízené vynulování
            g=g*gf;                             // vybraných barvových složek
            b=b*bf;
            putpixel(pix, x, y, r, g, b);
            cx0+=(xmax-xmin)/pix->width;        // posun na další bod na řádku
        }
        cy0+=(ymax-ymin)/pix->height;           // posun na další řádek
    }
} 

Barnsleyův fraktál M2 je zobrazen na čtvrtém a pátém obrázku. I zde si povšimněte „krystalických“ struktur, které je možné v obrázcích nalézt.

fractals24_4.png

Obrázek 4: Detail Barnsleyova fraktálu M2

fractals24_5.png

Obrázek 5: Další detail Barnsleyova fraktálu M2

5. Demonstrační příklad vykreslující fraktál Barnsley M2

Podobně jako v případě prvního demonstračního příkladu, i dnešní druhý demonstrační příklad, využívá výše vypsanou céčkovskou funkci. Pomocí druhého příkladu byl získán i následující obrázek. Všimněte si, že tato fraktální množina již není tak „krystalická“, jako fraktální množina M1.

fractals24_6.png

Obrázek 6: Screenshot druhého demonstračního příkladu s Barnsleyovým fraktálem M2

6. Fraktál pojmenovaný Barnsley M3

Třetí verze Mandelbrotovy fraktální množiny nazývaná Barnsley M3 používá už poměrně složitý iterační vztah, který je možné vyjádřit následujícím pseudokódem:

    if (real(z(n) > 0)
        z(n+1) = (real(z(n))^2 - imag(z(n))^2 - 1)
               + i * (2*real(z((n)) * imag(z((n)))
    else
        z(n+1) = (real(z(n))^2 - imag(z(n))^2 - 1 + real(c) * real(z(n))
               + i * (2*real(z((n)) * imag(z((n)) + imag(c) * real(z(n)) 

Při přepisu iteračního vztahu budeme postupovat podobným způsobem, jako u předchozích dvou fraktálních množin: rozepíšeme komplexní proměnné z a c na jejich reálnou a imaginární složku. Výsledný fragment kódu bude kupodivu velmi jednoduchý:

    zx2=zx*zx;                      // zkrácený výpočet druhé mocniny složek Z
    zy2=zy*zy;
    if (zx>0) {
        zxn=zx2-zy2-1;
        zyn=2.0*zx*zy;
    }
    else {
        zxn=zx2-zy2-1+cx0*zx;
        zyn=2.0*zx*zy+cy0*zx;
    } 

Tento kód je použitý i v céčkovské funkci, která slouží k výpočtu a vykreslení fraktální množiny M3 pro zadané vstupní parametry:

//-----------------------------------------------------------------------------
// Překreslení Barnsleyovy fraktální množiny M3
//-----------------------------------------------------------------------------
void recalcBarnsleyM3(pixmap *pix,              // pixmapa pro vykreslování
                  int    maxiter,               // maximální počet iterací
                  double scale,                 // měřítko obrazce
                  double xpos,                  // posun obrazce
                  double ypos,
                  int    palette,               // barvová paleta
                  int    rf, int gf, int bf)    // příznaky barvových složek
{
    double zx, zy, zx2, zy2, zxn, zyn;          // složky komplexní proměnné Z a Z^2
    double cx0, cy0;
    double xmin, ymin, xmax, ymax;              // rohy vykreslovaného obrazce v komplexní
                                                // rovině
    int    x, y;                                // počitadla sloupců a řádků v pixmapě
    int    iter;                                // počitadlo iterací
    unsigned char r, g, b;

    calcCorner(xpos, ypos, scale, &xmin, &ymin, &xmax, &ymax);
    cy0=ymin;
    for (y=0; y<pix->height; y++) {             // pro všechny řádky v pixmapě
        cx0=xmin;
        for (x=0; x<pix->width; x++) {          // pro všechny pixely na řádku
            zx=0;                               // nastavit počáteční hodnotu Z(0)
            zy=0;
            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) break;           // test na ukončení iterační smyčky
                if (zx>0) {                     // test na znaménko reálné složky Z
                    zxn=zx2-zy2-1;
                    zyn=2.0*zx*zy;              // kladné znaménko
                }
                else {
                    zxn=zx2-zy2-1+cx0*zx;       // záporné znaménko
                    zyn=2.0*zx*zy+cy0*zx;
                }
                zx=zxn;                         // přepis nových hodnot do proměnné Z
                zy=zyn;
            }
            mapPalette(palette, iter, &r, &g, &b);
            r=r*rf;                             // uživatelem řízené vynulování
            g=g*gf;                             // vybraných barvových složek
            b=b*bf;
            putpixel(pix, x, y, r, g, b);
            cx0+=(xmax-xmin)/pix->width;        // posun na další bod na řádku
        }
        cy0+=(ymax-ymin)/pix->height;           // posun na další řádek
    }
} 

Na sedmém a osmém obrázku jsou ukázány dva detaily Barnsleyovy fraktální množiny M3. V této množině je možné nalézt oblasti, které při vhodně zvolené barvové paletě připomínají mraky nebo turbulentní proudění dvou různě zabarvených kapalin.

fractals24_7.png

Obrázek 7: Detail Barnsleyova fraktálu M3

fractals24_8.png

Obrázek 8: Další detail Barnsleyova fraktálu M3

7. Demonstrační příklad vykreslující fraktál Barnsley M3

Dnešní třetí demonstrační příklad slouží k výpočtu a následnému vykreslení Barnsleyovy fraktální množiny M3. Screenshot získaný z tohoto demonstračního příkladu je zobrazený na devátém obrázku.

fractals24_9.png

Obrázek 9: Screenshot třetího demonstračního příkladu s Barnsleyovým fraktálem M3

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

V následujícím pokračování tohoto seriálu si popíšeme Juliovy verze Barnsleyových fraktálů, jež vychází z výše popsaných fraktálů M1, M2 a M3, ovšem jejich obrázky jsou již mnohem zajímavější.

Našli jste v článku chybu?

6. 4. 2006 11:51

Tak s těmi minikopiemi Mandelbrotovy množiny v Barnsleyho fraktálech M1, M2 a M3 jsem Vás neúmyslně mystifikoval :-( Měl jsem zato, že všechny iterované systémy, ve kterých se provádí aditivní operace s komplexní konstantou c, obsahují malé kopie Mandelbrotovy množiny.

Ve skutečnosti to však není úplně vždy pravda, tyto kopie jsou (myslím o tom píše Douday a Richter) obsaženy pouze v některých fraktálních množinách, zejména těch, kde se komplexní proměnná z umocňuje a k ní se…

5. 4. 2006 13:32

V předchozích dvou pokračováních seriálu jsme se zabývali Newtonovými fraktálními množinami. Zmiňoval jsem se také o podobě Newtonových množin a obrázku, který vznikne měřením ustálení kyvadla pohybujícího se nad třemi magnety.

Na stránce http://www.inf.ethz.ch/personal/muellren/pendulum/index.html jsou informace o jednom GPL projektu, který se podobnou problematikou zabývá. Naleznete tam také obrázky z celého experimentu a diferenciální rovnice pohybu kyvadla.

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

Vitalia.cz: Nestlé vyvinulo nový typ „netloustnoucího“ cukru

Nestlé vyvinulo nový typ „netloustnoucího“ cukru

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

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

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

Přehledná titulka, průvodci, responzivita

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

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

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

EET: Totálně nezvládli metodologii projektu

Lupa.cz: Teletext je „internetem hipsterů“

Teletext je „internetem hipsterů“

Měšec.cz: Air Bank zruší TOP3 garanci a zdražuje kurzy

Air Bank zruší TOP3 garanci a zdražuje kurzy

Vitalia.cz: Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Vitalia.cz: Když přijdete o oko, přijdete na rok o řidičák

Když přijdete o oko, přijdete na rok o řidičák

Podnikatel.cz: 1. den EET? Problémy s pokladnami

1. den EET? Problémy s pokladnami

Měšec.cz: Kdy vám stát dá na stěhování 50 000 Kč?

Kdy vám stát dá na stěhování 50 000 Kč?

Podnikatel.cz: Udávání kvůli EET začalo

Udávání kvůli EET začalo

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

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

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

Co všechno ovlivňuje ženskou plodnost?

Podnikatel.cz: Zavře krám u #EET Malá pokladna a Teeta?

Zavře krám u #EET Malá pokladna a Teeta?

Vitalia.cz: 9 největších mýtů o mase

9 největších mýtů o mase

Podnikatel.cz: Udávání a účtenková loterie, hloupá komedie

Udávání a účtenková loterie, hloupá komedie

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

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

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

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