title: Fast CPU ray-triangle intersection method
Creators: name: Pichler, Thomas Alois
Publisher: name: TU Wien
Year: 2018
Subjects: subject: ray-tracing
subject: ray-traingle intersection
subject: geometry
subject: physically based rendering
subject: ray-tracing
subject: ray-traingle intersection
subject: geometry
subject: physically based rendering

description: Raytracing ist eine Technik, mit der hochgradig realistische Bilder erzeugt werden können. Dieser Realismus wird durch das Simulieren der physikalisch korrekten Ausbreitung von Lichtstrahlen erzielt. Anwendungsgebiete für Raytracing sind beispielsweise Filmproduktion, Visualisierung, die Automobilindustrie, Kunst und Spieleentwicklung. “Rays” stellen in diesem Kontext Blickrichtungen und Lichtstrahlen dar, deren Verlauf in einer Szene verfolgt wird. Rays interagieren mit Objekten in dieser Szene (sie durchdringen sie, werden reflektiert, gebrochen etc.) und tragen im Endeffekt zu den jeweiligen Pixelwerten des generierten Bildes bei. Eine der wichtigsten Operationen in einem Raytracer ist die Berechnung von Schnittpunkten der Rays mit geometrischen Primitiven. Eines der meistgenutzten Primitiven ist das Dreieck. Schnittpunktberechnungen zwischen Rays und Dreiecken sind verhältnismäßig einfach, und komplexe Objekte werden oft durch Dreiecksnetze approximiert. Aus diesem Grund werden Schnittpunktberechnungen zwischen Rays und Dreiecken relativ häufig ausgeführt. Raytracing wird generell als eine eher langsame Methode der Bildgenerierung angesehen, weswegen in den letzten Jahren mehrere Algorithmen zur schnellen Ray-Dreieck-Schnittpunktberechnung vorgestellt wurden. Im Rahmen dieser Diplomarbeit wird ein neuer, schneller Algorithmus zur Ray-Dreieck-Schnittpunktberechnung in das CPU-basierte Raytracing-Framework PBRT implementiert. Er basiert auf Early-Termination-Strategien und transformiert Ray-Ebene-Schnittpunkte in ein 2D-Koordinatensystem. Für diese Transformation werden zwei verschiedene Ansätze beschrieben. Verschiedene Optimierungsmaßnahmen für den Algorithmus werden erforscht. Der Algorithmus wird hinsichtlich seiner Effizienz mit dem in PBRT implementierten Default-Algorithmus sowie mit einem anderen State-of-the-art-Algorithmus verglichen. Für die Tests werden realistische Szenen mit unterschiedlicher Komplexität und verschieden hohen Ray-Dreieck-Trefferraten verwendet. Die Ergebnisse zeigen, dass der neue Algorithmus hinsichtlich seiner Effizient den Default-Algorithmus bei jeder Szene übertrifft.
description: Ray tracing is a technique capable of synthesizing highly realistic images. It accurately simulates the physical distribution of light in a scene and can be used for movie production, scientific visualization, in the automotive industry, or by artists or game developers. In this context, rays of light, as well as lines of sight, are represented by “rays” which are traced throughout the scene. Rays interact with objects in the scene (they penetrate them, are reflected, refracted, etc.) and ultimately define the pixel values of the generated image. Thus, one crucial functionality of a ray tracing application is calculating the intersection of rays with scene primitives. One of the most often used primitives is the triangle. It enables relatively simple intersection calculations, and complex objects can be tessellated into triangles. Thus, a ray tracers ray-triangle intersection routine is called a considerable number of times per scene. Ray tracing is generally seen as a rather slow method of image generation. Thus, several algorithms for fast ray-triangle intersection have emerged within the last years. In the scope of this thesis, a novel, fast ray-triangle intersection algorithm is implemented into the CPU-based ray tracing framework PBRT. The algorithm features early termination strategies and transforms the ray-plane intersection point into a 2D coordinate system. For this transformation, two different approaches are discussed. Different optimizations are explored to further improve the algorithms performance. The algorithm is evaluated against PBRTs default algorithm and against another state-of-the-art ray-triangle intersection algorithm in terms of efficiency. Realistic scenes with different ray-triangle hit-rates and different scene complexity are used for the tests. The results show that the new algorithm outperforms the default algorithm for every scene.