Interval Analysis For Computer Graphics
John M. Snyder
California Institute of Technology
From Proceedings of SIGGRAPH 1992, Association for Computing
Machinery Special Interest Group on Computer Graphics (ACM SIGGRAPH),
1992, p. 121-130
Abstract
This paper discusses how interval analysis can be used to solve a wide variety
of problems in computer graphics. These problems include ray tracing,
interference detection, polygonal decomposition of parametric surfaces, and
CSG on solids bounded by parametric surfaces. Only two basic algorithms are
required: SOLVE, which computes solutions to a system of constraints, and
MINIMIZE, which computes the global minimum of a function, subject to a
system of constraints.
We present algorithms for SOLVE and MINIMIZE using interval analysis as
the conceptual framework. Crucial to the technique is the creation of
"inclusion functions"
for each constraint and function to be minimized.
Inclusion functions compute a bound on the range of a function, given a
similar bound on its domain, allowing a branch and bound approach to
constraint solution and constrained minimization. Inclusion functions also
allow the MINIMIZE algorithm to compute global rather than local minima,
unlike many other numerical algorithms.
Some very recent theoretical results are presented regarding existence and
uniqueness of roots of nonlinear equations, and global parameterizability of
implicitly described manifolds. To illustrate the power of the approach, the
basic algorithms are further developed into a new algorithm for the
approximation of implicit curves.