Skip to main content
Journal cover image

Computability and complexity of ray tracing

Publication ,  Journal Article
Reif, JH; Tygar, JD; Yoshida, A
Published in: Discrete & Computational Geometry
December 1, 1994

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. © 1994 Springer-Verlag New York Inc.

Duke Scholars

Altmetric Attention Stats
Dimensions Citation Stats

Published In

Discrete & Computational Geometry

DOI

EISSN

1432-0444

ISSN

0179-5376

Publication Date

December 1, 1994

Volume

11

Issue

1

Start / End Page

265 / 288

Related Subject Headings

  • Computation Theory & Mathematics
  • 49 Mathematical sciences
  • 46 Information and computing sciences
  • 0802 Computation Theory and Mathematics
  • 0103 Numerical and Computational Mathematics
  • 0101 Pure Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Reif, J. H., Tygar, J. D., & Yoshida, A. (1994). Computability and complexity of ray tracing. Discrete & Computational Geometry, 11(1), 265–288. https://doi.org/10.1007/BF02574009
Reif, J. H., J. D. Tygar, and A. Yoshida. “Computability and complexity of ray tracing.” Discrete & Computational Geometry 11, no. 1 (December 1, 1994): 265–88. https://doi.org/10.1007/BF02574009.
Reif JH, Tygar JD, Yoshida A. Computability and complexity of ray tracing. Discrete & Computational Geometry. 1994 Dec 1;11(1):265–88.
Reif, J. H., et al. “Computability and complexity of ray tracing.” Discrete & Computational Geometry, vol. 11, no. 1, Dec. 1994, pp. 265–88. Scopus, doi:10.1007/BF02574009.
Reif JH, Tygar JD, Yoshida A. Computability and complexity of ray tracing. Discrete & Computational Geometry. 1994 Dec 1;11(1):265–288.
Journal cover image

Published In

Discrete & Computational Geometry

DOI

EISSN

1432-0444

ISSN

0179-5376

Publication Date

December 1, 1994

Volume

11

Issue

1

Start / End Page

265 / 288

Related Subject Headings

  • Computation Theory & Mathematics
  • 49 Mathematical sciences
  • 46 Information and computing sciences
  • 0802 Computation Theory and Mathematics
  • 0103 Numerical and Computational Mathematics
  • 0101 Pure Mathematics