第五章1图形显示算法基础

13.1直线的生成算法3.1.1基本知识

只有画水平线,垂直线,及正方形对角线时,象素点集的位置才是准确的。显示一条直线,实际上是用最靠近这条直线的象素点集来近似地表示这条直线.有限的象素矩阵画点设备光栅显示器:

缓冲存储器，显示控制器，数/模转换器，阴级射线管（CRT）A(x1,y1)、B(x2,y2)、在纸上画一条直线和在计算机屏幕上画一条直线有什么本质的区别? 2生成直线的一般要求是：1.DDA算法（数值微分法）2.直线的Bresenham算法

确定象素最佳逼近某图形的过程通常称为光栅化。图形生成算法的工作:在显示器所给定的有限个象素组成的矩阵中,确定最佳逼近于图形的象素点集.1.象素是均匀分布的2.所画的线应是直的，且有精确的起点和终点4.最后直线的生成速度要快3.所显示的亮度应沿直线不变，且与直线的长度和方向无关。3.1.2直线光栅化的方法3已知端点A(x1,y1)、B(x2,y2),直线的微分方程：dy/dx=(y2-y1)/(x2-x1)=常数=m

yi+1＝yi+(y2-y1)/(x2-x1)*Δx=yi+m*Δx

yi=mxi+Byi+1=mxi+1+B=m(xi+Δx)+BA(x1,y1)B(x2,y2)Pi(xi,yi)Pi+1(xi+1,yi+1)dy=k·dxdx3.1.3

DDA算法(DigitalDifferentialAlgorithm)通过同时对x,y各增加一个小的增量,计算下一步的x,y值。在一个迭代算法中,如果每一步的x,y值是用前一步的值加上一个增量来获得,那么这种算法称为增量算法。4光栅中Δx=1直线的递推公式

yi+1＝yi+(y2-y1)/(x2-x1)xi+1＝xi+1doublex=x1,y=y1;m=(y2-y1)/(x2-x1);intk=abs(x2-x1);for(inti=0;i<k;i++){x=x+1;y=y+m;}

如果x2>x1≥0,y2>y1≥05oxyk>1讨论:oxyk<1xi+1=xi+1yi+1=yi+kyi+1=yi+1xi+1=xi+1/k(xi,yi)(xi+1,yi+1)(xi,yi)(xi+1,yi+1)因而造成隔行显示解决办法:将y看作自变量6结论：第一象限的直线DDA算法：(round(xi+1),yi+1)yi+1=yi+1xi+1=xi+1/kk>1(xi+1,round(yi+1)）xi+1=xi+1yi+1=yi+kk<1逼近直线的象素点的坐标直线上点的坐标递推公式直线的斜率起点（x1,y1），终点（x2,y2）(x2>x1,y2>y1)以（x1,y1）为起点7DDA算法的优、缺点

DDA算法的本质:效率低,不利于硬件实现直观可行

DDA算法也是一个增量算法。缺陷:做除法;须采用浮点数据计算要取整数->算法效率不高算法程序实现k=abs(x2-x1);if(abs(y2-y1)>k)doubledeltx=(x2-x1)/k;doubledelty=(y2-y1)/k;for(inti=0;i<=k;i++){x+=deltx;//x=x+deltx;y+=delty;//y=y+delty;}k=abs(y2-y1);

putpixel((int)x,(int)y,2);用数值方法解微分方程(数值微分法)81.问题的提出2.基本思想a.效率的意义b.希望找到一个简单的判决条件,迅速确定直线上的点。借助于一个决策变量d的正负符号,来确定下一个该点亮的象素点。最逼近Pi+1点的象素点是Ti+1点还是Si+1点？由ti+1与si+1二者的相对大小决定。若ti+1<si+1,则取Ti点(xi+1,yi+1)若ti+1>si+1,则取Si点(xi+1,yi)ti+1与si+1二者的大小可以由si+1-ti+1的正负来判定。stTiSi(r,q)3.1.4直线的Bresenham算法9为讨论方便,假定:直线斜率k在0,1之间起点坐标A(x1,y1)终点坐标B(x2,y2)将直线平移到原点则起点坐标（0，0),终点坐标B(dx,dy)dx=x2-x1dy=y2-y1其中直线方程为：且其中r=xi-1,q=yi-1stTiSi(r,q)所以定义di=dx(s-t)为决策变量10经推导di+1=di+2dy-2dx*(yi-yi-1)如果1)当di0，即s-t0,st,则点亮Ti，2)当di0，即s-t0,s<t,则点亮Si，di+1=di+2(dy-dx)下一个决策变量stTiSi(r,q)下一个决策变量yi=yi-1+1;xi=xi-1+1;yi=yi-1;xi=xi-1+1;di+1=di+2dy起点为(0,0)时,初始值d1=2dy-dx11x=0,y=0,dx=5,dy=4决策变量的初值d0=2*x*dx-2*y*dy+2*dy-dx＝3点亮点（0，0）d1=d0+2(dy-dx)＝3＋2*(4-5)=1>=0点亮点（1，1）点亮点（2，1）d3=d2+2dy＝-1＋2*4=7>=0d2=d1+2(dy-dx)＝1＋2*(4-5)=-1<=0点亮点（3，2）d3=d2+2(dy-dx)＝7＋2*(4-5)=5>=0点亮点（4，3）d4=d3+2(dy-dx)＝5＋2*(4-5)=3>=0点亮点（5，4）举例:从点A(0,0)到B(5,4)画一直线.di0di0yi=yi-1+1;xi=xi-1+1;yi=yi-1;xi=xi-1+1;12一个完整的直线算法应考虑以下几个方面1.水平线2.垂直线4.直线的斜率为m,|m|>15.|m|<16.Δy<07.Δx<0等3.45

线Bresenhanm算法的优点：(3)只有加法和乘2运算,在计算机内部是用位移操作实现的,效率高。因此，Bresenhanm算法的运算速度很快，并适于用硬件实现。(1)不必计算直线的斜率，因此不必作除法；(2)不用浮点数，只用整数；13开始x=x1;y=y1;dx=abs(x2-x1);dy=abs(y2-y1);s1=sign(x2-x1);s2=sign(y2-y1);T=dxdx=dydy=Tinter=1x>yInter=0d=2(x*dx-y*dy)+2*dy-dxi=1;putpixel(x,y,color)d>0YNYNd>0x=x+s1y=y+s2d=d+2(dy-dx)inter=1x=x+s1d=d+2*dyy=y+s2i=i+1YYNN14voidline(intx1,inty1,intx2,inty2,intc)/*参数c为直线的颜色*/{intdx,dy,x,y,d,const1,const2,,tmp;ints1,s2,inter;dx=abs(x2-x1);dy=abs(y2-y1);if(x2>x1)s1=1;elses1=-1;if(y2>y1)s2=1;elses2=-1;if(dy>dx){tmp=dx;dx=dy;dy=tmp;inter=1;}elseinter=-1;d=2*dy-dx;const1=2*dy;/*注意此时误差的*/const2=2*(dy-dx);/*变化参数取值.*/x=x1;y=y1;putpixel(x,y,c);for(i=1;i<dx;i++){if(d>=0){y+=s2;x+=s1;d+=const2;}else{if(inter==1)y+=s2;elsex+=s1;d+=const2;}putpiexl(x,y,c);}}15生成直线算法的进一步改进

1987年有人提出二步法，即没循环一次不是绘制一个象素，而是绘制二个象素，这样无疑可以把生成直线的速度提高一倍。只可能出现的四种情况ABCD同样，我们先考虑当直线的斜率m属于区间[0，1]时，在x方向每增加两个单元163.2.1

圆弧的扫描法已知圆的圆心坐标为（xc,yc），半径为R圆的直角坐标方程表示为(x-xc)2+(y-yc)2=R2x0=xc-Ry0=ycxi+1=xi+1yi+1(xi+1,Round(yi+1))缺点:

(1)运算速度慢

(2)显示质量不好(xc,yc)(xc-R,yc)角度DDA算法圆弧的扫描法正负法、圆弧的Bresenham算法、T-N方法等3.2圆弧的生成算法17由圆的参数方程推导出圆弧的增量算法的表达式:缺点：所产生的圆是不封闭的，且该圆的半径有不断增大的趋势。取微分令x0=Ry0=0起点(x0,y0)=0～2

,为所画圆弧的圆心角单位为弧度d＝2-m

——角度增量，m为整数。已知圆的圆心坐标为（0,0），半径为R(0,0)(R,0)3.2.2角度DDA算法(近似法)18PiPi+1原因：

Pi+1是在Pi上加一个小的矢量而得到，这个矢量垂直于位置矢量Pi。因此新的半径经常比前一个半径大，从而得到的曲线是一条螺线。将第二式中的xi用xi+1

代替,则有:yi+1=yi+xi+1d=yi+(xi-yid)d=d

xi+(1-d

2)yixi+1=xi-yid

为椭圆

d＝2-m，当m=4时，此椭圆与精确圆之间的误差E＝1.6％3.2.3椭圆差分法192024/9/9

–hjy-19dPi+1PiOXY1pixel=Rsind

d=arcsin-11/R令：3.2.4旋转法20xy(xc,yc)方程若F(x,y)<0点(x,y)在圆内若F(x,y)>0点(x,y)在圆外若F(x,y)=0点(x,y)在圆上2.F(x,y)=0是二阶光滑F－F＋F＋F－1.F(x,y)=0划分平面域为3个点集函数的特点：F＋F－圆的方程为：3.每一个点的曲率半径>步长(1pixel)3.2.5正负法（隐函数曲线)21(0,R)若点Pi在圆内或圆上，即F(xi,yi)≤0若点Pi在圆外，即F(xi,yi)＞0以第一个1/4圆弧为例，取圆弧的最上方点为起始点(x0,y0)，x0=0y0=R点Pi+1取R点，即xi+1=xi+1,yi+1=yi点Pi+1取B点，即xi+1=xi,yi+1=yi-1由当前点Pi(xi,yi)选择下一点Pi+1(xi+1,yi+1)的规则是：xyo22则当xi+1=xi+1,yi+1=yi时，当xi+1=xi,yi+1=yi-1时，23结论——第一个1/4圆弧的正负法算法：若F(xi,yi)≤0（点在内侧，下一点选外侧）若F(xi,yi)＞0（点在外侧，下一点选内侧）xi+1=xi+1,yi+1=yixi+1=xi,yi+1=yi-1已知圆心坐标为（xc,yc），半径为R，起始点(x0,y0)x0=xcy0=yc+R以坐标原点为圆心的第一象限1/4圆为例XYOV(xi,yi-1)P(xi,yi)H(xi+1,yi)D(xi+1,yi-1)(0,R)(R,0)起点为(0,R)，按顺时针方向生成圆则y为x的单调递减函数设P(xi,yi)点为当前点圆上的亮点下一个该显示的象素有三种可能:右方象素H、右下方D、下方象素V决定一象素使其与真正圆的距离的平方最小222)1(RyxmiiV--+=222)1()1(RyxmiiD--++=222)1(RyxmiiH-++=圆在与点P(xi,yi)附近光栅网格的相交关系只有5种123451.基本思想3.2.6圆弧的Bresenham算法25五种情况分解图：H,D,V全在圆内H在圆外，D,V在圆内D在圆上，H在圆外，V在圆内D,H在圆外，V在圆内D,V,H全在圆外3HDV5HDV4HDV2DVHV(xi,yi-1)P(xi,yi)H(xi+1,yi)D(xi+1,yi-1)123451HDV取D点取H点或D点取D点或V点取H点取V点首先计算圆心到右下角象素D的距离平方与圆心到圆弧上的点的距离平方之差如果Δi<0,说明D点在圆内,只能是1,2情况，可选D点或H点设为圆到象素H的距离平方与圆到象素D的距离平方之差。

＝|(xi+1)2+(yi)2-R2|-|(xi+1)2+(yi-1)2-R2|MhMd如果

<0,说明圆到D点的距离大于圆到H点的距离，应选H(xi+1,yi)如果

>0,应选D(xi+1,yi-1)如果

=0,规定选D(xi+1,yi-1)V(xi,yi-1)P(xi,yi)H(xi+1,yi)D(xi+1,yi-1)123对于情况2，左下角D总是位于圆内，而H点总是位于圆外(xi+1)2+(yi-1)2-R2<0=2(Δi+yi)-1对于情况1,由于y为一单调递减函数，只能选取H点因为：(xi+1)2+(yi)2-R2<0(xi+1)2+(yi-1)2-R2<0=(yi-1)2-(yi)2<0结论与情况2是一致的所以有：(xi+1)2+(yi)2-R2>=0V(xi,yi-1)P(xi,yi)H(xi+1,yi)D(xi+1,yi-1)123

＝|(xi+1)2+(yi)2-R2|-|(xi+1)2+(yi-1)2-R2|如果Δi>0,说明D点在圆外,只能是4,5情况，可选V点或D点设‘为圆到象素D的距离平方与圆到象素V的距离平方之差。‘＝|(xi+1)2+(yi-1)2-R2|-|(xi)2+(yi-1)2-R2|如果‘<0,说明圆到V点的距离大应选D(xi+1,yi-1)如果‘>0,如果‘=0,规定选D(xi+1,yi-1)说明圆到D点的距离大应选V(xi,yi-1)情况4:由于D在圆外，而V在圆内:

(xi+1)2+(yi-1)2-R2>=0(xi)2+(yi-1)2-R2<0‘=2(Δi－xi)-1对于情况5,由于y为一单调递减函数，只能选取V点‘=(xi+1)2-(xi)2>0结论与情况4是一致的对于情况3,应选D点V(xi,yi-1)P(xi,yi)H(xi+1,yi)D(xi+1,yi-1)45归纳总结：当Δi<0时，<=0,取H(xi+1,yi)点>0,取D(xi+1,yi-1)点当Δi>0时，‘<=0,取D(xi+1,yi-1)点‘>0,取V(xi,yi-1)点当Δi=0时，取D(xi+1,yi-1)点V(xi,yi-1)P(xi,yi)H(xi+1,yi)D(xi+1,yi-1)30水平移动到H(xi+1,yi)点Xi+1=xi+1yi+1=yiΔi+1=(xi+1+1)2+(yi+1-1)2-R2＝(xi+1)2+(yi-1)2-R2＝Δi+2xi+1+1对角移动到D点Xi+1=xi+1yi+1=yi-1Δi+1=Δi+2xi+1-2yi+1+2移动到V点Xi+1=xiyi+1=yi-1Δi+1=Δi-2yi+1+1V(xi,yi-1)P(xi,yi)H(xi+1,yi)D(xi+1,yi-1)

圆弧的Bresenham算法的优点:起点和终点准确，分布均匀，计算简单。由上面的分析,增量算法的递推公式:31画圆心为(0,0),半径R=8的四分之一的圆弧初始条件:x1=0;y1=8;R=8

1=(x1+1)2+(y1-1)2-R2=1+49-64=-14<0;

HD=2(1+y1)-1=2(-14+8)-1=-13<0取H点

2=

1+2x2+1=-14+2*1+1=-11<0

HD=2(2+y2)-1

=2(-11+8)-1=-7<0

HD=2(3+y3)-1

=2(-6+8)-1=3>0取D点取H点点亮点(0,8)可能点亮H或D点x2=1y2=8

3=

2+2x3+1=-11+2*2+1=-6<0x3=2y3=8x4=3y4=7Δ4=Δ3+2x4-2y4+2=-6+2*3-2*7+2=-12<0

HD=2(3+y4)-1

=2(-12+7)-1=-11<0取H点x4=4y4=7Δ5=Δ4+2x5+1=-12+2*4+1=-3<0

HD=2(4+y4)-1=2(-3+7)-1=9>0取D点x5=5y5=6Δ6=Δ5+2x5-2y5+2=-3+2*5-2*6+2=-3<0

HD=2(6+y6)-1=2(-3+6)-1=5>0取D点x6=6y6=5V(xi,yi-1)P(xi,yi)H(xi+1,yi)D(xi+1,yi-1)Δ7=Δ6+2x6-2y6+2=-3+2*6-2*5+2=1>0取D点x7=7y7=4

DV=2(6-x6)-1=2(1-6)-1=-11<0Δ8=Δ7+2x7-2y7+2=1+2*7-2*4+2=9>0

DV=2(7-x7)-1=2(9-7)-1=3>0取V点x8=7y8=3Δ9=Δ8

-2y8+1=9-2*3+1=4>0

DV=2(9-x8)-1=2(4-7)-1=-7<0取D点x9=8y9=2Δ10=Δ9+2x9-2y9+2=4+2*8-2*2+2=18>0

DV=2(10-x9)-1=2(18-8)-1=19>0取V点x10=8y10=1Δ11=Δ10

-2y10+1=19-2*2+1=16>0

DV=2(11-x10)-1=2(16-8)-1=15>0取V点x11=8y11=033Yy>=0YN结束起点x=0y=RΔD<0NYNΔD>0YNYN1/4圆程序流程图34上机：

1.编制圆弧正负法的算法程序；（下次上机时提交）

2.读懂并上机调试、运行圆弧的Bresenham算法程序；手工：画圆心为(0,0),半径R=10的四分之一的圆弧用圆弧的Bresenham算法计算各个象素点的坐标值作业:

1.完成直线DDA算法程序的实现2.画（0，0）到（8，－4）之间的线段3.完成直线Bresenham算法完整程序353.3.1概述曲线规则曲线——可用标准的解析式来描述的曲线。如圆、椭圆、抛物线、双曲线、渐开线、摆线等自由曲线——无法用标准的曲线方程来描述的曲线，通常由实际测量得到的一系列散乱的数据点(型值点)来确定。如汽车的外形曲线、等高线等。计算机显示曲线的基本原理是“以直代曲”,即用许多能满足精度要求的短的直线段代替曲线.如正多边形逼近圆3.3规则曲线的生成算法36xyo圆----圆上任意一点的曲率都相等,因此用角度DDA算法在屏幕上会产生较好的图像.1.椭圆等角度DDA算法椭圆若采用等周长的显示算法，只要有足够数量的段数，就会常发生较好的图像。希望：曲率较小的两侧取较大的周长增量曲率较大的两侧取较小的周长增量步长为等周长的椭圆算法的缺陷:1.曲率较小的两侧,点过密,曲率较大的两侧,点过稀.2.将涉及椭圆积分,计算费时,算法效率低.长轴两端的曲率太大,用少数几个等角度增量计算出来的点无法较精确地描述椭圆.3.3.2椭圆的显示算法37因此椭圆用参数方程表示:其中：圆心的坐标为(xc,yc),a,b为椭圆长短、半轴,

为参数取微分得:分析:1.当角接近0或时,两端的曲率较大,有:此时|dy|近似2.当角接近/2或3/2时,两端的曲率较大,有:此时|dx|近似由于a>b，所以两端点多，而两侧点少。且周长增量大小之比

a/b我们希望的周长增量可以自动获得等于弧长等于弧长38N——椭圆上显示点的个数i(xc,yc)392.椭圆的生成算法-------中点法给定椭圆参数中心(0，0)、长半轴a和短半轴b，该椭圆的一般方程为：

X2/a2+Y2/b2=1F(x,y)=b2x2+a2y2-a2b2=0 中点画圆法可以推广到一般二次曲线的生成现讨论第一象限椭圆弧的生成。在处理这段椭圆弧时，我们进一步把它分为两部分：上部分和下部分，以弧上斜率为-1的点作为分界。上半部分，斜率的绝对值>1,单位步长应为X方向，来确定下一个象素的位置下半部分，斜率的绝对值<1,单位步长应为Y方向，从而确定下一个象素的位置则该公式可作为中点算法的判别式：F(x,y)<0=0>0说明(x，y)在椭圆边界内说明(x，y)在椭圆边界上说明(x，y)在椭圆边界外40椭圆的斜率：dy/dx=-2b2x/(2a2y)

中点画椭圆，当我们确定一个象素之后，接着在两个候选点的中点计算一个判别式的值。并根据判别式符号确定哪个象素离椭圆更近。有一个象素点（xp,yp),那么下一对候选象素的中点是（xp+1,yp-0.5)。xp,ypxp+1,yp-0.5当斜率为-1时则：2b2x=2a2y上半部分的条件是：2b2x<=2a2y下半部分的条件是：2b2x>=2a2y假如上半部分椭圆判别式为：dp=F(xp+1,yp-0.5)=b2(xp+1)2+a2(yp-0.5)2-a2b2如果dp<＝0,中点在椭圆内，则取正右方的那个象素且判别式应更新为:dp+1=F(xp+2,yp-0.5)=dp+b2(2xp+3)如果dp>0,中点在椭圆外，则取右下方的那个象素且判别式应更新为：dp+1=F(xp+2,yp-1.5)=dp+b2(2xp+3)+2a2(-yp+1)41弧的起点为（b,0)第一个中点是(1,b-0.5)判别式的初值dp0=b2+a2(-b+0.25).步进方向由x改为方向ydp=b2(xp+0.5)2+a2(yp-1)2-a2b2下半部分的终止条件为y=0假如为椭圆弧的下半部分如果上半部分的最后一个象素为（xp,yp)，则且应改为从正下方和右下方两个象素中选择一个象素中点是（xp+0.5,yp-1)如果dp<＝0,中点在椭圆内，则取右下方的那个象素Pr(xp+1,yp-1)且判别式应更新为:dp+1=F(xp+1.5,yp-2)=dp+b2(2xp+2)+a2(-2yp+3)如果dp>0,中点在椭圆外，则取正下方的那个象素Pl（xp,yp-1）且判别式应更新为：dp+1=F(xp+0.5,yp-2)=dp+a2(2yp+3)在编写程序时应先更新决策变量d，再更新（x，y）上半部分的终止条件为：b2(x+1)<a2（y-0.5)下半部分的d的初值为上半部分计算的最后点下半部判别式的初值dp0=b2(x+0.5)2+a2(y-1)2-a2b242或抛物线标准方程为:y²=4ax(a为抛物线焦距)xyN——显示点的个数参数方程3.3.3抛物线的显示算法43基圆圆心在原点的渐开线参数方程为令起始角

s=0,终止角e=N——显示点的个数3.3.4渐开线的显示算法443.4.1基本概念1.插值-----构造一函数，使曲线或曲面严格通过所有的已知点。通常用已知函数代替被插的函数。2.逼近-----构造一函数，但曲线或曲面不严格通过各型值点，只要求最靠近。Bezier、B-Spline型值点3.拟合----插值逼近在曲线曲面的描述中，所构造的数学模型要：保证：1.空间的唯一性

2.物体的有界性、连续性

3.坐标变换后形状不变性（坐标独立性）Q1Q3Q0Q2P1（x1,y1)P2（x2,y2)P3（x3,y3)3.4自由曲线的生成算法45对数学式的一些要求是：1.有足够强的描述能力（局部、整体光滑）2.易控制（形）、易预测（闭凸包性、变差减小性----不稳、摆动）平面曲线空间曲线直角坐标方程y=f(x)或f(x,y)=0z=f(x,y)或f(x,y,z)=0参数坐标方程代数形式x=x(t)y=y(t)x=x(t)y=y(t)z=z(t)几何形式P(t)=[x(t)y(t)]P(t)=[x(t)y(t)z(t)]3.4.2曲线的表示方法461）易于处理多值问题；2）在多值的情况下，可以方便地指定曲线的延伸范围；3）具有几何不变性，其形状与坐标的选择无关，可以不依靠坐标系来研究图形的几何性质；4）易于进行几何变换，如仿射变换、射影变换等；5）易于计算曲线上的点（计算方便）；6）易定义空间曲线（规定曲线的范围和边界等）；7）便于曲线的分段描述。参数曲线描述的优点：471.型值点2.控制点指用来控制或调整曲线形状的特殊点。如BEZIER曲线段中的Q1与Q2点。Q1Q3Q0Q23.位置矢量表示曲线上任一点的坐标的矢量

P(t)=[x(t)y(t)z(t)]P1（x1,y1)P2（x2,y2)P3（x3,y3)P2’指通过测量或计算得到的曲线或曲面上少量描述曲线或曲面几何形状的数据点。3.4.3常用名词术语484.切矢量P'0P'1P0P1t=0t=1P(t)RP(t+△t)Q5.曲率T——单位切矢量△C△PC--弧长当Q趋向于r时：在极限情况下|△P|=△C设以弧长c为参数，曲线的方程为p(c)T(c+△c)T(c)T(c+△c)T(c)RQ△

△c若曲线上R，Q两点的参数分别为t和t＋△t，矢量△p＝p(t+△t)-p(t)496.几何连续性指两段曲线或两片曲面在连接处的连续状态。(1)Q1(1)=Q2(0)——C0（几何位置的连续）和G0连续(2)Q1(1)=Q2(0)Q'1(1)=Q'2(0)——C1连续（切矢连续）(3)Q1(t)和Q2(t)在P点处已有C0，C1连续

Q"1(1)=Q"2(0)——C2连续（曲率连续）Q1Q2Q4PQ3507.插值—函数逼近的重要方法插值设计方法：要求建立的曲线与曲面数学模型，严格通过已知的每一个型值点。在曲线、曲面中最常用的是线性插值和抛物线插值。（1）线性插值xyx1x2y1y2—点斜式—两点式假设给定函数f(x)在两个不同点x1和x2的值，y1=f(x1),y2=f(x2)现要求用一线性函数：y=(x)=ax+b,近似代替y=f(x).51（2）抛物线插值—---二次插值(0≤t≤1)P1P2P3P(0)=P1P(1)=P3P(0.5)=P2A0=P1A1=4P2-P3-3P1A2=2P1+2P3-4P2设已知f（x）在三个互异点P1,P2,P3,要求构造一个函数

(x)，使得(x)在各结点处与f（x）的值相等。528.逼近逼近设计方法:用这种方法建立的曲线与曲面数学模型只是近似地接近已知的型值点。逼近最常用的方法是最小二乘法。逼近好坏常用各点偏差的平方和或加权的方差和最小。9.拟合

拟合是指在曲线、曲面的设计中，用插值或逼近的方法使生成的曲线、曲面达到某些设计要求。如在允许的范围内贴近原始的型值点或控制点序列；曲线、曲面看上去要“光滑”等。53三次曲线：

二次曲线：参数变量的规格化一次曲线：0次曲线：连接两点的多项式的参数方程为：（A0，A1，A2，A3）为向量常数一次曲线：P'0P0P‘1P1t=1,P1t=0,P0P(0)=P0=A0P(1)=P1=A0+A1t

=P1P(t)=P0+(P1-P0)t54P(0)=P0=A0P(1)=A0+A1t

+A1t2=P1二次曲线：P'0P0P‘1P1P(0)’=A1+2A1t=P0’P(t)=P0+P0’t+(P1-P0-P0’

)t2三次曲线：

P(0)=P0=A0P(1)=A0+A1t

+A1t2=P1P(0)’=A1+2A1t=P0’P(1)’=A1+2A1t=P1’P(t)=P0+P0’t+(3P1–P1’

-3P0-2P0’

)t2+(2P1-2P0+P1’

+P0’

)t355三次曲线的参数方程的几何形式如下：其中T=[t3t2t11]

A=[A3A2A1A0]T

——代数系数矩阵已知曲线的端点位置矢量及切矢量：P0，P1，P'0，P'1P(0)=A0=P0P(1)=A3+A2+A1+A0=P1P'(0)=A1=P'0P'(1)=3A3+2A2+A1=P'1P'(t)=3A3t2+2A2t+A1A0=P0A1=P'0A2=-3P0+3P1-2P'0-P'1A3=2P0-2P1+P'0+P'1P'0P0P‘1P13.4.4三次参数样条曲线----HERMITE插值曲线56P(t)=(2P0-3P1+P'0+P'1)t3+(3P0+3P1-2P'0-P'1)t2+P'0t+P0

=(2t3-3t2+1)P0+(-2t3+3t2)P1+(t3-2t2+t)P'0

+(t3-t2)P'1

令H1=2t3-3t2+1H2=-2t3+3t2H3=t3-2t2+tH4=t3-t2

P(t)=H1P0+H2P1+H3P'0+H4P'1=HB其中H=[H1

H2

H3

H4]——调和函数

调和函数通过端点及其切失量产生整个t值范围内的其余各点列的坐标，并且只与参数t有关，由此便于我们通过修改边界条件来改变曲线形状。H1(t)H2(t)H3(t)H4(t)B=[P0P0P'0P'1]T

——几何系数矩阵或边界条件矩阵57A=MB

P(t)=TMB表示的曲线是由端点及其切矢量定义的三次参数曲线，称为三次Hermite曲线或Ferguson曲线或Coons曲线。58Coons曲线的性态分析:P(t)=H0,0(t)*[0,0]+H0,1(t)*[1,0]+H1,0(t)*[k,k]

+H1,1(t)*[k,-k]

设给出曲线的始点P0=[0,0]终点P1=[1,0]切矢的方向P'0=[k,+k]，P'

1=[k,-k]给出位置矢量曲线P0，P1和切矢量P'0，P'1，可以唯一确定一条Coons曲线。若切矢的方向和大小改变，则曲线的形状也随之变化。x=2(k-1)t3+3(k-1)t2+kty=k(-t2+t)为了求出尖点，可令：（1）当t=1/2,k=3时，曲线上将产生一个尖点。曲线不光滑（2）当k=0时，曲线退化为连接两个端点的直线段（3）当k>3时，曲线上将出现一个闭环。59

1962年法国雷诺(Renault)汽车公司的P.E.Bezier构造了一种以逼近为基础的参数曲线,这种曲线称为Bezier曲线，并以此为基础设计了UNISURF系统,该公司于1972年开始应用此系统。Bezier曲线是由一组折线集，或称之为Bezier曲线的特征多边形来定义的。

曲线的起点和终点和该多边形的起点和终点重合，且多边形的第一条边和最后一条边表示曲线在起点和终点处的切矢量方向。3.4.5

BEZIER曲线60

Coons曲线的几何信息是端点的位矢和切矢，曲线的形状很大程度上取决于切矢的大小。为了能更加直观地控制曲线的形状:在两端点切矢上适当选择两个点P0Q1Q0Q'1Q'0P0=Q0+(1/q)Q0’P1=Q1-(1/q)Q1’Q0’=q(P0-Q0)Q1’=q(Q1-P1)P(t)=TMB=[t3

t2t1]代入=[t3t2t1]1.三次Bezier曲线的公式通过切矢来控制曲线形状是比较困难的并且用这两点P0和P1以及Q0和Q1四个点来描述控制曲线Q0P0和Q0P0的长度取为各所在切矢长度的1/qP161BEZIER曲线的一般表达方式:P(t)=[t3

t2t1]（0

t

1）当q=3时，曲线最为接近多边形Q0P0P1Q1。令q＝3，得三次Bezier曲线的矩阵表达式：62B0,3B3,3B2,3B1,3三次Bezier曲线的调和函数63Q0,

Q1,Q2,Q3——曲线的特征矢量一阶导数的表达式64用B曲线逼近直线或圆弧1.直线P(t)=(1-t)3Q1+3(1-t)2tQ2+3(1-t)

t2Q3+t3Q4=(Q4–Q1+3Q2–3Q3)t3

+3(Q1–2Q2+Q3)t2

+3(Q2-Q1)t+Q1由于P(t)为直线,所以有:Q4–Q1+3Q2–3Q3=0Q1–2Q2+Q3=0Q3=Q1+2/3(Q4–Q1)Q2=Q1+1/3(Q4–Q1)P(t)=(1-t)Q1+tQ4为典型的直线参数方程Q1Q2Q3Q4Q1Q4Q2Q31/31/31/3652.圆弧P(t)=(1-t)3Q1+3(1-t)2tQ2+3(1-t)

t2Q3+t3Q4=(Q4–Q1+3Q2–3Q3)t3

+3(Q1–2Q2+Q3)t2

+3(Q2-Q1)t+Q1半径为1,第一象限的1/4圆弧Q1=[1,0]Q4=[0,1]Q2=[1,k]Q3=[k,1]P(1/2)=[,]误差=0.0027%OYXQ1(1,0)Q4(0,1)Q2(1,k)Q3(k,1)t=1/266

当给定空间n+1个点的位置矢量，Bezier曲线上各点坐标的公式为：Bi,n(t)——Bernstein基函数，调和函数Qi——构成该曲线的特征多边形各顶点的位置矢量当n=3时，2.BEZIER曲线67当n=1时Bezier曲线的表达式：0<=t<=1;矩阵表示：P(t)=[t1]-1110Q0Q10<=t>=1当n=2时Bezier曲线的表达式：0<=t<=1P(t)=[t2t1]-21-220100Q0Q1Q20<=t<=1矩阵表示：68Bezier曲线的不足：（1）曲线离特征多边形较远，逼近效果不好（2）Bezier曲线改变某一个控制点的位置对整条曲线都有影响，不能作局部修改，不易控制形状。（3）特征多边形的顶点个数决定了Bezier曲线的阶次，并且当n较大时，次数增大，计算不便。特征多边形对曲线的控制将会减弱；

1972年，Gordon（通用汽车公司）,Riesenfeld（20多岁）等人拓扩了Bezier曲线，用B样条函数代替了Bernstein函数，从而改进了Bezier特征多边形与Bernstein多项式次数有关，且是整体逼近的弱点。

由空间n+1个控制点生成的k阶B样条曲线是由L+1(L=n-k+1)段B样条曲线逼近而成，每个曲线段的形状仅由点列中的k+1个顺序排列的点所控制。1.概述3.4.6

B-SPLINE曲线69若从空间n+1个顶点Qi（i=0,1,…,n）中取相邻的三个顶点，构造出一段两次均匀B样条曲线，其矩阵表示为：2.二次均匀B样条曲线其中1)位置连续:相邻的两段曲线Pi(t)

和Pi+1(t),分别在t=0和t=1处满足:Pi-1(1)=Pi(0)1

in-1

代入上式Qi-1QiQi+1702)切矢连续：P’i-1(1)=P’i(0)1

in-2

3)增加柯西条件:(坐标变换后形状不变性)解得:其矩阵表达式:71二次均匀B样条曲线的特性几何特性首端:t=0末端:t=1曲线段的起点和终点为两线段的中点切矢:曲线段与两直线段相切Qi+1QiQi-1移动一个控制点,不影响整体,局部性好72如图所示,给出有序的n+1个位置矢量Qi（i=0,1,…,n),每相邻四个点一组,可以依次构成(n-2)个线性组合,即3.三次均匀B样条曲线Q0Q1Q2Q3Q8Q5Q6Q7Q41)位置连续:相邻的两段曲线Pi(t)和Pi+1(t),分别在t=0和t=1处满足:Pi-1(1)=Pi(0)1

in-1

代入上式732)切矢和曲率连续：P’i-1(1)=P’i(0)P”i-1(1)=P”i(0)(1

in-2)

3)增加柯西条件:(坐标变换后形状不变性)解得:和考虑函数的对称性,可以假设

X0(t)=X3(1-t)X1(t)=X4(1-t)74其矩阵表达式:Qi-1QiQi+1Qi+2Pi(0)Pi(1)式中Qi-1QiQi+1Qi+2为特征多边形的四个相邻顶点特征多边形有更多的顶点，则一条完整的B-Spline曲线将由若干段曲线所组成。75均匀三次B-Spline曲线的几何关系1.曲线段首、末端点的位置矢量2.曲线段首、末端点的切矢量3.曲线段首、末端点的曲率Qi-1QiQi+1Qi+2ABCDPi(1)Pi(0)Pi'(0)Pi'(1)Pi"(0)Pi''(1)其中ABCD为此段Bezier曲线的特征多边形的四个相邻顶点76（1）凸包性。即曲线位于控制多边形凸包范围内；（2）几何不变性。曲线的几何形状和位置与坐标系的选择无关；（3）变差缩减性。（4）连续性。（5）局部性。（6）造型的灵活性。可构造直线段、尖点、切线等特殊情况。4.B-SPLINE曲线的性质77

上机调试BEZIER曲线的生成程序，并编写B样条曲线程序。作业78doublex=x1,y=y1; m=(y2-y1)/(x2-x1);intk=abs(x2-x1);putpixel((int)x,(int)y,2);++x;//x=x+1\x++;y+=m;//y=y+m;}对于第一象限的直线，如斜率<1，x1<x2，其直线生成的程序为： {for(inti=1;i<=k;i++)当m>1时,x,

y>1因而造成隔行显示解决办法:将y看作自变量分析：公式变为:其中:m=(x2-x1)/(y2-y1)令deltx=x;delty=y;79改进的Bresenham算法由图可知若ε(xi+1)≥0yi+1,r=yir+1，(2)

若ε(xi+1)≤0yi+1,r=yir，xiXi+1Yi,rYi+1,rBADε(x)的几何意义Cxi列上已用（xi,yir）作为表示直线的点，设B点是直线上的点，其坐标为（xi+1,yi+1）

显然下一个表示直线的点（xi+1,yi+1,r）只能从图中的C或者D点中去选。设A为CD边的中点若B在A点上面则应取D点作为（xi+1,yi+1,r）

否则应取C点（xi+1,yi,r）为了能确定B在A点上面或下面，令ε(xi+1)=yi+1,r-yir-0.5（1）若B在A的下面，则有ε(xi+1)<0，