Hlavní navigace

Linearizované systémy iterovaných funkcí

27. 6. 2006
Doba čtení: 10 minut

Sdílet

V dnešním pokračování seriálu budou popsány takzvané linearizované systémy iterovaných funkcí (L-IFS), jejichž aplikací je možné generovat dvoudimenzionální i třídimenzionální obrazce, které vykazují základní fraktální charakteristiky. Vytvářené obrazce se přitom do značné míry liší od obrazců vzniklých aplikací "klasických" IFS systémů.

Obsah

1. Úvodní informace o linearizovaných systémech iterovaných funkcí
2. Souvislost mezi systémy IFS a L-IFS
3. Reprezentace systémů L-IFS v operační paměti
4. Algoritmus vytváření fraktálního obrazce pomocí systémů L-IFS
5. Demonstrační příklad na vykreslení systémů L-IFS
6. Obsah dalšího pokračování tohoto seriálu

1. Úvodní informace o linearizovaných systémech iterovaných funkcí

Jak jste se již mohli dočíst v perexu tohoto článku, dnes se budeme zabývat takzvanými linearizovanými systémy iterovaných funkcí (Linearized Iterated Functions Systems: L-IFS), pomocí nichž je možné vytvářet a především iteraktivně měnit tvar a strukturu velmi pěkně vypadajících plošných i prostorových obrazců, které mají fraktální strukturu, tj. jsou soběpodobné a obsahují nekonečně mnoho detailů v různých měřítkách zobrazení. Dále bude v tomto a také v následujícím pokračování seriálu popsáno rozšíření těchto systémů o takzvanou matici posloupnosti transformací, která slouží k další modifikaci výsledného plošného či prostorového obrázku.

Oproti aplikacím, které využívají klasické systémy iterovaných funkcí (Iterated Function Systems – IFS – viz předchozí části tohoto seriálu) je možné s pomocí linearizovaných systémů iterovaných funkcí vytvářet obrazce interaktivně a s okamžitou zpětnou odezvou uživateli. Samozřejmě si také ukážeme demonstrační příklady, ve kterých budou linearizované systémy iterovaných funkcí využity.

V předchozích částech tohoto seriálu bylo popsáno několik způsobů navržených pro generování fraktálních obrazců na bázi systémů iterovaných funkcí IFS. Pro tyto účely je IFS systém zadán množinou transformací φ=0, φ1, … φn} a v případě použití algoritmu náhodné procházky RWA či M-RWA i množinou pravděpodobností jednotlivých transformací π=0, π1, … πn, }. Z hlediska potřeb algoritmu pro výpočet fraktálního obrazu (koláže) pomocí IFS systémů je tato reprezentace jistě přínosná, protože přímo odráží datové struktury používané při realizaci algoritmu. Nevýhodnou však začne tato prezentace být pro uživatele, který se snaží interaktivním a názorným způsobem vytvářet pomocí systémů IFS různé obrazce a tvary.

Pro snadné zadání a modifikaci IFS systému je nutné umožnit uživateli provádět všechny změny interaktivně (tj. v reálném čase) a v co nejvyšší míře i názorně. Místo transformací a jejich pravděpodobností (tj. číselných hodnot) totiž uživatel po právu vyžaduje grafické znázornění a přímou interaktivní manipulaci se symboly zobrazenými na obrazovce počítače. Důležité jsou zejména rychlé odezvy systému na operace, které uživatel provádí, neméně však také snadnost a názornost manipulace se symboly na obrazovce. Jednou z možností, jak tyto podmínky splnit, je vytvoření interaktivního editoru, který uživateli umožní zadat libovolný obrazec a potom tento obrazec složit (pokrýt) z transformovaných kopií toho samého obrazce. Uživatel ovšem musí vytvořit kvalitní pokrytí celého obrazce, kde se jednotlivé transformované kopie obrazce navzájem nepřekrývají.

Další možností, jak interaktivně vytvořit a následně editovat IFS systém (resp. výslednou koláž), je použití zde popisovaných linearizovaných systémů iterovaných funkcí L-IFS. Systémy L-IFS jsou navrženy tak, aby u jejich vytváření nebylo zapotřebí zadávat základní obrazec a posléze složitě provádět jeho pokrytí. Rozdíl mezi systémy IFS a L-IFS pro uživatele vyplývá především z odlišné reprezentace obou typů systémů v operační paměti počítače.

Zásadní odlišnost L-IFS systémů oproti IFS systémům však spočívá ve skutečnosti, že uživatel nemusí při tvorbě obrazce zadávat číselné hodnoty jednotlivých transformací ani jejich pravděpodobností. Místo toho může interaktivně měnit polohu řídicích bodů v ploše či prostoru. S tímto způsobem editace objektů je uživatel většinou dobře obeznámen, protože se v počítačové grafice velmi často používá, například pro vytváření parametrických křivek a ploch. Jak uvidíme v dalším textu, existují i další souvislosti mezi parametrickými křivkami a fraktálními obrazci generovanými pomocí systémů L-IFS. Jedná se například o existenci konvexní obálky tvořené řídicími body.

Za určité (velmi významné) rozšíření možností při práci se systémy L-IFS lze považovat volbu poměru dělení úsečky, který lze taktéž nastavovat graficky a interaktivně. Dalším rozšířením, kterým se budu v této části zabývat, je vytvoření a editace matice posloupnosti transformací. Její grafická reprezentace sice existuje (například ve formě šipek spojujících jednotlivé řídicí body), v tomto případě je však mnohdy výhodnější matici změnit přímo v zobrazené tabulce přechodů (viz další díl tohoto seriálu).

fractals35_1

Obrázek 1: L-IFS systém vykreslený pro různé konstanty ξ

2. Souvislost mezi systémy IFS a L-IFS

Mezi klasickými systémy iterovaných funkcí (v dalším textu budu tyto systémy označovat pouze jejich anglickou zkratkou IFS), které byly popsány v předchozích částech tohoto seriálu, a linearizovanými systémy iterovaných funkcí (pro tyto systémy budu dále používat anglickou zkratku L-IFS) existuje mnoho souvislostí. Z čistě matematického hlediska jsou totiž L-IFS podmnožinou IFS. Jak jsem již popsal dříve, je systém iterovaných funkcí tvořen množinou libovolných zobrazení, definovaných nad libovolným prostorem s definovanou metrikou. Při popisu a následné implementaci těchto systémů se však beze ztráty obecnosti omezím na Euklidovské prostory En a množinu zobrazení velmi často redukuji na lineární či dokonce pouze afinní transformace (podle implementace se jedná buď o 2D nebo 3D transformace, jejichž princip je však až na dimenzi totožný, proto je v dalším textu dále nerozlišuji). Mezi lineární transformace patří posun, rotace, změna měřítka a zkosení.

L-IFS systémy nad Euklidovským prostorem En jsou podmnožinou IFS systémů nad ekvivalentním prostorem v tom smyslu, že je v nich povoleno použití pouze některých afinních transformací, konkrétně transformací posunu, změny měřítka a zkosení. Toto omezení L-IFS systémů vyplývá především ze způsobu vytváření a interaktivní editace systémů L-IFS uživatelem, z čehož je odvozena i odlišná vnitřní reprezentace obou systémů. Vždy platí, že L-IFS systém lze převést na systém IFS, opačný převod však není vždy možný, zejména v případech, kdy jsou použity transformace rotace, které nelze v L-IFS systémech vyjádřit.

Při práci se systémy L-IFS je tedy možné nejdříve provést jejich převod na systémy IFS a teprve poté vytvářet (tj. generovat) plošný obrazec či prostorové těleso pomocí algoritmů prezentovaných v předchozí podkapitole. Mnohdy je však výhodnější (a v některých případech také rychlejší) tento převod neprovádět a použít modifikovaný algoritmus pro vytváření koláží, jehož popis bude uveden v dalším textu. Výhodou druhého přístupu je fakt, že systém stále zůstává jednoduše modifikovatelný. Množství paměťového prostoru potřebného pro uložení jednotlivých transformací je, jak uvidíme v dalším textu, pro L-IFS i IFS systémy přibližně stejné, podobně jako časová složitost vytváření fraktálních obrazců.

fractals35_2

Obrázek 2: Další systém L-IFS vykreslený pro různé konstanty ξ

3. Reprezentace systémů L-IFS v operační paměti

Linearizované systémy iterovaných funkcí L-IFS jsou v operační paměti počítače reprezentovány poněkud odlišným způsobem, než klasické systémy iterovaných funkcí IFS. Místo množiny transformací (lineární transformace jsou v operační paměti uloženy jako matice velikosti 3 × 3 prvky pro plošné útvary, resp. 4 × 4 prvky pro prostorová fraktální tělesa. V případě, že se nepoužívají homogenní souřadnice, je možné z matic vyloučit poslední sloupcový vektor) Φ je použita množina řídicích bodů C=(C1,… Cn), které mají podle dimenzionality vytvářeného obrazce buď dvě nebo tři souřadnice. Dále je zadán globální parametr ξ, představující poměr dělení úsečky u, která spojuje vždy dvojici, kterou tvoří řídicí bod Ci a právě vygenerovaný bod Piter, tj. jedná se o úsečku u=CiPiter. Hodnotou parametru ξ je reálné číslo v rozsahu (0, 1) – samotné hranice intervalu není možné použít.

Příklad reprezentace systému L-IFS se čtyřmi řídicími body C1C4 a dělícím poměrem ξ je zobrazen na následujícím (třetím) obrázku.

fractals35_3

Obrázek 3: Příklad reprezentace systému L-IFS se čtyřmi řídicími body a poměrem dělení úsečky ξ

Konvexní obal vytvořený z řídicích bodů Ci určuje vnější hranici, ve které se nachází atraktor celého generovaného fraktálního obrazce. Poměr dělení úsečky ξ udává, ve kterém místě bude při generování vytvořen nový bod Piter+1. Poloha nového bodu závisí na poloze vybraného řídicího bodu Ci a na bodu, který byl vygenerován v předchozím iteračním kroku. Vztah pro výpočet polohy nového bodu v každém iteračním kroku vypadá následovně:

Piter+1=ξ×Ci+(1-ξ)×Piter

Z předchozí rovnice vyplývá, že nový bod Piter+1 leží na úsečce u=CiPiter. Parametr ξ určuje poměr, podle kterého je úsečka rozdělena na dvě části. V místě tohoto rozdělení (tj. ve společném vrcholu dvou nově vytvořených úseček u1 a u2) leží nový bod Piter+1. Zatímco poloha řídicích bodů Ci má vliv pouze na lokální charakteristiky generovaného obrazce, má parametr dělení úsečky ξ vliv na celý obrazec:

  • Pro 0 < ξ < 1/2 bude vygenerovaný obrazec spíše nahodilý a nebude patrná jeho vnitřní struktura.
  • Pro 1/2 < ξ < 1 budou vygenerované body více přitahovány k atraktoru systému, který se tak stane dobře viditelný.
fractals35_4

Obrázek 4: Konstrukce fraktálního obrazce pomocí systémů L-IFS

4. Algoritmus vytváření fraktálního obrazce pomocí systémů L-IFS

Algoritmus generování plošného či prostorového fraktálního obrazce ze zadaného L-IFS systému lze v neformálním programovacím jazyce popsat následující sekvencí příkazů (konkrétní implementace tohoto algoritmu vytvořeného v programovacím jazyce C je uvedena v další kapitole):

  • Vstupy programu:
    1. Množina řídicích bodů C=(C1 … Cn), které leží buď v rovině E2 nebo prostoru E3.
    2. Poměr dělení úsečky ξ zadaný v rozsahu (0, 1).
    3. Maximální počet iterací itermax (celé kladné číslo)
    4. Počet startovních iterací iterstart, přičemž platí podmínka iterstart < itermax.
  • Výstup programu:
    1. Rastrový obrazec či prostorový objekt složený z množiny navzájem izolovaných bodů, který reprezentuje atraktor systému L-IFS.
  • Inicializační sekvence:
    1. Automaticky zvol počáteční polohu bodu P0, který bude v dalších iteračních krocích transformován. Poloha bodu P0 nemá na tvar výsledného fraktálního obrazce velký význam, proto lze většinou pro jednoduchost algoritmu dosadit P0=[0, 0] pro obrazec v rovině, resp. P0=[0, 0, 0] pro prostorový útvar.
    2. Nastav čítač počtu iterací iter:=0.
  • Hlavní smyčka:
    1. Dokud platí podmínka iter<itermax, opakuj smyčku:
    2.    Vygeneruj náhodné číslo rand v rozsahu (1, n), kde n je počet řídicích bodů C.
    3.    Vytvoř pomyslnou úsečku u z bodu Piter do bodu Crand.
    4.    Podle vztahu Piter+1=ξ×Ci+(1-ξ)×Piter vygeneruj novou pozici bodu Piter+1.
    5.    Pokud platí podmínka iter>iterstart, pak vykresli pixel na pozici bodu Piter, nebo na této pozici vygeneruj bod v prostoru.
    6.    Zvyš počitadlo smyčky: iter:=iter+1.
    7. Konec smyčky
  • Zpracování výstupních dat:
    1. V případě tvorby plošného objektu vykresli výsledný rastrový obrázek.
    2. V případě tvorby prostorového objektu tento objekt transformuj do roviny obrazovky a zobraz.
  • Konec programu.
fractals35_5

Obrázek 5: Fraktální obrázek (koláž) vygenerovaný ze systému L-IFS

5. Demonstrační příklad na vykreslení systémů L-IFS

Abstraktní tvar algoritmu pro výpočet plošného obrazce pomocí linearizovaných systémů iterovaných funkcí vypadá po přepsání do programovacího jazyka C následovně:

//-----------------------------------------------------------------------------
// Vykreslení Sierpinského trojúhelníku pomocí linearizovaného systému
// iterovaných funkcí L-IFS
//-----------------------------------------------------------------------------
void recalcL_IFS( pixmap *pix,                      // pixmapa pro vykreslování
                  int    maxiter,                   // maximální počet iterací
                  double scale,                     // měřítko obrazce
                  double xpos,                      // posun obrazce
                  double ypos,
                  double ksi,                       // konstanta ovlivňující tvar fraktálu
                  int    rf, int gf, int bf,        // příznaky barvových složek
                  int    dr, int dg, int db,        // přírustky barvových složek
                  DrawType drawType)                // způsob vykreslení
{
    int    iter=0;                                  // počitadlo iterací
    int    threshold=50;                            // hranice počtu iterací pro vykreslování

    double x, y;                                    // poloha iterovaného bodu
    double xn, yn;                                  // nová poloha iterovaného bodu
    int    k;                                       // číslo vybraného řídicího bodu

    unsigned char red=rf ? dr : 0;                  // reálné přírustky barvových složek
    unsigned char green=gf ? dg : 0;
    unsigned char blue=bf ? db : 0;

    unsigned char pal[8][3]={                       // barvová paleta
        {0xff, 0x00, 0x00},                         // pro zvýraznění oblastí jednotlivých
        {0x00, 0xff, 0x00},                         // řídicích bodů
        {0x00, 0x00, 0xff},
        {0xff, 0xff, 0x00},
        {0x00, 0xff, 0xff},
        {0xff, 0x00, 0xff},
        {0xff, 0xff, 0xff},
        {0x80, 0x80, 0x80},
    };

    double IFS_sierpinsky[][7]={                    // řídicí body Sierpinského trojúhelníku
        { 256,  366},
        {  56,   20},
        { 456,   20}
    };

    x=0;
    y=0;                                            // nastavení počáteční polohy bodu
    srand(0);

    while (iter++<maxiter*100) {                    // iterační smyčka
        k=rand()%3;
        xn=x*(1.0-ksi)+ksi*IFS_sierpinsky[k][0];
        yn=y*(1.0-ksi)+ksi*IFS_sierpinsky[k][1];
        if (iter>threshold) {                       // je-li dosaženo hranice iterací
            switch (drawType) {                     // výběr vykreslovacího režimu
                case IterPutPixel:                  // prosté vykreslení pixelu
                    putpixel(pix, xn*scale+xpos,
                                  yn*scale+ypos,
                                  rf ? 0xff:0x00,
                                  gf ? 0xff:0x00,
                                  bf ? 0xff:0x00);
                    break;
                case IterAddPixel:                  // plošný histogram
                    addpixel(pix, xn*scale+xpos,
                                  yn*scale+ypos,
                                  red,
                                  green,
                                  blue);
                    break;
                case TransfPutPixel:                // obarvení oblastí řídicích bodů
                    putpixel(pix, xn*scale+xpos,
                                  yn*scale+ypos,
                                  pal[k&7][0],
                                  pal[k&7][1],
                                  pal[k&7][2]);
                    break;
                case TransfAddPixel:                // plošný histogram oblastí řídicích bodů
                    addpixel(pix, xn*scale+xpos,
                                  yn*scale+ypos,
                                  (!!pal[k&7][0])*dr,
                                  (!!pal[k&7][1])*dg,
                                  (!!pal[k&7][2])*db);
                    break;
                default:
                    break;
            }
        }
        x=xn;                                       // zapamatovat si novou pozici pracovního bodu
        y=yn;
    }
} 

Výše uvedená funkce recalcL_IFS() je implementována i v dnešním demonstračním příkladu. Po překladu a spuštění tohoto demonstračního příkladu se zobrazí linearizovaný systém iterovaných funkcí, který představuje pohled na známý Sierpinského trojúhelník. Pomocí kláves [Home] a [End] je možné měnit hodnotu dělení úsečky ξ a tím zásadním způsobem ovlivnit výsledný tvar. Dále je možné změnit maximální počet iterací, způsob vykreslování fraktálů (podobně jako u klasických systémů IFS) a jednotlivé barvové složky.

fractals35_6

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

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

V následujícím pokračování tohoto seriálu si ukážeme, jakým způsobem je možné v linearizovaných systémech iterovaných funkcí použít matici posloupnosti transformací a jak tato matice ovlivní tvar výsledného objektu či plošného obrazce.

fractals35_7

Obrázek 7: Sierpinského trojúhelník pro ξ=0,10

fractals35_8

Obrázek 8: Sierpinského trojúhelník pro ξ=0,20

UX DAy - tip 2

fractals35_9

Obrázek 9: Sierpinského trojúhelník pro ξ=0,35

fractals35_a

Obrázek 10: Sierpinského trojúhelník pro ξ=0,40

Byl pro vás článek přínosný?