FB6 Mathematik/Informatik/Physik

Institut für Informatik


Osnabrück University navigation and search


Main content

Top content

Sascha Kolodzey:
Parallele SAH KD-Tree Konstruktion auf GPUs für Raytracing dynamischer Szenen

Erstgutachter: Prof. Dr. Oliver Vornberger

Zweitgutachterin: Prof. Dr.-Ing. Elke Pulvermüller

Kontakt: skolodze@uni-osnabrueck.de

Arbeit als PDF: Masterarbeit (∼13,8 MB)

 

Zusammenfassung

Ein KD-Tree unter Verwendung der Surface Area Heuristic (SAH) zur Wahl der Split- Ebenen gilt in der Praxis als eine der besten Beschleunigungsstrukturen für das Raytracing. Gegenstand der vorliegenden Masterarbeit ist die Formulierung eines parallelen Algorithmus zur Konstruktion eines SAH KD-Trees sowie dessen vollständige Implementation auf einer GPU. Der Algorithmus in dieser Arbeit verfolgt den Ansatz, die Events eines Primitives beim Clipping nur auf der Split-Achse zu modifizieren. Die in vorherigen Ansätzen aufwändige Sortierung der geclippten Events auf jeder Ebene wird dadurch vermieden.

Rekursives Raytracing, Screenshot auf Basis der in dieser Arbeit entstandenen Software, BMW Modell von Mike Pan

Beispiel einer dynamischen Szene

Mit dem für diese Arbeit programmierten Framework (Rekursiver Echtzeit-Raytracer und entwickelter SAH KD-Tree) wird eine dynamische Szene (Ring aus Kugeln rotiert um das Objekt Bunny) berechnet. Hierbei ist einmal das Bunny aus einem metallischen Material (links) und einem gläsernen Material (rechts) modelliert. Der Raum, in dem sich die Objekte befinden, ist zusätzlich verspiegelt.

Für das Raytracing (1024 × 768 Pixel;110 ms, ca. 9 FPS) und die Erzeugung des KD-Trees (40 ms, ca. 25 FPS) werden in der Summe etwa 7 Frames pro Sekunde erreicht. Hierbei werden ca. 2 Mio. Rays (Schatten, Reflexion und Refraktion) erzeugt, die zugrunde liegende Szene besteht aus etwa 100K Dreiecken.