基于仿射算术和区间运算的直线与NURBS曲线/曲面求交

针对直线与参数空间NURBS曲线、直线与NURBS曲面求交问题，提出了一种改进的基于仿射算术和区间运算的直线与NURBS曲线/曲面求交的有效方法。该方法将基于边曲率或面曲率的子域分解方法应用到求交算法中，快速定位预迭代区间，减少不必要的迭代求交判断。与传统区间迭代算法相比，该求交算法为超线性收敛的快速迭代算法，在一定程度上解决了传统区间运算的“保守性”。另外，该方法放宽了对初始区间的要求，减少迭代次数，提高了迭代算法效率。通过计算区间算子判断给定直线与NURBS曲线/曲面有无交点和存在交点时的交点数目，保证了求解交点精度，为解决直线与曲线/曲面多交点判断及内外环或内外域判断等问题提供了有利条件。数值算例验证了该方法的有效性、计算精度和效率。

An Improved Fast Algorithm for Solving Intersections of Lines and NURBS Curves and Surfaces Using Interval Analysis with Affine Transform

An improved geometric method was presented for efficiently computing intersections between a line and a NURBS curve in parametric space or a line and a NURBS surface using interval arithmetic with affine transform. Combined with the subdomain decomposition algorithm based on the curve or surface curvatures, the appropriate preliminary iterative intervals could be determined quickly. In comparison with conventional interval iterative algorithms, the proposed method was superlinearly convergent which could overcome the conservatism of conventional interval arithmetic to some extents. In addition, the method prossessed the ability to relax requirements for initial iterative intervals, greatly to reduce numbers of unnecessary iterations and to promote the performance and efficiency of interval arithmetic. Based on the numbers of intersection points and the computational accuracy, this method could be applicable to the intersection problems of the inner and outer loop or domain. Numerical examples demonstrate the validity, accuracy and efficiency of the proposed method.