Efektivní algoritmy s využitím kd-stromů pro vrhání paprsků na GPU

Tato práce se zaměřuje na paralelní algoritmy pro stavbu a procházení k-d stromů za účelem zrychlení algoritmu sledování paprsku, převážně pro dynamické scény. Práce poskytuje úvod do k-d stromů a do architektury grafických karet. Dále poskytuje přehled a analýzu existujících řešení pro paralelní stavbu k-d stromů, pro stavbu k-d stromů pro dynamické scény, a pro procházení k-d stromů na grafické kartě. Je navrhnut a implementován framework podobající se hernímu enginu, aby poskytl základ na implementaci algoritmů souvisejících s algoritmem sledováním paprsků. Je představen návrh a popis implementace algoritmu stavby na grafické kartě využívající binning a frontu úloh, s podrobným popisem všech kroků. Je také představen návrh algoritmů na vkládání k-d stromů na CPU a GPU. Celkem je implementováno devět algoritmů: dva jednovláknové algoritmy stavby na CPU, používající přesný a přibližný výběr dělící roviny, jeden algoritmus stavby na GPU používající binning, jeden algoritmus na CPU pro vkládání k-d stromů, a čtyři algoritmy na procházení k-d stromů určené pro grafické karty spolu s tradičním algoritmem na procházení založeným na zásobníku. Implementované algoritmy jsou otestovány na deseti statických a pěti dynamických scénách. Výsledky jsou prezentovány v tabulkách pro každou scénu.