Ray distribution aware heuristics for bounding volume hierarchies construction in ray tracing

In the last few years, real-time computer graphics have been transitioning from a pipeline based on rasterization to one using ray tracing. Ray tracing makes it possible to accurately simulate the physical behavior of light rays, enabling developers of graphics content to reproduce high-fidelity scenes without using a plethora of techniques to mimic light transport. While ray tracing is widely used for off-line rendering, such as for CGI effects in films or animated movies, the same cannot be stated for on-line applications, such as videogames. The main problem with ray tracing is that simulating light transport is computationally expensive, reason why in recent videogames ray tracing is only used on small portions of the scene, or to simulate some effects (such as reflections, shadows, or ambient occlusion). In order to increase the spread of ray tracing in on-line rendering applications too, research is moving in two macro directions. The first one is to build GPUs with an architecture more suited for ray tracing, such as the RT cores from Turing Nvidia GPUs. The second, but not least important one, is to design software optimizations to make ray tracing cheaper. One of the problems that is ubiquitous in the ray tracing environment is to detect collisions between a ray and the geometry of the scene to render. Given the huge amount of primitives present in modern graphic applications, it is necessary to use a data structure to accelerate the ray collision retrieval process. The state-of-the-art structure is the Bounding Volume Hierarchy (BVH), a spatial binary tree which hierarchically organizes primitives, making it possible to skip entire sections of the scene that are spatially far away from the ray that is being traced. Building an optimal BVH is an NP-complete problem, therefore greedy algorithms and heuristics are used to construct them in real-world applications. The two heuristics used in state-of-the-art, namely Surface Area Heuristic (SAH) and Longest Splitting Plane Heuristic (LSPH), lay their foundations on some assumptions, the most relevant of which is that the ray distribution of the scene is uniform. However, another optimization used in a previous step of the ray tracing algorithm, called Monte Carlo Importance Sampling, generates artifacts in the distribution of the rays in the scene, rendering the SAH and LSPH hypothesis not accurate. In this thesis we propose two novel heuristics which are aware of the artifacts in the ray distribution, and leverage them to build potentially better BVHs, and therefore making any application using ray tracing faster. We also develop a top level structure enabling the use of the heuristics, along with a modern C++ implementation of the presented ideas. The implementation is eventually used in the testing phase, where we extract experimental results and comment on them. The first heuristic is called Projected Area Heuristic (PAH), and aims at better estimating the amount of rays that hits each node of the BVH, in order to have a better cost function during its construction. The second one, namely Splitting Plane Facing Heuristic (SPFH), aims at reducing the overlap among nodes of the BVH, consequently reducing the number of intersection tests needed during the BVH traversal phase.

Negli ultimi anni, la computer grafica in tempo reale sta passando da una pipeline basata sulla rasterizzazione a una che utilizza il ray tracing. Il ray tracing consente di simulare accuratamente il comportamento fisico dei raggi di luce, permettendo agli sviluppatori di contenuti grafici di riprodurre scene in modo realistico, senza utilizzare una miriade di tecniche per imitare il comportamento della luce. Se il ray tracing è ampiamente utilizzato per il rendering off-line, come ad esempio per gli effetti CGI nei film o nei cartoni animati, lo stesso non si può dire per le applicazioni on-line, come i videogiochi. Il problema principale del ray tracing è che simulare il trasporto della luce è computazionalmente costoso, motivo per cui nei videogiochi recenti il ray tracing è utilizzato solo su piccole porzioni della scena, o per simulare alcuni effetti (come riflessi, ombre o occlusione ambientale). Per aumentare la diffusione del ray tracing anche nelle applicazioni di rendering in tempo reale, la ricerca si sta muovendo in due macro direzioni. La prima è costruire GPU con un'architettura più adatta al ray tracing, come i core RT delle GPU Turing di Nvidia. La seconda, ma non meno importante, è progettare ottimizzazioni software per rendere il ray tracing meno costoso. Uno dei problemi onnipresenti nell'ambiente del ray tracing è rilevare le collisioni tra un raggio e la geometria della scena da renderizzare. Data la grande quantità di primitive presenti nelle moderne applicazioni grafiche, è necessario utilizzare una struttura dati per accelerare il processo di rilevamento delle collisioni dei raggi. La struttura usata allo stato dell'arte è la Bounding Volume Hierarchy (BVH), un albero binario spaziale che organizza gerarchicamente le primitive, rendendo possibile saltare intere sezioni della scena che sono lontane dal raggio che viene tracciato. Costruire un BVH ottimale è un problema NP-completo, quindi nelle applicazioni di uso comune si utilizzano algoritmi greedy ed euristiche. Le due euristiche utilizzate allo stato dell'arte, ovvero la Surface Area Heuristic (SAH) e la Longest Splitting Plane Heuristic (LSPH), si basano su alcune assunzioni, la più rilevante delle quali è che la distribuzione dei raggi nella scena sia uniforme. Tuttavia, un'altra ottimizzazione utilizzata in una fase precedente dell'algoritmo di ray tracing, chiamata Monte Carlo Importance Sampling, genera artefatti nella distribuzione dei raggi nella scena, rendendo l'ipotesi su cui si basano SAH e LSPH non accurata. In questa tesi proponiamo due nuove euristiche che tengono in considerazione gli artefatti nella distribuzione dei raggi e li sfruttano per costruire BVH potenzialmente migliori, migliorando dunque le prestazioni di qualunque applicazione usi il ray tracing. Sviluppiamo anche una struttura top-level che consente l'uso delle euristiche, insieme a un'implementazione in C++ moderno delle idee presentate. L'implementazione viene infine utilizzata nella fase di test, dove estraiamo i risultati sperimentali e li commentiamo. La prima euristica è chiamata Projected Area Heuristic (PAH), e mira a stimare meglio la quantità di raggi che colpisce ciascun nodo del BVH, al fine di avere una cost function migliore durante la sua costruzione. La seconda, denominata Splitting Plane Facing Heuristic (SPFH), cerca di ridurre la sovrapposizione tra i nodi del BVH, riducendo di conseguenza anche il numero di test di intersezione necessari durante la fase di attraversamento del BVH.