Visibility using Ray Tracing Algorithms and Data Structures

Ray tracing is a popular rendering method with built in visibility determination. However, the computational costs are significant. To reduce them, there has been extensive research leading to innovative data structures and algorithms that optimally utilize both object and image coherence. Investigating these from a visibility determination context without considering further optical effects is the main motivation. Three methods – one structure and two coherent tree traversal algorithms – are discussed. While the structure, RBSP Tree, aims to increase coherence, the algorithms, Coherent Rendering and Row Tracing, aim to optimise utilization of coherence provided by ray tracing structures (kd-trees, octrees).