Specifying useful error bounds for geometry tools: an intersector exemplar
The problem of geometric robustness is pervasive within CAGD. One aspect is to permit convenient user specification of error bounds, so as to ensure the usefulness of geometric models. Often, a useful specification requires an additional interface between the user and the geometric tool. As intersections of spline surface patches are fundamental within CAGD, we present a relation between model space and parameter space error bounds for an intersection algorithm as an exemplar of the additional interface needed for practical geometric tools. In particular, we consider the approximation of the intersection curve between two trimmed-surface patches. The Grandine-Klein intersector produces an approximation that is accurate to within a user-specified error bound, where that error bound is specified in parameter space. However, the end user is typically unaware of the details of this parametric domain, so selection of a parametric space error bound often relies upon heuristics. In this note our goal is to demonstrate how a user-specified error bound is made usable in practice through the straightforward application of the mathematical relation between model-space and parameter-space error bounds. The conversion of the model-space tolerance into a parameter-space tolerance is captured in a pre-processing interface to the intersection algorithm. The software implemented has proven to be reliable, efficient and user-friendly. It is based upon an elementary error analysis, which is also presented. (C) 2003 Elsevier Science B.V. All rights reserved.
error bounds geometric robustness surface intersection algorithms user interface