An algorithm for finding the intersection lines between two B-spline surfaces

A divide-and-conquer algorithm is presented for finding all the intersection lines between two B-spline surfaces. Each surface is organized as an $\text{n-}\text{branch}$ tree. For each intersection line, an initial point is detected after a depth-first search along one tree, ie the host tree. Extrapolation methods are then used to trace the entire length of the line, thus the line appears naturally in a continuous form. Efficiency of the algorithm is achieved by the employment of an adaptive division strategy and by the careful choice of the representation basis of the patches on both surfaces.