Computability and complexity of ray tracing
Computability and complexity of ray tracing
复制标题
光线追踪的可计算性和复杂性
DOI：
10.1007/bf02574009
复制
发表时间：
1994
影响因子：
0.8
通讯作者：
A. Yoshida
中科院分区：
文献类型：
--
作者：
J. Reif;J. D. Tygar;A. Yoshida
光线追踪问题是，给定一个光学系统以及初始光线的位置和方向，确定光线是否到达某个给定的最终位置。多年来，光线追踪一直被用于光学系统的设计和分析。光线追踪现在广泛应用于计算机图形学中，在全局光照下渲染具有复杂弯曲物体的场景。我们证明了一些三维简单光学系统（纯几何光学）的光线追踪问题是不可确定的。这些系统既可以由由有理二次方程表示的反射物体组成，也可以由有理线性方程表示的折射物体组成。在更严格的模型中，一些问题被证明是PSPACE困难的，或者有时在PSPACE中。
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.