Acceleration of P-k-d tree traversal using probabilistic occlusion

Abstract

The growing amount and complexity of particle data in various fields of study (e.g. molecular dynamics) poses an increasing demand of high-quality and high-performance visualizations of such data. Ray tracing is known for the high image quality it can produce and its well-suitedness to global illumination effects, e.g. shadows or ambient occlusion. Effects like these can serve as helpful cues for understanding three-dimensional structures within the data. As an optimization for the rendering of particle data, Wald et al. [WKJ+15] suggest the Particle-k-d (P-k-d) tree, a ray tracing acceleration structure for particles which does not require any memory overhead. Ibrahim et al. [IRR+21] propose a novel, probabilistic method to accelerate particle rendering by culling particles which are likely to be occluded. The goal of this thesis is to examine the viability of probabilistic occlusion culling in the context of a P-k-d-based ray tracer. I contribute by adapting the method proposed by Ibrahim et al. for the use within a ray tracing application and implementing the adapted method as an extension of a P-k-d ray tracer by Gralka et al. [GWG+20]. I go on to evaluate my approach with respect to visual quality and performance. My findings show that probabilistic occlusion culling can provide a performance improvement during super sampling. However, the magnitude of the improvement and the effect on visual quality are greatly dependent on the size of and features within the data set among other factors.

Die wachsende Menge und Komplexität von Partikeldaten in zahlreichen Forschungsgebieten (z.B. Molekulardynamik) erhöht die Nachfrage an hochqualitativen und hochperformanten Visualisierungen solcher Daten. Raytracing ist allgemein für seine hohe Bildqualität bekannt, sowie für seine gute Eignung gegenüber globaler Beleuchtungseffekte (z.B. Schatten oder Ambient Occlusion). Solche Effekte können als hilfreiche Referenz für das Verständnis drei-dimensionaler Strukturen innerhalb der Daten dienen. Um Raytracing für das Rendering von Partikeldaten zu optimieren, schlagen Wald et al. [WKJ+15] den Partikel-k-d-Baum (P-k-d-Baum) vor, eine Beschleunigungsstruktur für Partikeldaten, welche ohne zusätzlichen Speicherbedarf auskommt. Ibrahim et al. [IRR+21] präsentieren eine neuartige, probabilistische Methode zur Beschleunigung des Partikelrenderings durch Cullen mit großer Wahrscheinlichkeit verdeckter Partikel. Das Ziel dieser Arbeit ist, die Praktikabilität des Cullings basierend auf probabilistischer Verdeckung im Kontext eines P-k-d-basierten Raytracers zu untersuchen. Hierzu trage ich Anpassungen der Methode von Ibrahim et al. bei und implementiere die angepasste Methode als Erweiterung eines P-k-d-Raytracers von Gralka et al. [GWG+20]. Des Weiteren evaluiere ich den Ansatz hinsichtlich visueller Qualität und Leistungsfähigkeit. Meine Ergebnisse zeigen, dass Culling durch probabilistische Verdeckung eine Leistungssteigerung während des Supersamplings erzielen kann. Diese, sowie der Effekt auf die visuelle Qualität, hängen jedoch u.A. stark von der Größe und den Eigenschaften der gerenderten Daten ab.