TU Darmstadt / ULB / TUprints

Higher Performance Traversal and Construction of Tree-Based Raytracing Acceleration Structures

Wodniok, Dominik Maximilian (2019)
Higher Performance Traversal and Construction of Tree-Based Raytracing Acceleration Structures.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

Dissertation - Text (pdf document)
Dissertation_Dominik_Wodniok_2019.pdf - Accepted Version
Copyright Information: CC BY-NC-SA 4.0 International - Creative Commons, Attribution NonCommercial, ShareAlike.

Download (11MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Higher Performance Traversal and Construction of Tree-Based Raytracing Acceleration Structures
Language: English
Referees: Goesele, Prof. Dr. Michael ; Dachsbacher, Prof. Dr. Carsten
Date: 2019
Place of Publication: Darmstadt
Date of oral examination: 19 September 2018

Ray tracing is an important computational primitive used in different algorithms including collision detection, line-of-sight computations, ray tracing-based sound propagation, and most prominently light transport algorithms. It computes the closest intersections for a given set of rays and geometry. The geometry is usually modeled with a set of geometric primitives such as triangles or quadrangles which define a scene. An efficient ray tracing implementation needs to rely on an acceleration structure to decouple ray tracing complexity from scene complexity as far as possible. The most common ray tracing acceleration structures are kd-trees and bounding volume hierarchies (BVHs) which have an O(log n) ray tracing complexity in the number of scene primitives. Both structures offer similar ray tracing performance in practice. This thesis presents theoretical insights and practical approaches for higher quality, improved graphics processing unit (GPU) ray tracing performance, and faster construction of BVHs and kd-trees, where the focus is on BVHs.

The chosen construction strategy for BVHs and kd-trees has a significant impact on final ray tracing performance. The most common measure for the quality of BVHs and kd-trees is the surface area metric (SAM). Using assumptions on the distribution of ray origins and directions the SAM gives an approximation for the cost of traversing an acceleration structure without having to trace a single ray. High quality construction algorithms aim at reducing the SAM cost. The most widespread high quality greedy plane-sweep algorithm applies the surface area heuristic (SAH) which is a simplification of the SAM.

Advances in research on quality metrics for BVHs have shown that greedy SAH-based plane-sweep builders often construct BVHs with superior traversal performance despite the fact that the resulting SAM costs are higher than those created by more sophisticated builders.

Motivated by this observation we examine different construction algorithms that use the SAM cost of temporarily constructed SAH-built BVHs to guide the construction to higher quality BVHs. An extensive evaluation reveals that the resulting BVHs indeed achieve significantly higher trace performance for primary and secondary diffuse rays compared to BVHs constructed with standard plane-sweeping. Compared to the Spatial-BVH, a kd-tree/BVH hybrid, we still achieve an acceptable increase in performance. We show that the proposed algorithm has subquadratic computational complexity in the number of primitives, which renders it usable in practical applications.

An alternative construction algorithm to the plane-sweep BVH builder is agglomerative clustering, which constructs BVHs in a bottom-up fashion. It clusters primitives with a SAM-inspired heuristic and gives mixed quality BVHs compared to standard plane-sweeping construction. While related work only focused on the construction speed of this algorithm we examine clustering heuristics, which aim at higher hierarchy quality. We propose a fully SAM-based clustering heuristic which on average produces better performing BVHs compared to original agglomerative clustering.

The definitions of SAM and SAH are based on assumptions on the distribution of ray origins and directions to define a conditional geometric probability for intersecting nodes in kd-trees and BVHs. We analyze the probability function definition and show that the assumptions allow for an alternative probability definition. Unlike the conventional probability, our definition accounts for directional variation in the likelihood of intersecting objects from different directions. While the new probability does not result in improved practical tracing performance, we are able to provide an interesting insight on the conventional probability. We show that the conventional probability function is directly linked to our examined probability function and can be interpreted as covertly accounting for directional variation.

The path tracing light transport algorithm can require tracing of billions of rays. Thus, it can pay off to construct high quality acceleration structures to reduce the ray tracing cost of each ray. At the same time, the arising number of trace operations offers a tremendous amount of data parallelism. With CPUs moving towards many-core architectures and GPUs becoming more general purpose architectures, path tracing can now be well parallelized on commodity hardware. While parallelization is trivial in theory, properties of real hardware make efficient parallelization difficult, especially when tracing so called incoherent rays. These rays cause execution flow divergence, which reduces efficiency of SIMD-based parallelism and memory read efficiency due to incoherent memory access. We investigate how different BVH and node memory layouts as well as storing the BVH in different memory areas impacts the ray tracing performance of a GPU path tracer. We also optimize the BVH layout using information gathered in a pre-processing pass by applying a number of different BVH reordering techniques. This results in increased ray tracing performance.

Our final contribution is in the field of fast high quality BVH and kd-tree construction. Increased quality usually comes at the cost of higher construction time. To reduce construction time several algorithms have been proposed to construct acceleration structures in parallel on GPUs. These are able to perform full rebuilds in realtime for moderate scene sizes if all data completely fits into GPU memory. The sheer amount of data arising from geometric detail used in production rendering makes construction on GPUs, however, infeasible due to GPU memory limitations. Existing out-of-core GPU approaches perform hybrid bottom-up top-down construction which suffers from reduced acceleration structure quality in the critical upper levels of the tree. We present an out-of-core multi-GPU approach for full top-down SAH-based BVH and kd-tree construction, which is designed to work on larger scenes than conventional approaches and yields high quality trees. The algorithm is evaluated for scenes consisting of up to 1 billion triangles and performance scales with an increasing number of GPUs.

Alternative Abstract:
Alternative AbstractLanguage

Raytracing (dt. Strahlennachverfolgung) ist ein wichtiger Berechnungsbaustein der in verschiedenen Algorithmen wie der Kollisionserkennung, Sichtverbindungsberechnungen, die Raytracing-basierte Simulation von Schallausbreitung, so wie am prominentesten in Lichttransport-Algorithmen verwendet wird. Zu einer gegeben Menge an Strahlen und einem geometrischen Objekt berechnet Raytracing die nächste Schnittpunkte der Strahlen mit dem Objekt. Das geometrische Objekt ist dabei meist aus einer Menge geometrischer Primitive wie Drei- oder Vierecke zusammengesetzt, die eine Szene definieren. Eine effiziente Raytracing-Implementierung ist auf eine Beschleunigungsstruktur angewiesen, um die Raytracing-Komplexität so weit wie möglich von der Komplexität der Szene zu entkoppeln. Die gängigsten Beschleunigungsstrukturen sind kd-Bäume und BVHs (von engl. bounding volume hierarchy, dt. Hüllkörper-Hierarchie), die eine Raytracing-Komplexität von O(log n) in der Anzahl von Szenenprimitiven aufweisen. Beide Strukturen bieten in der Praxis eine ähnliche Raytracing Leistung. Diese Dissertation präsentiert theoretische Einsichten und praktische Ansätze für eine höhere Qualität, verbesserte Grafikprozessor (GPU) Raytracing Leistung, und schnellere Konstruktion von kd-Bäumen und BVHs, wobei der Fokus auf letzterem liegt.

Die gewählte Konstruktionsstrategie für kd-Bäume und BVHs hat einen signifikanten Einfluss auf die letzten Endes erzielbare Raytracing Leistung. Das gebräuchlichste Maß für die Qualität einer Baum-basierten Beschleunigungsstruktur ist die Oberflächenmetrik. Unter der Verwendung von Annahmen bezüglich der Verteilung von Strahlenursprüngen und -richtungen liefert die Oberflächenmetrik eine Approximation für den Berechnungsaufwand zur Durchquerung der Beschleunigungsstruktur, ohne einen Strahl zu verfolgen. Verfahren zur Konstruktion hochwertiger Beschleunigungsstrukturen zielen darauf ab, die Oberflächenmetrik zu minimieren. Der Standardalgorithmus zur hochwertigen Konstruktion ist der gierige Sweep-Algorithmus, der die Oberflächenheuristik verwendet, welche eine Vereinfachung der Oberflächenmetrik darstellt.

Forschung zu Qualitätsmetriken für BVHs hat ergeben, dass gierige Oberflächenheuristik-basierte Sweep-Algorithmen BVHs erzeugen können, die eine überlegene Raytracing Leistung erzielen, obwohl die resultierenden Oberflächenmetrik Kosten höher sind als die Kosten von BVHs, die mit weiterentwickelteren Verfahren konstruiert wurden. Basierend auf dieser Beobachtung untersuchen wir verschiedene Konstruktionsverfahren, welche die Kosten interimistisch mit der Oberflächenheuristik konstruierter BVHs verwenden, um BVHs höherer Qualität zu erzeugen. Eine umfangreiche Evaluierung zeigt, dass die resultierenden BVHs verglichen mit dem Standardverfahren für primäre und diffuse sekundäre Strahlen eine signifikant höhere Raytracing Leistung erzielen. Verglichen mit der räumlichen BVH, einem kd-Baum/BVH-Hybriden, erreichen wir immer noch einen akzeptablen Leistungszuwachs. Wir zeigen, dass der vorgeschlagene Algorithmus eine subquadratische Berechnungskomplexität in der Anzahl der Szenenprimitive besitzt, welche ihn in der Praxis nutzbar macht.

Ein alternativer Konstruktionsalgorithmus zum Sweep-Verfahren ist das agglomerierende Clustern, ein Bottom-up BVH Konstruktionsverfahren. Es clustert Primitive anhand einer Oberflächenmetrik-inspirierten Heuristik und gibt gemischte Ergebnisse im Vergleich zum Standardverfahren. Während sich weitere Forschung an diesem Verfahren auf die Konstruktionsgeschwindigkeit konzentriert hat, untersuchen wir Clusterungsheuristiken für ein höhere BVH Qualität. Wir schlagen eine voll Oberflächenmetrik-basierte Clusterungsheuristik vor, die im Durchschnitt bessere Ergebnisse erzielt als herkömmliches agglomerierendes Clustern.

Die Definitionen der Oberflächenmetrik und -heuristik basieren auf Annahmen zur Verteilung von Strahlenursprüngen und -richtungen, mit deren Hilfe eine bedingte Wahrscheinlichkeit für das Schneiden von Baumknoten definiert wird. Wir analysieren die Definition der Wahrscheinlichkeitsfunktion und zeigen, dass die Annahmen eine alternative Definition zulassen. Im Gegensatz zur herkömmlichen Definition beziehen wir die richtungsabhängige Variation der Schneidewahrscheinlichkeit von Objekten in die Herleitung mit ein. Während die alternative Definition in der Praxis nicht zu einer Zunahme der Raytracing Leistung geführt hat, sind wir in der Lage, eine interessante Einsicht bezüglich der herkömmlichen Definition zu liefern. Wir zeigen, dass die herkömmliche Definition direkt mit unserer alternativen Definition verbunden ist und so interpretiert werden kann, dass sie auf nicht offensichtliche Weise richtungsabhängige Variation berücksichtigt.

Der Path Tracing (dt. Pfadverfolgung) Lichttransport-Algorithmus kann das Nachverfolgen von Milliarden von Strahlen erfordern. Dafür kann es sich auszahlen, eine Beschleunigunsstruktur hoher Qualität zu bauen, um die Raytracing Kosten pro Stahl zu reduzieren. Gleichzeitig bietet die anfallende Anzahl an Strahlen einen hohen Grad an Datenparallelität. Mit der Entwicklung von CPUs in Richtung Vielkernprozessoren und GPUs zu Mehrzweck-Architekturen, kann Path Tracing nun einfach auf handelsüblicher Hardware parallelisiert werden. Während die Parallelisierung theoretisch trivial ist, machen Eigenschaften der Hardware eine effiziente Umsetzung schwierig, insbesondere dann, wenn so genannte inkohärente Strahlen verfolgt werden. Diese Strahlen verursachen Abweichungen im Ausführungsfluss, welche zu einer reduzierten Effizienz von SIMD-basierter Parallelität und der Speicherauslesung durch unzusammenhängenden Speicherzugriff führen. Wir untersuchen, wie sich verschiedene BVH und Knoten Speicherlayouts, so wie das Ablegen der Knoten in verschiedenen Speicherregionen auf die Raytracing Leistung eines GPU-basierten Path Tracers auswirken. Des Weiteren optimieren wir das BVH Layout anhand von Informationen aus einem Vorverarbeitungsschritt durch Anwendung verschiedener Baum Umordnungstechniken und erzielen dadurch eine höhere Raytracing Leistung.

Unser letzter Beitrag ist im Gebiet der schnellen Konstruktion von BVHs und kd-Bäumen hoher Qualität. Eine höhere Qualität bedingt für gewöhnlich eine höhere Konstruktionszeit. Um diese zu reduzieren wurden mehrere Algorithmen zur parallelen Beschleunigungsstruktur Konstruktion auf GPUs vorgeschlagen. Sie sind für moderate Szenengrößen in der Lage volle Wiederaufbauten in Echtzeit zu vollziehen, wenn alle Daten in den GPU-Speicher passen. Allein die Menge an Daten, die durch den geometrischen Detailgrad im Produktions-Rendering anfällt, macht diese Verfahren durch den limitierten Grafikspeicher unanwendbar. Existierende Out-of-Core-GPU-Ansätze führen eine hybride Bottom-up/Top-down Konstruktion durch, welche eine reduzierte Qualität in den wichtigen oberen Baumebenen aufweisen. Wir präsentieren einen Multi-GPU-fähigen Out-of-Core-Ansatz zur vollen Oberflächenheuristik-Sweep-basierten Top-down BVH und kd-Baum Konstruktion, welcher auf größere Szenen als konventionelle Ansätze ausgelegt ist und eine höhere Baumqualität erreicht. Das Verfahren wird mit Szenen, die aus bis zu eine Milliarde Dreiecken bestehen, evaluiert und skaliert mit zunehmender Anzahl an GPUs.

URN: urn:nbn:de:tuda-tuprints-88209
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science > Graphics, Capture and Massively Parallel Computing
Date Deposited: 02 Jul 2019 09:19
Last Modified: 09 Jul 2020 02:39
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/8820
PPN: 450280349
Actions (login required)
View Item View Item