Hlavní navigace

Fractals Everywhere?

Pavel Tišnovský

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…