An Efficient Method for Computing the Intersection bewteen Two B-Spline Curves
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 ini-tial values,while clipping methods are robust to obtain all intersection points but their efficiency of compu-tation 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 for-mula of convergence rate 2 for a contact case,which achieves much better performance than those of pre-vailing 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 im-proved by about 10％and 100％-300％for a traversal case and a contact case,respectively.
B-spline curve/curve intersectionclipping methodlinear bounding methodcontact casenon-polynomial function
NETL
NSTL
万方数据
