Approximate distance fields with non-vanishing gradients

For a given set of points S, a Euclidean distance field is defined by associating with every point p, of Euclidean space E-d a value that is equal to the Euclidean distance from p to S. Such distance fields have numerous computational applications, but are expensive to compute and may not be sufficiently smooth for some applications. Instead, popular implicit modeling techniques rely on various approximate fields constructed in a piecewise manner. All such constructions lead to sacrifices in distance properties that have not been properly studied or characterized. We show that the quality of an approximate distance field may be characterized locally near the boundary by its order of normalization and can be studied in terms of the field derivatives. The approach allows systematic quantitative assessment and comparison of various construction methods. In particular, we provide detailed analysis of several popular field construction methods that rely on set decompositions and R-junctions, as well as identify the key factors affecting the quality of the constructed fields. (C) 2004 Elsevier Inc. All rights reserved.