Hlavní navigace

Plynulý morfing mezi dvojicí IFS systémů

12. 7. 2006
Doba čtení: 11 minut

Sdílet

Dnešní článek o fraktálech navazuje na díly, ve kterých jsme se zabývali tvorbou systémů iterovaných funkcí IFS. Dnes si řekneme, jakým způsobem je možné provádět plynulou změnu tvaru (morfing) mezi několika IFS systémy. Zde popsaný princip byl použit v mnoha demech a také v několika profesionálních animacích.

Obsah

1. Animace změny tvaru systému iterovaných funkcí
2. Princip morfingu IFS systémů
3. Demonstrační příklad umožňující změnu tvaru IFS systému
4. Výpis nejdůležitějších metod použitých v demonstračním příkladu
    4.1 Vykreslení vygenerovaného bodu do pixmapy
    4.2 Vykreslení jednoho pixelu do pixmapy v závislosti na nastaveném režimu
    4.3 Implementovaný algoritmus vykreslení IFS koláže
5. Literatura
6. Odkazy na Internetu
7. Obsah dalšího pokračování tohoto seriálu

1. Animace změny tvaru systému iterovaných funkcí

V několika předchozích částech tohoto seriálu jsme si ukázali, jakým způsobem je možné vytvářet zajímavě vypadající koláže pomocí systémů iterovaných funkcí IFS. Původně statické obrázky je však možné poměrně jednoduchým způsobem „rozpohybovat“ a vygenerovat z nich působivou animaci. Dnes si ukážeme způsob vycházející z klasického morfingu. Na rozdíl od morfingu prováděného s libovolnými tvary však při práci s iterovanými funkcemi použijeme jednoduchý trik: nebudeme přímo pohybovat vygenerovanými body v rovině obrazovky, což by bylo náročné a ve výsledku nezajímavé, ale budeme měnit přímo parametry systému iterovaných funkcí (přesněji řečeno transformační matici A). Vzhledem k tomu, že se má jednat o morfing, tj. plynulou změnu tvaru mezi dvojicí tvarů zadaných, bude do „morfovacího“ procesu vstupovat dvojice systémů iterovaných funkcí IFS. Výsledkem morfingu bude plynulá animace mezi dvojicí koláží odpovídajících oběma zadaným IFS systémům. Ukázka morfingu mezi dvěma známými IFS systémy (Sierpinského trojúhelníkem a binárním stromem) je zobrazena na obrázcích 1 – 7.

fractals37_1

Obrázek 1: Postupná změna Sierpinského trojúhelníka na binární strom (100%:0%)

fractals37_2

Obrázek 2: Postupná změna Sierpinského trojúhelníka na binární strom (80%:20%)

fractals37_3

Obrázek 3: Postupná změna Sierpinského trojúhelníka na binární strom (60%:40%)

2. Princip morfingu IFS systémů

Jak již bylo řečeno v předchozí kapitole, spočívá princip morfingu IFS systémů v tom, že se postupně mění hodnoty uložené v transformační matici A. V nejjednodušším případě je možné postupovat tak, že se provede vážený součet odpovídajících koeficientů ai,j prvního a druhého systému:

ai,j=(1-morphRatio)×a1i,j + morphRatio×a2i,j

Kde parametr morphRatio nabývá hodnot z intervalu <0, 1>. Výše uvedený výpočet je samozřejmě nutné použít pro všechny transformace příslušející zadaným IFS systémům. Prakticky může aplikace výpočtu transformačních matic vypadat následovně (jedná se o zdrojový kód napsaný v programovacím jazyce Java):

double a[][]=new double [Size][MatSize];      // matice s koeficienty IFS systému

for (int j=0; j<Size; j++) {                  // přenos koeficientů IFS systému
    for (int i=0; i<MatSize; i++) {           // a smíchání prvního a druhého systému
        a[j][i]=(1.0-morphRatio)*data1[j+firstIFS*Size][i] // do výsledné matice
               +(morphRatio)*data2[j+secondIFS*Size][i];
    }
} 

Pozorný čtenář se může zeptat, co se stane v případě, že první IFS systém bude mít jiný počet transformací než systém druhý. Zde přichází na řadu drobná úprava toho systému, který má nižší počet transformací – jejich počet je uměle zvýšen, a to tak, že přidané transformace obsahují identitu, tj. jednotkovou matici, která po své aplikaci vrátí původní souřadnice bodu. Pravděpodobnost těchto uměle přidaných transformací je nastavena na jedničku, a to z toho důvodu, že po provedení výše uvedeného vzorce se mohou pravděpodobnosti předchozích transformací snížit tak, že by jejich součet již nebyl roven jedné, což je samozřejmě chyba, která by způsobila nekorektní práci algoritmu. Pod další čtveřicí obrázků je uveden příklad zápisu množiny transformací dvou IFS systémů; všimněte si posledních řádků s uměle přidanými transformacemi s identitami.

fractals37_4

Obrázek 4: Postupná změna Sierpinského trojúhelníka na binární strom (40%:60%)

fractals37_5

Obrázek 5: Postupná změna Sierpinského trojúhelníka na binární strom (20%:80%)

fractals37_6

Obrázek 6: Postupná změna Sierpinského trojúhelníka na binární strom (10%:90%)

fractals37_7

Obrázek 7: Postupná změna Sierpinského trojúhelníka na binární strom (0%:100%)

// fern
{ 0.850000, 0.040000,-0.040000, 0.850000, 0.000000, 1.600000, 0.850000},
{ 0.200000,-0.260000, 0.230000, 0.220000, 0.000000, 1.600000, 0.070000},
{-0.150000, 0.280000, 0.260000, 0.240000, 0.000000, 0.440000, 0.070000},
{ 0.000000, 0.000000, 0.000000, 0.160000, 0.000000, 0.000000, 0.010000},
{ 1.000000, 0.000000, 0.000000, 1.000000, 0.000000, 0.000000, 1.000000},

// triangle
{ 0.500000, 0.000000, 0.000000, 0.500000,-0.500000, 0.000000, 0.333333},
{ 0.500000, 0.000000, 0.000000, 0.500000, 0.500000, 0.000000, 0.333333},
{ 0.500000, 0.000000, 0.000000, 0.500000, 0.000000, 0.860000, 0.333334},
{ 1.000000, 0.000000, 0.000000, 1.000000, 0.000000, 0.000000, 1.000000},
{ 1.000000, 0.000000, 0.000000, 1.000000, 0.000000, 0.000000, 1.000000}, 

3. Demonstrační příklad umožňující změnu tvaru IFS systému

Dnešní demonstrační aplikace slouží k vytvoření a následnému zobrazení fraktálů, které vznikají postupnou aplikací transformací systému iterovaných funkcí (IFS) na počáteční bod ležící v rovině. Po spuštění aplikace je možné nastavit celkový počet provedených iterací, počet startovních iterací (při nichž se neprovádí vykreslování, pouze nastavování hranice opsaného obdélníku), tvar generovaného obrazce (tj. parametry dvou IFS systémů) a procentuelní poměr mezi těmito dvěma IFS systémy při výpočtu jednotlivých transformací. Také je možná specifikace typu vykreslovaných bodů a konvolučního filtru, který se na výsledný obrázek může aplikovat.

Vzhledem k tomu, že uživatel může specifikovat parametry dvou IFS systémů, provede aplikace nejprve sloučení těchto systémů podle předem zadaných koeficientů. Sloučení se provádí váženým součtem odpovídajících koeficientů transformačních matic IFS systémů podle principu popsaného v předchozí kapitole.

Každý vygenerovaný bod může být reprezentován buď jedním pixelem, což je nejjednodušší případ použitý prakticky ve všech ostatních aplikacích pro práci s IFS systémy, nebo malým obrazcem, jež může být složen až z několika desítek pixelů. Aplikací konvolučního filtru je možné obrázek vyhladit, aby v něm nebyly patrné stopy jednotlivých bodů; ovšem na úkor částečného rozmazání obrázku.

Ukázka grafického uživatelského rozhraní (GUI) tohoto demonstračního příkladu i s vytvořeným fraktálním obrazcem je uvedena na dalším obrázku, zdrojový kód si můžete prohlédnout či stáhnout z této stránky a po překladu pomocí překladače jazyka Java je možné aplikaci spustit přes AppletViewer.

fractals37_8

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

Vzhledem k určitým omezením, která jsou kladena na grafická uživatelská rozhraní appletů, je celá aplikace tvořena jednou pracovní plochou rozdělenou do několika částí. Na jednotlivých částech jsou umístěny ovládací prvky grafického uživatelského rozhraní. Pracovní plocha aplikace může být zobrazena přímo na ploše WWW stránky v internetovém prohlížeči – to znamená, že se nevytváří žádná další okna ani dialogy. Alternativně lze použít prohlížeč appletů AppletViewer, který je dodáván k některým vývojovým prostředím založeným na jazyku Java a také k Sunovskému JDK.

4. Výpis nejdůležitějších metod použitých v demonstračním příkladu

V této kapitole, resp. v jejích podkapitolách, budou stručně uvedeny a popsány zdrojové kódy nejdůležitějších metod dnešní demonstrační aplikace.

4.1 Vykreslení vygenerovaného bodu do pixmapy

Metoda sloužící k vykreslení jednoho vygenerovaného bodu do pixmapy se ve své podstatě skládá z několika volání metody putPixel(), jež je popsána v navazující podkapitole. Tvar bodu v rastru (pixmapě) je závislý na volbě uživatele; podle zvoleného tvaru se mění i volání a parametry funkce putPixel(). Také způsob vykreslení bodu (přímý zápis barvy či snížení jasu) se volí z grafického uživatelského rozhraní aplikace:

// -----------------------------------------------------------------------
// Vykreslení vygenerovaného bodu do pixmapy
// -----------------------------------------------------------------------
private void putPoint(int x, int y) {
    if (x<4) x=4;                               // kontrola mezí pixmapy
    if (x>=width-3) x=width-4;
    if (y<4) y=4;
    if (y>=height-3) y=height-4;
    y=height-1-y;
    if (pointShape!=PointShape.Diamond3x3 &&
        pointShape!=PointShape.Diamond5x5) {
        putPixel(x, y);                         // prostřední pixel
    }
    if (pointShape==PointShape.Cross3x3 ||
        pointShape==PointShape.Diamond3x3 ||
        pointShape==PointShape.Block3x3 ||
        pointShape==PointShape.Cross5x5 ||
        pointShape==PointShape.Block5x5 ||
        pointShape==PointShape.Horizontal3 ||
        pointShape==PointShape.Horizontal5) {
        putPixel(x-1,y);                        // pixel nalevo
        putPixel(x+1,y);                        // pixel napravo
    }
    if (pointShape==PointShape.Horizontal5 ||
        pointShape==PointShape.Cross5x5 ||
        pointShape==PointShape.Diamond5x5 ||
        pointShape==PointShape.Block5x5) {
        putPixel(x-2,y);                        // druhý pixel nalevo
        putPixel(x+2,y);                        // druhý pixel napravo
    }
    if (pointShape==PointShape.Cross3x3 ||
        pointShape==PointShape.Diamond3x3 ||
        pointShape==PointShape.Block3x3 ||
        pointShape==PointShape.Cross5x5 ||
        pointShape==PointShape.Block5x5 ||
        pointShape==PointShape.Vertical3 ||
        pointShape==PointShape.Vertical5) {
        putPixel(x, y-1);                       // pixel nahoře
        putPixel(x, y+1);                       // pixel dole
    }
    if (pointShape==PointShape.Vertical5 ||
        pointShape==PointShape.Cross5x5 ||
        pointShape==PointShape.Diamond5x5 ||
        pointShape==PointShape.Block5x5) {
        putPixel(x, y-2);                       // druhý pixel nahoře
        putPixel(x, y+2);                       // druhý pixel dole
    }
    if (pointShape==PointShape.XCross3x3 ||
        pointShape==PointShape.Block3x3 ||
        pointShape==PointShape.XCross5x5 ||
        pointShape==PointShape.Diamond5x5 ||
        pointShape==PointShape.Block5x5) {
        putPixel(x-1, y-1);                     // diagonální pixely
        putPixel(x-1, y+1);
        putPixel(x+1, y-1);
        putPixel(x+1, y+1);
    }
    if (pointShape==PointShape.XCross5x5 ||
        pointShape==PointShape.Block5x5) {
        putPixel(x-2, y-2);
        putPixel(x-2, y+2);
        putPixel(x+2, y-2);
        putPixel(x+2, y+2);
    }
    if (pointShape==PointShape.Block5x5) {
        putPixel(x-1, y-2);
        putPixel(x-1, y+2);
        putPixel(x+1, y-2);
        putPixel(x+1, y+2);
        putPixel(x-2, y-1);
        putPixel(x-2, y+1);
        putPixel(x+2, y-1);
        putPixel(x+2, y+1);
    }
} 
fractals37_9

Obrázek 9: Obrazec vzniklý morfingem mezi kapradinou a binárním stromem

4.2 Vykreslení jednoho pixelu do pixmapy v závislosti na nastaveném režimu

Tuto metodu využívá i výše uvedená metoda putPoint() pro vykreslování jednotlivých bodů do obrázku. V závislosti na nastaveném režimu se pixel buď přímo vykreslí (černou barvou na bílém pozadí), nebo se sníží intenzita pixelu tak, že se postupně blíží od původní bílé barvy k barvě černé. Také je prováděn test na přetečení aktuální hodnoty pixelu pod hodnotu 0×ff000000, což je kód černé neprůhledné barvy. Pixmapa, do které se má vykreslování provádět, je vytvořena velmi jednoduše jako jednorozměrné pole položek typu int. Takto vytvořená pixmapa je posléze použita jako zdroj dat pro obrázek typu Image, který je možné vykreslovat do grafického uživatelského rozhraní aplikace:

    private int pixmap[]=new int[width*height];               // alokace paměti pro pixmapu
    private MemoryImageSource imageSource=new MemoryImageSource(width, height, pixmap, 0, height);
    private Image image=createImage(imageSource);             // vytvoření obrázku 
// -----------------------------------------------------------------------
// Vykreslení jednoho pixelu podle nastaveného režimu
// -----------------------------------------------------------------------
private void putPixel(int x, int y) {
    switch (putpixelMode) {
        case 0:
            pixelSrc[x+y*width]=0xff000000;
            break;
        case 1:
            if (pixelSrc[x+y*width]>0xff040404)
                pixelSrc[x+y*width]-=0x00040404;
            break;
        case 2:
            if (pixelSrc[x+y*width]>0xff080808)
                pixelSrc[x+y*width]-=0x00080808;
            break;
        case 3:
            if (pixelSrc[x+y*width]>0xff0c0c0c)
                pixelSrc[x+y*width]-=0x000c0c0c;
            break;
        case 4:
            if (pixelSrc[x+y*width]>0xff101010)
                pixelSrc[x+y*width]-=0x00101010;
            break;
        case 5:
            if (pixelSrc[x+y*width]>0xff141414)
                pixelSrc[x+y*width]-=0x00141414;
            break;
        default:
            break;
    }
} 
fractals37_a

Obrázek 10: Další obrazec vzniklý morfingem

4.3 Implementovaný algoritmus vykreslení IFS koláže

V posledním výpisu je uveden implementovaný algoritmus pro vykreslení IFS koláže zapsané pomocí dvou „klasických“ systémů iterovaných funkcí IFS. Nejprve je proveden výpočet koeficientů IFS systému pomocí smíchání koeficientů obou vstupních systémů. Potom přichází na řadu iterační smyčka. V prvních několika iteracích (specifikovaných parametrem startIter) se pouze provádí výpočet polohy bodu v rovině a stanovují se hranice opsaného obdélníka (ten se svými hranami těsně dotýká IFS koláže). Jakmile čítač iterací dojde k hodnotě startIter, jsou hranice opsaného obdélníka zafixovány a v průběhu výpočtu jednoho snímku se již nemění. Ve všech dalších iteracích se již provádí vykreslení generovaných bodů, ovšem s tím, že souřadnice bodů jsou transformovány tak, aby ležely uvnitř opsaného obdélníku.

// -----------------------------------------------------------------------
// Vlastní aplikace algoritmu pro vykreslení IFS koláže
// -----------------------------------------------------------------------
private void generateIFS(double data1[][],      // předávaná data prvního IFS systému
                         double data2[][],      // předávaná data druhého IFS systému
                         int maxIter,           // maximální počet iterací
                         int startIter,         // počet startovních iterací
                         int width,             // horizontální rozlišení obrázku
                         int height) {          // vertikální rozlišení obrázku
    double x1=0, y1=0, x2=0, y2=0;              // generované souřadnice
    double xmin=1e10, xmax=-1e10;               // obdélník opsaný IFS fraktálu
    double ymin=1e10, ymax=-1e10;
    int    x, y, k;
    double pp, sum;
    double delitel=1.0;

    Random r=new Random(0);                     // generátor náhodných čísel
    double a[][]=new double [5][7];             // matice s koeficienty IFS systému

    for (int j=0; j<5; j++) {                   // přenos koeficientů IFS systému
        for (int i=0; i<7; i++) {               // a smíchání prvního a druhého systému
            a[j][i]=(1.0-morphRatio)*data1[j+firstIFS*5][i] // do výsledné matice
                   +(morphRatio)*data2[j+secondIFS*5][i];
        }
    }
    for (int i=0; i<maxIter; i++) {             // pro všechny iterace
        pp=r.nextDouble();
        sum=0;                                  // na základě náhodného čísla
        for (k=0; sum<=pp; k++)                 // najít transformaci
            sum+=a[k][6];
        k--;
        x2=x1*a[k][0] + y1*a[k][1] + a[k][4];   // aplikovat transformaci
        y2=x1*a[k][2] + y1*a[k][3] + a[k][5];
        x1=x2; y1=y2;
        if (i>startIter) {                      // pokud byl překročen počet
            x2=(x1-xmin)*(double)width/delitel; // startovních iterací
            y2=(y1-ymin)*(double)height/delitel;
            x=(int)x2; y=(int)y2;               // vypočítat a zobrazit pozice pixelu
            putPoint(x, y);
        }
        else {                                  // pokud se jedná o startovní iterace
            if (x1<xmin) xmin=x1;               // provést výpočet opsaného obdélníka
            if (y1<ymin) ymin=y1;
            if (x1>xmax) xmax=x1;
            if (y1>ymax) ymax=y1;
        }
        if (i==startIter) {                     // zafixovat opsaný obdélník
            xmin*=1.1;                          // pro jistotu přidat 10% plochy
            xmax*=1.1;
            ymin*=1.1;
            ymax*=1.1;
            delitel=(xmax-xmin);
            if (ymax-ymin>xmax-xmin) delitel=ymax-ymin;
        }
    }
} 
fractals37_b

Obrázek 11: Další obrazec vzniklý morfingem

5. Literatura

[1] Barnsley Michael: ''Fractals Everywhere '',
        Academic Press Inc., 1988, ISBN 0–12–079062–9

[2] Barnsley Michael, Devaney R. L., Mandelbrot Benoit B., Peitgenn Heinz-Otto, Saupe Dietmar, Voss Richard: ''The Science of Fractal Images '',
        Springer-Verlag, New York, 1988

[3] Barnsley Michael, Hurd Lyman P.: ''Fractal Image Compression '',
        A. K. Peters, 1993

[4] Devaney Robert L.: ''A First Course In Chaotic Dynamical Systems '',
        Addison-Wesley, Reading, MA, 1992

[5] Fischer Yuval (editor): ''Fractal Image Compression: Theory and Application '',
        Springer-Verlag, New York, 1995

[6] Gröller Eduard: ''Interactive design of Nonlinear Functions for Iterated Function System '',
        Technical University Vienna, 1995

[7] Lauwerier Hans: ''Fractals '',
        Princeton University Press, 1991

[8] Tišnovský Pavel: ''Návrh editoru IFS '',
        Vysoké učení technické v Brně, Fakulta elektrotechniky a informatiky, 1998

[9] Tišnovský Pavel: ''Interaktivní editor afinních transformací '',
        Vysoké učení technické v Brně, Fakulta elektrotechniky a informatiky, 1999

6. Odkazy na Internetu

[10] Tyler Bert, Wegner Tim a kol.: ''Fractint (fractal generator for DOS) '',
        http://www.frac­tint.org   (3.6.2006)

[11] Cygnus software: ''Fractal eXtreme (fractal generator for Windows) '',
        http://www.cygnus-software.com   (3.6.2006)

[12] Slijkerman Frederik: ''Ultra Fractal (fractal generator for Windows) '',
        http://www.ul­trafractal.com   (3.6.2006)

[13] Gintz Terry W.: ''Zplot (fractal generator) '',
        http://www.ge­ocities.com/So­Ho/Lofts/5601/ga­llery.htm   (3.6.2006)

[14] Chardonnet David: ''IFS Fractals Digital Encyclopedy '',
        http://www.chez­.com/fractals/ga­leries/gb_index­.html   (3.6.2006)

[15] Bowman Richard L.: ''IFS Fractal Generation Exercise '',
        http://www.brid­gewater.edu/de­partments/phy­sics/ISAW/Frac­talGenEx.html   (3.6.2006)

[16] Devaney Bob: ''Dynamical systems and Iterated Function Systems '',
        http://math.bu­.edu/people/bob/   (3.6.2006)

[17] Thornton Sterling: ''XenoDream (Interactive IFS Editor) '',
        http://xenodre­am.com   (3.6.2006)

UX DAy - tip 2

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

V následující části tohoto seriálu si popíšeme velmi zajímavou skupinu fraktálů, která úzce souvisí se systémy iterovaných funkcí. Jedná se o fraktály nazývané „Fractal Flame“, které vznikají několikerou generalizací původních IFS systémů.

fractals37_c

Obrázek 12: Ukázka fraktálu typu „Fractal Flame“

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

Autor článku

Vystudoval VUT FIT a v současné době pracuje na projektech vytvářených v jazycích Python a Go.