Top content

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.