Computing the distance between canal surfaces

Abstract

A canal surface is the envelope of a one-parameter set of moving spheres. We present an accurate and efficient method for computing the distance between two canal surfaces. First, we use a set of cone-spheres to enclose a canal surface. A cone-sphere is a surface generated by sweeping a sphere along a straight line segment with the radius of the sphere changing linearly; thus it is a truncated circular cone capped by spheres at the two ends. Then, for two canal surfaces we use the distances between their bounding cone-spheres to approximate their distance; the accuracy of this approximation is improved by subdividing the canal surfaces into more segments and use more cone-spheres to bound the segments, until a pre-specified threshold is reached. We present a method for computing tight bounding cone-spheres of a canal surface, which is an interesting problem in its own right. Based on it, we present a complete method for efficiently computing the distances between two canal surfaces using the distances among all pairs of their bounding cone-spheres. The key to its efficiency is a novel pruning technique that can eliminate most of the pairs of cone-spheres that do not contribute to the distance between the original canal surfaces. Experimental comparisons show that our method is more efficient than Lee et al's method [13] for computing the distance between two complex objects composed of many canal surfaces. © 2010 Springer-Verlag.