Hlavní navigace

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

Pavel Tišnovský 28. 3. 2006

V třiadvacátém pokračování seriálu věnovaného fraktálům používaným (nejenom) v počítačové grafice si ukážeme tvorbu modifikované fraktální množiny vzniklé aplikací Newtonovy iterační metody na polynom s komplexními kořeny. Uvedená modifikace spočívá v obarvení pixelů na základě počtu iterací. Dále si popíšeme Newtonovy fraktály odpovídající polynomům vyšších stupňů, použití neceločíselných mocnin a na závěr Newtonovy fraktály vytvořené pomocí polynomů s komplexními mocninami.

Obsah

1. Tvorba modifikovaných Newtonových fraktálů
2. Demonstrační příklady ukazující vykreslení modifikovaného Newtonova fraktálu
3. Newtonovy fraktály pro polynomy vyšších stupňů
4. Newtonova fraktální množina vytvořená pro polynom z4-1=0
5. Newtonova fraktální množina vytvořená pro polynom z8-1=0
6. Neceločíselná mocnina u polynomu řešeného Newtonovou iterační metodou
7. Komplexní mocnina u polynomu řešeného Newtonovou iterační metodou
8. Obsah dalšího pokračování tohoto seriálu

1. Tvorba modifikovaných Newtonových fraktálů

V předchozím pokračování tohoto seriálu jsme si jak po teoretické stránce, tak i na demonstračním příkladu ukázali, jakým způsobem je možné vykreslit Newtonovu fraktální množinu, která vznikne aplikací Newtonovy iterační metody na polynomy s komplexními kořeny. Nejjednodušším polynomem, který už vykazuje velkou citlivost na počáteční podmínky a současně má i všechny základní fraktální charakteristiky, je polynom určený vztahem z3-1=0. Newtonův fraktál příslušející k tomuto polynomu, tj. fraktál tvořený pomocí iteračního vztahu zi+1=zi-(zi3-1)/(3zi2), se vykresluje pomocí pouhých čtyř barev, barvy samozřejmě mohou být libovolně zvoleny z celé barvové škály.

První barvou jsou obarveny ty body, které se po provedení několika iterací, tj. ještě před dosažením maximálního povoleného množství iterací, přiblíží k prvnímu kořenu polynomu, druhou barvou body odpovídající druhému kořenu, třetí barvou body odpovídající třetímu kořenu a konečně čtvrtá barva je rezervována pro ty body, u nichž není možné rozhodnout, ke kterému kořenu řešení iterační metody spěje (konverguje) – buď se jedná o body, pro něž nebylo použito dostatečného množství iterací, nebo o body, které se již z principu k žádnému řešení nepřibližují. Na prvním obrázku je pro připomenutí vykreslen Newtonův fraktál po 255 iteračních krocích. Jednotlivým pixelům jsou přiřazovány tyto barvy: červená (první kořen), zelená (druhý kořen), modrá (třetí kořen) a černá (metoda nedospěla k žádnému z kořenů).

fractals23_1
Obrázek 1: Newtonův fraktál polynomu z3-1=0 vykreslený standardní metodou po 255 iteračních krocích

Jak je z prvního obrázku patrné, není Newtonův fraktál z estetického hlediska (například pro účely generování procedurálních textur) příliš zajímavý, zejména kvůli použití malého množství barev. Existuje však i modifikovaný způsob vykreslení Newtonova fraktálu, který je postaven na stejné koncepci vykreslování, jaká je použita u již dříve popsaných Mandelbrotových a Juliových množin. Jednotlivé body (resp.  při vykreslování na obrazovce spíše pixely) nejsou při použití modifikované metody obarveny na základě příslušnosti k některému z kořenů, ale podle celkového počtu iterací, které bylo nutné provést pro jednoznačné rozhodnutí, ke kterému kořenu daný bod (pixel) přísluší, tj. ke kterému kořenu řešení konverguje. Pro některé body, zejména ty, jež se nachází blízko kořenů, je nutné provést pouze malý počet iterací, avšak body, které se nachází na hranici přitažlivosti mezi dvěma kořeny, vyžadují velké množství iterací, takže výsledný obrázek nám vlastně podává informaci o výpočetní složitosti řešení v různých částech komplexní roviny. Newtonova množina vypočtená touto modifikovanou metodou je zobrazena na druhém obrázku.

fractals23_2
Obrázek 2: Newtonův fraktál z3-1=0 vykreslený modifikovanou metodou po 255 iteračních krocích

Obě metody vykreslování, tj. metodu standardní i metodu modifikovanou, je možné navzájem zkombinovat a na jednom obrázku zdůraznit jak kořeny, ke kterým řešení pomocí Newtonovy iterační metody spěje, tak i počet iterací, které je nutné provést pro nalezení tohoto řešení. Kombinace obou metod je z programátorského hlediska velmi jednoduchá: nejprve se bod či pixel obarví na základě počtu iterací a posléze je jedna z barvových složek (R, B, B) modifikována podle toho, ke kterému kořenu řešení Newtonovy iterační metody konverguje. Pokud například řešení jednoznačně dospělo k prvnímu kořenu, je červená barvová složka snížena na polovinu svého původního jasu, u řešení konvergující ke druhému kořenu je změněna zelená barvová složka a konečně u řešení, jež dospělo ke třetímu kořenu, je snížen jas modré barvové složky. Newtonův fraktál vykreslený kombinací standardní a modifikované metody je zobrazen na třetím obrázku. U Newtonových fraktálů, které vznikají aplikací polynomů vyšších stupňů, je situace komplikovanější, protože není možné modifikovat přímo barvové složky R, G, B (kořenů je více než dostupných barvových složek). Proto se zde volí další kombinace, např. je dvěma kořenům přiřazena stejná operace pro modifikaci barvových složek.

fractals23_3
Obrázek 3: Newtonův fraktál z3-1=0 vykreslený kombinací standardní a modifikované metody po 255 iteračních krocích

2. Demonstrační příklady ukazující vykreslení modifikovaného Newtonova fraktálu

Modifikovaná metoda určená pro výpočet a následné vykreslení Newtonovy fraktální množiny je implementována v dnešním prvním demonstračním příkladu. Po překladu a následném spuštění tohoto příkladu je možné způsob zobrazení fraktálu modifikovat pomocí kláves [0]-[9] (změna barvové palety), klávesy [,], [.], [<] a [>] slouží ke změně počtu iterací, kurzorovými šipkami je možné množinu v komplexní rovině posouvat a pomocí kláves [PageUp] a [PageDown] se mění měřítko obrazce, tj. stupeň zvětšení či zmenšení. Zobrazený fraktál je možné uložit do souboru stiskem klávesy [S], celý program se ukončí klávesou [Q] nebo [Esc]. Screenshot prvního demonstračního příkladu je zobrazený na čtvrtém obrázku.

fractals23_4
Obrázek 4: Screenshot prvního demonstračního příkladu

Funkce, která v prvním demonstračním příkladu slouží k výpočtu fraktálního obrazce, vypadá následovně:

//-----------------------------------------------------------------------------
// Překreslení Newtonovy fraktální množiny pro polynom z^3-1=0 modifikovanou
// metodou
//-----------------------------------------------------------------------------
void recalcNewton(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, Z^2 a Z^3
    double zx0, zy0;
    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;

#define PI 3.1415927
#define EPSILON 0.1
#define DIST2(x1, y1, x2, y2) (((x1)-(x2))*((x1)-(x2))+((y1)-(y2))*((y1)-(y2)))

    double rootx[3]={1.0, cos(2.0*PI/3.0), cos(4.0*PI/3.0)};
    double rooty[3]={0.0, sin(2.0*PI/3.0), sin(4.0*PI/3.0)};

    calcCorner(xpos, ypos, scale, &xmin, &ymin, &xmax, &ymax);
    zy0=ymin;
    for (y=0; y<pix->height; y++) {             // pro všechny řádky v pixmapě
        zx0=xmin;
        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
                zy2=zy*zy;                      // složek Z
                zxn=2.0/3.0*zx+(zx2-zy2)/(3.0*(zx2*zx2+zy2*zy2+2.0*zx2*zy2));
                zyn=2.0/3.0*zy-2.0*zx*zy/(3.0*(zx2*zx2+zy2*zy2+2.0*zx2*zy2));
                                                // test na přiblížení ke kořenům polynomu
                if (DIST2(zxn, zyn, rootx[0], rooty[0])<EPSILON ||
                    DIST2(zxn, zyn, rootx[1], rooty[1])<EPSILON ||
                    DIST2(zxn, zyn, rootx[2], rooty[2])<EPSILON) break;
                zx=zxn;
                zy=zyn;
            }
            if (iter==0) iter++;                // zabránit vznikům černých ostrůvků
            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);
            zx0+=(xmax-xmin)/pix->width;        // posun na další bod na řádku
        }
        zy0+=(ymax-ymin)/pix->height;           // posun na další řádek
    }
} 

Kombinovaná metoda, při které se zobrazuje jak počet iterací, tak i kořen, ke kterému řešení Newtonovy iterační metody konverguje, je implementována v dnešním druhém demonstračním příkladu. Screenshot druhého demonstračního příkladu, který je možné ovládat stejným způsobem, jako příklad předchozí, je zobrazený na pátém obrázku. Ze screenshotu je patrné, že jednotlivým kořenům odpovídají v použité barvové paletě odstíny červené, zelené a žluté barvy, přičemž počet iterací je vyjádřen sytostí a intenzitou těchto barvových složek.

fractals23_5
Obrázek 5: Screenshot druhého demonstračního příkladu

Funkce, která ve druhém demonstračním příkladu slouží k výpočtu fraktálního obrazce, vypadá následovně:

//-----------------------------------------------------------------------------
// Překreslení Newtonovy fraktální množiny pro polynom z^3-1=0 modifikovanou
// metodou kombinovanou se zvýrazněním kořenů, ke kterým řešení konverguje
//-----------------------------------------------------------------------------
void recalcNewton(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, Z^2 a Z^3
    double zx0, zy0;
    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;

#define PI 3.1415927
#define EPSILON 0.1
#define DIST2(x1, y1, x2, y2) (((x1)-(x2))*((x1)-(x2))+((y1)-(y2))*((y1)-(y2)))

    double rootx[3]={1.0, cos(2.0*PI/3.0), cos(4.0*PI/3.0)};
    double rooty[3]={0.0, sin(2.0*PI/3.0), sin(4.0*PI/3.0)};

    calcCorner(xpos, ypos, scale, &xmin, &ymin, &xmax, &ymax);
    zy0=ymin;
    for (y=0; y<pix->height; y++) {             // pro všechny řádky v pixmapě
        zx0=xmin;
        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
                zy2=zy*zy;                      // složek Z
                zxn=2.0/3.0*zx+(zx2-zy2)/(3.0*(zx2*zx2+zy2*zy2+2.0*zx2*zy2));
                zyn=2.0/3.0*zy-2.0*zx*zy/(3.0*(zx2*zx2+zy2*zy2+2.0*zx2*zy2));
                                                // test na přiblížení ke kořenům polynomů
                if (DIST2(zxn, zyn, rootx[0], rooty[0])<EPSILON ||
                    DIST2(zxn, zyn, rootx[1], rooty[1])<EPSILON ||
                    DIST2(zxn, zyn, rootx[2], rooty[2])<EPSILON) break;
                zx=zxn;
                zy=zyn;
            }
            if (iter==0) iter++;                // zabránit vznikům černých ostrůvků
            mapPalette(palette, iter*10, &r, &g, &b);
            if (DIST2(zxn, zyn, rootx[0], rooty[0])<EPSILON) r/=2;
            if (DIST2(zxn, zyn, rootx[1], rooty[1])<EPSILON) g/=2;
            if (DIST2(zxn, zyn, rootx[2], rooty[2])<EPSILON) b/=2;
            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);
            zx0+=(xmax-xmin)/pix->width;        // posun na další bod na řádku
        }
        zy0+=(ymax-ymin)/pix->height;           // posun na další řádek
    }
} 

3. Newtonovy fraktály pro polynomy vyšších stupňů

Oba výše uvedené demonstrační příklady sloužily „pouze“ k výpočtu a následnému vykreslení Newtonovy fraktální množiny odpovídající řešení polynomu určeného vztahem z3-1=0. Zcela stejnou metodou je však možné nalézat i kořeny polynomů vyšších stupňů, přičemž výsledné obrázky fraktálních množin budou samozřejmě odlišné, protože se v komplexní rovině bude nacházet více kořenů, ke kterým řešení bude konvergovat (polynomy jsou na celém definičním oboru diferencovatelné, což je podmínka pro použití Newtonovy iterační metody). V dalších dvou kapitolách si ukážeme obrázky vzniklé použitím Newtonovy iterační metody na polynom z4-1=0 a z8-1=0. Vzhledem k tomu, že dvojice zmíněných polynomů má své kořeny (řešení) umístěné v pravidelných intervalech na jednotkové kružnici se středem v počátku komplexní roviny, bude i výsledná fraktální množina vykazovat velkou symetrii, čehož je možné využít pro urychlení výpočtů.

4. Newtonova fraktální množina vytvořená pro polynom z4-1=0

Newtonova fraktální množina odpovídající řešení polynomu z4-1=0 je zajímavá především z programátorského hlediska. Díky symetrii obrázku vůči horizontální i vertikální ose je možné výpočet fraktálu zjednodušit a zejména značným způsobem urychlit, neboť stačí vypočítat pouze čtvrtinu obrazce – zbylé tři čtvrtiny obrazce se pouze zrcadlí, a proto se zde pouze provádí kopie barev pixelů, nikoli časově mnohem náročnější výpočet v iterační smyčce. Newtonova fraktální množina pro polynom z4-1=0 je zobrazena na šestém obrázku. Na tomto obrázku jsou použity čtyři barvy (červená, zelená, modrá a azurová) odpovídající čtyřem kořenům polynomu. Pátou barvou je barva černá, kterou jsou vykresleny pixely, pro něž nebylo řešení pro daný počet iterací nalezeno. Pro vytvoření sedmého obrázku byla použita modifikovaná metoda, u níž se zvýrazňuje počet iterací provedených za účelem nalezení kořenů.

fractals23_6
Obrázek 6: Newtonova fraktální množina polynomu z4-1=0

fractals23_7
Obrázek 7: Newtonova fraktální množina polynomu z4-1=0 vykreslená modifikovanou metodou

5. Newtonova fraktální množina vytvořená pro polynom z8-1=0

Newtonovu fraktální množinu pro polynom z8-1=0 je možné vykreslit ještě rychlejším způsobem než tomu bylo u polynomu čtvrtého stupně. Je to umožněno tím, že obrázek této fraktální množiny je symetrický jak kolem obou os (horizontální i vertikální), tak i okolo přímek se sklonem π/4 a 3π/4. Proto je nutné iterační metodou vypočítat pouze pixely ležící v jednom oktantu (tj. vypočítat osminu obrázku), barvy zbylých pixelů se pouze okopírují. Ukázky Newtonovy fraktální množiny vytvořené z polynomu z8-1=0 a vykreslené modifikovanou metodou jsou uvedeny na sedmém a osmém obrázku.

fractals23_8
Obrázek 7: Newtonova fraktální množina polynomu z8-1=0

fractals23_9
Obrázek 8: Další Newtonova fraktální množina polynomu z8-1=0

6. Neceločíselná mocnina u polynomu řešeného Newtonovou iterační metodou

Na desátém obrázku je zobrazena Newtonova fraktální množina příslušející polynomu s neceločíselnou mocninou (z matematického hlediska se vlastně ani nejedná o polynom). Z obrázku je patrné, že použití neceločíselné mocniny má za následek vznik ostrých hranic mezi jednotlivými částmi fraktálu. Parametry polynomu i způsob jeho obarvení byly získány z demonstračních dat přikládaných k programu FractInt. V případě použití neceločíselných mocnin není samozřejmě možné využít symetrie obrázku pro urychlení výpočtů.

fractals23_a
Obrázek 10: Newtonova fraktální množina pro polynom s neceločíselnou mocninou

7. Komplexní mocnina u polynomu řešeného Newtonovou iterační metodou

Myšlenku použití neceločíselných mocnin je možné dále rozšířit tím způsobem, že se místo reálného čísla použije číslo komplexní, tj. polynom bude nabývat tvaru zc-1=0, kde c je libovolné nenulové komplexní číslo. Na jedenáctém obrázku je zobrazen Newtonův fraktál pro polynom, jehož komplexní mocnina měla hodnotu 0+3i. Dvanáctý obrázek byl získán aplikací Newtonovy iterační metody na polynom s komplexní mocninou 3+3i. Podobně jako v předchozím případě, i při použití komplexních mocnin není výsledný obrázek symetrický, tj. výpočty nelze urychlit využitím symetrie.

fractals23_b
Obrázek 11: Newtonova fraktální množina pro polynom s komplexní mocninou 0+3i

fractals23_c
Obrázek 12: Newtonova fraktální množina pro polynom s komplexní mocninou 3+3i

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

V následujícím pokračování tohoto seriálu si popíšeme fraktály vytvořené v komplexní rovině Michaelem Barnsleym, po němž také získaly své jméno.

Našli jste v článku chybu?

5. 4. 2006 11:05

Dobry den,

tak jsem se dival do zdrojaku FractIntu, a vypada to, ze vypocty u Newtonovych mnozin vyssich mocnin (tj. zn-1=0) jsou tam reseny docela jednoduse. Cely vypocet je rozdelen do dvou kroku:

  1. Jedrive si vyjadri vsechny koreny daneho polynomu, coz je jednoduche, protoze koreny lezi na jednotkove kruznici a jsou po ni pravidelne rozmisteny. Jednim z korenu je hodnota 1+0i, takze se zacne od ni a provede se (n-1) kroku s rozdilem uhlu 2*Pi/n. To je ta prvni (a jednodussi cast).
  2. Po…

28. 3. 2006 13:00

Pavel Tisnovsky (neregistrovaný)
Dobry den, mam dojem, ze napriklad v programu FractInt jsou u fraktalu zalozenych na vzorcich z->z^x+c (Mandelbrotova a Juliova mnozina) a z^c-1=0 (Newtonova mnozina) nektera zjednoduseni implementovana. Ta zjednoduseni se IMHO aplikuji jak pred rozpisem cisel Z a C ve vzorcich na slozky, tak i po tomto rozpisu (spis nez o vysokou matematiku pujde o hrani si se zavorkami a Hornerovo schema). Podivam se do zdrojovych kodu, sice to neni snadne vycist, ale po chvili hledani to snad najdu [tusim,…
Vitalia.cz: „Připluly“ z Německa a možná obsahují jed

„Připluly“ z Německa a možná obsahují jed

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

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

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

Přehledná titulka, průvodci, responzivita

Root.cz: Telegram spustil anonymní blog Telegraph

Telegram spustil anonymní blog Telegraph

Vitalia.cz: Říká amoleta - a myslí palačinka

Říká amoleta - a myslí palačinka

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

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

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

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

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

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

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

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

Lupa.cz: Teletext je „internetem hipsterů“

Teletext je „internetem hipsterů“

DigiZone.cz: ČRa DVB-T2 ověřeno: Hisense a Sencor

ČRa DVB-T2 ověřeno: Hisense a Sencor

Měšec.cz: Jak vymáhat výživné zadarmo?

Jak vymáhat výživné zadarmo?

Vitalia.cz: Spor o mortadelu: podle Lidlu falšovaná nebyla

Spor o mortadelu: podle Lidlu falšovaná nebyla

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

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

Měšec.cz: mBank cenzuruje, zrušila mFórum

mBank cenzuruje, zrušila mFórum

120na80.cz: Jak oddálit Alzheimera?

Jak oddálit Alzheimera?

Vitalia.cz: Znáte „černý detox“? Ani to nezkoušejte

Znáte „černý detox“? Ani to nezkoušejte

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

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

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

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

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

EET: Totálně nezvládli metodologii projektu