Hlavní navigace

Mandelbrotovy a Juliovy množiny ve čtyřrozměrném prostoru

Pavel Tišnovský 16. 1. 2007

V dnešním pokračování seriálu si ukážeme, jakým způsobem vypočítat Mandelbrotovy a Juliovy množiny ležící ve čtyřrozměrném prostoru. Výpočty ve 4D prostoru budeme provádět buď pomocí minule vysvětlených kvaternionů nebo hyperkomplexních čísel. Dále si řekneme, jaké volně dostupné aplikace lze použít pro vykreslování čtyřrozměrných fraktálů.

Obsah

1. Mandelbrotova množina vytvořená ve čtyřrozměrném prostoru
2. Juliovy množiny ve čtyřrozměrném prostoru
3. Iterační smyčka pro výpočet Mandelbrotovy množiny či množin Juliových
4. Programy určené pro vykreslení fraktálů ve čtyřrozměrném prostoru
5. Aplikace Gnofract4d
6. Aplikace FractInt
7. Aplikace Quat
8. Raytracer POV-Ray
9. Obsah dalšího pokračování tohoto seriálu

1. Mandelbrotova množina vytvořená ve čtyřrozměrném prostoru

V předchozí části tohoto seriálu jsme si popsali kvaterniony a hyperkomplexní čísla, včetně jejich základních vlastností důležitých při jejich praktickém používání. Obě tyto algebraické struktury, z nichž každá má své přednosti a zápory, je možné využít při tvorbě čtyřrozměrných objektů, což si ukážeme na tvorbě čtyřrozměrné varianty Mandelbrotovy množiny a čtyřrozměrných variant množin Juliových. Mandelbrotova množina ve čtyřrozměrném prostoru se počítá podobným způsobem jako Mandelbrotova množina v komplexní rovině, pouze se liší typ použitých proměnných a konstant. Nejprve si připomeňme, jak jsme postupovali při výpočtu této fraktální struktury v komplexní rovině. V předchozích částech tohoto seriálu (konkrétně už ve dvanáctém dílu) jsme si řekli, že Mandelbrotova množina je vytvořena pomocí velmi jednoduchého dynamického systému, který je založený na iteraci funkce komplexní paraboly. Vlastní iterační výpočet má tvar:

zn+1=zn2+c

kde proměnné z a c leží v komplexní rovině. Způsob iteračního výpočtu je zobrazen na prvním obrázku.

fractals63_1

Obrázek 1: Iterační výpočet bodů ležících v Mandelbrotově množině

V průběhu iteračního výpočtu se hodnota z postupně mění, zatímco hodnota c zůstává konstantní – tato se mění pouze při přesunu výpočtu na nový bod ležící v komplexní rovině (většinou tento bod odpovídá pixelu zobrazenému v nějaké pixmapě). Celý iterační proces začíná s určitou startovní hodnotou z0, takže systém postupně generuje sekvenci hodnot zk, které nazýváme orbit. Postup si ukážeme na prvních čtyřech iteracích:

z1=(z0)2+c
z2=((z0)2+c)+c
z3=(((z0)2+c)­2+c)2+c
z4=((((z0)2+c­)2+c)2+c)2+c
 

Při práci se systémem popsaným v předchozím textu nás zajímá, zda pro danou startovní hodnotu z0 a konstantu c posloupnost zk konverguje či diverguje. Mandelbrotova množina je totiž definována jako množina všech komplexních čísel i, které produkují konečný orbit nuly (tj. posloupnost konvergující či alespoň oscilující). Na základě trojúhelníkové nerovnosti je možné odvodit vztah pro test na divergenci. Ze vztahu vyplývá, že jakmile velikost zk přesáhne hodnotu 2 (pokud je tato hodnota umocněna, nazývá se bailout), je jisté, že daný orbit není konečný, tj. posloupnost diverguje ke komplexnímu nekonečnu.

Při praktických výpočtech Mandelbrotovy množiny se pro každou startovní hodnotu z0 v několika iteracích až stovkách iterací testuje, zda hodnota zk přesáhla hodnotu bailout. Podle toho se daný bod, který je na obrazovce reprezentován pixelem, obarví buď první nebo druhou barvou z dvoubarevné palety (viz druhý obrázek). Další, dnes pravděpodobně nejčastěji používanou, metodou je obarvení pixelů podle toho, v kolikáté iteraci bylo zjištěno překročení hodnoty bailout.

fractals63_2

Obrázek 2: Mandelbrotova množina vykreslená v komplexní rovině

Nyní se konečně přesuňme z komplexní roviny do čtyřrozměrného prostoru, ať už kvaternionového nebo hyperkomplexního. V obou případech (které nyní nemusíme rozlišovat) se ani definice ani vlastní výpočet Mandelbrotovy množiny nezmění, tj. stále je používán výše uvedený iterační vztah zn+1=zn2+c. Jediná podstatná změna nastává v tom, že konstanta c, startovní hodnota z0, posloupnost zk i všechny výpočty již nebudou prováděny „pouze“ s komplexními hodnotami, ale s kvaterniony či hyperkomplexními čísly. To znamená, že například c=c1+ici+jcj+kck, kde 1, i, j, k jsou jednotky, jejichž lineární kombinací může být vytvořen jakýkoli kvaternion či hyperkomplexní číslo. Také test na bailout se provádí stejným způsobem, nesmíme však zapomenout na to, že nyní se absolutní hodnota (velikost) z vypočítá pomocí vzorce:

|z|=(z12+zi2+­zj2+zk2)1/2

To, jakým způsobem budou jednotlivé dimenze při výpočtech využity, již záleží na konkrétní aplikaci. Jedná se o to, že v komplexní rovině jsme mohli konstantu c měnit podle toho, v jakém místě jsme počítali barvu daného pixelu. Mezi pozicí pixelu a hodnotou konstanty c tedy existovala jednoznačná transformace. To je sice ve čtyřrozměrném prostoru také možné (vlastně by to znamenalo čtyři vnořené smyčky plus jednu smyčku iterační), z praktických důvodů se však buď jedna nebo dokonce dvě dimenze „zploští“ tím, způsobem, že jsou příslušné hodnoty nastaveny na konstantu pro každý počítaný bod.

Pokud například při výpočtech budeme vždy dosazovat ck=1,5, provádíme vlastně velmi jednoduché ořezání původního čtyřrozměrného objektu trojrozměrným prostorem a výsledkem bude trojrozměrný objekt. V programu Gnofract4d a FractInt se dokonce provádí „zploštění“ dvou dimenzí; konkrétně ve FractIntu se pro fraktály nazvané QUAT a QUATJUL nastavují konstanty cj a ck. Výsledkem je plošný útvar (obrázek), který se zobrazuje naprosto stejným způsobem jako klasické fraktály v komplexní rovině.

2. Juliovy množiny ve čtyřrozměrném prostoru

Juliovy množiny vykreslované ve čtyřrozměrném prostoru vznikly – podobně jako výše popsaná čtyřrozměrná varianta původně dvourozměrné Mandelbrotovy množiny – přímočarým rozšířením „klasických“ Juliových množin vytvářených v komplexní rovině. Namísto provádění iterativního výpočtu v komplexní rovině, ve které jsou souřadné osy určeny dvojicí jednotkových a na sebe kolmých vektorů 1 a i, jsou ve čtyřrozměrném prostoru souřadné osy určeny čtyřmi vektory 1, i, j a k, které jsou taktéž na sebe kolmé. Připomeňme si, že iterační výpočet pro Juliovy množiny je naprosto stejný jako iterační výpočet Mandelbrotovy množiny (to platí ve 2D i ve 4D). Oba výpočty se liší pouze počátečními podmínkami, tj. nastavením proměnných z0 a c.

Zatímco v komplexní rovině je tvar každé Juliovy množiny určen hodnotou komplexní konstanty c=cre+icim, je tvar 4D Juliovy množiny ovlivněn konstantou c=c1+ici+jcj+kck, tj. čtveřicí reálných parametrů, které tvoří lineární kombinaci se čtyřmi jednotkovými vektory čtyřrozměrného kvaternionového či hyperkomplexního prostoru. Pro c ležící mimo oblast 4D Mandelbrotovy množiny vzniká čtyřrozměrná varianta Cantorova prachu, pro ostatní c je Juliova množina ve 4D spojitá (to však nemusí platit pro její 3D řez, ten může být nespojitý). Všechny dále popisované aplikace pracují převážně se čtyřrozměrnými Juliovými množinami, zejména z důvodu jejich značné variability. Příklad trojrozměrného řezu původně čtyřrozměrné Juliovy množiny je ukázán na třetím obrázku.

fractals63_3

Obrázek 3: Trojrozměrný řez 4D Juliovou množinou

3. Iterační smyčka pro výpočet Mandelbrotovy množiny či množin Juliových

Z předchozích kapitol víme, že se pro vyjádření vnitřních bodů Mandelbrotovy množiny i Juliových množin používá shodný výpočet, jehož základem je iterační smyčka, ve které se opakovaně provádí výpočet zk+1=zk2+c. Pojďme si nyní ukázat, jak by mohla tato iterační smyčka vypadat v případě použití kvaternionové algebry. Pravidla pro násobení jednotkových složek v této algebře jsme si uvedli v předchozí části tohoto seriálu. Součet dvou kvaternionů je jednoduchý (provádí se složku po složce), zbývá tedy odvodit vztah pro výpočet zk2. Pro součin dvou kvaternionů q1 a q2 platí:

q1q2=
    1(x1x2 – y1y2 – z1z2 – w1w2) +
    i(y1x2 + x1y2 + w1z2 – z1w2) +
    j(z1x2 – w1y2 + x1z2 + y1w2) +
    k(w1x2 + z1y2 – y1z2 + x1w2

pokud však budeme násobit ten stejný kvaternion, tj. dosadíme q=q1=q2, výpočet je možné zjednodušit:

q2=qq=
    1(xx – yy – zz – ww) +
    i(yx + xy + wz – zw) +
    j(zx – wy + xz + yw) +
    k(wx + zy – yz + xw)
=
    1(x2 – y2 – z2 – w2) +
    2ixy +
    2jxz +
    2kxw
 

Výsledný vztah je (opět pouze v případě kvaternionů, ne čísel hyperkomplexních) pro všechny tři vektorové složky i, j a k symetrický. Pro zajímavost: pokud dosadíme z=w=0, tj. z kvaternionu vytvoříme komplexní číslo, bude i výsledný vztah odpovídat mocnině komplexního čísla. S využitím výše uvedeného vztahu můžeme iterační smyčku zapsat následujícím způsobem (vstupem je kvaternionová hodnota z=[zx, zy, zz, zw] a c=[cx, cy, cz, cw]):

do {
    zx2=zx*zx;
    zy2=zy*zy;
    zz2=zz*zz;
    zw2=zw*zw;

    zx1=zx2-zy2-zz2-zw2;
    zy1=2.0*zx*zy;
    zz1=2.0*zx*zz;
    zw1=2.0*zx*zw;

    zx=zx1+cx;
    zy=zy1+cy;
    zz=zz1+cz;
    zw=zw1+cw;

    i++;
} while ((i<MAXITER) && (zx2+zy2+zz2+zw2)<BAILOUT); 

fractals63_4

Obrázek 4: Původně čtyřrozměrný fraktál zobrazený pomocí raytracingu

4. Programy určené pro vykreslení fraktálů ve čtyřrozměrném prostoru

Zatímco programových aplikací, které jsou určeny pro vytváření obrázků dynamických systémů v komplexní rovině, je nepřeberné množství a jsou vytvořeny pro nejrůznější platformy (od mobilních telefonů přes běžná PC s jejich nestandardními operačními systémy až po výkonné superpočítače), aplikací určených pro další typy fraktálů je již podstatně méně. Najdeme sice několik vhodných aplikací pro práci se systémy iterovaných funkcí (IFS), L-systémy či stochastickými systémy, výběr je však poměrně malý. Ještě menší výběr však máme v případě, že hledáme aplikaci vhodnou pro vykreslování čtyřrozměrných fraktálů. V následujících odstavcích si popíšeme čtyři programy z oblasti freeware a zejména open source, které je možné pro tuto činnost použít. Jedná se o programy Gnofract4d (pátá kapitola), FractInt (šestá kapitola), Quat (sedmá kapitola) a POV-Ray (kapitola osmá).

5. Aplikace Gnofract4d

Program Gnofract4d, který je dostupný na adresách http://gnofrac­t4d.sourcefor­ge.net/ popř. http://source­forge.net/pro­jects/gnofrac­t4d, umožňuje pracovat s Mandelbrotovými i Juliovými množinami počítanými v kvaternionovém či hyperkomplexním čtyřrozměrném prostoru. Možnosti zobrazení jsou však menší, protože je podporováno pouze vykreslení plošného řezu počítaným objektem. Výsledkem je tedy mapa těchto dynamických systémů s obarvením pixelů závisejícím na počtu iterací. Předností tohoto programu je kvalitní překladač souborů obsahujících popisy nových fraktálů, takže není problém přidat další čtyřrozměrné fraktály (některé definice se objevily například na sci.fractals). Použitý překladač je kompatibilní jak se syntaxí použitou ve FractIntu, tak i s programem Ultra Fractal. S vhodnou definicí fraktálu je možné připravit i jeho animaci, například rotaci.

6. Aplikace FractInt

Další aplikací, která umožňuje práci se čtyřrozměrnými fraktály, je známý program FractInt (http://www.frac­tint.org/), který je vyvíjen jak ve své původní DOSovské variantě, tak i ve variantě určené pro operační systémy Unix se systémem X-Window (samozřejmě včetně Linuxu). Ve FractIntu je k dispozici několik typů čtyřrozměrných fraktálů. Čtyři typy (HYPERCOMPLEX, HYPERCOMPLEXJ, QUAT a QUATJUL) jsou vykreslovány stejným způsobem jako u výše zmíněného programu Gnofract4d, tj. jako plošné řezy s pixely obarvenými podle počtu iterací. Poslední typ, jenž se jmenuje JULIBROT, je již určen pro vykreslování trojrozměrných řezů původních čtyřrozměrných fraktálů. Kromě základních 4D Mandelbrotových a Juliových množin jsou podporovány i fraktály využívající další funkce, například Lambda apod. Specialitou FractIntu je podpora červeno-modrých brýlí, s jejichž pomocí se dají některé trojrozměrné fraktály prohlížet tak, aby vynikla i jejich hloubka (v tomto případě však na úkor barev).

fractals63_5

Obrázek 5: Obrázek trojrozměrného fraktálu určený pro prohlížení červeno-modrými brýlemi

7. Aplikace Quat

Jedním z mála úspěšných programů určených pro práci se čtyřrozměrnými fraktály je program nazvaný jednoduše Quat. Tento program je dostupný na velké množství platforem ve variantě spustitelné z příkazového řádku. Pro Linux a Microsoft Windows existuje i klient disponující grafickým uživatelským rozhraním. Pomocí programu Quat je možné nastavit a posléze vykreslit velké množství fraktálů vytvořených v kvaternionovém či hyperkomplexním čtyřrozměrném prostoru. Lze nastavit mnoho způsobů obarvení těchto fraktálů i případné ořezávací roviny, kterými je možné vykreslovaný obrazec omezit, aby byla patrná jeho vnitřní struktura. V novějších verzích je podporováno i vykreslování přes Z-buffer a také antialiasing, který je právě u 4D fraktálů vhodné provádět, aby se vykreslovaný povrch zbavil všech chyb a nespojitostí. Ukázka grafického uživatelského rozhraní tohoto programu je zobrazena na šestém a sedmém obrázku.

fractals63_6

Obrázek 6: Nastavení parametrů fraktálu v programu Quat

fractals63_7

Obrázek 7: Výsledný fraktál vykreslený v programu Quat

8. Raytracer POV-Ray

Vykreslování čtyřrozměrných fraktálů je podporováno i ve známém raytraceru POV-Ray (http://www.po­vray.org/). Do vytvářené scény je možné přidat Juliovy množiny vytvořené buď v kvaternionovém nebo hyperkomplexním čtyřrozměrném prostoru (http://www.po­vray.org/docu­mentation/view/3­.6.1/280/). Dále se musí specifikovat ořezávací prostor, pomocí kterého se původně čtyřrozměrný objekt projekcí změní na objekt trojrozměrný, který je posléze raytracingem vykreslen. POV-Ray při vykreslování spočítá i normály povrchu, s jejichž pomocí je možné za pomoci Phongova osvětlovacího modelu spočítat světelné poměry na vykreslovaném objektu. Samozřejmě je možné použít i všechny další možnosti POV-Raye při úpravě povrchu, včetně průhlednosti, možnosti pokrytí procedurální texturou atd. Bližší informace budou uvedeny v následující části tohoto seriálu.

fractals63_8

Obrázek 8: Několik variant kvaternionové Juliovy množiny vykreslené raytracerem POV-Ray

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

V následujícím pokračování tohoto seriálu si stručně popíšeme možnosti ovládání dvou programů určených pro vykreslování fraktálů ve čtyřrozměrném prostoru. Bude se jednat o popis programu Quat a také o zobrazení čtyřrozměrných fraktálních objektů pomocí známého raytraceru POV-Ray.

Našli jste v článku chybu?

6. 7. 2009 21:03

STABO (neregistrovaný)

Nejen Mandebrotovy množiny a Juliovy množiny, ale hlavně jejich grafické a barevné zobrazení jsou fascinující počátek nového umění – Fraktální grafiky. Více v novém vydání knihy : Alternativní budoucnost 2012

19. 1. 2007 9:38

Raytracery pracuji s popisem sceny zalozene na (ted trosku zjednodusim) implicitnich plochach. Kupodivu prave s trojuhelniky a meshemi obecne maji docela problemy. Zkusim popsat raytracing na renderingu koule, ale plati to pro prakticky vsechny dalsi objekty, s kterymi POVRay pracuje.

Vsechny body lezici na povrchu koule splnuji rovnici:

(x-x0)^2+(y-y0)^2+(z-z0)^2-r^2=0

Kde [x0, y0, z0] je souradnice stredu koule a "r" je jeji polomer.

Raytracer pracuje tak, ze kazdym pixelem vypoc…







Podnikatel.cz: EET: Totálně nezvládli metodologii projektu

EET: Totálně nezvládli metodologii projektu

Lupa.cz: Propustili je z Avastu, už po nich sahá ESET

Propustili je z Avastu, už po nich sahá ESET

DigiZone.cz: ČRo rozšiřuje DAB do Berouna

ČRo rozšiřuje DAB do Berouna

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

Přehledná titulka, průvodci, responzivita

120na80.cz: Pánové, pečujte o svoje přirození a prostatu

Pánové, pečujte o svoje přirození a prostatu

Vitalia.cz: Baletky propagují zdravotní superpostel

Baletky propagují zdravotní superpostel

DigiZone.cz: ČRa DVB-T2 ověřeno: Hisense a Sencor

ČRa DVB-T2 ověřeno: Hisense a Sencor

Vitalia.cz: „Připluly“ z Německa a možná obsahují jed

„Připluly“ z Německa a možná obsahují jed

DigiZone.cz: Recenze Westworld: zavraždit a...

Recenze Westworld: zavraždit a...

Měšec.cz: U levneELEKTRO.cz už reklamaci nevyřídíte

U levneELEKTRO.cz už reklamaci nevyřídíte

Lupa.cz: Avast po spojení s AVG propustí 700 lidí

Avast po spojení s AVG propustí 700 lidí

Vitalia.cz: Říká amoleta - a myslí palačinka

Říká amoleta - a myslí palačinka

DigiZone.cz: ČT má dalšího zástupce v EBU

ČT má dalšího zástupce v EBU

Podnikatel.cz: Podnikatelům dorazí varování od BSA

Podnikatelům dorazí varování od BSA

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

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

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

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

Podnikatel.cz: Prodává přes internet. Kdy platí zdravotko?

Prodává přes internet. Kdy platí zdravotko?

Lupa.cz: Insolvenční řízení kvůli cookies? Vítejte v ČR

Insolvenční řízení kvůli cookies? Vítejte v ČR

Vitalia.cz: 9 největších mýtů o mase

9 největších mýtů o mase

Podnikatel.cz: Na poslední chvíli šokuje vyjímkami v EET

Na poslední chvíli šokuje vyjímkami v EET