Paper Info
Title
Interval analysis for computer graphics
Abstract
This paper discusses how interval analysis can be used to solve a wide vari- ety 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. Wepresentalgorithms for SOLVEand MINIMIZE using intervalanalysis as the conceptual framework. Crucial to the technique is the creation of "inclu- sion functions" for each constraint and function to be minimized. Inclusion functionscompute a bound on the range of a function, given a similar bound on itsdomain, 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. Somevery recent theoretical resultsarepresented 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 approx- imation of implicit curves.
Year
DOI
Venue
1992
10.1145/142920.134024
Special Interest Group on Computer Graphics
Keywords
DocType
Volume
approximation,constrained minimization,constraint solution,implicit curve,inclusion function,interval analysis
Conference
26
Issue
ISSN
ISBN
2
0097-8930
0-89791-479-1
Citations 
PageRank 
References 
129
11.92
8
Authors
1
Search Limit
100129
Name
Order
Citations
PageRank
John Snyder12579172.17