Real-time ray tracing on the GPU : ray tracing using CUDA and kD-trees

Abstract

Die Strahlen-Verfolgung ("Ray-Tracing") ist ein Verfahren zur Berechnung von Bildern, dass seit den späten 1970er-Jahren bekannt ist.<br />Dieses Verfahren ist typischerweise ein so genannter "off-line" Algorithmus, was bedeutet, dass die Berechnung für ein Bild zwischen mehreren Sekunden oder Minuten bis hin zu mehreren Stunden oder gar Tagen benötigen kann. Im Zuge dieser Diplomarbeit wurde ein Programm zur Strahlen-Verfolgung ("Raytracer") entwickelt, der die Erzeugung von Bildern in Echtzeit ermöglicht. "Echtzeit" im Sinne der Computer-Graphik bedeutet dabei, 60 oder mehr Bilder pro Sekunde berechnen und anzeigen zu können. Um solch hohe Bilderzeugungsraten erreichen zu können, wird der Raytracer komplett auf der Graphikkarte (GPU) ausgeführt. Ermöglicht wird dies durch verwenden der Technologie CUDA. CUDA wurde vom Graphikkarten-Hersteller Nvidia entwickelt und erlaubt es, den Prozessor einer Graphikkarte in ähnlicher Art und Weise zu programmieren wie den einer CPU. Damit ist es möglich, die volle Rechenleistung einer Graphikkarte auszunutzen. Ein wichtiger Teil eines Raytracers sind dessen Beschleunigungsdatenstrukturen. Diese werden verwendet, um das Aufsuchen von Objekten im geometrischen Raum zu beschleunigen. In dieser Diplomarbeit wurden so genannte kD-Bäume in zwei unterschiedlichen Varianten implementiert. Ein kD-Baum ist ein binärer Baum, bei dem jeder Knoten einen gegebenen geometrischen Raum durch achsparallele Ebenen in zwei Unterräume teilt. Zusätzlich wurde für die Programmierung des Raytracers eine CUDA Bibliothek für "Aardvark" entwickelt. Aardvark ist die hauseigene Rendering-Engine des VRVis Forschungs-GmbH. Die Bibliothek erlaubt es, CUDA-Funktionalität innerhalb von Aardvark ohne großen Initialaufwand verwenden zu können. Der Raytracer ist Teil eines größeren Software-Projekts namens "HILITE", welches am VRVis umgesetzt wird.<br />

In computer graphics, ray tracing is a well-known image generation algorithm which exists since the late 1970s. Ray tracing is typically known as an offline algorithm, which means that the image generation process takes several seconds to minutes or even hours or days. In this thesis I present a ray tracer which runs in real-time.<br />Real-time in terms of computer graphics means that 60 or more images per second (frames per second, FPS) are created. To achieve such frame rates, the ray tracer runs completely on the graphics card (GPU). This is possible by making use of Nvidia's CUDA-API. With CUDA, it is possible to program the processor of a graphics card similar to a processor of a CPU. This way, the computational power of a graphics card can be fully utilized. A crucial part of any ray tracer is the acceleration data structure (ADS) used. The ADS is needed to efficiently search in geometric space. In this thesis, two variants of so called kD-Trees have been implemented. A kD-Tree is a binary tree, which divides at each node a given geometric space into two halves using an axis aligned splitting plane. Furthermore, a CUDA library for the rendering engine Aardvark, which is the in-house rendering engine at the VRVis Research Center, was developed to access CUDA functionality from within Aardvark in an easy and convenient way. The ray tracer is part of a current software project called "HILITE" at the VRVis Research Center.<br />