Unified approach to solve the intersection curve tracing problem in geometric modelling

Abstract

Computation of a parametrization of the intersection curve of two surfaces in R³ is a common and fundamental operation occurring in Geometric Modelling, CAD, Robotics, etc. It is, in general, a non-trivial problem to solve. Except for special classes of surfaces like planes and quadrics, analytical solutions are difficult to obtain, and so numerical approximations are resorted to. A major subproblem associated with the numerical determination of these curves is the problem of numerically tracing a connected curve component given one point on it. A lot of work has been reported in the literature to solve this problem. In particular, a class of methods called marching methods have been popularly used. However, these marching methods suffer from the following drawbacks:

They do not define an approximation rigorously. They do not pay much attention to error control. They are not the most efficient. They are a scattered class of methods.

The aim of this thesis is to eliminate these drawbacks. We first give a rigorous definition of an approximate parametrization to the intersection curve and establish that a carefully defined marching method does produce a valid approximation. Then we formulate the curve tracing problem as a problem of solving a special vector field. This not only forms the unifying factor for existing curve tracing methods, but also leads to new and better alternatives. We suggest various new procedures having good error control capabilities for solving the vector field, and numerically test them on a collection of curve tracing problems taken from the Geometric Modelling literature. Three performance measures having relevance to Geometric Modelling-viz. cost of computation, data size of approximate parametrization, and accuracy-are used to compare the procedures. Based on the data from the numerical testing, we make an overall recommendation on the best procedure for use in Geometric Modelling.