Computability and complexity of ray tracing |
| |
Authors: | J H Reif J D Tygar A Yoshida |
| |
Institution: | (1) Department of Computer Science, Duke University, 27706 Durham, NC, USA;(2) Department of Computer Science, Carnegie Mellon University, 15213 Pittsburgh, PA, USA |
| |
Abstract: | The ray-tracing problem is, given an optical system and the position and direction of an initial light ray, to decide if the light ray reaches 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 in some three-dimensional simple optical systems (purely geometrical optics) are undecidable.
These systems may consist of either reflective objects that are represented by rational quadratic equations, or refractive
objects that are represented by rational linear equations. Some problems in more restricted models are shown to be PSPACE-hard
or sometimes in PSPACE.
A preliminary version of this paper appeared as “The Computability and Complexity of Optical Beam Tracing” in theProceedings of the 31st Annual Symposium on Foundations of Computer Science, October 1990, Vol. I, pp. 106–114. The research of J. H. Reif and A. Yoshida was supported in part by Air Force Contract
No. AFOSR-87-0386, DARPA/ARO Contract No. DAAL03-88-K-0195, DARPA/ISTO Contract No. N00014-88-K-0458, and NASA subcontract
550-63 of primecontract NASS-30428. J.D. Tygar's research was supported in part by the Defense Advanced Research Projects
Agency under Contract No. F33615-87-C-1449 and by a National Science Foundation Presidential Young Investigator Award under
Contract No. CCR-8858087. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|