Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!mit-eddie!andante!don
From: don@andante.att.com (Don Mitchell)
Newsgroups: comp.graphics
Subject: Ray Tracing with Interval Arithmetic
Message-ID: <44326@andante.att.com>
Date: 7 Nov 90 22:44:58 GMT
Organization: AT&T Bell Laboratories, Murray Hill, NJ
Lines: 35


    "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.