ABSTRACT
Earlier approaches to surface intersection used the subdivision properties of NURBS surfaces based on a ‘divide and conquer’ paradigm [13]. However, this approach may be slow and is not guaranteed to be robust in terms of finding all components of the intersection curve. In the last decade ‘marching methods’ have received a lot of attention for the evaluation of intersection curves [13,1,2,3,9]. Tracing techniques involve the computation of a start ing point on each component and locating all the singular points. Given the
starting points, these algorithms use marching methods to trace the intersec tion curve and in the process use robust methods to determine all the branches at singular points. In particular, the tracing algorithms use the algebraic for mulation of the intersection problem (e.g. three algebraic equations in four unknowns for NURBS surfaces) and find successive points on the curve with first order approximations and refinement using Newton-Raphson’s method. However, it is not clear what a good step size should be at each stage. A small step size makes the overall approach slow, and a large step size may result in convergence problems. It is possible to compute a higher order local approx imation at each point on the curve [1], however this involves a great deal of symbolic computation and may not be efficient for high degree intersection curves. Therefore, implementing a robust tracer based on Newton-Raphson’s method can be fairly non-trivial and in many cases may not work at all [5]. Other approaches consist of approximating the intersection curve using lattice methods or geometric Hermite approximation [15].
