Název: Sledování paprsku pomocí k-D tree
Překlad názvu: Ray Tracing Using k-D Tree
Autoři: Šilhavý, Miroslav ; Herout, Adam (oponent) ; Havel, Jiří (vedoucí práce)
Typ dokumentu: Diplomové práce
Rok: 2010
Jazyk: cze
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [cze] [eng]
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.
Klíčová slova: BSP strom; k-D strom; konstrukce k-D stromu; Metody sledování paprsku; objektový a prostorový medián; průchod k-D stromem; SAH cenový model; BSP tree; construction of k-D tree; k-D tree; object and space median; Ray tracing methods; SAH cost model; traversing k-D tree

Instituce: Vysoké učení technické v Brně (web)
Informace o dostupnosti dokumentu: Plný text je dostupný v Digitální knihovně VUT.
Původní záznam: http://hdl.handle.net/11012/54306

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-237163


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Vysoké učení technické v Brně
Vysokoškolské kvalifikační práce > Diplomové práce