Abstract:
The intersection problem between curves and surfaces has wide applications in computer graphics and computer-aided design. Iterative methods, such as the Newton’s method, are efficient but need good initial values, while clipping methods are robust to obtain all intersection points but their efficiency of computation is not so good, especially for computing a contact intersection point. This paper presents a hybrid method for computing intersections between two B-spline curves. There are three main contributions. Firstly, it provides an efficient clipping method of linear complexity, which can be used to obtain good initial values. Secondly, it presents a simple method for verifying traversal cases, and provides a derivative-free method with a higher efficiency index which generalizes the secant method. Finally, it presents a new iterative formula of convergence rate 2 for a contact case, which achieves much better performance than those of prevailing Newton’s method and clipping methods. In principle, by combining with root-isolation method, it can be applied for the intersection problem of non-polynomial curves. Numerical experimental results show that, comparing with prevailing Newton’s method, the computational efficiency of the new method can be improved by about 10% and 100%-300% for a traversal case and a contact case, respectively.