Interval analysis for computer graphics
John M. Snyder · ACM SIGGRAPH Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH) · 1992
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 numerica...
Cited by 246 works. doi:10.1145/133994.134024
Authors
References
- Methods and Applications of Interval Analysis
- Introduction to Interval Computation
- New Computer Methods for Global Optimization
- Proceedings on Graphics interface '91
- On ray tracing parametric surfaces
- Accurate triangulations of deformed, intersecting surfaces
- Geometric collisions for time-dependent parametric surfaces
- Geometric collisions for time-dependent parametric surfaces
- Tracing surface intersections
- Guaranteed ray intersections with implicit surfaces