don@andante.att.com (Don Mitchell) (11/08/90)
"Robust Ray Tracing with Interval Arithmetic", by Don Mitchell, pp.
68-74 in the Proceedings of Graphics Interface '90, Canadian Infor-
mation Processing Society (Toronto), 1990.
"Very interesting paper, but I believe that the convergence of
the method is quite slow, even slower than bisection."
The interval-arithmetic algorithm is a root-isolation algorithm. It
gets used in combination with root-refinement (something much faster
than bisection and much safer than Newton's method, hopefully). The
speed of convergence depends a lot on how you are refining
intersections. If you are just performing the interval algorithm until
it converges to a root, that would be very slow and not really a
proper application of the method.
For a benchmark image containing a number of 4th degree algebraic
surfaces, the interval method was about three times slower than a
specialized polynomial solver (e.g., Sturm sequences). Its hard to
compare its run time on transcendental surfaces, since I don't know any
other way except Kalra's Lipschitz method (described in SIGGRAPH 89).
I think interval arithmetic is more straightforward than the Lipschitz
methods, particularly for surfaces with singular gradients (like
concave superquadrics). It does not require an off-line human
calculation to derive Lipschitz conditions.
There are also a lot of improvements that I didn't mention (or
implemented later). For example, there are faster interval multiply
algorithms than the one I gave. You can do the root isolation
algorithm with (F, dF/dt) instead of (F, grad F). There are also ways
of using the derivative intervals to narrow the function intervals with
the mean-value theorem.
Like a lot of techniques, there is a long journey between theory and
implementation.