Dipl.-Inform. Martin Tillmann

Die Konstruktion von SAH-basierten kD-Bäumen ist ein wichtiger Schritt für schnelles Raytracing. Die Abwägung von Konstruktionsdauer, Speicherbedarf und Anfrageleistung stellt ein zentrales Problem für Konstruktionsalgorithmen dar. Optimale Werte für die Parameter dieser Algorithmen können die Gesamtleistung eines Raytracers deutlich steigern, hängen aber von vielen Faktoren ab und sind nur schwer manuell zu finden. Online-Autotuning kann diese Aufgabe während der Laufzeit übernehmen und automatisieren. Wir haben uns in dieser Arbeit mit der Frage auseinandergesetzt, ob sich Online-Autotuning für die Konstruktion von kD-Bäumen lohnt, also ob sich der benötigte Overhead für Echtzeit-Anwendungen schnell genug amortisieren kann. Hierzu haben wir für mehrere Algorithmen und Eingabedaten Vergleichstests mit und ohne Autotuner durchgeführt. Wir konnten dabei merklich kürzere Laufzeiten für optimal gewählte Parameter feststellen. Bei stichprobenartigen Tests zeigte sich zudem, dass auch die Amortisation schnell genug eintritt, um für Anwendungsfälle interessant zu sein.