3.3 曲线图形

3.3.1 曲线的生成算法

1.Bezier曲线

1962年，法国雷诺汽车公司的P.E.Bezier构造了一种以逼近为基础的参数曲线和曲面的设计方法，并用这种方法完成了一种称为UNISURF的曲线和曲面设计系统。1972年该系统被投入应用。Bezier方法将函数逼近同几何表示结合起来，使得设计师在计算机上作图就像使用作图工具一样得心应手。

（1） Bezier曲线的定义。给定空间n+1个点的位置矢量Pi（i=0，1，2，…，n），则Bezier参数曲线上各点坐标的插值公式是

其中，Pi构成该Bezier曲线的特征多边形，Bi，n（t）是n次Bernstein基函数：

Bezier曲线实例如图3-24所示。

当n=1时，P（t）=P0B0，1（t）+P1B1，1（t）=P0 （1-t）+P1t

一次Bezier曲线是连接P0与P1的直线段。

当n=2时，P（t）=P0B0，2（t）+P1B1，2（t）+P2B2，2（t）=P0（1-t）2-2P1t（1-t）+P2t2

二次Bezier曲线是一条过P0、P2的抛物线。

当n=3时，P（t）=P0B0，3（t）+P1B1，3（t）+P2B2，3（t） +P3B3，3（t）

=P0（1-t） 3 +3P1t（1-t） 2+3P2t2（1-t） +P3t3

三次Bezier曲线如图3-24所示，其Bernstein基函数曲线如图3-25所示。

（2） Bernstein基函数的性质。

① 正性。

② 端点性质。

③ 权性。

④ 对称性。

⑤ 递推性。

还有一些其他性质这里不一一列出。

（3） Bezier曲线的性质。

① 端点性质。

● 曲线端点位置矢量：

当t=0时，P（0）=P0；

当t=1时，P（1）=Pn。

由此可见，Bezier曲线的起点、终点与相应的特征多边形的起点、终点重合。

● 切矢量：

当t=0时，；

当t=1时，。

这说明Bezier曲线的起点和终点处的切线方向和特征多边形的第1条边及最后一条边的走向一致。

② 对称性：由控制顶点构造出的新Bezier曲线，与原Bezier曲线形状相同，但走向相反。

③ 凸包性：在[0，1]区间变化时，对某一个t值，P（t）是特征多边形各顶点Pi的加权平均，加权因子依次是Bi，n（t）。在几何图形上，曲线落在Pi构成的凸包之中，如图3-26所示。

④ 几何不变性：Bezier曲线的位置和形状与其特征多边形顶点的位置有关，它不依赖坐标系的选择。

还有一些其他性质这里不一一列出。

（4） Bezier曲线的程序设计。

① 三次Bezier曲线的程序设计如下。

CDC ∗pDC=GetDC（）;
pDC-＞MoveTo（x[0]，y[0]）;         //移到曲线上的第一个点
for（t=0.01;t＜1.0001;t=t+0.01）
{     //计算基函数
      b03=（1-t）∗（1-t）∗（1-t）;
      b13=3∗t∗（1-t）∗（1-t）;
      b23=3∗t∗t∗（1-t）;
      b33=t∗t∗t;
      //计算曲线上的点坐标
      x=b03∗x[0]+b13∗x[1]+b23∗x[2]+b33∗x[3];
      y=b03∗y[0]+b13∗y[1]+b23∗y[2]+b33∗y[3];
      pDC-＞LineTo（x，y）;         //用小直线段绘制曲线
}

② n次Bezier曲线的程序设计如下。

//计算基函数
float b(int i,int n,float t)
{ int k,a=1,b=1;
    for(k=i+1;k<=n;k++) a=a . k;
    for(k=1;k<=n -i;k++) b=b . k;
    float bh =(float)a / b;
    for(k=1;k<=i;k++) bh=bh . t;
    for (k=1;k<=n -i;k++) bh=bh . (1 -t);
    return bh;
}
//绘制Bezier 曲线程序段
CDC .pDC=GetDC();
pDC->MoveTo (x[0],y[0]);            //移到曲线上的第一个点
for(t=0.05 ;t<=1.00001;t=t+0.05)
{    xx=0;yy=0;
    for(i=0; i<=n;i++)
    {     bb=b(i, n, t);          //计算基函数
          xx=xx + x[i] . bb;      //计算曲线上的点坐标
          yy=yy + y[i] . bb;


    }
    pDC->LineTo (xx,yy);            //通过小直线段生成曲线
}

设x[6]={10，100，150，230，300，320}，y[6]={10，200，230，100，120，200}，图3-27所示为程序运行后所绘制的Bezier曲线。

2.Bezier曲线的递推算法

（1） 递推算法公式。如图3-28所示，设P0、20 P、P2是一条抛物线上3个不同顺序的点。过P0和P2点的两切线交于P1点，在20P点的切线交P0P1和P2P1于10P和11P，则如下比例成立：

这是所谓抛物线的三切线定理。

当P0、P2固定，引入参数t，令上述比值为t: （1-t），即有：

t从0变到1，第1、2式分别表示控制二边形的第1、2条边，它们是两条一次Bezier曲线。将第1、2式代入第3式得：

P02=(1-t)P0+2t(1-t)P1+t2P2

当t从0变到1时，它表示了由3顶点P0、P1、P2三点定义的一条二次Bezier曲线，并且表明这个二次Bezier曲线20P可以定义为分别由前两个顶点（P0，P1）和后两个顶点（P1，P2）决定的一次Bezier曲线的线性组合。依次类推，由4个控制点定义的三次Bezier曲线30 P可被定义为分别由（P0，P1，P2）和（P1，P2，P3）确定的两条二次Bezier曲线的线性组合，由（n+1）个控制点Pi（i=0，1，…，n）定义的n次Bezier曲线0nP可被定义为分别由前、后n个控制点定义的两条（n-1）次Bezier曲线10n

P-与1

1n

P-的线性组合：

由此得到Bezier曲线的递推计算公式：

这便是著名的de Casteljau算法。用这一递推公式，在给定参数下求Bezier曲线上一点P（t）非常有效。上式中：Pi0=PiBezier曲线的控制点，0nP即为曲线P（t）上具有参数t的点。de Casteljau算法稳定可靠，直观简便，是计算Bezier曲线的基本算法和标准算法。

（2） 递推算法程序设计。

CDC ∗pDC=GetDC（）;
pDC-＞MoveTo（x[0]，y[0]）;
for（t=0.05;t＜1.0001;t=t+0.05）
{    for（i=0;i＜=n;i++）
     xx[i]=x[i]，yy[i]=y[i];
  for（k=1;k＜=n;k++）
  { for（int i=0;i＜n-k;i++）
      {   xx[i]=xx[i]∗（1-t）+xx[i+1]∗t;
          yy[i]=yy[i]∗（1-t）+yy[i+1]∗t;
      }
  }
  pDC-＞LineTo （xx[0]，yy[0]）;
}

（3） 递推算法几何作图。

当n=3时，de Casteljau算法递推出的kiP呈直角三角形，对应结果如图3-29所示。从左向右递推，最右边点30P即为曲线上的点。

这一算法可用简单的几何作图来实现。给定参数[0，1]t∈，把定义域分成长度为t: （1-t）的两段。依次对原始控制多边形每一边执行同样的定比分割，所得分点就是第1级递推生成的中间顶点Pi1(i=0,1,…,n-1)；对这些中间顶点构成的控制多边形再执行同样的定比分割，得第2级中间顶点Pi1(i=0,1,…,n-1)

重复进行下去，直到n级递推得到一个中间顶点0nP即为所求曲线上的点P（t），如图3-30所示。

3.Bezier曲线的拼接

描述复杂的曲线时必须增加特征多边形的顶点数，使Bezier曲线的次数提高，而高次多项式又会带来计算上的困难，实际使用中，一般不超过10次。因此对于复杂的曲线有时采用多段曲线相互拼接起来，并在接合处保持一定的连续条件。下面讨论两段Bezier曲线达到不同阶几何连续的条件。

给定两条Bezier曲线P（t）和Q（t），相应控制点为Pi(i=0,1,…,n)和Qj(j=0,1,…,m)，且令ai=Pi-Pi-1,bj=Qj-Qj-1，如图3-31所示，把两条曲线连接起来。

要使它们达到G0（零阶连续）连续的充要条件是Pn=Q0；要使它们达到G1（一阶连续）连续的充要条件是Pn-1、Pn=Q0、Q1三点共线。

根据Bezier曲线的拼接条件，可以将一个高次Bezier曲线分解成几个低次Bezier曲线。如图3-32所示，设给定特征多边形的顶点为P0、P1、P2、P3、P4、P5，由它们控制的曲线为5次Bezier曲线（虚曲线）。如果在P2、P3直线上增加一个控制点Q，则P0、P1、P2、Q和Q、P3、P4、P5分别控制2个三次Bezier曲线（实曲线），在连接处具有一阶连续。

4.Bezier曲线的升阶与降阶

（1） Bezier曲线的升阶。保持Bezier曲线的形状与定向不变，增加控制顶点数，可以提高Bezier曲线的次数。增加控制顶点数，就增加了对曲线进行形状控制的灵活性，在构造曲面方面有着重要的应用。对于一些由曲线生成曲面的算法，要求那些曲线必须是同次的。应用升阶的方法，可以把低于最高次数的曲线提升到最高次数，而获得同样的次数。

曲线升阶后，原控制顶点会发生变化。设给定原始控制顶点为P0，P1，…，Pn，定义了一条n次Bezier曲线：

增加一个顶点后，仍定义同一条曲线的新控制顶点为则

对上式左边乘以（t+（1-t）），得

比较等式两边项的系数，得

化简即得

式中，P-1=Pn+1=0

说明：新的控制顶点以参数值按分段线性插值从原始特征多边形得出；升阶后的新的特征多边形在原始特征多边形的凸包内；特征多边形更靠近曲线。

三次Bezier曲线的升阶实例如图3-33所示。

（2） Bezier曲线的降阶。降阶是升阶的逆过程。给定一条由原始控制顶点Pi（i=0，1，…，n）定义的n次Bezier曲线，要求找到一条由新控制顶点定义的n-1次Bezier曲线来逼近原始曲线。假定是由升阶得到，则由升阶公式有

从这个方程可以导出两个递推公式：

其中，第1个递推公式在靠近P0处趋向生成较好的逼近，而第2个递推公式在靠近Pn处趋向生成较好的逼近。

5.反算Bezier曲线控制点

Bezier曲线是由控制点控制的，曲线只经过控制点的起点和终点。如果要构造一条Bezier曲线经过给定n+1个型值点Qi（i=0，1，2，…，n），可反求该Bezier曲线的控制点。根据Bezier曲线表达式：

令t=i/n，列出n+1个的方程：

根据以上列出的n+1个线性方程组，可以求出过Qi点的Bezier曲线的控制点Pi(i=0,1,…,n)。

3.3.2 B样条曲线

以Bernstein基函数构造的Bezier曲线有许多优越性，但有两点不足：其一是Bezier曲线不能做局部修改；其二是Bezier曲线的拼接比较复杂。1972年，Gordon和Riesenfeld等人提出了B样条方法，在保留Bezier方法全部优点的同时，克服了Bezier方法的弱点。

1.B样条的定义

B样条曲线方程定义为

式中，Pi（i=0，1，…，n）是控制多边形的顶点，Ni，k(t)(i=0,1,…,n)称为k阶（k-1）次B样条基函数。

B样条的基函数由Cox-deBoor递推公式定义为（约定0/0=0）

式中，ti是节点值，构成了k阶B样条函数的节点矢量，其中的节点是非递减序列。

2.B样条曲线类型的划分

B样条曲线按其节点矢量中节点的分布情况，可划分为多种类型。假定控制多边形的顶点为Pi（i=0，1，…，n），下面介绍两种常用的简单类型。

（1） 均匀周期样条曲线。

均匀：节点矢量ti=i(i=0,1,2,…,n+k)，ti-ti+1=常数。

周期：所有基函数形状一样，都可由其中一个基函数平移得到。

如图3-34所示为4个周期性二次基函数。

① 二次均匀周期B样条曲线。

下面推导出二次均匀周期B样条曲线的表达式：

根据图3-34可知，在任何t处，只有3个基函数不为零，因此得出各区间二次B样条分段表达式如下：

从图3-34中可以看出，各区间中的3个N函数形状完全一样，因此可将各区间归一化到[0，1]中，N函数全部由N0，3表示。第i段曲线可以表示为：

仍用P（t）表示：

例如：给定如图3-35所示的5个控制点，则由它们控制的二次B样条曲线有3段，由P0、P1、P2控制的二次B样条曲线为P（t）=P0（1-t）2/2+P1（-t2+t+1/2）+P2t2/2当t=0时，P（0）=0.5P0+0.5P1（为P0P1的中点）当t=1时，P（1）=0.5P1+0.5P2（为P1P2的中点）同理，由P1、P2、P3控制的二次B样条曲线为

由P2、P3、P4控制的二次B样条曲线为

可见二次B样条曲线经过控制多边形各边的中点，各段曲线在各边的中点处一阶连续，其所共有的切线就是控制多边形的边。

主要VC程序代码为：

    CDC .pDC=GetDC();
    x1=(x[0] + x[1]) . 0.5;
    y1=(y[0] + y[1]) . 0.5;
    pDC->MoveTo (x1,y1);
    for(i=0; i<n-2; i++)
        { for(t=0.01; t<1.0001; t=t+0.01)
            { n2=(1 -t) . (1 -t) . 0.5;
              n1=(-2 . t . t + 2 . t + 1) . 0.5;
              n0=t . t . 0.5;
              x1=x[i] . n2 + x[i + 1] . n1 + x[i + 2] . n0;
              y1=y[i] . n2 + y[i + 1] . n1 + y[i + 2] . n0;
              pDC->LineTo (x1,y1);
        }
}

② 三次均匀周期B样条曲线。

对于三次B样条曲线，需要计算N0，4（t），可以得出N0，4（t）是一个4段函数，因此每段三次B样条曲线由4个控制点控制，其表达式为

如图3-36所示为两段三次B样条曲线，两段曲线在连接处二阶连续。图中也反映出了三次B样条曲线的几何特征。

其主要VC程序代码为：

    CDC .pDC=GetDC();
    x1=(x[0] + x[2]) . 0.5 / 3 + 2 . x[1] / 3;
    y1=(y[0] + y[2]) . 0.5 / 3 + 2 . y[1] / 3;
    pDC->MoveTo (x1,y1);
    for(i=0;i<n-3;i++)
    {     for(t=0.01; t<1.0001; t=t+0.01)
    {     n0=(-t . t . t + 3 . t . t -3 . t + 1) / 6;
          n1=(3 . t . t . t -6 . t . t + 4) / 6;
          n2=(-3 . t . t . t + 3 . t . t + 3 . t + 1) / 6;
          n3=t . t . t / 6;
          x1=x[i] . n0 + x[i + 1] . n1 + x[i + 2] . n2 + x[i + 3] . n3;
          y1=y[i] . n0 + y[i + 1] . n1 + y[i + 2] . n2 + y[i + 3] . n3;
          pDC->LineTo (x1,y1);
    }
}

（2） 准均匀非周期的B样条曲线。

与均匀周期B样条曲线的差别在于：两端节点具有重复度k，基函数不是周期出现。

① 节点矢量的定义。

下面假设n=5（6个控制点）时，k取不同值时的节点矢量值：

k=2：节点矢量为（0，0，1，2，3，4，5，5） 0≤t≤5

k=3：节点矢量为（0，0，0，1，2，3，4，4，4） 0≤t≤4

k=4：节点矢量为（0，0，0，0，1，2，3，3，3，3） 0≤t≤3

k=5：节点矢量为（0，0，0，0，0，1，2，2，2，2，2） 0≤t≤2

k=6：节点矢量为（0，0，0，0，0，0，1，1，1，1，1，1） 0≤t≤1

如图3-37所示，它显示出不同k值的B样条曲线。当k=2时，准均匀非周期B样条曲线就是控制多边形本身；当k=6时，准均匀非周期B样条曲线就是Bezier曲线。

② 基函数。准均匀非周期二次B样条曲线的基函数如图3-38所示。

均匀B样条曲线没有保留Bezier曲线端点的几何性质，即样条曲线的首末端点不再是控制多边形的首末端点。采用准均匀的B样条曲线就是为了解决这个问题，使曲线在端点的行为有较好的控制，如图3-39所示。

（3） 非均匀B样条曲线。

在这种类型里，任意分布的节点矢量T=[t0，t1，…，tn+k]，只要在数学上成立（节点序列非递减，两端节点重复度≤k，内节点重复度≤k-1）都可选取。这样的节点矢量定义了非均匀B样条基函数。

3.B样条曲线的性质

（1） 局部性。由于B样条的局部性，k阶B样条曲线上参数为t∈[ti，ti+k]的一点P（t）至多与k个控制顶点有关，与其他控制顶点无关；移动该曲线的第i个控制顶点Pi至多影响到定义在区间（ti，ti+k）上那部分曲线的形状，对曲线的其余部分不发生影响。

（2） 连续性。P（t）在r重节点ti（k≤i ≤n）处的连续阶不低于k-1-r。整条曲线P（t）的连续阶不低于k-1-rmax，其中rmax表示位于区间（tk-1，tn+1）内的节点的最大重数。

（3） 凸包性。P（t）在区间（ti，ti+1），k-1≤i ≤n上的部分位于k个点Pi-k+1，…，Pi的凸包Ci内，整条曲线则位于各凸包Ci的并集

（4） 分段参数多项式。P（t）在每一区间（ti，ti+1），k-1≤i≤n上都是次数不高于k-1的参数t的多项式，P（t）是参数t的k-1次分段多项式。

（5） 几何不变性。B样条曲线的形状和位置与坐标系的选择无关。

（6） 造型的灵活性。B样条曲线可以构造直线段、尖点、切线等特殊情况，如图3-40所示。对于四阶（三次）B样条曲线P（t），若要在其中得到一条直线段，只要Pi、Pi+1、Pi+2、Pi+3这4点位于一条直线上，此时P（t）对应的ti+3≤t≤ti+4的曲线即为一条直线，且和Pi、Pi+1、Pi+2、Pi+3所在的直线重合，如图3-40（a）所示。

为了使P（t）能过Pi点，只要使Pi、Pi+1、Pi+2重合，此时P（t）过Pi点（尖点），尖点也可通过三重节点得到，如图3-40（b）所示。

为了使曲线P（t）和某一直线L相切，只要取Pi、Pi+1、Pi+2位于L上及Pi+3的重数不大于2，如图3-40（c）所示。