Úloha 077: Efektivní implementace Mitchellova algoritmu

Úkolem je doplnit do existující implementace Mitchellova algoritmu (vzorkování v rovině) vhodnou geometrickou vyhledávací strukturu, aby byl výpočet řádově urychlen. Mitchellův algoritmus nejlepšího kandidáta je popsaný v článku Don P. Mitchell: Spectrally optimal sampling for distribution ray tracing.

Mitchell alg.

Základ

Jako základ poslouží projekt 077mitchell z repository grcis. Je připravena aplikace, ve které lze spouštět různé vzorkovací algoritmy v rovině (po dvou variantách náhodného vzorkování a Mitchellova algoritmu). Hustota pravděpodobnosti je buď uniformní, nebo lze vybrat několik možností včetně řízení vstupním rastrovým obrázkem. Aplikace má několik dalších přirozených funkcí, zobrazování a export vygenerovaných souborů vzorků, nastavování základních parametrů vzorkování (počet vzorků N, semínko náhodného generátoru seed nebo rozlišení visualizací).

Vzorkovací algoritmy jsou třídy implementující interface ISampling, jejich ukázky najdete v souborech Samplings.cs a Mitchell.cs. Vstupní řídící hustota pravděpodobnosti je třída s interface IPdf.

Pozornost soustředíme na Mitchellův vzorkovací algoritmus implementovaný ve třídách MitchellSampling (uniformní hustota pravděpodobnosti) a MitchellDensitySampling (libovolná hustota pravděpodobnosti). Po stisku tlačítka Generate se spustí metoda GenerateSampleSet(), výsledkem je sada vzorků požadovaných vlastností. Oblast umisťování vzorků je jednotkový čtverec [0,1]². Kvůli charakteru Mitchellova algoritmu - generování N.K kandidátů a jejich porovnávání s existujícími vzorky - je algoritmus velmi pomalý.

Co implementovat

Všechny úpravy programu jsou soustředěny ve zdrojovém souboru Mitchell.cs. Je potřeba zejména:

vytvořit novou třídu podobnou MitchellSampling implementující urychlené prohledávání (zde by se dalo uvažovat i o nëadaptivní datové struktuře, např. Grid)
pro vzorkování řízené libovolnou hustotou můžete vytvořit další třídu vycházející z MitchellDensitySampling a používající k urychlení adaptivní (hierarchickou) datovou strukturu, např. KD-tree nebo R-tree
nové třídy je potřeba zaregistrovat ve statické metodě DefaultSampling(), aby se nabízely ve formuláři
urychlovací datové struktury by měly počítat několik jednoduchých statistických údajů: počet porovnání bod vs. bod (pointPointCounter), bod vs. obdélník (pointBoxCounter) a počet operací v haldě (heapCounter - myslí se všechny O(log N) operace dohromady). Tyto statistiky se potom vypisují ve formuláři a slouží pro přehlednou kontrolu výpočtu
jako zdroj náhody se musí používat připravená instance RandomJames, tak bude zajištěn potřebný determinismus
ponechte beze změny výpočet hashovací hodnoty hash, tak bude možné porovnat přesnost implemetnace s pilotním algoritmem (hash obsahuje zakódované indexy kandidátů, kteří byli skutečně do výsledné sady vybráni .. při shodné počáteční inicializaci seed by se měla i hashovací hodnota shodovat)

Další poznámky

Ponechejte v aplikaci původní implementace MitchellSampling a MitchellDensitySampling, budou se hodit k porovnání výsledku (viz hash). Porovnejte rychlost a přesvědčte se, že vaše implementace vracejí stejné výsledky!
Nezapomeňte ponechat testování přerušení výpočtu uživatelem ( if ( userBreak ) break; )
Textový parametr string param použijte k předání hodnot z formuláře do vaší implementace. Pilotní třídy např. používají k=<number> k zadání konstanty Mitchellova algoritmu a toroid={false|true} přepíná mezi výpočtem metriky ve čtverci a v uzavřeném prostoru toroidu
Metoda GenerateSampleSet() musí vracet počet skutečně vygenerovaných vzorků

Materiály

Přehledné shrnutí zdrojů informací:
Don P. Mitchell: Spectrally optimal sampling for distribution ray tracing
Prezentace z přednášky PRG
Pelikán: Náhodné rozmisťování bodů v rovině (příspěvek na CSGG 2014)
Pelikán: Náhodné rozmisťování bodů v rovině (prezentace z CSGG 2014)

Termín

Odevzdat do: 14. 12. 2014

Body

10 bodů (neadaptivní urychlení pro uniformní hustotu pravděpodobnosti)
10 až 15 bodů navíc za adaptivitu (vzorkování řízené hostotou) a obecnost (toroid apod.)

Projekt

Visual Studio 2010 projekt: 077mitchell

Zdrojový soubor

Modifikujte a odevzdejte soubor: Mitchell.cs
Do komentáře na první řádce napište své jméno!
Nezapomeňte popsat parametry a alespoň stručně upřesnit metodu.