Interval analysis for computer graphics

John M. Snyder

1992 · 249 citations · 17 references

Concepts

TL;DR

Computer graphics problems such as ray tracing, interference detection, polygonal decomposition of parametric surfaces, and constructive solid geometry on parametric solids are addressed. The paper aims to apply interval analysis to solve diverse computer graphics problems by presenting SOLVE and MINIMIZE algorithms. The authors develop SOLVE and MINIMIZE algorithms based on interval analysis, employing inclusion functions to bound ranges and enable branch‑and‑bound constraint solving and global minimization. The study presents recent theoretical results on root existence, uniqueness, and global parameterizability of implicitly described manifolds, and demonstrates the approach by extending the algorithms to approximate implicit curves. CR Categories: I.3.5 (Computer Graphics: Computational Geometry and Object Modeling) and G.4 (Mathematical Software: Reliability and Robustness).

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. CR Categories: I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling; G.4 [Mathematical Software]: Reliability and Robustness Additional

References

17