CAGD: 第八章 曲线的几何处理技术

    第八章 曲线的几何处理技术

前面我们已经介绍了CAD/CAM中常用的曲线表示方法及其相关理论，这些曲线在外形设计和制造中的有效使用很大程度上依赖于能否方便地对其进行各种几何操作，或许设计者要求按一定的光滑约束将多段曲线连接在一起，或许两曲线的交点是工程设计中的一个关键点等等。着就是曲线的几何处理，常用的几何处理包括：求交点（intersecting）、过渡（filleting）、延拓（extension）、混合（blending）、等距线计算（offseting）等。我们这里重点讨论求交、等距线计算以及过渡三种操作。

8.1 曲线求交

求交是最为重要的曲线运算，它是图形裁剪、消隐的基础。按照曲线的类型，可以将曲线求交分为以下三类：

⑴ 两直线段相交

空间两直线段如果排除相互平行与异面，它们的相交有两种情况：或相交于一点，或重叠（部分或全部）。

令两条直线段的参数方程分别为：

则其交点为，即

因为，那么：

（8.1.1）

同理

（8.1.2）

由此可得交点：

（8.1.3）

当然，这里所求出的交点并不一定是所要求的交点，因为我们处理的是直线段。因此，为了保证交点的有效性，还必须进行有效性检查，即对条件进行判断。若条件真，则为有效交点，否则为无效交点。

⑵ 直线段与曲线段相交

设直线段的方程为

为一曲线段（），它可以是Bézier曲线、B样条曲线、NURBS曲线等，那么与的交点为

或者

如果是分段的次多项式或分段有理多项式，则交点所满足方程的一般形式是：

经矢量运算可得

（8.1.4）

用数值方法求解上述方程，即可求得参数，再通过有效性检查方可求出要求的交点。

⑶ 曲线与曲线相交

设有空间曲线段（）和（），那么其交点满足的方程是：

它是两个未知量的非线性方程组。对于平面曲线来说，两条曲线要么相交，要么不相交。上述方程组恰有两个方程，可以直接求解。常用的方法是Newton-Raphson迭代方法。

将上述方程写成分量形式，则有

（8.1.5）

设真正的交点是，如果我们已经求得的近似交点为，记

（8.1.6）

则由Taylor展开可得

忽略二阶以上的高阶项，则有：

即：

（8.1.7）

求解此方程组，解出。如果（与真正交点的误差）满足精度要求，则交点参数为：

（8.1.8）

迭代过程结束。否则，以为交点的新的近似解，继续迭代。如果迭代不收敛，则两曲线不相交，否则有交。

该方法的特点是交点精确，且不依赖于曲线的类型。然而，如果曲线是Bézier曲线或B样条曲线，则可采用较为方便的离散求交。下面，我们以Bézier曲线为例介绍离散求交算法的基本原理。

我们知道，Bézier曲线完全位于它的控制顶点的凸包之中，因此对两条Bézier曲线来说，其交点的计算可转化为控制多边形凸包的相交性判断及曲线的分割。如果两控制多边形的凸包不相交，则曲线一定不相交；否则，将两曲线一分为二，再对子曲线的控制多边形的凸包的相交性进行判断。如此重复，直至获得明确的结果：要么相交，求出交点；要么不相交。其算法过程如下：

a. Bézier曲线的离散求交算法

Step1 判断两曲线和的控制多边形凸包的相交性。若相交转至Step2，否则Step5；

Step2 精度判断。若满足精度要求，转至Step5，否则转至Step3；

Step3 分别对两曲线、进行中点分割（参数为），得到曲线段和；

Step4 对曲线段对和的控制多边形的凸包两两进行相交性测试。若不相交，转至Step5；否则将凸包相交的控制多边形所对应的曲线送入和，转至Step2；

Step5 输出结果。

 

b. 算法的数据结构

离散求交算法采用的数据结构为二叉树，其逻辑结构如图8.1所示。

 

图8.1 离散求交算法数据结构

c. 交点参数的确定

交点参数确定采用的方法是对相交曲线段两端点的参数进行修正，设起点和终点的参数分别为、，则：

① 初始化。，；

② 分割。若左段曲线参与求交，则修正终点参数：；若右段曲线参与求交，则修正起点参数：，其中为分割次数；

③ 交点参数为。

对于空间曲线来说，方程组（8.1.7）为一超定方程组，即有两个未知量，三个方程。此时，求解的方法是将曲线投影到某一坐标平面（如xoy平面）上，求解由x、y分量构成的方程组。如果有交，将其对应参数代入z分量进行验证即可。

8.2 曲线的等距线

曲线的等距线（offset）是将曲线上每一点沿其法矢方向平移一给定的距离所得点构成的曲线，它是数控加工中刀具中心点的轨迹。因此，等距线计算对于2D轮廓加工和3D平截线加工必不可少。

设曲线的方程为，则对应的等距线方程为

（8.2.1）

这里为常量，为处的单位法矢。

由等距线的方程可以看出，对于给定的参数多项式曲线或有理参数多项式曲线，其相应的等距线一般来说已不再是同类型的曲线了，它的方程相当复杂。除非特殊曲线（如圆弧、直线段），一般来说需进行二次拟合，以便按一定步长计算出等距线来。因此，对于等距线的研究主要集中在什么样的曲线之等距线可以精确表示方面。

设是平面有理参数多项式曲线，如果存在一多项式函数使得满足条件：

（8.2.2）

则的等距线可精确表示成一有理参数多项式曲线。

证明 因为

所以

满足条件（8.2.2）的多项式曲线或有理多项式曲线称之为Pythagoras曲线，简称PH曲线。由此可以看出，圆弧是PH曲线，因而圆弧的等距线可以精确表示之。

8.3曲线的过渡

工程上，尤其是在航空、航天、汽车、船舶等行业中，为使产品外表具有良好的力学性能及外观；为避免加工中出现啃刀，往往需要在任意两条曲线、两张曲面间构造一条过渡曲线或一张过渡曲面。曲线间的过渡指的是在两条曲线间按给定的半径构造一圆弧，使其与母曲线保持连续。通常，曲线间的过渡有以下几种：直线间的过渡、直线圆弧间的过渡、圆弧间的过渡，以及曲线间的过渡。曲线间的过渡问题实质上是构造等距线与求交。

设是两条平面曲线，过渡半径为，则两曲线间的过渡曲线算法如下：

Step1 构造等距线

Step2 求曲线与之交点及交点参数。若，则转Step3；否则，过渡半径不合适；

Step3 求与在处切线之交点；

Step4 以、、为控制顶点，为权因子构造有理二次Bézier曲线，即为所求的过渡圆弧。

下面，我们举例说明直线间的过渡。给定平面上两条直线：

及过渡半径。

① 求与之交点；

② 拾取直线与上各一点；

③ 计算夹角；

④ 确定过渡圆之圆心及在两直线上的切点：

设，若，则上切点的参数为，否则切点的参数为。直线上切点的参数可类似求出。过渡圆圆心为