高级检索

两条NURBS曲线求交的高效迭代方法

An Efficient Iterative Method for Intersecting Two NURBS Curves

  • 摘要: 针对NURBS曲线求交问题, 提出一种基于有理函数插值的高效迭代算法. 针对传统方法如牛顿法和割线法对初始值敏感且难以处理相切情况, 隐式化法和纯细分法存在计算复杂度高或数值不稳定问题, 提出结合细分法的新型有理函数插值迭代策略, 有效地提升求交计算效率和迭代计算稳定性. 首先构造双点导数约束的有理插值函数, 逼近曲线参数方程; 然后推导出一元二次方程获取相应的迭代公式, 实现高效的收敛. 实验包含贯穿、相切及4 000例不同次数曲线的基准测试. 结果表明, 与现有的同类迭代法相比, 在相切的情况下, 所提算法效率提高约200%; 数值实例结果表明, 该算法的整体求交效率是OCCT几何内核的5~50倍, 比ACIS几何内核高21%~180%, 证明了其有效性.

     

    Abstract: This paper presents an efficient iterative algorithm using rational function interpolation for NURBS curve intersection. Traditional methods, like Newton’s and Secant methods, are sensitive to initial values and struggle with tangential cases, while implicitization and subdivision methods exhibit high computational complexity or instability. To address these shortcomings, we developed a novel iterative strategy that inte-grates rational function interpolation with a subdivision method, which significantly improves both the ef-ficiency and stability of the intersection calculation. The algorithm first constructs a rational interpolation function, constrained by two-point derivatives, to approximate the curves’ parametric equations. It then de-rives a corresponding iterative formula from a quadratic equation to achieve rapid convergence. We per-formed extensive experiments, including scenarios with crossing and tangential intersections, alongside a benchmark test involving 4 000 curves of varying degrees. Results showed that for tangential intersections, our algorithm is approximately 200% more efficient than comparable iterative methods. Furthermore, nu-merical examples demonstrate that the overall intersection efficiency is 5 to 50 times that of the OCCT and 21% to 180% higher than the ACIS, confirming the algorithm’s effectiveness.

     

/

返回文章
返回