Sledování paprsku pomocí k-D tree
Loading...
Date
Authors
ORCID
Advisor
Referee
Mark
E
Journal Title
Journal ISSN
Volume Title
Publisher
Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract
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.
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.
Description
Citation
ŠILHAVÝ, M. Sledování paprsku pomocí k-D tree [online]. Brno: Vysoké učení technické v Brně. Fakulta informačních technologií. 2010.
Document type
Document version
Date of access to the full text
Language of document
cs
Study field
Počítačová grafika a multimédia
Comittee
doc. Dr. Ing. Jan Černocký (předseda)
prof. RNDr. Alexandr Meduna, CSc. (místopředseda)
Ing. Vladimír Bartík, Ph.D. (člen)
Doc. Ing. Zdeněk Havlice, CSc. (člen)
prof. Ing. Adam Herout, Ph.D. (člen)
doc. Mgr. Adam Rogalewicz, Ph.D. (člen)
Date of acceptance
2010-06-21
Defence
Student nejprve prezentoval výsledky, kterých dosáhl v rámci své práce. Komise se pak seznámila s hodnocením vedoucího a posudkem oponenta práce. Student následně odpověděl na otázky oponenta a na další otázky přítomných. Komise se na základě posudku oponenta, hodnocení vedoucího, přednesené prezentace a odpovědí studenta na položené otázky rozhodla práci hodnotit stupněm E. Otázky u obhajoby: PŘEDEVŠÍM: vysvětlete VELICE DOBŘE původ zdrojových kódů (nejen z projektu PGR ale i další zdroje zdrojového kódu). Vysvětlete, proč se ve zdrojovém kódu ani v textu práce nehovoří o tříčlenném kolektivu autorů projektu odevzdaného do PGR. V kapitole 2.2.3.1 píšete o algoritmu Radiozita, že pracuje na principu "vystřelování světelných paprsků z objektů", což je špatně. Jak je to správně? Co znamená, že se algoritmus "pohybuje na hranici složitosti O(N log N)" (str 22, poslední odstavec)?
Result of defence
práce byla úspěšně obhájena
Document licence
Standardní licenční smlouva - přístup k plnému textu bez omezení