Hlavní navigace

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

Pavel Tišnovský 4. 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, do jakých kategorií (či typů) se Juliovy množiny dělí. Také si ukážeme způsob vykreslování Juliových množin na několika demonstračních příkladech.

Obsah

1. Vykreslení Juliových množin
2. Funkce pro výpočet bodů ležících v Juliově množině
3. Typy Juliových množin
4. Demonstrační příklad: vykreslení Juliovy množiny
5. Demonstrační příklad: změna měřítka a posun obrazce
6. Demonstrační příklad: změna komplexní konstanty c
7. Obsah dalšího pokračování tohoto seriálu

1. Vykreslení Juliových množin

Pro vykreslování Juliových množin je použit postup, který je v mnohém podobný postupu vykreslení v další části popsané Mandelbrotovy množiny. Každému bodu v komplexní rovině je přiřazena určitá hodnota z0, která odpovídá souřadnicím bodu, tj. jeho reálné a imaginární složce. Pro tuto hodnotu a pro hodnotu c (která je pro danou Juliovu množinu konstantní) je zjištěno, zda posloupnost z0, z1, …zn diverguje či nikoliv. Pokud posloupnost diverguje, tj. velikost |zi| překročí hodnotu 2, bod o souřadnicích odpovídajících hodnotě z0neleží uvnitř Juliovy množiny. Pokud naopak posloupnost po zadaném maximálním počtu iterací nediverguje (tj. velikost |zn| nepřekročí hodnotu 2), je právě zpracovávaný bod z0 prohlášen za prvek dané Juliovy množiny. Každá Juliova množina je charakterizována komplexní konstantou c, která do značné míry ovlivňuje tvar množiny, tj. body, které leží uvnitř množiny.

Algoritmus pro zjištění, zda bod leží uvnitř Juliovy množiny, lze v neformálním programovacím jazyce zapsat následujícím způsobem:

  1. nastav celočíselnou proměnnou iter:=0
  2. nastav komplexní proměnnou z:=pozice_bodu_v_kom­plexní_rovině
  3. pokud iter<MaxIter prováděj smyčku:
  4.     nastav z:=z2+c
  5.     jestliže |z|>2 bod neleží v Juliově množině; konec algoritmu
  6.     nastav iter:=iter+1
  7. konec iterační smyčky
  8. bod leží uvnitř Juliovy množiny; konec algoritmu

Výše uvedený algoritmus lze přepsat do reálného programovacího jazyka, v našem případě do jazyka C. V následující kapitole je uvedena funkce pro výpočet všech bodů v určené oblasti komplexní roviny. V této funkci si všimněme skutečnosti, že komplexní hodnota c (v programu je uložena v reálných proměnných nazvaných cx a cy) je pevně daná uživatelem, například na základě interaktivního dialogu, zatímco počáteční hodnota posloupnosti z0 (v programu je uložena v reálných proměnných zx a zy) se mění podle polohy testovaného bodu v komplexní rovině. Vzhledem k tomu, že je hodnotac zadávána uživatelem, existuje nekonečné množství Juliových množin. Jak již víme z předchozího pokračování tohoto seriálu, má smysl uvažovat pouze o hodnotách c, pro něž platí vztah |c|<2.

Frac 11 - 1

Obrázek 1: Výřez Juliovy množiny

2. Funkce pro výpočet bodů ležících v Juliově množině

Funkce recalcJulia() provádí výpočet bodů ležících v Juliově množině na základě několika zadaných parametrů:

  • V parametrech width a height je specifikována velikost mřížky, ve které se body počítají. Čím je hodnota těchto parametrů větší, tím jemnější mřížka (při zobrazování pixmapa) bude vytvořena a samozřejmě se úměrně prodlouží i doba výpočtu.
  • V parametrech xmin, xmax, ymin a ymax jsou specifikovány mezní pozice počítaných bodů v komplexní rovině. Tyto body leží v osově orientovaném obdélníku a hodnota parametrů určuje vzdálenost stran obdélníka od reálné a imaginární osy. Vzhledem k tomu, že pro neprázdné Juliovy množiny platí |c|<2, měly by být všechny čtyři popisované parametry v absolutní hodnotě menší než 2.
  • V parametrech cx a cy je předána hodnota komplexní konstanty c, která určuje tvar Juliovy množiny. Parametr cx odpovídá reálné složce c, parametr cy imaginární složce. Pojmenování parametrů souvisí se způsobem zobrazení Juliovy množiny na obrazovce, kdy reálná osa v komplexní rovině odpovídá horizontálnímu směru a imaginární složka směru vertikálnímu.
  • V posledním parametru maxiter je předán maximální počet iterací. Pokud iterační výpočet dosáhne tohoto počtu iterací a přitom není splněna podmínka |zi|>2, je daný bod prohlášen za prvek Juliovy množiny, což ale není z matematického hlediska korektní. Čím vyšší je počet iterací, tím přesnější je výpočet, ale za cenu prodloužení doby výpočtu.
//-----------------------------------------------------------------------------
// Výpočet bodů ležících v Juliově množině
//-----------------------------------------------------------------------------
void recalcJulia(int    width,              // velikost bitmapy či mřížky
                 int    height,             // pro kterou se body počítají
                 double xmin,
                 double xmax,               // mezní pozice
                 double ymin,               // v komplexní rovině
                 double ymax,
                 double cx,                 // parametry Juliovy množiny
                 double cy,                 // - komplexní konstanta C
                 int    maxiter)            // maximální počet iterací
{
    int         i, j, iter;                 // počitadla smyček
    double      zx, zy;                     // hodnota komplexní proměnné Z
    double      zx2, zy2;                   // druhé mocniny složek proměnné Z
    double      x,y;                        // pozice v komplexní rovině

    y=ymin;
    for (j=0; j<height; j++) {              // pro všechny řádky mřížky
        x=xmin;
        for (i=0; i<width; i++) {           // pro všechny sloupce mřížky
            zx=x;                           // nastavit počáteční hodnotu
            zy=y;                           // proměnné Z
            iter=0;                         // příprava iterační smyčky

            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;              // výpočet nové hodnoty Z
                iter++;                     // zvýšit hodnotu počitadla iterací
            } while (iter<maxiter && (zx2+zy2)<4.0);// ukončovací test smyčky

            // výpis výsledku, který se liší podle toho, zda
            // bod leží uvnitř množiny či vně (posloupnost diverguje)
            printf("point [%5.3f+%5.3fi]: %s\n", x, y, (iter==maxiter) ? "in" : "out");

            x+=(xmax-xmin)/width;           // posun na další bod v řádku
        }
        y+=(ymax-ymin)/height;              // posun na další řádek v komplexní rovině
        printf("row %d, to do %d\n", j+1, height-j-1);// výpis kontrolní zprávy
    }
} 
Frac 11 - 2

Obrázek 2: Juliova množina s upravenou paletou barev

3. Typy Juliových množin

Jak již bylo v první kapitole, existuje nekonečné množství Juliových množin, které se od sebe liší hodnotou c, jež je použita při výpočtu bodů ležících uvnitř množiny. Juliovy množiny lze v závislosti na hodnotě c rozdělit na tři typy:

  1. Pro některé hodnoty c tvoří body ležící v Juliově množině spojitou oblast, to znamená, že každé dva body v takovéto Juliově množině je možné navzájem spojit určitou křivkou tak, že celá křivka leží uvnitř Juliovy množiny. Tato oblast je vždy jedna, neexistují tedy například navzájem izolované „ostrovy“.
  2. Pro jiné hodnoty c jsou jednotlivé body tvořící Juliovu množinu zcela izolovány, tj. v jejich okolí neexistuje další bod, který by ležel v Juliově množině. Taková „rozložená“ Juliova množina se nazývá Fatouův prach (Fatou dust) nebo také Cantorův prach (Cantor dust).
  3. Třetí možnost leží na hranici obou předchozích. Body ležící uvnitř Juliovy množiny sice nejsou vzájemně izolovány, ale současně netvoří žádnou plochu (body na úsečce také nejsou izolovány, ale úsečka má nulovou plochu).

Vztah mezi hodnotou komplexní konstanty c a typem Juliovy množiny je velmi složitý a při jeho detailním zkoumání byla nalezena „mapa“ všech Juliových množin – Mandelbrotova množina (ta bude podrobněji popsána v dalším pokračování tohoto seriálu). Na následující trojici obrázků jsou zobrazeny všechny tři popsané typy Juliových množin. Na třetím obrázku je zobrazena spojitá Juliova množina, jejíž prvky (body) tvoří souvislou plochu. Na obrázku čtvrtém je zobrazena Juliova množina na hranici spojitosti – body ležící v množině je možné navzájem propojit, ale tvoří nulovou plochu. Na pátém obrázku je zobrazen Cantorův, resp. Fatouův prach – Juliova množina tvořená pouze izolovanými body, které není možné (v rámci množiny) navzájem propojit. Body, které leží uvnitř dané Juliovy množiny, odpovídají na obrázcích pixelům s nastavenou černou barvou. Body ležící vně množiny jsou obarveny podle zeleno-žluté barevné škály (palety) tak, že barva pixelu odpovídá číslu iterace, ve které bylo zjištěno, že bod není součástí Juliovy množiny. Čím světlejší je pixel, tím více iterací bylo zapotřebí k dosažení podmínky |zi|>2.

Frac 11 - 3

Obrázek 3: Spojitá Juliova množina s vnitřními body a nenulovou plochou

Frac 11 - 4

Obrázek 4: Juliova množina na hranici spojitosti, tj. bez vnitřních bodů (s nulovou vnitřní plochou)

Frac 11 - 5

Obrázek 5: Cantorův prach – Juliova množina tvořená pouze izolovanými body

4. Demonstrační příklad: vykreslení Juliovy množiny

Po překladu a spuštění prvního demonstračního příkladu se zobrazí Juliova množina s komplexní konstantou c nastavenou na hodnotu -0,771+0,115i. Zobrazená pixmapa obsahuje pouze pixely ve stupních šedi, kde světlost pixelu odpovídá číslu iterace, při které se zjistilo, že bod odpovídající pixelu nepatří do Juliovy množiny. V případě, že bod do Juliovy množiny patří, je mu přiřazena největší světlost. V programu je vytvořena procedura filterPixmap(), která zajišťuje filtraci vzniklé pixmapy tak, aby byla pokryta celá škála světlostí i v případě, že maximální počet iterací je nastaven na menší hodnotu než 255. Volání této procedury je samozřejmě možné odstranit, nebo zcela změnit způsob výpočtu barvy jednotlivých pixelů. Na programových řádcích 41 a 42 je možné měnit hodnotu komplexní konstanty c:

#define CX     -0.771
#define CY      0.115 

Ovládání prvního demonstračního příkladu je sepsáno v následující tabulce:

Klávesy použité v prvním demonstračním 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
Q ukončení tohoto demonstračního příkladu
Esc má stejný význam jako klávesa Q

Zdrojový kód prvního demonstračního příkladu je uložený ke stažení, k dispozici je i HTML verze s obarvenou syntaxí.

Frac 11 - 6

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

5. Demonstrační příklad: změna měřítka a posun obrazce

Po překladu a spuštění druhého demonstračního příkladu se zobrazí Juliova množina s komplexní konstantou c=-0,188+0,666i. Na rozdíl od prvního demonstračního příkladu je možné měnit pohled na Juliovu množinu, tj. mapování mezi pixely na obrazovce a polohami bodů v komplexní rovině. Pomocí kurzorových šipek se celým obrazcem pohybuje o cca pět procent ve vybraném směru. Pomocí kláves [Page Up] a [Page Down] se mění měřítko obrazce – tzv. zoom. Popis všech klávesových zkratek je uveden v následující tabulce.

Klávesy použité ve druhém demonstračním 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
š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
Q ukončení tohoto demonstračního příkladu
Esc má stejný význam jako klávesa Q

Zdrojový kód druhého demonstračního příkladu je uložený pro stažení, k dispozici je samozřejmě i HTML verze s obarvenou syntaxí.

Frac 11 - 7

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

Frac 11 - 8

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

6. Demonstrační příklad: změna komplexní konstanty c

Dnešní třetí demonstrační příklad se od předchozích dvou demonstračních příkladů liší v tom, že je možné interaktivně měnit hodnotu komplexní konstanty c a tím ovlivňovat tvar zobrazené Juliovy množiny. Změna reálné části konstanty c se provádí pomocí kláves [1] a[2], změna imaginární části pomocí kláves [3] a [4]. V dalších pokračováních tohoto seriálu si ukážeme, jak je možné konstantu c měnit podle polohy kurzoru v obrázku Mandelbrotovy množiny, prozatím si však musíme vystačit s ovládáním pomocí klávesnice:

Klávesy použité ve třetím demonstračním 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
1 snížení reálné části konstanty c o 0.01
2 zvýšení reálné části konstanty c o 0.01
3 snížení imaginární části konstanty c o 0.01
4 zvýšení imaginární části konstanty c o 0.01
š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
Q ukončení tohoto demonstračního příkladu
Esc má stejný význam jako klávesa Q

Zdrojový kód třetího demonstračního příkladu je uložený ke stažení, k dispozici je, podobně jako u předchozích příkladů, i HTML verze s obarvenou syntaxí.

Frac 11 - 9

Obrázek 9: Screenshot třetího demonstračního příkladu

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

V dalším pokračování tohoto seriálu si popíšeme Mandelbrotovu množinu, která představuje jakousi mapu všech možných tvarů Juliových množin. Současně se jedná o nejznámější fraktál vůbec, který je zobrazený v nesčetném množství publikací a jehož algoritmus používá mnoho programů pro generování fraktálních obrazců.

Našli jste v článku chybu?

4. 1. 2006 16:20

To ano, ale to lib-ko je tam pro Visual Studio. Ja radeji pro MinGW pouzivam starsi GLUT, ten sice neobsahuje rozsireni "pro hry" (zmena rozliseni atd.), ale zato se bez problemu slinkuje i s dalsimi prekladaci, vcetne starych Borlandu (ty jsme pouzivali ve skole).
Podnikatel.cz: K EET. Štamgast už peníze na stole nenechá

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

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

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

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

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

DigiZone.cz: ČRo rozšiřuje DAB do Berouna

ČRo rozšiřuje DAB do Berouna

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

Přehledná titulka, průvodci, responzivita

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

EET: Totálně nezvládli metodologii projektu

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

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

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

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

Vitalia.cz: Baletky propagují zdravotní superpostel

Baletky propagují zdravotní superpostel

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

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

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

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

Sony KD-55XD8005 s Android 6.0

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

Jak vymáhat výživné zadarmo?

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

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

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

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

Root.cz: Vypadl Google a rozbilo se toho hodně

Vypadl Google a rozbilo se toho hodně

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

1. den EET? Problémy s pokladnami

Lupa.cz: Teletext je „internetem hipsterů“

Teletext je „internetem hipsterů“

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

Rakovina oka. Jak ji pozná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