曲线的几何处理技术

第八章曲线的几何处理技术前面我们已经介绍了CAD/CAM中常用的曲线表示方法及其相关理论，这些曲线在外形设计和制造中的有效使用很大程度上依赖于能否方便地对其进行各种几何操作，或许设计者要求按一定的光滑约束将多段曲线连接在一起，或许两曲线的交点是工程设计中的一个关键点等等。着就是曲线的几何处理，常用的几何处理包括：求交点（intersecting）、过渡（filleting）、延拓（extension）、混合（blending）、等距线计算（offseting）等。我们这里重点讨论求交、等距线计算以及过渡三种操作。8.1曲线求交求交是最为重要的曲线运算，它是图形裁剪、消隐的基础。按照曲线的类型，可以将曲线求交分为以下三类：⑴两直线段相交空间两直线段如果排除相互平行与异面，它们的相交有两种情况：或相交于一点，或重叠（部分或全部）。令两条直线段的参数方程分别为：]1,0[,,)(,)(vuvvuudcQbaP则其交点为rQP)()(vu，即vudcba因为0)()(ubada，那么：],,det[],,det[dcbdcaiu（8.1.1）同理],,det[],,det[dbacbaiv（8.1.2）由此可得交点：iivudcbar（8.1.3）当然，这里所求出的交点r并不一定是所要求的交点，因为我们处理的是直线段。因此，为了保证交点的有效性，还必须进行有效性检查，即对条件10,10iivu进行判断。若条件真，则为有效交点，否则为无效交点。⑵直线段与曲线段相交设直线段的方程为]1,0[,)(uuubaP)(vQ为一曲线段（10v），它可以是Bézier曲线、B样条曲线、NURBS曲线等，那么)(uP与)(vQ的交点为rQP)()(vu或者0)()(vuQP计算机辅助几何设计130如果)(vQ是分段的k次多项式或分段有理多项式，则交点所满足方程的一般形式是：uvvvkkkkbaCCCC1110经矢量运算可得0][)(1110kkkkvvvCCCCba（8.1.4）用数值方法求解上述方程，即可求得参数iv，再通过有效性检查方可求出要求的交点。⑶曲线与曲线相交设有空间曲线段)(uP（10u）和)(vQ（10v），那么其交点满足的方程是：0)()(vuQP它是两个未知量vu,的非线性方程组。对于平面曲线来说，两条曲线要么相交，要么不相交。上述方程组恰有两个方程，可以直接求解。常用的方法是Newton-Raphson迭代方法。将上述方程写成分量形式，则有0)()(),(0)()(),(vuvuGvuvuFyyxxQPQP（8.1.5）设真正的交点是),(vu，如果我们已经求得的近似交点为),(rrvu，记rrvvvuuu,（8.1.6）则由Taylor展开可得),(),(),(),(0),(),(),(),(0rrrrrrrrrrrrvuvGvvuuGuvuGvuGvuvFvvuuFuvuFvuF忽略二阶以上的高阶项，则有：),(),(),(),(),(),(rrrrrrrrrrrrvuGvuvGvvuuGuvuFvuvFvvuuFu即：)()()()(ryryrxrxyyxxuvuvvuPQPQQPQP（8.1.7）求解此方程组，解出vu,。如果vu,（与真正交点的误差）满足精度要求，则交点参数为：vvvuuurrrr11,（8.1.8）迭代过程结束。否则，以),(11rrvu为交点的新的近似解，继续迭代。如果迭代不收敛，则两曲线不相交，否则有交。该方法的特点是交点精确，且不依赖于曲线的类型。然而，如果曲线是Bézier曲线或B样条曲线，则可采用较为方便的离散求交。下面，我们以Bézier曲线为例介绍离散求交算法的基本原理。131第八章曲线的几何处理技术我们知道，Bézier曲线完全位于它的控制顶点的凸包之中，因此对两条Bézier曲线来说，其交点的计算可转化为控制多边形凸包的相交性判断及曲线的分割。如果两控制多边形的凸包不相交，则曲线一定不相交；否则，将两曲线一分为二，再对子曲线的控制多边形的凸包的相交性进行判断。如此重复，直至获得明确的结果：要么相交，求出交点；要么不相交。其算法过程如下：a.Bézier曲线的离散求交算法Step1判断两曲线1C和2C的控制多边形凸包的相交性。若相交转至Step2，否则Step5；Step2精度判断。若满足精度要求，转至Step5，否则转至Step3；Step3分别对两曲线1C、2C进行中点分割（参数为21），得到曲线段1211,CC和2221,CC；Step4对曲线段对),(1211CC和),(2221CC的控制多边形的凸包两两进行相交性测试。若不相交，转至Step5；否则将凸包相交的控制多边形所对应的曲线送入1C和2C，转至Step2；Step5输出结果。b.算法的数据结构离散求交算法采用的数据结构为二叉树，其逻辑结构如图8.1所示。图8.1离散求交算法数据结构c.交点参数的确定交点参数确定采用的方法是对相交曲线段两端点的参数进行修正，设起点和终点的参数分别为0u、1u，则：①初始化。00u，11u；②分割。若左段曲线参与求交，则修正终点参数1u：kuu2111；若右段曲线参与求交，则修正起点参数0u：kuu2100，其中k为分割次数；③交点参数为2)(10uu。Curve1Curve211122122111112222221计算机辅助几何设计132对于空间曲线来说，方程组（8.1.7）为一超定方程组，即有两个未知量，三个方程。此时，求解的方法是将曲线投影到某一坐标平面（如xoy平面）上，求解由x、y分量构成的方程组。如果有交，将其对应参数代入z分量进行验证即可。8.2曲线的等距线曲线的等距线（offset）是将曲线上每一点沿其法矢方向平移一给定的距离所得点构成的曲线，它是数控加工中刀具中心点的轨迹。因此，等距线计算对于2D轮廓加工和3D平截线加工必不可少。设曲线的方程为)(uP，则对应的等距线方程为)()()(uruuoffNPP（8.2.1）这里r为常量，N)(u为)(uP处的单位法矢。由等距线的方程可以看出，对于给定的参数多项式曲线或有理参数多项式曲线)(uP，其相应的等距线一般来说已不再是同类型的曲线了，它的方程相当复杂。除非特殊曲线（如圆弧、直线段），一般来说需进行二次拟合，以便按一定步长计算出等距线来。因此，对于等距线的研究主要集中在什么样的曲线之等距线可以精确表示方面。设))(),(()(uyuxuP是平面有理参数多项式曲线，如果存在一多项式函数)(u使得)(uP满足条件：)())(())((222uuyux（8.2.2）则)(uP的等距线可精确表示成一有理参数多项式曲线。证明因为)())(),(())(())(())(),(()(22uuxuyuyuxuxuyuN所以)())()()(),()()(()())(),(()(uuxuuyuyruuxuruyuxuoffNP满足条件（8.2.2）的多项式曲线或有理多项式曲线称之为Pythagoras曲线，简称PH曲线。由此可以看出，圆弧是PH曲线，因而圆弧的等距线可以精确表示之。8.3曲线的过渡工程上，尤其是在航空、航天、汽车、船舶等行业中，为使产品外表具有良好的力学性能及外观；为避免加工中出现啃刀，往往需要在任意两条曲线、两张曲面间构造一条过渡曲线或一张过渡曲面。曲线间的过渡指的是在两条曲线间按给定的半径构造一圆弧，使其与母曲线保持1G连续。通常，曲线间的过渡有以下几种：直线间的过渡、直线圆弧间的过渡、圆弧间的过渡，以及曲线间的过渡。曲线间的过渡问题实质上是构造等距线与求交。设)(),(vuQP是两条平面曲线，过渡半径为r，则两曲线间的过渡曲线算法如下：Step1构造等距线133第八章曲线的几何处理技术10),()()(uuruuPoffNPP10),()()(vvrvvQoffNQQStep2求曲线)(uoffP与)(voffQ之交点oI及交点参数iivu,。若1,0iivu，则转Step3；否则，过渡半径不合适；Step3求)(uP与)(vQ在iivu,处切线之交点I；Step4以)(iuP、I、)(ivQ为控制顶点，)()(cos,121120ioivuQIP为权因子构造有理二次Bézier曲线，即为所求的过渡圆弧。下面，我们举例说明直线间的过渡。给定平面上两条直线：10,)1()(:10,)1()(:102101vvvvLuuuuLqqQppP及过渡半径r。①求1L与2L之交点),(oovuI；②拾取直线1L与2L上各一点)(),(vuQP；③计算夹角PIQ；④确定过渡圆之圆心及在两直线上的切点：设2rctga，若ouu，则10pp上切点1T的参数为100ppau，否则切点的参数为100ppau。直线2L上切点2T的参数可类似求出。过渡圆圆心为]2[cos12122ITTIO