Ray tracing by linear interval estimations

Ray tracing is a method of rendering objects that mimics the behavior of light. It is capable of producing images of high quality and realism. Bezier surfaces are one of the classes of objects to which ray tracing has been successfully applied, and it is of interest to have computer programs which ray trace a Bezier surface quickly and reliably. A recent advance in reliable computing, the introduction of Linear Interval Estimations (LIES) by Buhler, makes possible a new ray tracing algorithm for Bezier surfaces that has enhanced robustness characteristics. LIEs constitute a new type of bounding volume for Bezier surfaces and subsurfaces. The crucial step in a ray tracing method is determination of ray-surface intersection solutions. In the new method, the generally nonlinear ray-surface intersection problem is replaced with a linear ray-LIE intersection method. For a given subsurface a LIE is computed that is a bounding volume for the subsurface. The solution in parameter space to the ray-LIE intersection gives bounds on the ray-surface intersection solution. Only the part of the ray-LIE intersection solution that is within the original subsurface domain is relevant. The remainder is pruned away to give the portion of the original domain that may contain a ray-surface intersection. The ray-surface intersection solution is found by iterating the sequence of ray-LIE intersection followed by pruning. The use of interval and affine arithmetics produces a reliable method. We are able to prove the method's reliability and illustrate it with experimental results.