高级检索

两条B样条曲线求交的高效计算方法

An Efficient Method for Computing the Intersection bewteen Two B-Spline Curves

  • 摘要: 曲线曲面间求交计算在CG和CAD中有着广泛的应用.牛顿法等迭代法计算效率高但需要良好的初始值;裁剪法具有良好的鲁棒性但计算效率不理想,尤其是对于相切情况的求交问题.为此,提出一种计算2条B样条曲线交点的混合方法.首先提出一种高效的线性复杂度裁剪方法,用于获得良好的初始值;然后提出一种与导数无关且效率更高的改进的割线法,用于验证贯穿性相交情况;最后提出一个相切情况下收敛阶为2的迭代公式,其性能远优于现有的牛顿法和裁剪法.理论上,混合方法若与根隔离法相结合,可以应用于更多类型曲线间的求交问题.数值实验结果表明,与现有的同类方法相比,在贯穿情况下,所提方法的计算效率提高约10%,在相切情况下则提高约100%~300%.

     

    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.

     

/

返回文章
返回