Hlavní navigace

Fractals Everywhere?

Pavel Tišnovský 13. 3. 2007

Jedna z nejznámějších knížek pojednávajících o fraktálech se jmenuje "Fractals Everywhere". Tímto názvem nám autor, jímž není nikdo jiný než Michael Barnsley, naznačuje, že fraktální struktury můžeme vidět všude kolem sebe. Ukazuje se však, že ne všechny obrázky, které na první pohled vypadají "fraktálově", opravdu fraktály jsou.

Obsah

1. Fractals Everywhere?
2. Moaré s kružnicovým vzorkem
3. Funkce pro výpočet kružnicového vzorku
4. První demonstrační příklad – základní moaré s kružnicovým vzorkem
5. Rozšíření repertoáru funkcí při tvorbě moaré
6. Druhý demonstrační příklad – použití dalších typů funkcí při tvorbě moaré
7. Odkazy na další informační zdroje
8. Obsah dalšího pokračování tohoto seriálu

1. Fractals Everywhere?

Jak již bylo napsáno v perexu článku, budeme se dnes zabývat obrázky, které na první pohled vypadají jako fraktály, ale ve skutečnosti se o fraktály nejedná, protože struktury, které jsou na těchto obrázcích zobrazeny, nejsou nezávislé na změně měřítka ani soběpodobné. Přesněji řečeno – v určitých mezích měřítka, tj. míry zvětšení, můžeme soběpodobnost pozorovat, ale jakmile tyto meze překročíme, získáme obrázek s pravidelnými strukturami, které nemají s fraktály prakticky již nic společného.

Konkrétně se budeme zabývat velmi jednoduchou metodou pro tvorbu moaré s kružnicovým vzorkem. Tuto metodu lze zobecnit a vytvořit i jiné vzorky než kruhové. Příště si také ukážeme slavnou Perlinovu funkci, která se velmi často používá při tvorbě procedurálních textur, například v mnoha modelovacích programech (3D modelování) či raytracerech (typickým zástupcem těchto raytracerů je již několikrát zmiňovaný POVRay).

fractals71_1
Obrázek 1: Perlinova funkce použitá pro tvorbu procedurálních textur mraků v atmosféře planety

2. Moaré s kružnicovým vzorkem

Velmi zajímavý vzorek založený na efektu moaré vytvořil John Connett z Minnesotské univerzity. O tomto vzorku, který ve své podstatě názorně ukazuje vliv aliasu při tvorbě rastrových obrázků, později pojednal i A. K. Dewdney v časopise Scientific American. Tento vzorek je generovaný velmi jednoduchým způsobem: každému pixelu ve vytvářeném rastrovém obrázku (pixmapě) je přiřazena dvojice souřadnic [x, y]. Tyto souřadnice obecně neodpovídají celočíselným indexům pixelu, které můžeme například označit [i, j].

Posléze je pro každý pixel vypočtena hodnota z podle vztahu z=x2+y2. To je vše – žádné iterace ani testování na bailout se neprovádí, pouze se na základě vypočtené hodnoty z vybere vhodná barva z barvové palety a pixel se obarví. Už z tohoto popisu nám může být zřejmé, že se nejedná o fraktál, protože bez opakovaného výpočtu nelze získat soběpodobné struktury.

fractals71_2
Obrázek 2: Moaré s kružnicovým vzorkem

Tímto přímočarým a jednoduchým způsobem je možné vytvářet fantastické vzorky, pouze stačí měnit barvovou paletu (ideální jsou plynulé přechody mezi barvami – gradient) a měřítko, pomocí kterého se převádí celočíselné pozice pixelů v rastru [i, j] na souřadnice [x, y]. Zbývá nám odpovědět na otázku, proč tento vzorek není fraktálem. Odpověď je jednoduchá – při neustálém zvětšování obrázku se dostaneme k limitu, na němž již není žádný vzorek patrný.

Jinými slovy to znamená, že mezi sousedními pixely jsou tak malé rozdíly v souřadnicích [x, y], že i jejich druhá mocnina z=x2+y2 má prakticky stejnou hodnotu, takže je oběma pixelům přiřazena stejná barva. Tento limit u fraktálů při žádném měřítku neobjevíme – například hranice Mandelbrotovy množiny či množin Juliových je při jakémkoli měřítku stále stejně složitá a především soběpodobná.

fractals71_3
Obrázek 3: Mez zvětšení, při kterém již kružnicový vzorek začíná mizet

To, že moaré s kružnicovým vzorkem netvoří fraktální strukturu, však nic nemění na tom, že se pomocí něho dají vytvářet zajímavé obrázky a textury, proto si jeho tvorbu podrobněji popíšeme v následujících dvou kapitolách. Praktická poznámka: pro 3D textury není tento vzorek vhodný, protože při různém pohledu na scénu (natáčení, přibližování apod.) dochází k několikanásobnému aliasu, který se projevuje nežádoucím poblikáváním a aplikace antialiasingu naopak může zcela vymazat původní detaily v textuře.

fractals71_4
Obrázek 4: Při určitém měřítku narazíme na limit, pod kterým již nevidíme další detaily (viz střed obrázku, při jehož zvětšení již další detaily nebudou patrné)

3. Funkce pro výpočet kružnicového vzorku

Algoritmický zápis funkce provádějící výpočet kružnicového vzorku je velmi jednoduchý, zvláště když využijeme dříve popsanou funkci pro mapování barvové palety (tu jsme použili například při obarvení Mandelbrotovy množiny, množin Juliových nebo v minulé části pro Markus-Lyapunovovy fraktály). Jako parametry této funkce je zadána pixmapa, do které bude prováděno vykreslování (obarvování jednotlivých pixelů), číslo (index) barvové palety a čtveřice souřadnic, které specifikují dva krajní body obdélníka ležícího v rovině. Souřadnice [xmin, ymin] určují levý dolní roh obdélníka, souřadnice [xmax, ymax] pak pravý horní roh. Vzdálenost mezi oběma rohy vlastně určuje měřítko zvětšení vzorku, podrobnosti budou uvedeny v následující kapitole. Zdrojový text funkce může být v programovacím jazyku C napsán například následujícím způsobem:

//-----------------------------------------------------------------------------
// Funkce provádějící výpočet moaré s kružnicovým vzorkem
//-----------------------------------------------------------------------------
void recalcCirclePattern(pixmap *pix,           // pracovní pixmapa do které se vykresluje
                    int    palette,             // číslo barvové palety (0-9)
                    double xmin,                // meze fraktálu v rovině
                    double ymin,                // levý dolní roh
                    double xmax,
                    double ymax)                // pravý horní roh
{
    int x, y, z;                                // počitadla smyček a celočíselná hodnota z
    double x1, y1, x2, y2;                      // přepočtená pozice pixelu

    y1=ymin;
    for (y=0; y<pix->height; y++) {             // pro všechny řádky pracovní pixmapy
        x1=xmin;                                // počáteční hodnota x1
        for (x=0; x<pix->width; x++) {          // pro všechny pixely na řádku
            unsigned char r, g, b;
            x1+=(xmax-xmin)/pix->width;         // posun na další hodnotu x1
            x2=x1*x1;                           // výpočet x1^2 a x2^2
            y2=y1*y1;
            z=x2+y2;                            // výpočet hodnoty z
            mapPalette(palette, z & 0xff, &r, &g, &b); // mapování na barvovou paletu
            putpixel(pix, x, y, r, g, b);       // a vytištění pixelu
        }
        // přechod na další řádek
        y1+=(ymax-ymin)/pix->height;            // posun na další hodnotu y1
    }

}

//-----------------------------------------------------------------------------
// finito
//----------------------------------------------------------------------------- 

fractals71_5
Obrázek 5: Další ukázka moaré s kružnicovým vzorem

4. První demonstrační příklad – základní moaré s kružnicovým vzorkem

V dnešním prvním demonstračním příkladu je implementována výše uvedená funkce recalcCirclePat­tern() pro tvorbu moaré s kružnicovým vzorkem. Po překladu a spuštění tohoto příkladu se vytvoří padesát obrázků se jmény circle00.tgacircle49.tga, všechny vygenerované obrázky mají shodné rozlišení 400×400 pixelů, tj. jsou čtvercové, a jsou uloženy v plnobarevném (truecolor) formátu. Každý obrázek obsahuje jeden kružnicový vzor při odlišném nastavení zvětšení. Také barvová paleta je periodicky střídána.

Všechny obrázky s kružnicovým vzorkem, které jsou v tomto článku uvedeny, jsou vytvořeny právě za použití prvního demonstračního příkladu, jehož zdrojový kód můžete získat zde, popř. i jako HTML soubor s obarvenou syntaxí.

fractals71_6
Obrázek 6: Textura vytvořená v prvním demonstračním příkladu

fractals71_7
Obrázek 7: Další textura vytvořená v prvním demonstračním příkladu

5. Rozšíření repertoáru funkcí při tvorbě moaré

Předchozí příklad je možné rozšířit o volbu dalších funkcí, které se použijí při výpočtu moaré. Výběr funkcí je takřka libovolný, pouze je žádoucí, aby při výpočtech docházelo k přetékání přes hodnotu 255 – tím vzniká požadovaný efekt tvořící základ vzorku. Některé níže uvedené „vhodné“ funkce je možné nalézt například na adrese http://www.ed­daardvark.co.uk/pyt­hon_patterns/cir­cle_pattern.html, další funkce si můžeme podle svého uvážení sami doplnit. To je případ funkce xyfun2(), která je použita v dnešním druhém demonstračním příkladu.

Označení funkce Tvar funkce
circle zfactor×(x × x + y × y)
anticircle zfactor×(x × x – y × y)
xyfun zfactor×(x × x + xyfactor × x × y + y × y)
x3y3 zfactor×(x × x × x + y × y × y)
x4y4 zfactor×(x × x × x × x + y × y × y × y)
x3y3_xy zfactor×(x × x × x + y × y × y) / (x × y)
xpy_xmy zfactor×(x + y) / (x – y)

fractals71_8
Obrázek 8: Moaré vypočtené s pomocí funkce nazvané x3y3

6. Druhý demonstrační příklad – použití dalších typů funkcí při tvorbě moaré

Dnešní druhý demonstrační příklad, jehož zdrojový kód je přístupný z tohoto odkazu (samozřejmě existuje také HTML verze s obarvenou syntaxí) vznikl rozšířením příkladu prvního o možnost volby funkce, která je použita při tvorbě moaré. Tato funkce musí akceptovat dva parametry – přepočtené souřadnice pixelu – a vracet hodnotu, která je použita při přístupu do barvové palety. Oba parametry i návratová hodnota je typu double, tj. numerická hodnota uložená ve formátu pohyblivé řádové čárky se zvýšenou („dvojitou“) přesností.

Vlastní předávání vybrané funkce pro výpočet moaré je možné v programovacím jazyku C realizovat přes ukazatel na funkci, jak to ostatně je ukázáno v následujícím fragmentu kódu. Vzhledem k tomu, že samotný identifikátor funkce bez závorek představuje v céčku její adresu, je použití odkazů na funkce velmi jednoduché a přímočaré (na rozdíl od některých jiných programovacích jazyků, kde je zapotřebí tento užitečný programátorský obrat řešit například pomocí rozhraní či hierarchie objektů):

//-----------------------------------------------------------------------------
// Základní funkce pro výpočet moaré
//-----------------------------------------------------------------------------
double circle(double x, double y)
{
    return x*x+y*y;
}



//-----------------------------------------------------------------------------
// Alternativní funkce pro výpočet moaré - anticircle
//-----------------------------------------------------------------------------
double anticircle(double x, double y)
{
    return x*x-y*y;
}



//-----------------------------------------------------------------------------
// Alternativní funkce pro výpočet moaré - x3y3
//-----------------------------------------------------------------------------
double x3y3(double x, double y)
{
    return x*x*x+y*y*y;
}



//-----------------------------------------------------------------------------
// Alternativní funkce pro výpočet moaré - x4y4
//-----------------------------------------------------------------------------
double x4y4(double x, double y)
{
    return x*x*x*x+y*y*y*y;
}



//-----------------------------------------------------------------------------
// Alternativní funkce pro výpočet moaré - xyfun s pevně nastavenou
//                                         multiplikativní konstantou
//-----------------------------------------------------------------------------
double xyfun(double x, double y)
{
    return x*x+y*y+x*y*1.5;
}



//-----------------------------------------------------------------------------
// Funkce provádějící výpočet moaré s obecným vzorkem
//-----------------------------------------------------------------------------
void recalcPattern( pixmap *pix,                // pracovní pixmapa
                    int    palette,             // číslo barvové palety
                    double xmin,                // meze fraktálu v rovině
                    double ymin,                // levý dolní roh
                    double xmax,
                    double ymax,                // pravý horní roh
                    double (*fce)(double, double)) // funkce provádějící vlastní výpočet
{
    int x, y, z;                                // počitadla smyček a celočíselná hodnota z
    double x1, y1;                              // přepočtená pozice pixelu

    y1=ymin;
    for (y=0; y<pix->height; y++) {             // pro všechny řádky pracovní pixmapy
        x1=xmin;                                // počáteční hodnota x1
        for (x=0; x<pix->width; x++) {          // pro všechny pixely na řádku
            unsigned char r, g, b;
            x1+=(xmax-xmin)/pix->width;         // posun na další hodnotu x1
            z=(double)fce(x1, y1);              // výpočet vzorku
            mapPalette(palette, z & 0xff, &r, &g, &b); // mapování na barvovou paletu
            putpixel(pix, x, y, r, g, b);       // a vytištění pixelu
        }
        // přechod na další řádek
        y1+=(ymax-ymin)/pix->height;            // posun na další hodnotu y1
    }

}

// Ukázka volání funkce počítající celý obrázek.

// Všimněte si specifikace ukazatele na funkci -
// v ANSI/ISO céčku je samotný identifikátor funkce bez závorek
// chápán jako ukazatel na tuto funkci, není tedy nutné
// psát výraz pro získání její adresy pomocí operátoru &
// ani jiných obratů.
recalcPattern(pix, i%10, 0, 0, mez+15, mez+15, xyfun2);



//-----------------------------------------------------------------------------
// finito
//----------------------------------------------------------------------------- 

fractals71_9
Obrázek 9: Moaré vypočtené s pomocí funkce nazvané xyfun2

7. Odkazy na další informační zdroje

  1. Barnsley Michael:
    Fractals Everywhere,
    Academic Press Inc., 1988, ISBN 0–12–079062–9
  2. Dewdney A. K:
    Computer Recreations,
    časopis Scientific American
  3. Perlin K. and Hoffert E. M.:
    Hypertexture,
    Computer graphics, Volume 23, Number 3, July 1989, pages 253–262
  4. Peitgen Heinz-Otto, Jurgens Hartmut, Saupe Dietmar:
    Chaos and Fractals: New Frontiers of Science,
    Springer-Verlag, New York, 1992
  5. Peitgen Heinz-Otto, Richter Peter:
    The Beauty of Fractals,
    Springer-Verlag, New York, 1986, ISBN~0–387–15851–0
  6. POV-Team:
    POV-Ray v3.1g User's documen­tation,
    Elektronická dokumentace k programu POV-Ray, 1999
  7. Wegner Timothy, Tyler Bert:
    Fractal Creations, Second Edition,
    The Waite Group Press, 1993
  8. WWW stránky raytraceru POV-Ray:
    http://www.po­vray.org
  9. WWW stránky programu FractInt:
    http://www.frac­tint.org
  10. Circle patterns:
    http://www.ed­daardvark.co.uk/pyt­hon_patterns/cir­cle_pattern.html
  11. Perlin Noise and Turbulence:
    http://local.was­p.uwa.edu.au/~pbou­rke/texture_co­lour/perlin/

fractals71_a
Obrázek 10: Moaré vypočtené s pomocí funkce nazvané x4y4

fractals71_b
Obrázek 11: Další moaré vypočtené s pomocí funkce nazvané xyfun2

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

V následující části tohoto seriálu dokončíme téma „nefraktálů“ popisem slavné Perlinovy funkce. Ukážeme si její praktické použití zejména při tvorbě procedurálních textur, především v různých modelovacích programech a raytracerech.

fractals71_c
Obrázek 12: Moaré vypočtené s pomocí funkce nazvané xyfun
Našli jste v článku chybu?

16. 3. 2007 9:58

... (neregistrovaný)
Tak ona ta technologie je dnes také někde jinde oproti době, kdy běžné 17" LCD monitory stály 12 tisíc. 6bitové barvy mají dnes většinou jen low-end modely, pozorovací úhly u technologií jako S-PVA nebo S-IPS jsou také nesrovnatelně lepší, stejně tak i doby odezvy, atd. Netvrdím, že tam stále některé problémy nejsou, ale pokrok je určitě znatelný.

15. 3. 2007 17:33

Posuzovani je slozite, vetsina LCD panelu stejne sjizdi ze stejne linky, na nalepku nehledte (AOC, Adi, Fujitsu - to stejne). Asi by melo smysl porovnavat vyrobky stejne cenove kategorie, ale i to brzo sklouzne do debaty ne nepodobne nekonecnym diskusim na tema LP vs. CD (analog vs digital).

Osobne jsem take zvolil LCD, a to v dobe, kdy bylo jeste docela drahe (17" za 12000 bez DPH), ale ty vyse zminene problemy tam jsou patrne - kazda technologie ma holt svoje a i CRTcka porad maji uplatn…

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

Přehledná titulka, průvodci, responzivita

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

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

Root.cz: 250 Mbit/s po telefonní lince, když máte štěstí

250 Mbit/s po telefonní lince, když máte štěstí

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: Seznam mění vedení. Pavel Zima v čele končí

Seznam mění vedení. Pavel Zima v čele končí

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

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

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

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

Horní cesty dýchací. Zkuste fytofarmaka

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

Jsou čajové sáčky toxické?

Vitalia.cz: Mondelez stahuje rizikovou čokoládu Milka

Mondelez stahuje rizikovou čokoládu Milka

Podnikatel.cz: Babiš: E-shopy z EET možná vyjmeme

Babiš: E-shopy z EET možná vyjmeme

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

Rakovina oka. Jak ji poznáte?

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

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

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

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

Vitalia.cz: To není kašel! Správná diagnóza zachrání život

To není kašel! Správná diagnóza zachrání život

Lupa.cz: Teletext je „internetem hipsterů“

Teletext je „internetem hipsterů“

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

Jak vymáhat výživné zadarmo?

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

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

Dáte si jahody s plísní?

Vitalia.cz: Baletky propagují zdravotní superpostel

Baletky propagují zdravotní superpostel