两条B样条曲线求交的高效计算方法
An Efficient Method for Computing the Intersection bewteen Two B-Spline Curves
王永澳 1吕杭汀 1陈小雕1
作者信息
- 1. 杭州电子科技大学计算机学院 杭州 310018
- 折叠
摘要
曲线曲面间求交计算在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 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样条曲线/曲线求交/裁剪法/线性包围法/相切/非多项式函数Key words
B-spline curve/curve intersection/clipping method/linear bounding method/contact case/non-polynomial function引用本文复制引用
基金项目
国家自然科学基金面上项目(61972120)
出版年
2024
NETL
NSTL
万方数据