点到空间NURBS曲线距离的筛选迭代求取方法

陈良骥 马龙飞 赵 波 高 飞

1(桂林理工大学机械与控制工程学院 广西 桂林 541004) 2(天津工业大学机械工程学院 天津 300387)

0 引 言

叶轮作为航空发动机的核心部件，是一类具有代表性且造型比较规范的通道类复杂零件，往往由自由复杂曲面构成[1-3]。由于非均匀有理B样条曲线(NURBS)优秀的自由曲面造型能力，1991年，STEP国际标准亦把NURBS作为定义产品形状的唯一数学方法[4]。如何快速、精确地求取空间一点到样条曲线的最短距离是NURBS曲线在计算辅助设计与制造应用中最基础也是最重要的问题。

李蔚等[5]基于高斯-牛顿法并通过多次微分坐标变换进行微小情况下点到曲线的最短距离求取。郭慧等[6]提出了一种基于NURBS样条曲线插值与遗传算法相结合方法来确定点到曲线最短距离。展俊德等[7]提出了一种利用控制顶点投影法计算点到平面NURBS曲线最小距离的算法，具体做法是将NURBS曲线分割为若干小曲线并对其依次进行搜索得到最短距离。Chen等[8]利用圆形修剪技术提出了一种计算点与NURBS曲线之间的最小距离的新方法。Li等[9]提出了一种新的正交投影方法，用于计算点与空间参数曲线之间的最小距离。Zhu等[10]将欧氏空间中从点到曲线的投影点即正交投影点计算算法扩展到弯曲空间，给出了弯曲空间上正交投影的点计算方法进而得到点到曲线最短距离。

以上方法均可有效求取点到空间NURBS曲线的距离。但由于各种方法对初值等因素的要求不同，算法收敛性也大不相同，且算法较为复杂、鲁棒性差。本文通过对NURBS曲线的节点向量进行两次快速筛选并结合筛选出的节点附近曲线的几何特性精确锁定参数搜索迭代区间，进而通过多次迭代的方式求取最短距离。

1 NURBS曲线模型及生成

在三维笛卡尔空间中，一条关于参数ξ的p次NURBS曲线向量表达式如下：

(1)

式中：{Pi}是NURBS曲线的n+1个三维控制点；{ri}是各个控制点对应权重值；{Ni,p(ξ)}是定义在节点向量X上的p次B样条基函数，这里X={ξ0,ξ1,…，ξn+p+1}。

p次B样条基函数的计算式如下：

(2)

式(2)为一种迭代计算过程，例如对三次NURBS曲线的基函数N1,3(ξ)，其迭代计算过程如图1所示。

图1 三次NURBS曲线某基函数推导示意

p次NURBS曲线基函数的一阶导函数可用如下表达式计算出：

(3)

则NURBS曲线的一阶导矢表达式为：

(4)

2 最短距离求取

2.1 理论最短距离模型

现行方法中，求取空间点A(xA,yA,zA)到NURBS曲线的最短距离主要采取在NURBS曲线上搜索数据点的方法，逐一求取与A的距离，并进行大小比较，直到搜索到距离最短时为止。如果对NURBS曲线进行整体搜索，即相当于在曲线的参数空间ξ∈[0，1]内进行搜索。如此可得整体搜索时，A点到NURBS曲线的最短距离dmin的数学计算模型：

(5)

按式(5)计算点到NURBS曲线间的最短距离是一种理论求取值，实际上由于参数空间的连续性，可取参数点有无穷多个，因此整体搜索计算最短距离的方法效率低下而且实际应用时也是不可行的。对此，本文提出如下参数搜索区间快速确定方法，将最短距离的求取进行参数搜索区间的预处理，直接缩小参数搜索范围快速锁定最短距离所对应的参数范围。

2.2 参数搜索区间锁定

搜索区间锁定的目的是对可能存在最短距离的参数范围进行精确定性分析，减小距离计算的工作量，提高最短距离搜索程序运行速度。下面分两步渐进锁定参数搜索区间。

如图2所示，A为NURBS曲线外待求与NURBS曲线最短距离的空间点，ξi(i=0,1,…,n+p+1)为定义NURBS曲线的节点向量X中的某个节点参数。首先应计算出NURBS曲线所有节点参数对应点与空间点A的距离，以此确定初步参数搜索区间的大致位置。将节点向量X各节点参数映射至线性空间可得到具体的参数数据点，并结合式(5)进行初次筛选，得到最小距离l，同时记录其对应节点参数。

图2 节点中的最短距离点确定

经过初步筛选后可知所求取参数的搜索区间应在参数ξi附近。显然，最终要锁定的参数区间必须包含最短距离点所对应参数在内才能实现最短距离的求取。

将ξi代入式(1)可以得到该参数所对应的NURBS的数据点Q(ξi)，曲线外一点A与Q(ξi)间的单位方向向量TAQ如下：

(6)

将ξi代入式(4)可得到NURBS曲线在点Q(ξi)处的一阶导矢Q′(ξi)。

为便于后面叙述的理解，我们先对空间点、NURBS曲线上的点、NURBS曲线在某点处一阶导矢以及最短距离间的关系作如图3所示的说明。图3中，A和B均为NURBS曲线外的空间点，若NURBS曲线上与A或B距离最短的点为已知，则A或B与相应NURBS曲线上最短距离点间的连线应与NURBS曲线上距离最短点处的一阶导矢呈相互垂直的几何关系。再结合式(6)，我们可根据TAQ与一阶导矢Q′(ξi)间的夹角是否为直角来判断NURBS曲线上的点是否为与空间点距离最短的点。夹角θ可由式(7)求得。

(7)

图3 最短距离下点与曲线几何关系

图4为夹角θ在距离最短点附近的大小变化。可知夹角θ在距离最短点处为直角，在距离最短点左侧为锐角，在距离最短点右侧为钝角，利用这个规律可对最短距离点的参数所在的搜索区间进行最终锁定。最终锁定的方法如下：

1) 若θ=90°，则该参数所对应曲线数据点为最短距离点，参数代入式(5)完成最短距离求取。

2) 若θ<90°，则向该参数右端按预先设置的参数增量继续搜索，重复计算出新的夹角θ，直至θ≥90°。假定此时重复计算的次数为k，此时对应的参数为ξk，则可将参数搜索区间确定为[ξk-1，ξk]。

3) 若θ>90°，则向该参数左端按预先设置的参数增量继续搜索，重复计算出新的夹角θ，直至θ≤90°。假定此时重复计算的次数k，此时对应的参数为ξk，则可将参数搜索区间确定为[ξk，ξk-1]。

(a) (b)图4 不同位置下夹角θ的变化

2.3 求取距离

在参数的搜索区间最终锁定后，即可进行最小距离点的参数的搜索求解计算。求解计算的核心思想是将参数ξ的参数搜索区间[ξ左,ξ右]进行等间距划分为若干个参数点，如图5所示，应用式(5)求得相对较小距离及与之对应的参数，以该参数为中心参数，缩短参数搜索区间后再次将区间等间距划分，直到前后求得的较小距离差小于预设求解误差时停止搜索计算。现将具体搜索求解计算过程陈述如下。

图5 参数搜索区间等间距划分搜索

经过第2.2节中所述几种情况的分析，可获得参数ξ的最终参数搜索区间[ξ左,ξ右]，将该区间等间距划分为H个参数点，则每个参数点的参数间距应为：

(8)

所以，每个参数点的数值应为：

ξj=ξ左+jΔξj=1,2,…,H

(9)

将ξ左、ξ右、所有参数值ξj代入式(5)可求得第1次搜索的较小距离ε1。

第2次搜索时，以ε1所对应的参数点为中心参数ξ中，采取将参数搜索区间长度缩小一半的处理方式。即区间长度由式(10)确定。

(10)

将ξ左和ξ右分别重新计算为：

ξ左=ξ中-L2/2

(11)

ξ右=ξ中+L2/2

(12)

再次将参数搜索区间[ξ左,ξ右]等间距划分为H个参数后，可求得第2次搜索后的较小距离ε2。

判断|ε2-ε1|是否小于或等于预设求解误差σ，若是则最小距离ε为ε1和ε2中的较小者，若否则继续进行第3次、第4次、…、第m次搜索，直到|εm-εm-1|≤σ成立为止，取最小距离ε为εm和εm-1中的较小者。

以上为曲线外一点到NURBS曲线最短距离的求取方法，图6为求取流程。

图6 最短距离求取流程

3 实例验证

一般NURBS曲线G2连续即可满足大部分场合，G2连续代表样条曲线二阶导矢连续，故本文对p=3的NURBS曲线进行研究。给定曲线外一点A。NURBS曲线生成数据来自五轴数控加工数据。先由CAM软件生成叶轮流道曲面的刀具切削运动轨迹，经过刀具轨迹离散，最终生成含有刀心点、刀轴向量、刀触点的刀位文件。切削语句的格式如下：

GOTO/x,y,z,i,j,k＄＄x′,y′,z′

上述格式中：(x,y,z)为工件坐标系下刀心点位置坐标，取其进行曲线拟合。参加NURBS曲线拟合的数据点(刀心点坐标)如表1所示。

表1 待拟合数据点

通过编制的MATLAB程序读取表1中数据点进行NURBS样条拟合。拟合后节点向量X=(0 0 0 0 0.142 9 0.214 4 0.285 9 0.357 3 0.428 8 0.500 2 0.571 6 0.643 1 0.714 5 0.785 8 0.857 0 1 1 1 1)，拟合时反算求得的控制点如表2所示。

表2 NURBS曲线控制点

续表2

取待测点A1=(109.1 76.1 71)、A2=(114.5 128.2 39)，通过编制的MATLAB程序读取NURBS曲线信息并进行最短距离求取。求解点到样条曲线距离问题为无约束非线性问题，将文献[3]所使用的高斯-牛顿法应用于本文的问题背景，高斯-牛顿法收敛速度为二阶且精度较高，常用于解决该类问题。

将文献[3]中NURBS节点向量区间的中值参数ξ=0.5设置为迭代初值，编制并运行相应的MATLAB程序，获得的相关数据与本文方法获得的数据进行对比，表3为两种方法在求解误差σ=0.000 1 mm下求解的最短距离值及计算耗时情况。

表3 求取的最短距离及计算耗时

可以看出，通过对两点距离的求取的验证，两种方法皆可求得最短距离。而本文方法的求取效率比较高，耗时短。

4 结 语

针对空间一点到NURBS曲线的最短距离求取问题，提出一种参数区间筛选迭代方法。该方法不用事先给定初值，可直接通过点与曲线的几何关系，经两个步骤后最终锁定参数搜索区间，然后根据最短距离求解误差的要求对该参数区间进行迭代搜索，求得最短距离。通过MATLAB编程与其他现有方法对比后，结果表明本文方法不仅能达到相同的求取精度，而且还能具有较高的求取效率。