Efficient ray tracing of many light sources

Standard ray tracing algorithm slow down unacceptably when a large number of light sources are in the scene because the shadow determination process is O(n), where n is the number of light sources. This thesis puts forward a new Light Extent Volumes approach to efficiently ray tracing scenes with many light sources. By building a hierarchical tree of light extent volumes one can approach approximately logarithmic complexity for typical scenes in determining which light sources contribute significant irradiance to the intersection point. This allows tens of thousands of light sources in a scene to be rendered in reasonable time. The relative performance of the algorithm improves as the number of light sources increases in the scene. It achieves significant speedup over other existing approaches, up to 150 times faster. Moreover, the algorithm requires minimal memory overhead for shadow testing acceleration. Another important feature is its simplicity of implementation. In addition, the approach is orthogonal to most other global illumination techniques and can be added to existing direct light calculation and optimizations. The Light Extent Volumes approach is a practical algorithm for efficiently ray tracing scenes with many light sources.