Computability and complexity of ray tracing


Journal Article

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.

Full Text

Duke Authors

Cited Authors

  • Reif, JH; Tygar, JD; Yoshida, A

Published Date

  • December 1, 1994

Published In

Volume / Issue

  • 11 / 1

Start / End Page

  • 265 - 288

Electronic International Standard Serial Number (EISSN)

  • 1432-0444

International Standard Serial Number (ISSN)

  • 0179-5376

Digital Object Identifier (DOI)

  • 10.1007/BF02574009

Citation Source

  • Scopus