计算机图形学第4章二维图形生成和变换技术

第四章第四章 目录目录 第四章第四章 二维图形生成和变换技术二维图形生成和变换技术 4.1 4.1 根本绘图元素根本绘图元素 4.2 4.2 直线段的生成直线段的生成 4.3 4.3 曲线的生成曲线的生成 4.4 4.4 区域填充区域填充 4.5 4.5 二维图形变换二维图形变换 4.6 4.6 二维图形剪裁二维图形剪裁 1第四章第四章 二维图形生成和变换技术二维图形生成和变换技术 又称平面又称平面图形图形图形图形又称立体图形又称立体图形三维图形最终还是用二维三维图形最终还是用二维图形，即图片、屏幕、纸图形，即图片、屏幕、纸张等的形式来表示。张等的形式来表示。无论什么复杂图形，它们无无论什么复杂图形，它们无非是由直线段和曲线段组成，非是由直线段和曲线段组成，三维图形经投影后最终变三维图形经投影后最终变成了二维图形，成了二维图形，图形设备显示图形设备显示曲线段时，最曲线段时，最终还是将曲线终还是将曲线段转化成一系段转化成一系列直线段逼近列直线段逼近表示表示 因此，所有图形我们都可以看成是由直线段组成。因此，所有图形我们都可以看成是由直线段组成。对二维图形的处理是计算机图形学的根底对二维图形的处理是计算机图形学的根底2 4.1 根本绘图元素根本绘图元素 在在第第二二章章我我们们已已讨讨论论过过坐坐标标系系统统的的世世界界坐坐标标系系、标标准准坐坐标标系系和和设设备备坐坐标标系系三三种种坐坐标标系系。坐坐标标系系统统确确定定之之后后，需需要要使使用用不不同同的的绘绘图图元元素素来来描描述述图图形形，它它们们是是点点、直直线线、曲线和其他根本的图形元素。曲线和其他根本的图形元素。第四章第四章 二维图形生成和变换技术二维图形生成和变换技术 4.1 4.1 根本绘图元素根本绘图元素 4.2 4.2 直线段的生成直线段的生成 4.3 4.3 曲线的生成曲线的生成 4.4 4.4 区域填充区域填充 4.5 4.5 二维图形变换二维图形变换 4.6 4.6 二维图像剪裁二维图像剪裁 3一、点一、点 点是图形中最根本的图素，直线、曲线以及点是图形中最根本的图素，直线、曲线以及其他的图元都是点的集合。其他的图元都是点的集合。在计算机图形学中，点是用数值坐标来表示在计算机图形学中，点是用数值坐标来表示的。的。XY在直角坐标系中在直角坐标系中点由点由x x，y y两两个数值组成的坐个数值组成的坐标表示标表示XYZ在三维坐标系中点在三维坐标系中点是由是由x x，y y，z z三个数值组成的坐三个数值组成的坐标表示标表示 4二、直线二、直线 一一条条直直线线是是指指所所有有在在它它上上面面的的点点的的集集合合,在在图形学中研究的对象是直线段。图形学中研究的对象是直线段。线线段段的的起起点点坐坐标标XsXs，YsYs。终终点点坐坐标标XeXe，YeYe这这两两点点就就确确定定了了这这条条线线段段，并并用用线线段段上上的的任任意一点意一点x x，y y均满足：均满足：5 图形显示器是由一个个排列有序的像素所构成，画图形显示器是由一个个排列有序的像素所构成，画一条直线实际上是根据一系列计算出来并与该线靠近的一条直线实际上是根据一系列计算出来并与该线靠近的像素而绘制。像素而绘制。因此，显示器划分的像素点越多分辨率越高因此，显示器划分的像素点越多分辨率越高 由象素组由象素组成的线段成的线段6 绘图仪绘制线段是笔在绘图仪绘制线段是笔在X,YX,Y方向移动，画线时单方向方向移动，画线时单方向的一次移动距离称为步矩，设备的步矩越小，绘出的图的一次移动距离称为步矩，设备的步矩越小，绘出的图形越精确。形越精确。YOX绘图仪绘图仪画线段画线段7三、三、曲线曲线 曲线包括圆、椭圆、弧线和由许多类型的方程曲线包括圆、椭圆、弧线和由许多类型的方程所确定的图形。在计算机图形程序设计中最好将所确定的图形。在计算机图形程序设计中最好将曲线定义成不能构成直线的点的集合。曲线被认曲线定义成不能构成直线的点的集合。曲线被认为是图形学的根底。为是图形学的根底。三次参数三次参数曲线曲线8四、区域填充四、区域填充 区域填充是一个彩色区域，可以是均匀的也可以是不均区域填充是一个彩色区域，可以是均匀的也可以是不均匀的，区域边界可以是直线也可以是曲线。匀的，区域边界可以是直线也可以是曲线。可提供不同的内部填充类型用以充满区域内部，填充的可提供不同的内部填充类型用以充满区域内部，填充的类型可能是不同的颜色，不同的灰度或者不同的填充图案。类型可能是不同的颜色，不同的灰度或者不同的填充图案。还可以用方程生成的梯度变化曲线完成填充过程。阴影填还可以用方程生成的梯度变化曲线完成填充过程。阴影填充可以通过来自一个光源的投影直线计算出，因而在填充充可以通过来自一个光源的投影直线计算出，因而在填充区域中的像素相应地发生变化。用户可根据系统硬件和软区域中的像素相应地发生变化。用户可根据系统硬件和软件，用一种或几种色彩进行填充，也可使用多种颜色填充件，用一种或几种色彩进行填充，也可使用多种颜色填充区域。区域。阴影填充阴影填充元素图元素图 94.2 4.2 直线段的生成直线段的生成 直线段是最根本的图形，因此，直线段生成的直线段是最根本的图形，因此，直线段生成的质量好坏与速度快慢将直接影响整个图形生成的质量好坏与速度快慢将直接影响整个图形生成的质量和速度。质量和速度。直线生成算法在图形软件设计中起着关键的作直线生成算法在图形软件设计中起着关键的作用。用。下面介绍几种直线生成算法：下面介绍几种直线生成算法：逐点比较法逐点比较法数值微分法数值微分法DDADDA法法BresenhamBresenham法法第四章第四章 二维图形生成和变换技术二维图形生成和变换技术 4.1 4.1 根本绘图元素根本绘图元素 4.2 4.2 直线段的生成直线段的生成 4.3 4.3 曲线的生成曲线的生成 4.4 4.4 区域填充区域填充 4.5 4.5 二维图形变换二维图形变换 4.6 4.6 二维图像剪裁二维图像剪裁 10一、一、逐点比较法逐点比较法 1.1.定义定义 在绘图过程中绘图笔每走一步就与规定的图形进行在绘图过程中绘图笔每走一步就与规定的图形进行比较，然后决定下一步走向，用步步逼近的方法画出规比较，然后决定下一步走向，用步步逼近的方法画出规定的图形（对于显示器一样）定的图形（对于显示器一样）2.2.逐点比较法执行过程逐点比较法执行过程 (1)(1)偏差计算偏差计算 下面我们以第一象限为例来说明偏差计算的方法下面我们以第一象限为例来说明偏差计算的方法 1)偏差判断公式偏差判断公式11 设要画选线段设要画选线段OAOA，当前的位置为当前的位置为M M，因为因为偏差角度很小，偏差角度很小，所以我们用所以我们用OAOA和和OMOM的斜率之差来计算偏差的斜率之差来计算偏差。由下图可知：由下图可知：=tg=tgtg=tg=12当当0 0时，表示笔在时，表示笔在OAOA线段下方，应该向线段下方，应该向+Y+Y方向走一步方向走一步当当0 0时，表示笔在时，表示笔在OAOA线段上方，应该向线段上方，应该向+X+X方向走一步方向走一步由于分母由于分母XMXAXMXA0 0，因此只需判断分子，因此只需判断分子 YMXA YMXAYAXMYAXM的正负的正负即可，得偏差公式：即可，得偏差公式：FM FMYMXAYMXAYAXMYAXM对任意点，偏差函数的一般形式为：对任意点，偏差函数的一般形式为：Fi FiXAYiXAYiYAXiYAXi其中，其中，XAXA，YAYA是终点是终点A A坐标。坐标。2 2递推公式递推公式 由公式可以看出，由于每次要计算两次乘法和一次减法，由公式可以看出，由于每次要计算两次乘法和一次减法，所以计算工作量大，所以计算工作量大，为了简化计算，可设法用前一点的偏为了简化计算，可设法用前一点的偏差来推算后一点的走步方向以及走步后的偏差，这种方法差来推算后一点的走步方向以及走步后的偏差，这种方法称为递推法。递推公式很容易用计算机实现。称为递推法。递推公式很容易用计算机实现。13递推公式可根据以下图用偏差函数判断笔进方向的图例得递推公式可根据以下图用偏差函数判断笔进方向的图例得出出设笔当前位置为设笔当前位置为 M1(X1 M1(X1，Y1)Y1)，此时，此时F1F1Y1XAY1XA YAX1 YAX10 0，应走，应走+Y+Y一步到一步到M2M2即即X2X2X1X1，Y2=Y1Y2=Y11 1，1 1表示走一步表示走一步M2M2处的偏差为：处的偏差为：F2=Y2XAF2=Y2XAYAX2=F1YAX2=F1XAXA用用X2X2X1X1，Y2=Y1Y2=Y11 1代入得到代入得到假设假设F20F20，应走，应走X X一步到一步到M3M3，那么那么X3=X2X3=X21 1，Y3=Y2Y3=Y2，M3M3处的偏差为：处的偏差为：F3=Y3XAF3=Y3XAYAX3=Y2XAYAX3=Y2XAYAX2YAX2YA=F2YA=F2YA YA 这样依次进行下去，就得到第这样依次进行下去，就得到第i i步的递推公式步的递推公式 ：当当Fi0Fi0时，向时，向+X+X方向走一步，此时偏差方向走一步，此时偏差FiFi1 1FiFiYAYAi=1i=1，2 2，nn。当当Fi0Fi0时，向时，向+Y+Y方向走一步，此时偏差方向走一步，此时偏差FiFi1 1FiFiXAXAi=1i=1，2 2，nn。偏差偏差FiFi的推算，只用到终点坐标值的推算，只用到终点坐标值XA XA，YAYA而与中间点的坐标而与中间点的坐标值无关，且只需进行加减运算。值无关，且只需进行加减运算。14 3 3任意象限偏差计算任意象限偏差计算对于第二、三、四象限的直线，也可类似推出。当直对于第二、三、四象限的直线，也可类似推出。当直线段处于第二、三、四象限时，偏差值的计算及走步线段处于第二、三、四象限时，偏差值的计算及走步方向下表方向下表直线段位直线段位置置走步方向走步方向偏差值偏差值F FK K00走步方向走步方向偏差值偏差值F FK K =y2?1:4;x=xl;y=y1;if(x2xl)k=y2?1:4;x=xl;y=y1;elseelsek=y2=y1?2:3;x=x2;y=y2;k=y2=y1?2:3;x=x2;y=y2;putpixel(x,y,1);putpixel(x,y,1);坐标差坐标差dx=dx=x x2 2-x x1 1 dy=dy=y y2 2-y y1 1 总步数总步数 象限象限 控制步数控制步数偏差判偏差判别公式别公式由已知直线两端由已知直线两端点坐标求坐标差点坐标求坐标差 根据端点坐根据端点坐标值判断所标值判断所在象限在象限17for(i=0,f=0;in;ifor(i=0,f=0;i=0)if(f=0)switch(k)switch(k)case 1:putpixel(xcase 1:putpixel(x,y,l);f,y,l);f=dy;break;=dy;break;case 2:putpixel(x,ycase 2:putpixel(x,y,l);f,l);f=dx;break;=dx;break;case 3:putpixel(xcase 3:putpixel(x,y,l);f,y,l);f=dy;break;=dy;break;case 4:putpixel(x,ycase 4:putpixel(x,y,1);f,1);f=dx;break;=dx;break;elseelseswitch(k)switch(k)case 1:putpixel(x,ycase 1:putpixel(x,y,l);f,l);f=dx;break;=dx;break;case 2:putpixel(xcase 2:putpixel(x,y,l);f,y,l);f=dy;break;=dy;break;case 3:putpixel(x,ycase 3:putpixel(x,y,l);f,l);f=dx;break;=dx;break;case 4:putpixel(xcase 4:putpixel(x,y,1);f,y,1);f=dy;break;=dy;break;当偏差判别式当偏差判别式=0=0时，时，由直线段所在位置决由直线段所在位置决定其走步方向，以及定其走步方向，以及下步的偏差值下步的偏差值 当偏差判别式当偏差判别式=0X2-X1=48X2-X1=4若取若取x x为一个象素单为一个象素单位，则由位，则由y yi i1 1=y yi i xx则可能出现象素点不连则可能出现象素点不连续的情况续的情况若取若取y y为一个象素单位，为一个象素单位，则由则由x xi i1 1=x xi i yy则象素点连续则象素点连续21 4.DDA 4.DDA的算法程序的算法程序下下面面给给出出简简单单DDADDA算算法法,选选择择xx或或yy中中较较大大者者为为一一个个像像素单位，其相应方向的增量为素单位，其相应方向的增量为1 1。DDA-line(DDA-line(x xl l,y y1 1,x x2 2,y y2 2)int int x xl l,y y1 1,x x2 2,y y2 2;real increx,increy,x,y;real increx,increy,x,y;int length,i;int length,i;if(abs(if(abs(x x2 2x xl l)abs()abs(y y2 2y y1 1)length=abs(length=abs(x x2 2x x1 1););elseelselength=abs(length=abs(y y2 2y y1 1););increx=(increx=(x x2 2x x1 1)/length;)/length;increy=(increy=(y y2 2y y1 1)/length;)/length;选定选定x x2 2x xl l和和y y2 2y y1 1中较大中较大者做为步进方者做为步进方向向求求x x和和y y方向方向的增量比例的增量比例22x x=x x1 1;y y=y y1 1;for(i=l;i=length;i for(i=l;i1/2e1/2e1/2e0e0e ey/xy/xl le0eincrex)if(increyincrex)temp=increx;temp=increx;increx=increy;increx=increy;increy=temp;increy=temp;interchange=1;interchange=1;Else interchange=0;Else interchange=0;e=2*increy e=2*increyincrex;increx;for(i=1;i=increx;ifor(i=1;i=0)if(e=0)if(interchange=1)x=x if(interchange=1)x=xs1;s1;else y=y else y=ys2;s2;e=e e=e2*increx;2*increx;if(interchange=1)if(interchange=1)y=yy=ys2;s2;Else Else x=xx=xs1;s1;e=ee=e2*increy 2*increy 29第四章第四章 二维图形生成和变换技术二维图形生成和变换技术 4.1 4.1 根本绘图元素根本绘图元素 4.2 4.2 直线段的生成直线段的生成 4.3 4.3 曲线的生成曲线的生成 4.4 4.4 区域填充区域填充 4.5 4.5 二维图形变换二维图形变换 4.6 4.6 二维图像剪裁二维图像剪裁 4.3 4.3 曲线的生成曲线的生成 在科学技术中常常需要绘制曲线，而绘制曲在科学技术中常常需要绘制曲线，而绘制曲线的根据或要求各不相同，通常遇到的约有下述线的根据或要求各不相同，通常遇到的约有下述几种情况。几种情况。l l规那么曲线的绘制：曲线的方程，要求画规那么曲线的绘制：曲线的方程，要求画出曲线出曲线2 2曲线拟合：由试验或观测得到了一批数据曲线拟合：由试验或观测得到了一批数据点，要求用一个函数近似地说明数据点坐标间的点，要求用一个函数近似地说明数据点坐标间的关系，并画出函数的图像曲线。关系，并画出函数的图像曲线。3 3曲线插值：由试验、观测或计算得到了由曲线插值：由试验、观测或计算得到了由假设干个离散点组成的点列，要求用光滑的曲线假设干个离散点组成的点列，要求用光滑的曲线把这些离散点连结起来。曲线插值与曲线拟合不把这些离散点连结起来。曲线插值与曲线拟合不同，拟合并不要求曲线通过数据点。同，拟合并不要求曲线通过数据点。4 4曲线逼近：在曲线形状设计中，给定了折曲线逼近：在曲线形状设计中，给定了折线轮廓，要求用曲线逼近这个折线轮廓。线轮廓，要求用曲线逼近这个折线轮廓。30 上述各类问题都要求画出曲线，不同的是，上述各类问题都要求画出曲线，不同的是，规那么曲线的绘制中曲线的方程为，而曲线拟合、规那么曲线的绘制中曲线的方程为，而曲线拟合、曲线插值、曲线逼近问题那么需要首先找出或构曲线插值、曲线逼近问题那么需要首先找出或构造出曲线的方程，再根据曲线方程画出曲线。除造出曲线的方程，再根据曲线方程画出曲线。除圆等少数曲线外，根据方程画曲线一般是先计算圆等少数曲线外，根据方程画曲线一般是先计算出曲线上一系列适当靠近的点，然后依次将这些出曲线上一系列适当靠近的点，然后依次将这些点用直线连起来，得到一条由折线表示的近似曲点用直线连起来，得到一条由折线表示的近似曲线。只要这些点靠得足够近，看起来就是一条光线。只要这些点靠得足够近，看起来就是一条光滑的曲线。滑的曲线。31当当判判断断结结果果落落在在圆圆外外时时，向向X X方方向向走走一一步步。直直到到再再次次到达圆内为止。到达圆内为止。一、一、圆弧的生成圆弧的生成 1 1逐点比较法逐点比较法 (1)(1)根本思想根本思想 逐点比较法绘制圆弧的原理与逐点比较法生逐点比较法绘制圆弧的原理与逐点比较法生成线段类似，也是在图形输出设备上每输出逼近成线段类似，也是在图形输出设备上每输出逼近欲画的圆弧。欲画的圆弧。用逆时针画第一象限中的用逆时针画第一象限中的ABAB圆弧的过程如下：圆弧的过程如下：YOX从从始始点点xAxA，yAyA点点开开始始画画起起，首首先先向向圆圆内内走走一一步步，也也就就是是先先向向X X方方向向走走一一步步，然然后后与与所所要要画的圆弧进行比较画的圆弧进行比较判判断断结结果果，落落在在圆圆内内时时向向Y Y方方向向走走一一步步，依依次次类类推推，一一直直到到达达圆处为止圆处为止 当画到终点以当画到终点以xBxB，yByB时，终时，终止比较，止比较，ABAB圆弧圆弧绘制结束。绘制结束。A(XA,YA)B(XB,YB)32 逐点比较法绘制圆弧时一般定为先进后出，有顺圆走逐点比较法绘制圆弧时一般定为先进后出，有顺圆走向和逆圆走向两种移动规那么。向和逆圆走向两种移动规那么。顺时针走向顺时针走向逆时针走向逆时针走向33(2)(2)判别函数判别函数从上面绘制圆弧的过程可知，归根到底，是用什么方法从上面绘制圆弧的过程可知，归根到底，是用什么方法来比较当前点是否落在圆内，还是落在圆外，然后决定来比较当前点是否落在圆内，还是落在圆外，然后决定走向。设圆心为走向。设圆心为o ox0 x0，y0y0，起点坐标为，起点坐标为A AxAxA，yAyA，终点坐标为终点坐标为B BxBxB，yByB，并假定绘图笔当前点位置为，并假定绘图笔当前点位置为M MxMxM，yMyM，于是圆的半径为，于是圆的半径为R R，即，即 YO（x0，y0）XA(XA,YA)B(XB,YB)RRmMxM，yM34令令FMFMRMRMR R作为判别函数。为了简化计算，取作为判别函数。为了简化计算，取 由由于于RMRMR R很很小小作作为为判判别别函函数数，显显然：然：FM FM0 0，表示，表示M M点在圆弧内点在圆弧内 走走+Y+Y方向方向 FM FM0 0，表示，表示M M点在圆弧外点在圆弧外 走走-X-X方向方向 FM FM0 0，表示，表示M M点在圆弧上点在圆弧上 走走-X-X方向方向(约定约定因此，根据因此，根据FMFM的正负，可以确定走向。的正负，可以确定走向。YO（x0，y0）XA(XA,YA)B(XB,YB)RRmM（xM，yM）F FM M0 0，走走+Y Y方向方向 M（xM，yM）F FM M00，走走-X X方向方向35 (3)(3)递推公式递推公式 因为起始点因为起始点A A在圆上，所以在圆上，所以Fo=0Fo=0，根据约定，所以应走，根据约定，所以应走-X-X方向一步方向一步xx，移动后坐标值为，移动后坐标值为 那么有：那么有：由于由于 所以所以F1F10 0应是应是+Y+Y方向一步方向一步yy，移动后坐标值为：，移动后坐标值为：36 (4)(4)一般递推公式一般递推公式如如此此推推导导下下去去，对对于于第第i i步步i=0i=0，l l，2 2，n n，如如果果Fi 0Fi 0，那么走一步，那么走一步xx：Xi Xil l Xi Xix x Yi Yi1=Yi1=Yi Fi Fi1=Fi1=Fi2x(Xi2x(XiX0)X0)x2x2如果如果FiFi0 0，那么走一步十，那么走一步十yy：Xi Xil l Xi Xi Yi Yi1=Yi1=Yiyy Fi Fi1=Fi+2y(Yi1=Fi+2y(YiY0)Y0)y2y2对象素显示，当对象素显示，当x0 x0，y0y0为为(0(0，0)0)，x=y=1x=y=1时时Fi0Fi0时，坐标值及判别函数为：时，坐标值及判别函数为：Xi Xil l Xi-1 Xi-1 Yi Yi1 1 Yi Yi Fi Fi1=Fi1=Fi2xi2xi1 1当当Fi Fi 0 0时，坐标值及判别函数为：时，坐标值及判别函数为：Xi Xil l Xi Yi Xi Yi1=Yi1=Yi1 1 Fi Fi1=Fi1=Fi2Yi2Yi1 137 对对于于、象象限限的的逆逆向向和和顺顺向向圆圆弧弧情情况况，上上述述过过程推导相似，可得其判别函数和走步规那么。程推导相似，可得其判别函数和走步规那么。象限象限Fi0Fi0Fi0Fi0移动移动运算公式运算公式移动量移动量运算公式运算公式逆逆I Ixxyy逆逆xxyy=顺顺xxyy顺顺xxyy逆逆yy xx逆逆yyxx顺顺I Iyyxx=顺顺yyxx表中表中x xi i=，y yi i=38 (5)(5)终点判断终点判断终终点点判判断断可可以以采采用用简简单单方方法法，即即每每走走一一步步x x或或y y，都都与与终终点点坐标比较，令终点坐标为坐标比较，令终点坐标为xBxB，yByB，假设当，假设当 且且(为为给给定定某某一一正正整整数数。如如可可取取为为1)1)，就就认认为为已已到到达达终终点。点。392 2、数值微分法、数值微分法DDADDA法法(1)(1)一般一般DDADDA法法 1)1)一般递推公式一般递推公式 圆弧的圆弧的DDADDA法和直线段法和直线段DDADDA法类似，也是根据圆弧的法类似，也是根据圆弧的微分方程来实现的，我们以圆心在坐标系原点，半径为微分方程来实现的，我们以圆心在坐标系原点，半径为R R的一段圆弧为例来讨论。的一段圆弧为例来讨论。圆心在原点圆心在原点0 0，0 0，半径为，半径为R R的圆方程为：的圆方程为：它的微分方程为：它的微分方程为：40假设令假设令:即可得离散变量微分方程形式为即可得离散变量微分方程形式为(差分代替微分：差分代替微分：式中：式中：为一很小常数。假设设为一很小常数。假设设XnXn，YnYn为用为用DDADDA法法顺顺 时针画第一象限的圆弧在时针画第一象限的圆弧在X X，Y Y方向增量值，由上式可知，方向增量值，由上式可知，那么我们有下式顺时针那么我们有下式顺时针Y Y方向减少：方向减少：44 这就是一般递推公式这就是一般递推公式41用矩阵表示为：用矩阵表示为：(4-5)(4-5)2)2)求精确递推公式求精确递推公式由式由式(4-4)(4-4)得：得：=42所以式所以式4-44-4表示并不是一个圆，而是一个半径逐渐增大表示并不是一个圆，而是一个半径逐渐增大的螺旋线。要得到圆的方程，必须要使式的螺旋线。要得到圆的方程，必须要使式4-54-5中系数矩中系数矩阵行列式值为阵行列式值为1 1。即由原式。即由原式4-54-5中的中的 变为变为1 1。假设取。假设取就能满足要求。即有：就能满足要求。即有：=43也即：也即：4 46 6这就是精确递推公式这就是精确递推公式,求求Xn+1Xn+1用用Yn+1,Yn+1,显然显然Yn+1Yn+1比比YnYn精度精度高。高。=44 由由4-64-6可知，即在计算时，我们不用可知，即在计算时，我们不用ynyn的结果，的结果，而是直接引用而是直接引用ynyn1 1的值，这一点是显然的，由的值，这一点是显然的，由ynyn1 1比比ynyn更为准确因而计算更为准确因而计算xnxn1 1时直接用时直接用ynyn1 1而不用而不用ynyn。当当较大时做出的图形为椭圆，取较小的较大时做出的图形为椭圆，取较小的时，可时，可提高作图精度，一般取提高作图精度，一般取 ，d d为绘图笔走步步长，假为绘图笔走步步长，假设是设是光栅显示器，那么光栅显示器，那么d=1d=1。和逐点比较法一样，对于不同的象限及顺逆时针画和逐点比较法一样，对于不同的象限及顺逆时针画图时都要赋给图时都要赋给以适当符号。对于圆心不在圆点的圆，以适当符号。对于圆心不在圆点的圆，可以作坐标轴的平移，把圆心移到原点。由于可以作坐标轴的平移，把圆心移到原点。由于值取很值取很小时，虽然画圆精度提高，但计算工作量将会增加，为小时，虽然画圆精度提高，但计算工作量将会增加，为此，我们可采用角度增量法来解决这一问题。此，我们可采用角度增量法来解决这一问题。45(2)(2)角度角度DDADDA法法 角度角度DDADDA法比上面介绍的法比上面介绍的DDADDA法更加容易理解，它实际上就法更加容易理解，它实际上就是把圆或圆弧分成是把圆或圆弧分成N N等分。用等分。用N N段相邻的直线来逼近圆或圆弧，段相邻的直线来逼近圆或圆弧，这种方法显然是建立在直线段生成算法的根底之上的，因而这种方法显然是建立在直线段生成算法的根底之上的，因而其效率要低些，但很好理解。其效率要低些，但很好理解。圆心在圆心在x0,y0 x0,y0,半径为半径为R R的圆参数方程为：的圆参数方程为：46 假设将整个圆分成假设将整个圆分成N N等份，即把等份，即把 2 2分为分为N N 等份。每一份等份。每一份=2=2N N，那么有参数式递推形式：，那么有参数式递推形式：其中其中i=I*i=I*I=0,1,2,N I=0,1,2,N1 1 最后将相邻的最后将相邻的xixi，yiyi，xixil l，yiyil l用直线段一用直线段一一相连就可近似地画出圆。一相连就可近似地画出圆。如果要求只画一段圆弧，如圆弧的起始角为如果要求只画一段圆弧，如圆弧的起始角为1,1,终止角终止角为为22，那么仍用，那么仍用N N等份表示时，只要将上式中等份表示时，只要将上式中22修改为修改为2211。47二、二、规那么曲线生成规那么曲线生成 所谓规那么曲线就是一条曲线可以用标准代所谓规那么曲线就是一条曲线可以用标准代数方程来描述。在解析几何这门学科中，我们已数方程来描述。在解析几何这门学科中，我们已经把几何问题和代数问题紧密结合起来，例如，经把几何问题和代数问题紧密结合起来，例如，在平面直角坐标系内，如果一条曲线上的点都能在平面直角坐标系内，如果一条曲线上的点都能满足符合某种条件，而满足该条件点又均位于这满足符合某种条件，而满足该条件点又均位于这条曲线上，那么我们就可以把这种对应关系写成条曲线上，那么我们就可以把这种对应关系写成一个确定函数式：一个确定函数式：y=f(x)y=f(x)这个函数式就称为曲线的方程；同样，该这个函数式就称为曲线的方程；同样，该曲线即为这个方程的曲线。例如，圆的方程可写曲线即为这个方程的曲线。例如，圆的方程可写成成x2x2y2=R2y2=R2，椭圆的方程可以写成，椭圆的方程可以写成 同样，还可以写出比方双曲线，抛物线等的方程。同样，还可以写出比方双曲线，抛物线等的方程。48 在绘制这些曲线的时候，我们可以借助于各种标准工在绘制这些曲线的时候，我们可以借助于各种标准工具，比方画圆可以用圆规，划椭圆也可以用椭圆规。但具，比方画圆可以用圆规，划椭圆也可以用椭圆规。但对于非圆曲线，绘制时的更一般方法是借助于曲线板。对于非圆曲线，绘制时的更一般方法是借助于曲线板。我们现在平面上确定一些满足条件的、位于曲线上的坐我们现在平面上确定一些满足条件的、位于曲线上的坐标点，然后借用曲线板把这些点分段光滑地连接成曲线。标点，然后借用曲线板把这些点分段光滑地连接成曲线。绘出的曲线的精确程度，那么取决于我们所选择的数据绘出的曲线的精确程度，那么取决于我们所选择的数据点的精度和数量。坐标点的精度高，点的数量取得多，点的精度和数量。坐标点的精度高，点的数量取得多，那么连成的曲线愈接近于理想曲线。那么连成的曲线愈接近于理想曲线。其实，以上所说的方法也就是用计算机来绘制各类曲其实，以上所说的方法也就是用计算机来绘制各类曲线的根本原理。由于图形输出设备的根本动作是显示像线的根本原理。由于图形输出设备的根本动作是显示像素点或者是画以步长为单位的直线段，所以，从图形显素点或者是画以步长为单位的直线段，所以，从图形显示器和绘图机上输出的图形，一般除了水平线和垂直线示器和绘图机上输出的图形，一般除了水平线和垂直线以外，其他的各种线条，包括直线和曲线，都是由很多以外，其他的各种线条，包括直线和曲线，都是由很多的短直线构成的锯齿形线条组成的。从理论上讲，绝对的短直线构成的锯齿形线条组成的。从理论上讲，绝对光滑的理想曲线是绘不来的。光滑的理想曲线是绘不来的。49 一个绘制任何曲线的根本原理，就是要把曲线离散一个绘制任何曲线的根本原理，就是要把曲线离散化，把它们分割成很多短直线段，用这些短直线段组成化，把它们分割成很多短直线段，用这些短直线段组成的拆线来逼近曲线。至于这些短直线段取多长，那么取的拆线来逼近曲线。至于这些短直线段取多长，那么取决于图形输出设备的精度和我们绘制的曲线所要求的精决于图形输出设备的精度和我们绘制的曲线所要求的精度，但我们所要求到达的精度不能逾越图形设备所实际度，但我们所要求到达的精度不能逾越图形设备所实际具有的精度。具有的精度。50 曲线的方程共有三种形式：曲线的方程共有三种形式：1 1一般函数：一般函数：y=f(x)y=f(x)如椭圆方程：如椭圆方程：绘制曲线绘制曲线 y=f(x)y=f(x)应给出自变量应给出自变量 x x的取值范围的取值范围xlxl，x2x2，选取适当选取适当x x增量增量xx，计算出曲线上一系列点的坐标，依，计算出曲线上一系列点的坐标，依次用直线连接即可画出曲线。次用直线连接即可画出曲线。2 2参数方程曲线：参数方程曲线：如椭圆方程：如椭圆方程：曲线用参数方程表示在研究曲线曲线用参数方程表示在研究曲线性质和用计算机绘制曲线时是很方性质和用计算机绘制曲线时是很方便的。参数便的。参数t t在一定取值范围内变在一定取值范围内变动即可算出曲线上一系列点的纵横动即可算出曲线上一系列点的纵横坐标，从而画出曲线。坐标，从而画出曲线。51(3)(3)极坐标方程曲线生成极坐标方程曲线生成 极坐标方程形势是极坐标方程形势是r=P()r=P()，式中，式中r r为向径，为向径，为极角，为极角，但绘图时使用的是直角坐标系，因此在绘制极坐标方程但绘图时使用的是直角坐标系，因此在绘制极坐标方程曲线时，需先将点的极坐标曲线时，需先将点的极坐标r,r,转换成直角坐标转换成直角坐标(x,y),(x,y),然后才能画出这个点曲线。坐标转换公式为：然后才能画出这个点曲线。坐标转换公式为：x=rcos x=rcos y=rsin (t=0 y=rsin (t=0 2)2)52 三、自由曲线生成三、自由曲线生成 自由曲线是一条无法用标准代数方程来描述曲线。在自由曲线是一条无法用标准代数方程来描述曲线。在实际中，自由曲线应用都是非常广泛，比方轮船身外形实际中，自由曲线应用都是非常广泛，比方轮船身外形放样时的样条曲线，汽车、飞机及各种产品的外形曲线放样时的样条曲线，汽车、飞机及各种产品的外形曲线都可以看成是自由曲线。通常计算机生成曲线的方法分都可以看成是自由曲线。通常计算机生成曲线的方法分为两类：为两类：l l插值的方法：要求生成的曲线通过每个数据点，即插值的方法：要求生成的曲线通过每个数据点，即型值点。曲线插值方法有多项式插值，分段多项式插值，型值点。曲线插值方法有多项式插值，分段多项式插值，样条函数插值等。样条函数插值等。2 2拟合方法：要求生成曲线靠近每个数据点型值点拟合方法：要求生成曲线靠近每个数据点型值点，但不一定要求通过每个点。拟合方法有最小二乘法，但不一定要求通过每个点。拟合方法有最小二乘法，贝塞尔方法，贝塞尔方法，B B样条方法等。样条方法等。531 1三次样条曲线三次样条曲线1 1定义定义 1 1样样条条曲曲线线：有有假假设设干干个个离离散散点点，要要用用一一条条曲曲线线光光滑滑通通过过这这些些点点，我我们们可可以以把把这这条条曲曲线线想想象象成成一一条条具具有有相相当当柔柔韧韧性性的的木木条条，离离散散点点那那么么是是固固定定木木条条的的钉钉子子，在在挠挠度度不不大大的的情情况况下下，木木条条弯弯曲曲而而不不断断裂裂，这这样样，曲曲线线在在每每个个离离散散点点处处都都保保证证连连续续。在在放放样样加加工工过过程程中中，一一般般将将这这种种木木条条称称作作样样条条，此种类型曲线即称为样条曲线。此种类型曲线即称为样条曲线。p1p2p3pipn2 2三次样条曲线：曲线的形式有许多种，考虑到既要保三次样条曲线：曲线的形式有许多种，考虑到既要保证一定的精度，计算又不至于太复杂，一般我们取三次多证一定的精度，计算又不至于太复杂，一般我们取三次多项式的曲线作为此种类型曲线近似曲线，也称之为三次样项式的曲线作为此种类型曲线近似曲线，也称之为三次样条曲线。条曲线。542 2三次样条曲线生成算法原理三次样条曲线生成算法原理 1 1三次多项式函数表示三次多项式函数表示设平面上有设平面上有N N个型值点，表示为个型值点，表示为ViVixixi，yiyi，i=li=l ，2,n2,n1,n1,n,且且xlxlx2x2xnxn设设SiSix x表示第表示第i i段的三次多项式函数段的三次多项式函数 且且SiSixixi=yi=yi，SiSixixi1 1=yi=yi1 1，可将可将SiSix x写成：写成：(1)(1)i=li=l，2,n2,n1 xxi,xi+11 xxi,xi+1 其中其中aiai，mimi，cici和和didi为待定系数。为待定系数。图4.25三次样条曲线因为因为n n个离散个离散点只有点只有n n1 1段段要求出三次要求出三次多项式，关多项式，关键是求待定键是求待定系数系数55为为了了使使整整体体上上看看仍仍为为一一条条光光滑滑曲曲线线，那那么么在在相相邻邻两两端端曲曲 线的交点处应有相同的切线与曲率。即：线的交点处应有相同的切线与曲率。即：2 2求待定系数求待定系数aiai，mimi，cici和和didi 如果将多项式待定系数如果将多项式待定系数aiai，mimi，cici和和didi求出，那么各段求出，那么各段 三项多项式就可求出，曲线就可以画出来。三项多项式就可求出，曲线就可以画出来。将将xi xi ，xixi1 1处的值代入处的值代入Si(x)Si(x)表达式，得：表达式，得：56对对SiSiX X求导求导 假设令假设令由由57解联立方程：先将解联立方程：先将yiyi，yiyi1 1看成量，解方程组得：看成量，解方程组得：由于由于yyi i、yyi i1 1是未知的，故直接用是未知的，故直接用m mi i、m mi i1 1来表示来表示,即即 m mi i=y=yi i,m,mi i1 1=y=yi+1i+1,c,ci i和和d di i又可写成：又可写成：58求求mimii=1,2,)i=1,2,)显然，假设求出了显然，假设求出了mimi、mimi1 1，那么，那么aiai、cici和和didi就全部就全部求出了，这时，求出了，这时，Si(x)Si(x)也就确定。为了求出也就确定。为了求出mi mi，(i=1,2,(i=1,2,，n n1),1),我们考虑我们考虑 Si Si(Xi)(Xi)，对，对4 4式求式求导得：导得：59将将Ci-1Ci-1，CiCi，di-1 di-1分别用分别用mi-1mi-1，mimi，mimi1 1来表示来表示,代入代入(9(9式，式，(见幻灯见幻灯5959页经整理得：页经整理得：60 以上是以上是m1m1，m2mn-1,mnm2mn-1,mn为未知量的方程组，称为为未知量的方程组，称为“三转角方程三转角方程(力学上或力学上或m m连续性方程，由于有连续性方程，由于有n n个未知量，个未知量，n n2 2个方程，要使其有唯一解，应再增加两个方程。这时，个方程，要使其有唯一解，应再增加两个方程。这时，我们通过增加边界条件来得到两个新的方程。我们通过增加边界条件来得到两个新的方程。边界条件的方法很多，一般都是根据具体问题的需要加边界条件的方法很多，一般都是根据具体问题的需要加以确定，这里我们给出几种常用的边界条件。以确定，这里我们给出几种常用的边界条件。(1)(1)夹持端：限定两端切线方向，假设夹持端：限定两端切线方向，假设 ml mlk1k1，mnmnk2,k1k2,k1和和 k2 k2是常数，这实际上增加了两个方程。是常数，这实际上增加了两个方程。(2)(2)抛物端：认为曲线在第抛物端：认为曲线在第1 1段和第段和第n n1 1段末端为抛物线，段末端为抛物线，即此二段曲线的二阶导数为常数。因此而得：即此二段曲线的二阶导数为常数。因此而得：613 3自由端：端点处二阶导数为自由端：端点处二阶导数为 0 0，即，即y1y1 0 0，yn yn 0 0，由此而得，由此而得:对于以上三种边界条件，我们可以用统一两个方程来表示，对于以上三种边界条件，我们可以用统一两个方程来表示，即写成：即写成：62式中各种条件下的系数值见下表：式中各种条件下的系数值见下表：所以，将这两个统一的方程和前面所以，将这两个统一的方程和前面n n 2 2个方程组合得：个方程组合得：边界条件边界条件1 1，n nR R1 1,R,Rn n夹持端夹持端1 1=0=0，n n=0=0R R1 1=2k=2k1 1,R,Rn n=2k=2k2 2自由端自由端1 1=1=1，n n=1=1R R1 1=R=Rn n=抛物端抛物端1 1=2=2，n n=2=2R R1 1=R=Rn n=63 它们是它们是n n个未知量和个未知量和n n个方程组成的方程组，用矩阵形个方程组成的方程组，用矩阵形式表示为：式表示为：=显然，在上述三对角系数矩阵中。由于显然，在上述三对角系数矩阵中。由于|i|i|i|=1(i=2,3n|i|=1(i=2,3n1),0=i,n=1,1),0=i,n=1,主对角线上的元素为主对角线上的元素为2 2，对角严格占优势，故方程组的，对角严格占优势，故方程组的系数矩阵奇异，从而方程组有唯一解。用系数矩阵奇异，从而方程组有唯一解。用“追赶法很容追赶法很容易解这个方程组，并可节省大量的计算时间和存储空间。易解这个方程组，并可节省大量的计算时间和存储空间。64当求出了所有的当求出了所有的mimi后，那么，所有的后，那么，所有的ai,ciai,ci和和didi也就确定，也就确定，从而所有的从而所有的Si(x)Si(x)也确定了。这时，每给定一个也确定了。这时，每给定一个x x值，如值，如x=x*x=x*，先判断好，先判断好x*x*所在的区间，假设所在的区间，假设xi=x*=xixi=x*=xi1 1，那，那么利用么利用Si(x)Si(x)可计算出可计算出S(x*)S(x*)的函数值，即的函数值，即y*=S(x*)y*=S(x*)。为了。为了画出三次样条曲线，可将画出三次样条曲线，可将x x从从x1x1到到xnxn取一系列的值，计算取一系列的值，计算出相应的出相应的S(x)S(x)，然后用直线段一一连接相邻的，然后用直线段一一连接相邻的S(x)S(x)点。点。653)3)三次样条函数曲线解题步骤三次样条函数曲线解题步骤 根据实际情况决定边界条件三个条件根据实际情况决定边界条件三个条件,夹持端，抛物夹持端，抛物 线端，自由端线端，自由端根据几个型值点坐标建立方程组根据几个型值点坐标建立方程组用追赶法或其它方法解方程组，先求出用追赶法或其它方法解方程组，先求出m1,m2,mnm1,m2,mn求出求出mimi后然后用后然后用mimi再求再求ai,ciai,ci，didi，从而可确定各线段，从而可确定各线段 Si(x)Si(x)由由Si(x)Si(x)计算各段内假设干插值点并依次用直线相连，计算各段内假设干插值点并依次用直线相连，画画 出三次样条曲线出三次样条曲线 对于挠度大的情况下，三次样条函数并不太适合，而对于挠度大的情况下，三次样条函数并不太适合，而可采用三次参数多项式。可采用三次参数多项式。662 2、贝塞尔、贝塞尔(Bezier)(Bezier)曲线曲线1 1BezierBezier曲线的概述曲线的概述 1)1)贝塞尔曲线的定义贝塞尔曲线的定义 三次样条曲线是通过所有指定的数据点，但三次样条曲线是通过所有指定的数据点，但曲线的形状依赖于边界条件曲线的形状依赖于边界条件斜率或二阶导数。斜率或二阶导数。用斜率或二阶导数等数字去控制曲线形状，不能用斜率或二阶导数等数字去控制曲线形状，不能提供设计曲线形状所需直观感觉，也就是曲线的提供设计曲线形状所需直观感觉，也就是曲线的形状和数字之间不一定有明显关系。此外，三次形状和数字之间不一定有明显关系。此外，三次样条曲线各段都是三次曲线，这对曲线形状设计样条曲线各段都是三次曲线，这对曲线形状设计来说是不够灵活的，不能直观表示出应该如何修来说是不够灵活的，不能直观表示出应该如何修改以及如何控制曲线形状。事实上，设计曲线形改以及如何控制曲线形状。事实上，设计曲线形状时，设计师常用做法是先用折线勾画一个轮廓，状时，设计师常用做法是先用折线勾画一个轮廓，再用曲线去逼近这个折线轮廓。再用曲线去逼近这个折线轮廓。用光滑参数曲线段去逼近折线多边形的一种用光滑参数曲线段去逼近折线多边形的一种法国雷诺公司工程师贝塞尔法国雷诺公司工程师贝塞尔(PEBezier)70(PEBezier)70年年代初提出了一种描述曲线方法就是用光滑参数曲代初提出了一种描述曲线方法就是用光滑参数曲线段逼近折线多边形的一种数学模型，称为线段逼近折线多边形的一种数学模型，称为BezierBezier曲线曲线67BezierBezier曲线及曲线及其特征多边形其特征多边形682 2贝塞尔曲线的特点贝塞尔曲线的特点 贝塞尔曲线不要求给出导数，只要给出数据点就可构贝塞尔曲线不要求给出导数，只要给出数据点就可构 造曲线，造曲线，贝塞尔曲线次数严格依赖于确定该段曲线的数据贝塞尔曲线次数严格依赖于确定该段曲线的数据 点个数，曲线形状依赖于该多边形的形状，一般两点个数，曲线形状依赖于该多边形的形状，一般两 个数据点是一次曲线，三个数据点是二次曲线，四个个数据点是一次曲线，三个数据点是二次曲线，四个 数据点是三次曲线。数据点是三次曲线。贝塞尔曲线不完全通过数据点，只有该多边形第一个贝塞尔曲线不完全通过数据点，只有该多边形第一个 顶点和最后一个顶点在曲线上。顶点和最后一个顶点在曲线上。P0P1P2P369 2 2BezierBezier曲线数学表达形式曲线数学表达形式 BezierBezier曲曲线线是是由由一一组组折折线线来来定定义义的的，且且第第一一点点和和最最后后一一点点在在曲曲线线上上，第第一一条条和和最最后后一一条条折折线线分分别别表表示示出出曲曲线线在在起起点点和和终终点点处处切切线线方方向向。BezierBezier曲曲线线通通常常由由(n(nl)l)个个顶顶点点定义一个定义一个n n次多项式，曲线上各点参数方程式为：次多项式，曲线上各点参数方程式为：4 41414 参数参数t0,1t0,1 0=i=n 0=i=n为整数值为整数值 n n是是多多项项式式次次数数，也也是是曲曲线线次次数数，通通常常由由n n1 1个个顶顶点点确确定的曲线为定的曲线为n n次曲线。次曲线。PiPi是是第第i i个个顶顶点点的的坐坐标标值值x x和和y y，Bi,nBi,nt t是是伯伯恩恩斯坦斯坦(Bernstein)(Bernstein)多项式，称为基函数，其定义如下：多项式，称为基函数，其定义如下：70 (3)(3)BezierBezier曲线的性质曲线的性质 1)1)端点性质端点性质BeBeZ Zierier曲线的起点和终点分别是特征多边形的第一个顶曲线的起点和终点分别是特征多边形的第一个顶点和最后一个顶点。点和最后一个顶点。在曲线的起点处，在曲线的起点处，t=0t=0，代入代入(4-14)(4-14)得得上式中除了上式中除了i i0 0这一项，其他项都为零，所以这一项，其他项都为零，所以P(0)P(0)P0P0同理，在曲线终点处同理，在曲线终点处t tl l那么那么P(1)=PnP(1)=Pn规定规定71曲线在起点和终点处的切线分别是特征多边形的第一曲线在起点和终点处的切线分别是特征多边形的第一 条边和最后一条边，且切矢的模长分别为相应边长的条边和最后一条边，且切矢的模长分别为相应边长的n n倍倍 对式对式4-144-14求导得推导过程从略：求导得推导过程从略：于是在曲线的起点和终点处分别有于是在曲线的起点和终点处分别有 P(0)=n(P1 P(0)=n(P1P0)P0)P(1)=n(PnP(1)=n(PnPn-1)Pn-1)722 2凸包性凸包性 对对区区间间0,10,1的的任任一一值值u u，点点P(u)P(u)必必须须落落在在由由特特征征多多边边形形顶顶点点所所张张成成的的凸凸包包内内。即即当当特特征征多多边边形形为为凸凸时时，BezierBezier曲曲线线也也是是凸凸的的；当当特特征征多多边边形形有有凹凹有有凸凸时时，其其曲曲线的凸凹形状与之对应，且在其凸包范围内线的凸凹形状与之对应，且在其凸包范围内733 3几何不变性几何不变性由由BezierBezier曲线的定义式曲线的定义式4 41414 曲曲线线的的形形状状由由特特征征多多边边形形的的顶顶点点PiPii i0 0，l l，n n唯唯一一确确定定，与与坐坐标标系系的的选选取取无无关关。这这就就是是几几何何不不变性，变性，BezierBezier曲线的几何作图法就是一个很好的例证。曲线的几何作图法就是一个很好的例证。(3)(3)几个低次几个低次BezierBezier曲线曲线 1 1一次一次BezierBezier曲线曲线 当当n=1n=1时，式时，式(4-14)(4-14)为为 说明一次说明一次BezierBezier曲线是连接曲线是连接P0P0和和P1P1直线段。直线段。742 2二次二次BezierBezier曲线曲线 当当n n2 2时式时式(4-14)(4-14)为为 说明二次说明二次BezierBezier曲线是一段抛物线。用矩阵表示为曲线是一段抛物线。用矩阵表示为 753 3三次三次BezierBezier曲线曲线 当当n n3 3时式时式(4-14)(4-14)为为 76用矩阵表示为：用矩阵表示为：77一般的，对于一般的，对于n n次次BezierBezier曲线，用矩阵形式可表示为：曲线，用矩阵形式可表示为：具具体体绘绘图图时时，要要将将控控制制点点位位置置矢矢量量分分解解为为二二维维平平面面上上x x，y y方向上分量，那么上述式可分解为：方向上分量，那么上述式可分解为：78(4)Bezier