Average-Case Ray Shooting Algorithms for Global Illumination

application of Monte Carlo methods, thus repetively sampling some given
scene space via a ray shooting algorithm. I will present the state of the
art of ray shooting algorithms, since their use takes the significant time
portion within the global illumination algorithms. I will describe the
theory behind the ray shooting algorithms concerning the time and space
complexity, particularly for the algorithms directed at the average-case
complexity. Then I will survey the basic methods developed within computer
graphics and computational geometry within last two decades with their pros
and cons. In detail I will present the ray shooting algorithms based on
kd-trees, including the kd-tree construction and ray traversal, special
techniques for memory mapping of the kd-tree, and less known techniques for
the kd-tree construction and traversal. With the stress on the average-case
complexity I will present how far from optimum are the current ray shooting
algorithms. At present this issue is becoming quite important, since in a
few years it is likely to be possible to apply the global illumination
algorithms on a single processor in real-time rate (25fps) even for huge
sized scenes. I will also discuss the open problems related to ray shooting
algorithms and possible directions for future research.