Ray Tracing Using k-D Tree

Tato práce se zabývá metodami sledování paprsku a jejich akcelerací pomocí k-D stromu. Poskytuje částečný rozbor a přehled algoritmů od klasického střílení paprsku k rekurzivnímu přístupu až k distribuovanému sledování paprsku. Věnuje se rozboru struktury BSP stromu a dále jeho podtřídy k-D stromu, uvádí základní algoritmus jejich konstrukce i průchodu. Dále se podrobněji zabývá technikami konstrukce k-D stromu, které jsou založeny na správném umístění řezací plochy do buňky stromu. Mezi techniky rozebrané v této práci patří půlení s využitím prostorového mediánu, objektového a poměrně nové techniky cenového modelu SAH, neboli surface area heuristic. K závěru práce uvádí výsledky testů a porovnání výkonnosti uvedených metod, ze kterých vychází nejlépe právě SAH.This thesis deals with ray tracing methods and their acceleration. It gives partial study and review of algorithms from classical ray shooting algorithm to recursive approach up to distributed ray tracing algorithm. Significant part of this thesis is devoted to BSP tree structure and its subclass of k-D tree, it shows simple algorithm for its construction and traversal. The rest of thesis is dealing with k-D tree construction techniques, which are based on the right choice of the splitting plane inside the every cell of k-D tree. The techniques upon the thesis is based on are space median, object median and relatively new cost model technique named SAH, otherwise as surface area heuristic. All three techniques are put into testing and performance comparison. In the conclusion the results of tests are reviewed, from where SAH is coming out as a winner.