Interval methods in geometric modeling

摘要

This paper is about using interval computations in location, simplification, and root-finding for multivariate implicit functions that are used as shape primitives in a set-theoretic (that is, a CSG) geometric modeller. Three problems are discussed, and solutions to them presented: the location and simplification of the surfaces of semialgebraic sets (surfaces involving some transcendental functions are dealt with as well); the generalization of Newton-Raphson using intervals; and interval ray-tracing. Examples are presented for both conventional three-dimensional geometric models and for CSG models in higher dimensions representing configuration-space maps for moving and colliding three-dimensional objects.