Ray tracing is used in computer graphics to generate images. The process of rendering images using ray tracing includes testing large counts of rays for intersection against geometry. Testing for ray-geometry intersection is more formally known as the Ray Shooting Problem (RSP) and has broad applications across multiple communities. Hierarchical acceleration structures are frequently employed to index geometry and increase processing speed. Such hierarchical structures make it almost impossible for central processing units to predict memory access and branching patterns. This project focuses on the Bounding Volume Hierarchy (BVH) structure and improving its performance when querying large batches of first hit ray-geometry intersections. The core contribution is an Interleaved Prefetching Ray Traversal (IPRT) algorithm that addresses memory and branching issues. Five standardized test scenarios with varying geometric complexity provide evaluation data. The experimental evaluation suggests that for incoherent rays, IPRT achieves 6:1 - 41:8% faster performance compared to Stackless Traversal. However, for fully coherent rays, performance is 68:8 - 149:1% slower. These results suggest that for select ray tracing workloads that elicit low coherence, the IPRT algorithm is likely to outperform Stackless Traversal. A microarchitectural analysis affirms previous research; memory accesses and branching behavior are critical for performance. Surprisingly, addressing each component in isolation yields no significant performance improvement. It is paramount to address the two simultaneously, as the IPRT algorithm does successfully. / Ray tracing används inom datorgrafik för att generera bilder. Att rendera bilder med ray tracing kräver att datorer simulerar stora mängder ljusstrålar i en virtuell miljö. Problemet att beräkna om en stråle träffar geometri är mer formellt känt som Ray Shooting Problem (RSP) och har breda applikationer inom flera områden. Hierarkiska accelerationsstrukturer används ofta för att indexera geometri och öka beräkningshastighet. Sådana hierarkiska strukturer gör det nästan omöjligt för centrala processorenheter att förutsäga minnesåtkomst och förgreningsmönster. Detta projekt fokuserar på Bounding Volume Hierarchy (BVH) strukturen och dess prestanda. En ny algoritm tas fram för att behandla dessa identifierade problem: Interleaved Prefetching Ray Traversal (IPRT). Fem standardiserade testscener med varierande geometrisk komplexitet används för experimentell utvärdering. Den experimentella utvärderingen antyder i jämförelse med Stackless Traversal så uppnår IPRT-algoritmen 6:1 - 41:8% bättre prestanda för osammanhängande strålar. När det gäller helt sammanhängande strålar är prestandan dock 68:8 - 149:1% långsammare. En mikroarkitektisk analys bekräftar tidigare forskning; minnesåtkomst och förgreningsbeteende är mycket viktigt för prestanda. Isolerad optimering av faktorerna ger dessvärre ingen signifikant prestandaförbättring. Det är därför ytterst viktigt att optimera båda komponenter samtidigt, vilket IPRT-algoritmen lyckas med.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-305022 |
| Date | January 2021 |
| Creators | Meyer, Viktor |
| Publisher | KTH, Skolan för elektroteknik och datavetenskap (EECS) |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-EECS-EX ; 2021:696 |
Page generated in 0.0021 seconds