ComputingComputer ScienceComputer GraphicsData VisualizationInformation VisualizationInformation GraphicsStatistical GraphicsInterval Analysis
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).
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
17
Chanderjit L. Bajaj, Christoph M. Hoffmann, Robert E. Lynch et al. · Computer Aided Geometric Design · 1988 · 253 citations
On ray tracing parametric surfaces
Daniel L. Toth · ACM SIGGRAPH Computer Graphics · 1985 · 185 citations
Accurate triangulations of deformed, intersecting surfaces
Brian Von Herzen, Alan H. Barr · 1987 · 173 citations · Full text
Guaranteed ray intersections with implicit surfaces
D. Kalra, Alan H. Barr · 1989 · 156 citations