Hlavní navigace

Vykreslování a animace 4D fraktálů v POV-Rayi

23. 1. 2007
Doba čtení: 13 minut

Sdílet

V dnešním článku o fraktálech si řekneme, jakými metodami je možné vykreslit čtyřrozměrné Mandelbrotovy a Juliovy množiny. Posléze si ukážeme vytváření těchto fraktálů ve známém raytraceru POV-Ray, včetně tvorby zajímavě vypadajících animací vznikajících využitím čtvrtého (nevykreslovaného) rozměru jako času.

Obsah

1. Různé metody vykreslení čtyřrozměrných fraktálů
2. Vyčíslení plošných řezů čtyřrozměrným fraktálem
3. Integrace podél paprsku
4. Raytracing či raycasting
5. Převod na polygonální síť
6. Vytváření 4D fraktálů v programu POV-Ray
7. Vykreslení trojrozměrného řezu čtyřrozměrnou Juliovou množinou
8. Využití čtvrtého rozměru jako času při tvorbě animací
9. Obsah dalšího pokračování tohoto seriálu

1. Různé metody vykreslení čtyřrozměrných fraktálů

Zatímco dvourozměrné fraktály bylo velmi snadné vykreslovat do bitmap či pixmap a bez problémů jsme si poradili i s fraktály trojrozměrnými (jednalo se o trojrozměrné IFS a trojrozměrné L-systémy), se čtyřrozměrnými fraktálními objekty nastávají při jejich vykreslování již větší problémy. Celá úloha zobrazení je komplikována zejména kvůli existenci „přebývajícího“ čtvrtého rozměru a dále také kvůli tomu, že většinou chceme vhodným způsobem zviditelnit povrch těchto objektů metodami založenými na existenci normálových vektorů. Mezi tyto metody patří i raycasting a raytracing. Povrch 4D fraktálů je však obecně nediferencovatelný, tj. nelze u něj analyticky vyjádřit parciální derivace v bodech na povrchu, proto je nutné použít numerické techniky, které však nejsou ani přesné, ani rychlé.

V dalších třech kapitolách si popíšeme tři možné způsoby vykreslování čtyřrozměrných fraktálů. Jedná se o metodu provádějící vyčíslování plošných (2D) řezů původně čtyřrozměrným objektem (druhá kapitola), přímočarou a poměrně jednoduchou metodu integrace podél paprsku (kapitola třetí), raytracing a raycasting (zpětné rekurzivní i nerekurzivní sledování paprsku, čtvrtá kapitola) a konečně o převod původně objemového modelu na polygonální síť (pátá kapitola).

2. Vyčíslení plošných řezů čtyřrozměrným fraktálem

Metoda, při níž se provádí vyčíslení plošných (2D) řezů původně čtyřrozměrným fraktálním objektem, je velmi jednoduchá, avšak výsledkem není trojrozměrný obrázek, ale „pouze“ plošná bitmapa či pixmapa. Základem metody je redukce původně čtyřrozměrného prostoru na plochu. Tato redukce se provádí tak, že se vybraná dvojice souřadnic odpovídajících jednotkovým vektorům (1, i, j, k) nastaví na konstantní hodnoty. Z předchozích částí tohoto seriálu již víme, že každý kvaternion či hyperkomplexní hodnotu můžeme zapsat ve tvaru q=x+yi+zj+wk. Pokud například pro celý počítaný obrázek nastavíme z=0,5 a w=0,0, budou jedinými měněnými hodnotami x a y. Původně čtyřrozměrný fraktál se nám tak de facto zredukuje na klasický dynamický systém vykreslovaný v komplexní rovině, jeho tvar však bude odlišný.

Tento způsob vykreslování „čtyřrozměrných“ fraktálů je použit v mnoha programech, například v minule popsaném programu Gnofract4D, dále v Ultra Fractalu či FractIntu. Poslední jmenovaná aplikace – FractInt – tuto vykreslovací techniku používá u fraktálů nazvaných QUAT (Mandelbrotova množina vypočtená pomocí kvaternionů), QUATJUL (Juliovy množiny vypočtené pomocí kvaternionů), HYPERCOMPLEX (Mandelbrotova množina vypočtená pomocí hyperkomplexních čísel) a HYPERCOMPLEXJ (Juliovy množiny vypočtené pomocí hyperkomplexních čísel). Na obrázcích níže jsou uvedeny ukázky Mandelbrotovy množiny a Juliových množin vypočtené pomocí kvaternionů v programu FractInt. Při vykreslování se měnily souřadnice x a y odpovídající jednotkovým vektorům 1 a i, další dvě souřadnice z a w odpovídající vektorům j a k byly nastaveny na konstantní hodnotu. Tyto hodnoty výrazným způsobem ovlivnily výsledné obrázky.

fractals64_1

Obrázek 1: Na první pohled „klasická“ Mandelbrotova množina je ve skutečnosti čtyřrozměrným fraktálem s cz=0 a cw=0

fractals64_2

Obrázek 2: Plošný řez čtyřrozměrnou Mandelbrotovou množinou s nastavením cz=-0,2 cw=0,3

fractals64_3

Obrázek 3: Detail plošného řezu čtyřrozměrnou Mandelbrotovou množinou s nastavením cz=0,0 cw=1,0

fractals64_4

Obrázek 4: Plošný řez čtyřrozměrnou Juliovou množinou s nastavením cx=-0,22 cy=0,58 c­z=-0,2 cw=0,3 (odpovídá Mandelbrotově množině zobrazené na druhém obrázku)

fractals64_5

Obrázek 5: Plošný řez čtyřrozměrnou Juliovou množinou s nastavením cx=-0,13 cy=0,18 c­z=0,0 cw=1,0 (odpovídá Mandelbrotově množině zobrazené na třetím obrázku)

fractals64_6

Obrázek 6: Plošný řez čtyřrozměrnou Juliovou množinou s nastavením cx=-0,64 cy=0,18 c­z=-0,2 cw=0,3 (odpovídá Mandelbrotově množině zobrazené na druhém obrázku)

3. Integrace podél paprsku

Další metodou je takzvaná integrace podél paprsku. Jedná se o metodu vycházející z rastrové objemové reprezentace prostorových objektů. Tento způsob reprezentace těles vznikl jednoduchým a přímočarým rozšířením dvourozměrných rastrových obrazů (bitmap resp. pixmap) do třech rozměrů. Část trojrozměrného prostoru je rozdělena na množství pravidelných elementárních objemových jednotek, které se nazývají voxely. Termín voxel vznikl zkrácením anglického termínu Volume Element. Svou (na první pohled nelogickou) zkratkou – písmeno X ve slovním základu – ukazuje na svou podobnost s pixelem, což je zkratka termínu Picture Element. Původně spojitý trojrozměrný prostor se tedy diskretizuje na jednotlivé mikroobjemy, podobně jako je tomu v případě bitmap a pixmap u dvourozměrných obrazů, kde je původně spojitá plocha rozdělena na dále nedělitelné plošky (pixely).

Pro účely zde popisovaných algoritmů můžeme za voxely poněkud nepřesně považovat osově orientované krychličky nebo kvádry, ve skutečnosti se však jedná o pouhé navzorkované bezrozměrné body, stejně jako pixely. V základní podobě, kdy potřebujeme pouze vyjádřit, zda daná část v prostoru náleží či nenáleží do tělesa, mohou voxely nabývat pouze dvou stavů – obsazeno, neobsazeno. Pro každý voxel tedy v tomto případě stačí zaznamenat pouze jeden bit, jehož hodnota signalizuje obsazenost či neobsazenost voxelu tělesem. Druhá možnost spočívá v záznamu počtu provedených iterací. To je právě případ zde popisované metody integrace podél paprsku. Jak tedy můžeme tuto metodu použít? Celý postup si můžeme shrnout do několika bodů:

  1. Nejprve je zapotřebí zvolit jednu dimenzi, která bude při vykreslování konstantní. Typicky se za konstantu volí poslední dimenze vztažená k jednotkovému vektoru k, není to však podmínkou.
  2. Vlastní vykreslování probíhá ve čtyřech do sebe vnořených smyčkách. V prvních třech vnějších smyčkách se postupně mění hodnoty čtyřrozměrné konstanty c=cx+cyi+czj+cwk. Postačují nám pouze tři smyčky, protože čtvrtá hodnota je zvolena v prvním bodu zpracování jako konstantní.
  3. Nejvnitřnější smyčka vykonává vlastní iterační výpočet. Výsledkem tohoto výpočtu je celočíselná hodnota říkající, kolik iterací bylo zapotřebí provést, aby se dosáhlo podmínky |z|>bailout. Pokud této podmínky nebylo dosaženo, tj. došlo k divergenci orbitu, je výsledkem nejvnitřnější smyčky hodnota odpovídající maximálnímu počtu iterací.
  4. Hodnota vrácená z iterační smyčky je vložena do trojrozměrného voxelového pole, které uchovává hustoty jednotlivých voxelů. Čím vyšší je uložená hodnota (vyšší počet iterací), tím větší je hustota v okolí daného voxelu.
  5. Výsledné zobrazení scény probíhá tak, že se zvolí souřadnice pozorovatele a promítací roviny. Posléze se od pozorovatele do scény vrhají paprsky (podobně jako u raytracingu). Na rozdíl od raytracingu se však nehledá průsečík s nějakým povrchem, ale sčítají se hustoty voxelů, které paprsek protne při svém průletu scénou. Rychlým algoritmem výpočtu průsečíků paprsku s voxely je například algoritmus DDA či Bresenhamův algoritmus pro 3D úsečku.
  6. Na základě vypočtené sumy hustot je obarven příslušný pixel na obrazovce. Výsledkem je tedy obrázek podobný rentgenovému či ultrazvukovému snímku. Předností tohoto postupu je, že se zobrazí i odlehlé části fraktálního objektu, nevýhodou pak fakt, že není zvýrazněn povrch.

Problém může nastat při vykreslování objemových dat reprezentovaných pomocí voxelů. Dnešní běžné grafické akcelerátory s voxely přímo nepracují, pro tuto oblast jsou určeny specializované grafické karty typu VolumePro. Můžeme však využít softwarovou podporu dodávanou některými firmami i jako open source knihovny. V oblasti programové podpory pro práci s objemovými daty existuje především programové rozhraní (API) s názvem SGI Volumizer od firmy SGI. Nejedná se přímo o knihovnu pro obecnou práci s voxelovými daty, protože jde pouze o nástroj definující funkce pro zobrazení voxelových dat s využitím grafických akcelerátorů. Programové rozhraní je vytvořeno přes knihovnu OpenGL.

Existují i specializované knihovny pro vykreslování voxelových dat (volume rendering). Jednou z těchto knihoven je VolPack Volume Rendering Library, která byla vyvíjena jako součást výzkumného projektu zobrazování objemových dat. Tato knihovna je postavena na nové skupině rychlých algoritmů zobrazování objemů. Autorem knihovny VolPack je Philippe Lacroute. Knihovna nevyžaduje ani nepoužívá žádný specializovaný hardware a je přenositelná na většinu platforem, přičemž dosahuje velmi rychlých časů zobrazování. Na dnes již poněkud obstarožní pracovní stanici SGI Indigo trvá zobrazení struktury o velikosti 2563 voxelů přibližně jednu sekundu.

Kromě specializovaných knihoven existují i komplexní nástroje pro práci s voxelovými daty. Nejznámější nástroje jsou vyvíjeny společností Volume Graphics pod názvem VGL. VGL je rozšiřitelné a vysoce flexibilní 3D programovací prostředí pro tvorbu různých aplikací založených na zobrazování objemů. Může se jednat jak o specializované medicínské aplikace, tak i o zobrazování zvláštních efektů ve filmovém průmyslu. Výhodou VGL je značná rychlost zobrazení i na standardních platformách PC, nevýhodou je nepřístupnost zdrojových kódů a komerční ochrana formátů a rozhraní.

4. Raytracing či raycasting

Raytracing (rekurzivní zpětné sledování paprsku) a raycasting (zpětné sledování paprsku) se provádí tím způsobem, že se do scény obsahující 4D fraktál vrhají paprsky procházející jednotlivými pixely na obrazovce. Následně se počítají průsečíky každého paprsku s povrchem 4D fraktálu, což vyžaduje numerické metody, protože povrch 4D fraktálu není možné vyjádřit analyticky. Kromě souřadnice průsečíku paprsku s povrchem je také nutné vypočítat normálový vektor v daném místě povrchu – ten je posléze použit k výpočtu lokálních parametrů osvětlení a také pro výpočet odraženého paprsku v případě použití raytracingu. Vzhledem k tomu, že je raytracing použit i v programu POV-Ray, budeme se tímto způsobem vizualizace zabývat v následujících kapitolách.

5. Převod na polygonální síť

Polygonální (též plošková) reprezentace je velmi často v prostorové počítačové grafice využívaná buď přímo jako primární formát dat dané aplikace nebo jako formát určený pro vykreslování trojrozměrných těles. Základním prvkem (grafickým primitivem) této reprezentace je trojúhelník, u něhož je vždy zaručeno, že všechny tři jeho vrcholy vždy leží v jedné rovině. Tato vlastnost trojúhelníku je důležitá zejména při vykreslování s využitím současných grafických akcelerátorů, protože značně zjednodušuje vykreslovací (renderovací) algoritmy implementované ve vykreslovacím řetězci v grafickém akcelerátoru.

Některé standardy pro uložení (například VRML či STL) a zobrazování prostorových dat (zejména OpenGL, Direct3D a v minulosti také GKS 3D) podporují použití i dalších grafických primitiv, zejména čtyřúhelníků a mnohoúhelníků s více vrcholy. Pro korektní práci většiny algoritmů je však zapotřebí zajistit, aby tyto prvky byly konvexní a jejich vrcholy ležely v jedné ploše, což samozřejmě poněkud komplikuje návrh a implementaci algoritmů použitých v grafických aplikacích. Vždy je však pomocí triangulace a/nebo teselace možné tyto složitější prvky převést na jednodušší trojúhelníky s tou nevýhodou, že se zvětší množství dat nutných pro popis převáděného prvku.

Převod trojrozměrného řezu původně čtyřrozměrného fraktálu na polygonální síť je poměrně složitá procedura. Většinou se provádí ve dvou krocích. V prvním kroku je vypočten voxelový model, podobně jako v případě metody integrace podél paprsku. Jednotlivé voxely však nejsou ohodnoceny libovolnou celočíselnou hodnotou, ale pouze jednobitovým příznakem říkajícím, zda je daná část prostoru vyplněna (voxel leží uvnitř fraktálu) či nikoli.

Tento objemový model je posléze převeden na síť trojúhelníků buď algoritmem Marching Cubes nebo Marching Tetrahedra. Výsledkem je poměrně hrubá síť, což se projevuje zejména při osvětlování takto vytvořeného modelu (normálové vektory závisí pouze na 26 sousedních voxelech). Síť je možné zjemnit už při vytváření objemového (voxelového) modelu zvýšením rozlišení 3D mřížky. Předností tohoto způsobu je návaznost na značné množství programů, které dokážou trojúhelníkovou mřížku zpracovat a vložit do složitějších scén. Jedná se o prakticky všechny 3D CAD a CAM programy, 3D Studio, Blender, Maya apod.

6. Vytváření 4D fraktálů v programu POVRay

Známý raytracer POV-Ray podporuje už několik let (konkrétně od verze 3) vykreslování čtyřrozměrných Juliových množin vypočtených buď pomocí kvaternionové nebo hyperkomplexní algebry. Do popisu scény je možné vložit objekt nazvaný julia_fractal, u kterého je nutné specifikovat typ použité algebry (hyperkomplexní či kvaternionová), hodnotu čtyřrozměrné konstanty c, maximální počet iterací, přesnost numerických výpočtů atd.

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. Možnosti POV-Raye si popíšeme v dalších dvou kapitolách, na které navazuje celý další díl tohoto seriálu.

7. Vykreslení trojrozměrného řezu čtyřrozměrnou Juliovou množinou

V této kapitole si ukážeme dva demonstrační popisy scény, ve které se nachází 3D řez původně čtyřrozměrnou Juliovou množinou. První scéna obsahuje Juliovu množinu vypočtenou pomocí kvaternionové algebry. Za povšimnutí stojí zejména způsob vyjádření 3D prostoru, který slouží k ořezu 4D fraktálu. 3D prostor je specifikován čtyřrozměrným vektorem a jedním reálným číslem. Je to velmi podobné specifikaci roviny, která je zadána trojrozměrným vektorem (normálou) a reálným číslem, tj. posunem roviny od počátku. U 3D prostoru je situace stejná, ovšem s tím rozdílem, že „normála“ má čtyři souřadnice. První demonstrační scéna je popsána v souboru s následujícím obsahem:

// Ukázka vykreslení původně čtyřrozměrné Juliovy množiny
// pomocí raytraceru POV-Ray

// specifikace verze POV-Raye
#version 3.0

// globální nastavení scény
global_settings {
    assumed_gamma 2.2
}

#include "colors.inc"

// nastavení kamery
camera {
    location <20, 20, -10>
    look_at  <0,0,0>
}

// nastavení dvojice světelných zdrojů

// první světelný zdroj
light_source {
    <200, 50, -80>
    color White
}

// druhý světelný zdroj
light_source {
    <50, 100, -200>
    color LightGray
}

// čtyřrozměrná Juliova množina
object {
    julia_fractal {
        <-0.5188, 0.5201, 0, 0> // hodnota konstanty c
        quaternion             // typ použité algebry
        sqr                    // iterační funkce z=>z^2+c
        max_iteration 9        // maximální počet iterací
        precision 40           // přesnost výpočtu průsečíku paprsku
        slice <0, 0, 0, 1>, 0  // ořezávací 3D podprostor ("normála" a posun)
    }
    texture {
        pigment {
            color Sienna}
        finish {
            ambient 0.3
            diffuse 0.7
            phong 1
        }
    }
    scale 10
}

// podlaha s texturou šachovnice
plane {y, -10
    texture {
        pigment {
            checker
            color White color Black
        }
        scale 6
    }
}

// finito 

fractals64_7

Obrázek 7: První scéna vykreslená programem POV-Ray

Druhá demonstrační scéna se do značné míry podobá scéně první, ovšem s tím rozdílem, že Juliova množina má nastavenou jinou konstantu c a také použitím hyperkomplexní algebry oproti algebře kvaternionové. Výsledkem je objekt obsahující „čtvercové“ části, na rozdíl od „kruhových“ částí v případě prvního objektu. Tento rozdíl je způsobem rozdílnými multiplikativními operacemi v obou algebrách. Zápis druhé scény má tvar:

// Ukázka vykreslení původně čtyřrozměrné Juliovy množiny
// pomocí raytraceru POV-Ray

// specifikace verze POV-Raye
#version 3.0

// globální nastavení scény
global_settings {
    assumed_gamma 2.2
}

#include "colors.inc"

// nastavení kamery
camera {
    location <20, 20, -10>
    look_at  <0,0,0>
}

// nastavení dvojice světelných zdrojů

// první světelný zdroj
light_source {
    <200, 50, -80>
    color White
}

// druhý světelný zdroj
light_source {
    <50, 100, -200>
    color LightGray
}

// čtyřrozměrná Juliova množina
object {
    julia_fractal {
        <-0.35, -0.25, 0.55, 0.35> // hodnota konstanty c
        hypercomplex           // typ použité algebry
        sqr                    // iterační funkce z=>z^2+c
        max_iteration 9        // maximální počet iterací
        precision 40           // přesnost výpočtu průsečíku paprsku
        slice <0, 0, 0, 1>, 0  // ořezávací 3D podprostor ("normála" a posun)
    }
    texture {
        pigment {
            color Sienna}
        finish {
            ambient 0.3
            diffuse 0.7
            phong 1
        }
    }
    scale 10
}

// podlaha s texturou šachovnice
plane {y, -10
    texture {
        pigment {
            checker
            color White color Black
        }
        scale 6
    }
}

// finito 

fractals64_8

Obrázek 8: Druhá scéna vykreslená programem POV-Ray

8. Využití čtvrtého rozměru jako času při tvorbě animací

V předchozí kapitole jsme viděli, že při specifikaci čtyřrozměrné Juliovy množiny jsme zadávali poměrně velké množství konstant; zejména se jedná o čtyři hodnoty konstanty c a pět hodnot při zápisu 3D podprostoru. Nabízí se zde možnost průběžné změny některé z těchto konstant. Dnes si ukážeme velmi jednoduchou (a poměrně nezajímavou) animaci, která byla vytvořena tak, že se průběžně měnila jedna složka čtyřrozměrné konstanty c. Přitom bylo využito faktu, že POV-Ray umožňuje použití speciální reálné proměnné nazvané clock, kterou je možné měnit buď z příkazového řádku, nebo v inicializačních souborech *.ini. Zde byla zvolena druhá možnost a příslušný inicializační soubor obsahoval následující řádky:

[animace]
Width=704
Height=576
Initial_Frame = 0
Final_Frame = 199
Initial_Clock = 0.0
Final_Clock = 1.0 

V tomto inicializačním souboru je napsáno, že se má vytvořit 200 snímků očíslovaných od 0 do 199. V jednotlivých snímcích se průběžně mění hodnota proměnné clock od nuly do jedničky, tj. ve snímku číslo nula je clock=0.0, ve snímku číslo 99 platí clock=0.5 atd. Zápis scény, který používá tuto proměnnou, vypadá následovně:

// Ukázka jednoduché animace původně čtyřrozměrné Juliovy množiny

// specifikace verze POV-Raye
#version 3.0

// globální nastavení scény
global_settings {
    assumed_gamma 2.2
}

#include "colors.inc"

// nastavení kamery
camera {
    location <20, 20, -10>
    look_at  <0, -5, 0>
}

// nastavení dvojice světelných zdrojů

// první světelný zdroj
light_source {
    <200, 50, -80>
    color White
}

// druhý světelný zdroj
light_source {
    <50, 100, -200>
    color LightGray
}

// čtyřrozměrná Juliova množina
object {
    julia_fractal {
        <-0.1826, (clock*3)-1.5, 0, 0> // použití "animační" proměnné clock
        quaternion
        sqr
        max_iteration 10
        precision 20
        slice <0, 0, 0, 1>, 0
    }
    texture {
        pigment {
            color Sienna
        }
        finish {
            ambient 0.3
            diffuse 0.7
            phong 1
        }
    }
    scale 10
}

// podlaha s texturou šachovnice
plane {y, -10
    texture {
        pigment {
            checker
            color White color Black
        }
        scale 6
    }
}

// finito 

Výslednou animaci vytvořenou ve formátu MPEG-1 si můžete stáhnout zde.

root_podpora

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

V další části tohoto seriálu budeme pokračovat v popisu možností programu POV-Ray při vykreslování trojrozměrných řezů původně čtyřrozměrných Juliových množin, zejména možnosti práce s hyperkomplexní algebrou. Také si ukážeme další možnosti animace těchto objektů. Jako návnadu na další díl si prohlédněte tuto animaci.

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