Given two sculptured objects, described by a collection of rational Bezier patches, we propose an algorithm that provides the distance between them if the objects are not intersecting, or a measure of penetration otherwise. The algorithm extends the upper-lower bound subdivision approach to the computation of the nearest points by considering the relative orientations between the subdivided patches. All required geometric constructions can be described as rational Bezier patches so that their control points can be precomputed from those of the original patches. Additional operations have been designed to exhibit linear complexity with the total number of involved control points.

Computing the distance between modelled objects is proving to be a fundamental operation for solving many problems in robotics and elsewhere. Most of the previous work in this area has focused on computing the distance between polyhedra, as the problem is easier to solve than the general case and the answer is sufficient for many problems. Here we focus on computing the distance between convex objects defined by NURBS curves or patches, for which the critical step is the evaluation of the support mapping. Experimental results are given for the two-dimensional case.