Úloha 089: Efektivní implementace fraktálního tělesa

Úkolem je implementovat některé fraktální těleso (např. známou Sphereflake) a dostatečně optimalizovat výpočet průsečíku paprsku pomocí vhodné urychlovací metody.

Základ

Základem poslouží projekt 048rtmontecarlo-script (nebo 048rtmontecarlo) z repository grcis. Je připravena aplikace, která umí počítat obrázek dané scény s použitím konfigurovatelného sledování paprsku a volitelného paralelismu (multi-core CPU).
Pokud byste chtěli využít možnosti definovat scénu scriptem, použijte projekt 048rtmontecarlo-script a popis scény vložte do nového .cs souboru (inspirace viz vestavěné scény z adresáře data/rtscenes/). I do skriptu je předán textový parametr Param: z formuláře.

Relevantní interface a třídy

ISolid - obecný interface pro tělesa, která se umí protnout paprskem. Tento interface musí implementovat Vaše nová třída.
Sphere - konkrétní implementace jednoduchého tělesa, zde si všimněte, co všechno musíte i Vy implementovat, kouli navíc budete potřebovat pro průsečíky na nejhlubší úrovni hierarchie..

Co modifikovat

Ve zdrojovém souboru MonteCarloRT.cs založte novou třídu, např. public class SphereFlake : DefaultSceneNode, ISolid a do ní napište svoji implementaci (inspirace viz class Sphere).
Do definice scény (CustomScene) přidejte Vaše těleso/tělesa, možná budete potřebovat modifikovat i polohu kamery, světelné zdroje, materiály, apod.

Dále budete muset implementovat vhodný urychlovací mechanismus, doporučuji obohatit rekurzivní fraktální těleso hierarchií obalových těles (třeba zase koulí) a při rekurzivním sestupu ořezávat neprotnuté větve.
Pokud si vyberete jiný fraktál, budete možná potřebovat obecnou urychlovací hierarchii pro množinu malých trojúhelníčků (octree, KD-tree nebo R-tree viz přednášky o urychlovacích metodách nebo o datových strukturách pro prostorové vyhledávání).

Náměty

Jestli se Váš fraktál skládá z trojúhelníčků, měli byste ho nejdřív do nějaké úrovně hierarchie zkonstruovat a naplnit zvolenou urychlovací datovou strukturu KD-tree nebo R-tree (BVH), případně Octree (oktantový strom). Varianty stromů s duplicitou jsou KD-tree a Octree, R-tree duplicitní trojúhelníky nesmí obsahovat. Používejte "bucket-tree", tj. listy s maximálně N trojúhelníky, např. 2 <= N <= 8 (nejlepší je deklarovat N jako konstantu a vyzkoušet její vliv na rychlost výpočtu).

Pokud si zvolíte "Sphereflake", bude možná stačit rekurzivní sestup obohatit o obalová tělesa podstromů (větví) a ořezávat neprotnuté větve.

Pozor: Váš kód musí být re-entrantní, protože se bude pouštět v paralelním prostředí! Do objektu fraktálu si nesmíte ukládat žádné pomocné hodnoty. Příp. urychlovací struktoru (strom) musíte postavit na začátku, při inicializaci, pak už bude (pro jednotlivá výpočetní vlákna) sdílená a "read-only".

Geometrická podpora

Ve třídě Geometry jsou pro Vás připraveny užitečné metody: RayTriangleIntersection(), RayBoxIntersection() resp. RayBoxIntersectionInv(). Ty používejte k získání průsečíku paprsku s jednotlivým trojúhelníkem nebo obalovým kvádrem (AABB).
Nezapomeňte inkrementovat čítače CSGInnerNode.countBoundingBoxes resp. CSGInnerNode.countTriangles počítající výpočty průseku paprsku s obalovým kvádrem resp. s jednotlivým trojúhelníkem.
Podobná úloha v minulosti (urychlování průsečíku se sítí trojúhelníků): 050, grcis projekt 050rtmesh. Tam také najdete jednoduché ukázky výpočtu průsečíku paprsku s trojúhelníky..

Literatura

Nejen pro pokročilé:

R-tree (Wikipedia entry)
Vlastimil Havran: Heuristic Ray Shooting Algorithms (PhD disertační páce)
Ingo Wald, Vlastimil Havran: On building fast kd-Trees for Ray Tracing, and on doing that in O(N log N)

Co odevzdat

Musíte poslat zdrojový soubor MonteCarloRT.cs, případně pár spočítaných obrázků. Pokud budete používat scripty definující scénu, nezapomeňte je též přiložit.

Termín

Odevzdat do: 9. 6. 2019

Body

Základ: 25 bodů (minimálně Sphereflake rozumně urychlená),
další body navíc za jiný fraktál složený s trojúhelníčků a urychlený obecným hierarchickým systémem (R-tree, KD-tree, octree).

Projekt

Visual Studio projekt: 048rtmontecarlo-script nebo 048montecarlo

Zdrojový soubor

Modifikujte a odevzdejte soubor: MonteCarloRT.cs
Ve funkci InitializeScenes() zadejte své jméno!