Editing Ray tracing (graphics) (section)

== Computational complexity ==
Various complexity results have been proven for certain formulations of the ray tracing problem. In particular, if the decision version of the ray tracing problem is defined as follows<ref>{{cite web |title=Computability and Complexity of Ray Tracing |url=https://www.cs.duke.edu/~reif/paper/tygar/raytracing.pdf |website=CS.Duke.edu }}</ref> – given a light ray's initial position and direction and some fixed point, does the ray eventually reach that point, then the referenced paper proves the following results:
* Ray tracing in 3-D optical systems with a finite set of reflective or refractive objects represented by a system of rational quadratic inequalities is [[Undecidable problem|undecidable]].
* Ray tracing in 3-D optical systems with a finite set of refractive objects represented by a system of rational linear inequalities is undecidable.
* Ray tracing in 3-D optical systems with a finite set of rectangular reflective or refractive objects is undecidable.
* Ray tracing in 3-D optical systems with a finite set of reflective or partially reflective objects represented by a system of linear inequalities, some of which can be irrational is undecidable.
* Ray tracing in 3-D optical systems with a finite set of reflective or partially reflective objects represented by a system of rational linear inequalities is [[PSPACE]]-hard.
* For any dimension equal to or greater than 2, ray tracing with a finite set of parallel and perpendicular reflective surfaces represented by rational linear inequalities is in PSPACE.