The Computability and Complexity of Optical Beam Tracing
Consider optical systems consisting of a set of refractive or reflective surfaces. The ray tracing problem is, given an optical system and the position and direction of an initial light ray, to decide if a light ray reaches some given final position. We assume the position and the tangent of the incident angle of the initial light ray is rational. For many years, ray tracing has been used for designing and analyzing optical systems. Ray tracing is now used extensively in computer graphics to render scenes with complex curved objects. We investigate the computability and complexity of the ray tracing problems over various optical models. Our results show that, depending on the optical model, ray tracing is sometimes undecidable, sometimes PSPACE-hard, and sometimes in PSPACE.
