Trojrozměrné IFS a raytracer POV-Ray

Obsah

1. Trojrozměrné systémy iterovaných funkcí
2. Způsob zobrazení trojrozměrných systémů iterovaných funkcí
3. Implementace výpočtu a zobrazení trojrozměrného systému iterovaných funkcí
4. Demonstrační příklad vykreslující trojrozměrné systémy iterovaných funkcí
5. Vizualizace trojrozměrných IFS systémů pomocí programu POV-Ray
6. Druhý demonstrační příklad: převodník pro program POV-Ray
7. Ukázka souboru s vygenerovanými body IFS systému
8. Ukázka vygenerovaného souboru určeného pro program POV-Ray
9. Obsah dalšího pokračování tohoto seriálu

1. Trojrozměrné systémy iterovaných funkcí

V deseti předchozích částech tohoto seriálu jsme si ukázali několik navzájem odlišných postupů vedoucích k vytvoření obrazů dvojrozměrných systémů iterovaných funkcí (IFS). Některé popisované metody byly jednoduché, přímočaré a přitom velmi snadno implementovatelné (například RWA: Random Walk Algorithm – algoritmus náhodné procházky), jiné se buď zaměřily na urychlení vykreslování spolu s nezbytnou větší složitostí celého postupu (MPA: Minimal Plotting Algorithm – algoritmus generování minima pixelů) či naopak k vytvoření co nejrealističtěji vypadající kresby (zejména minule a předminule popisovaný algoritmus Fractal Flame a částečně také linearizované IFS).

Dnes celé povídání o systémech iterovaných funkcí ukončíme několika ukázkami tvorby modelů trojrozměrných IFS systémů. Modely vytvořené v dnešních demonstračních příkladech je možné použít buď samostatně, nebo je možné je po konverzi zakomponovat do složitější prostorové scény a tu posléze vykreslit v některém z mnoha dostupných modelovacích či renderovacích programů, například v oblíbeném Blenderu.

Obrázek 1: Trojrozměrný model IFS systému vykreslený v okně prvního demonstračního příkladu

2. Způsob zobrazení trojrozměrných systémů iterovaných funkcí

Z předchozích částí tohoto seriálu již víme, že při vizualizaci systémů iterovaných funkcí jsou postupně, tj. po aplikaci jednotlivých lineárních či nelineárních transformací, generovány body P_n. Prozatím jsme tyto body, jež ležely v rovině E², považovali za souřadnice v rastrovém obrázku a na jejich zaokrouhlenou pozici jsme pomocí předem definovaného postupu změnili barvu pixelu (například v závislosti na počtu „zásahů“ daného pixelu, vybrané lineární transformaci apod.).

Prakticky nic nám nebrání v rozšíření již prezentovaných algoritmů tak, aby se místo bodů v rovině E² vytvářely body ležící v trojrozměrném prostoru E³. Rozšíření spočívá v tom, že se transformační matice příslušející každé transformaci zvětší – místo matice o velikosti 3×3 prvky musí být použita matice 4×4 prvky, ovšem s tím, že poslední sloupec transformační matice má vždy hodnotu [0, 0, 0, 1]^T a tím pádem nemusí být explicitně ukládán v operační paměti počítače. Konkrétní způsob výpočtu a zobrazení trojrozměrných IFS je uveden v následující kapitole.

Obrázek 2: Soběpodobný objekt na bázi osmistěnu vykreslený v okně prvního demonstračního příkladu

3. Implementace výpočtu a zobrazení trojrozměrného systému iterovaných funkcí

U systémů iterovaných funkcí vytvářených v ploše byla každá lineární transformace popsána maticí A velikosti 3×3 prvky, přičemž poslední sloupec matice měl hodnotu [0, 0, 1]^T, tj. nemusely se s ním provádět žádné výpočty. To by ostatně nemělo žádný smysl, neboť pomocí posledního sloupce se mění hodnota souřadnice w (tu je nutné používat pouze při práci s homogenními souřadnicemi). Aplikaci každé lineární transformace je možné popsat následujícím vztahem:

[x_n+1,y_n+1,1]­=[x_n,y_n,1]×A

Při práci s prostorovými IFS systémy se transformační matice popisující jednotlivé transformace rozšíří na velikost 4×4 prvky, přičemž poslední sloupec má hodnotu [0, 0, 0, 1]^T a výpočet transformace je možné popsat vztahem:

[x_n+1,y_n+1,z_n­+1,1]=[x_n,y_n,z_n,1]×B

Pro uložení transformační matice B je zapotřebí šestnácti čísel (4×4), ale vzhledem k předem známé hodnotě posledního sloupce nám dostačuje pouze čísel dvanáct. Pokud si uvědomíme, že pro každou transformaci musíme znát i její pravděpodobnost π_i, dojdeme k závěru, že každou lineární transformaci trojrozměrného IFS systému je možné popsat pouze pomocí třinácti čísel. IFS systém s i transforma­cemi je tak možné uložit na i×13×4 bytů v případě, že pro každou číselnou hodnotu je použit formát float podle normy IEEE 754 s jednoduchou přesností.

Praktická implementace vygenerování trojrozměrného modelu systému iterovaných funkcí je ukázána na následující Céčkovské funkci. Všimněte si způsobu zápisu lineárních transformací do dvojrozměrného pole a aplikace vybrané transformace na souřadnice uložené v proměnných x, y, z:

/* ---------------------------------------------------------------------------- */
/* Tato funkce vytvoří množinu trojrozměrných bodů představujících obraz        */
/* trojrozměrného IFS systému                                                   */
/* ---------------------------------------------------------------------------- */
void create_3d_ifs(Object *o, int type, int start_iter, int max_iter)
{
    int     i, k;
    float   x, y, z, x1, y1, z1;                /* souřadnice v prostoru */
    float   pp, sum;
    point3DF point3D;

    float ifs[][13]={                           /* pole lineárních transformací */
        { 0.000000f, 0.000000f, 0.000000f, 0.000000f, 0.180000f, 0.000000f, 0.000000f, 0.000000f, 0.000000f, 0.000000f, 0.000000f, 0.000000f, 0.010000f},
        { 0.850000f, 0.000000f, 0.000000f, 0.000000f, 0.850000f, 0.100000f, 0.000000f,-0.100000f, 0.850000f, 0.000000f, 1.600000f, 0.000000f, 0.850000f},
        { 0.200000f,-0.200000f, 0.000000f, 0.200000f, 0.200000f, 0.000000f, 0.000000f, 0.000000f, 0.300000f, 0.000000f, 0.800000f, 0.000000f, 0.070000f},
        {-0.200000f, 0.200000f, 0.000000f, 0.200000f, 0.200000f, 0.000000f, 0.000000f, 0.000000f, 0.300000f, 0.000000f, 0.800000f, 0.000000f, 0.070000f},
    };

    if (!ifs) return;
    /* alokace paměti pro seznam vygenerovaných bodů v prostoru */
    point3DListDestroy(o->point3DList);
    point3DListAlloc(o->point3DList, max_iter-start_iter);

    /* příprava pro iterační smyčku */
    x=y=z=0.0;
    i=0;
    point3DListFirst(o->point3DList);

    /* iterační smyčka */
    while (!point3DListIsLast(o->point3DList)) {
        pp=arandom(999.0)/1000.0;
        sum=0;
        for (k=0; sum<=pp; k++)                 /* výběr transformace na */
            sum+=ifs[k][12];                    /* základě její pravděpodobnosti */
        k--;
                                                /* aplikace transformace */
        x1=ifs[k][0]*x+ifs[k][1]*y+ifs[k][2]*z+ifs[k][9];
        y1=ifs[k][3]*x+ifs[k][4]*y+ifs[k][5]*z+ifs[k][10];
        z1=ifs[k][6]*x+ifs[k][7]*y+ifs[k][8]*z+ifs[k][11];
        x=x1;y=y1;z=z1;
        if (i>=start_iter) {                    /* po proběhnutí startovních transformací */
            point3D.position.x=x;               /* se vygeneruje bod v prostoru */
            point3D.position.y=y;
            point3D.position.z=z;
            point3DListSetpoint3DF(o->point3DList, &point3D);
            point3DListNext(o->point3DList);    /* posun v seznamu na další bod */
        }
        i++;
    }
} 

Obrázek 3: Objekt vytvořený v demonstračním příkladu

4. Demonstrační příklad vykreslující trojrozměrné systémy iterovaných funkcí

Céčková funkce ukázaná v předchozí kapitole je implementována i v dnešním prvním demonstračním příkladu, který je poměrně rozsáhlý (v minulosti jsem ho totiž použil v jednom větším projektu). Pomocí této demonstrační aplikace je možné vytvářet modely těles složených z jednotlivých neorientovaných elementárních plošek nazývaných surfely. Vytvořené trojrozměrné modely nejsou popsány analytickou geometrií, jak to bývá v počítačové grafice zvykem, ale generátorem systémů iterovaných funkcí IFS. Generativně vytvořené modely těles se díky tomu vyznačují soběpodobností a fraktální strukturou. Dnešní demonstrační aplikace neobsahuje plnohodnotný editor systémů iterovaných funkcí, ale pouze galerii předem připravených IFS systémů, jejichž aplikací vznikají zajímavé (a vždy soběpodobné) trojrozměrné modely těles, například:

1. pyramida
2. pravidelný čtyřstěn
3. pravidelný osmistěn
4. krychle
5. pravidelný dvanáctistěn
6. pravidelný dvacetistěn
7. model trojrozměrné kapradiny
8. model trojrozměrného keře
9. model trojrozměrného křídla
10. modely podobající se přírodním objektům i umělým artefaktům

Po spuštění demonstrační aplikace se zobrazí jediné okno, které představuje pracovní plochu se zobrazeným trojrozměrným modelem i ovládacími prvky. Ovládání celé aplikace je možné provádět pomocí myši, klávesnice či kombinací obou těchto vstupních zařízení. V levém horním rohu se nachází tlačítko, kterým je možné vyvolat hlavní menu. Pod tímto tlačítkem je po levé straně pracovní plochy zobrazena stručná nápověda. V dolní části jsou zobrazeny další ovládací prvky, které se kontextově mění podle právě probíhající operace. Ve zbylé části pracovní plochy je vyobrazen model tělesa, kterým je možné natáčet, posouvat ho a přibližovat i oddalovat. Následuje stručný popis jednotlivých ovládacích prvků, které je možné vybírat a měnit pomocí myši:

• Výběr modelu, který se má vytvořit a následně vykreslit, se provádí pomocí ovládacího prvku Object type. Pokud je tento prvek vybrán pomocí levého tlačítka myši, dojde k přepnutí na další typ tělesa resp. k němu příslušejícímu systému iterovaných funkcí IFS (typy se cyklicky opakují). Pokud je však prvek vybrán pravým tlačítkem myši, zobrazí se kontextové menu, ve kterém je možné vhodný model vybrat. Kontextové menu má dvě úrovně; v první se zvolí třída modelu a ve druhé jeho varianty.
• Dalším ovládacím prvkem je prvek nazvaný Surfels size. Levým tlačítkem je možné cyklicky přepínat mezi deseti velikostmi zobrazených surfelů, pravé tlačítko slouží k zobrazení kontextového menu, ve kterém se všechny povolené velikosti 1–9 nachází.
• Ovládacím prvkem Shading lze zvolit jednu z pěti možností barevné intenzity vykreslovaných surfelů. Buď jsou všechny surfely nastaveny na stejnou intenzitu, nebo je jejich intenzita závislá na některé jejich souřadnici – x-ové, y-ové, z-ové či vzdálenosti od pozorovatele po průmětu do prostoru obrazovky. Levé tlačítko myši opět slouží k postupnému výběru některého typu stínování, pravým tlačítkem se zobrazí příslušné kontextové menu.
• Pomocí ovládacího prvku Depth buffer je možné zapínat či opětovně vypínat funkci paměti hloubky – depth bufferu (Z-bufferu). Při zapnuté paměti hloubky jsou vzdálenější surfely přepsány surfely bližšími. V případě, že je povoleno míchání barevných intenzit surfelů (blending), je vhodnější paměť hloubky vyřadit z činnosti.
• Ovládacím prvkem Blending se povoluje a zakazuje míchání barevných intenzit surfelů. Při zapnutém míchání se intenzity obrazů surfelů, které leží ve stejném fragmentu sčítají podle jejich přednastavených hodnot průhlednosti (průhlednost může nabývat hodnot od 0 do 1, což odpovídá hodnotám 0% až 100%). Průhlednosti lze taktéž nastavit pomocí tohoto ovládacího prvku stlačením pravého tlačítka myši a výběrem hodnoty ze zobrazeného kontextového menu.
• Vedle výše zmíněných ovládacích prvků se nachází posuvný box, kterým je možné měnit počet surfelů, ze kterých má být výsledný model tělesa vytvořen. Počet surfelů vlastně odpovídá maximálnímu počtu iterací provedených při vytváření trojrozměrného modelu systému iterovaných funkcí IFS.
• Další posuvné boxy slouží k nastavení barev a současně průhledností jednotlivých ovládacích prvků i výsledného modelu tělesa. Myší lze měnit intenzitu jednotlivých barvových složek i průhlednosti alfa. Klepnutím levým tlačítkem myši na název ovládacího prvku lze zvolit další ovládací prvek v řadě – opět je použita cyklická změna subdialogů.
• Myš lze použít i při změně pohledu na vytvořený model. Posunem myši se stlačeným levým tlačítkem v části plochy s modelem je možné modelem natáčet. Při stlačeném pravém tlačítku myši se model může přibližovat a oddalovat. Pokud je ještě stlačena klávesa Ctrl, je model v okně posouván v horizontálním i vertikálním směru. Kromě toho je možné použít i kurzorové klávesy, kterými se zvyšuje či naopak snižuje automatická rotace objektu okolo jednotlivých souřadných os (nezávisle na změně pohledu vlivem uživatele). Zastavení automatické rotace zajistí klávesová zkratka Ctrl+M.

Ihned po výběru některého předdefinovaného IFS systému je proveden přepočet všech surfelů, kterými je vybraný IFS systém reprezentován na obrazovce počítače. Při generování se v prvních sto iteracích žádné surfely negenerují, protože by se nemusely nacházet poblíž atraktoru IFS systému. Po proběhnutí všech iterací a vygenerování uživatelem zadaného počtu surfelů je vypočtena lineární transformace, které jsou všechny vygenerované surfely podrobeny před jejich promítnutím na obrazovku. Transformace se skládá ze změny měřítka a případného posunu tak, aby všechny nově generované surfely měly své středy umístěny v jednotkové krychli.

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

V následující tabulce je uveden soupis klávesových zkratek, kterými lze tuto demonstrační aplikaci ovládat.

5. Vizualizace trojrozměrných IFS systémů pomocí programu POV-Ray

Předchozí demonstrační příklad byl poměrně komplikovaný (alespoň s ohledem na velikost zdrojového souboru), a přesto neřešil jeden základní problém – vkládání vytvořených trojrozměrných modelů IFS systémů do větších 3D scén. Vzhledem k tomu, že modely trojrozměrných systémů iterovaných funkcí jsou složeny z jednotlivých bodů, není většinou možné provádět přímé importy, protože většina modelovacích či renderovacích programů neumožňuje práci s bodovými entitami. Z tohoto důvodu je vhodné původní bezrozměrné body převést na jiný typ entit; nabízí se buď koule o malém poloměru či bloby (metaballs). Počet iterací použitých pro vytvoření 3D IFS je vhodné ponechat na relativně malé hodnotě (tisíce či desetitisíce), aby bylo možné vytvořený model bez problémů dále zpracovávat.

Export je možné provést do některého z široce podporovaných formátů určených pro popis 3D scén. Široce použitelné jsou například formáty 3DS (3D Studio), DXF (standard pro CAD systémy), OFF a NFF (textový popis 3D scény), WRL (popis 3D scény jazykem VRML, který je dnes poněkud neprávem opomíjený) atd. Jednu z možností převodu – konkrétně do formátu skriptu určeného pro známý raytracer POV-Ray – ukazuje i druhý demonstrační příklad, který je blíže popsán v následující kapitole.

Obrázek 5: Model trojrozměrného IFS systému vykreslený pomocí raytraceru POV-Ray

6. Druhý demonstrační příklad: převodník pro program POV-Ray

Dnešní druhý demonstrační příklad slouží k převodu bodů reprezentujících trojrozměrný model IFS systému do formátu určeného pro další zpracování známým raytracingovým programem POV-Ray (viz http://www.po­vray.org). Vstupní soubor, který má být podroben konverzi, má velmi jednoduchý formát a je možné ho získat při běhu prvního demonstračního příkladu stlačením klávesy S popř. klávesy P.

Po stlačení jedné z uvedených kláves vznikne čistý ASCII soubor (pojmenovaný podle aktuálního datumu a času), který je pro účely co nejjednoduššího zpracování orientován na jednotlivé řádky, narozdíl od PostScriptu, kde není nutné konce řádku zapisovat. Na prvním řádku se nachází skupina písmen, pomocí níž je řečeno, které informace o bodech jsou v souboru uloženy. Nám postačí pouze pozice jednotlivých bodů, žádné další údaje nejsou zapotřebí (z tohoto důvodu první řádek musí obsahovat písmeno p – position a f – float). Na druhém řádku se nachází číslo udávající celkový počet bodů uložených v souboru. Na základě tohoto údaje je možné při programovém zpracování předem alokovat pole pro všechny body. Na dalších řádcích souboru se již nachází informace o jednotlivých bodech (co bod, to jeden řádek v souboru), přičemž je vždy zaručeno, že první tři čísla udávají souřadnice bodů v prostoru a další číselné údaje, kde mohou být uvedeny například informace o textuře, barvě atd., na řádku nejsou povinné.

Výstupní formát určený pro program POV-Ray je již více komplikovaný, i když se opět jedná o čistý textový formát, tentokrát však již s rysy plnohodnotného programovacího jazyka. Nám však pro tuto chvíli postačí vědět, že každý bod načtený ze vstupního souboru je převeden na entitu typu sphere, tj. kouli, která má poloměr nastavený na jedničku (je možné změnit ve zdrojovém kódu programu) a texturu s názvem OBJTEXT. Ukázka vstupního souboru, ve kterém jsou uloženy souřadnice bodů v prostoru, je uvedena v sedmé kapitole a v kapitole osmé je zachycen výpis skriptu s popisem trojrozměrné scény určený pro raytracingový program POV-Ray.

Použití tohoto konverzního programu je velmi jednoduché. Formát příkazové řádky pro spuštění konverze je následující:

fractals40_2 soubor.sfl soubor.pov 

kde:

1. fractals40_2 je jméno spustitelného souboru získaného úspěšným překladem zdrojového textu.
2. soubor.sfl je jméno souboru obsahujícího popis 3D modelu systému iterovaných funkcí. Tento soubor je vytvořen v dnešním prvním demonstračním příkladu.
3. soubor.pov je jméno souboru určeného pro program POV-Ray, který má být konverzí vytvořen.

Obrázek 6: Model trojrozměrného IFS systému vykreslený pomocí raytraceru POV-Ray – trojrozměrná verze původně plošné kapradiny Michaela Barnsleye

7. Ukázka souboru s vygenerovanými body IFS systému

pfsb
10000
28.996 59.553 57.116 1
64.547 30.980 28.509 1
57.274 66.791 39.255 1
78.686 34.599 19.578 1
39.294 18.503  9.740 1

// následuje dalších cca 10000 souřadnic bodů spolu s jejich velikostmi 

Obrázek 7: Model trojrozměrného IFS systému vykreslený pomocí raytraceru POV-Ray – soběpodobná pyramida

8. Ukázka vygenerovaného souboru určeného pro program POV-Ray

camera {
        location  <125, 150, 200>
        look_at   <0, -10, 0>
}

object { light_source { <300, 100, 350>  color rgb <1.0, 1.0, 1.0> } }
object { light_source { < 10, 200, -100> color rgb <1.0, 1.0, 1.0> } }

#declare PVTXTEXT =
texture {
    pigment {
        color rgbf <0.000, 0.500, 1.000, 0.000>
        turbulence <0.520, 0.600, 0.360>
    }
    normal {
        ripples    1.000
        octaves    8.400
        frequency  4.000
    }
    finish {
        phong 0.900
        reflection 0.0
    }
    scale 0.5
}

#declare OBJTEXT=
texture {
    pigment {
        color rgb <1.0, 0.7, 0.7>
    }
    finish {
        diffuse 1.0
        ambient 0.5
    }
}

plane { y, -60
    texture {PVTXTEXT
        scale 300
    }
}
sphere { < 28.996000, 59.553001, 57.116001>, 1 texture { OBJTEXT }}
sphere { < 64.546997, 30.980000, 28.509001>, 1 texture { OBJTEXT }}
sphere { < 57.273998, 66.791000, 39.255001>, 1 texture { OBJTEXT }}
sphere { < 78.685997, 34.598999, 19.577999>, 1 texture { OBJTEXT }}
sphere { < 39.293999, 18.503000, 9.740000>, 1 texture { OBJTEXT }}

// následuje dalších cca 10000 entit typu "sphere" 

Obrázek 8: Model trojrozměrného IFS systému vykreslený pomocí raytraceru POV-Ray – artefakt

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

Poměrně velkou a námi prozatím opomíjenou skupinou fraktálů jsou stochastické fraktály, tj. fraktály, při jejichž vytváření hraje nezanedbatelnou úlohu náhoda. Jelikož mají tyto fraktály v počítačové grafice své nezastupitelné místo, budeme se jimi zabývat v několika následujících částech tohoto seriálu.

Obrázek: Téma dalšího pokračování tohoto seriálu – jednoduchý stochastický fraktál