COMPUTABILITY AND COMPLEXITY OF RAY-TRACING

The ray-tracing problem is, given an optical system and the position a nd direction of an initial light ray, to decide if the light ray reach es some given final position. 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 under global illumination. We show that ray-tracing problems i n some three-dimensional simple optical systems (purely geometrical op tics) are undecidable. These systems may consist of either reflective objects that are represented by rational quadratic equations, or refra ctive objects that are represented by rational linear equations. Some problems in more restricted models are shown to be PSPACE-hard or some times in PSPACE.